Testing table with QSortFilterProxy

With the test framework set up as described in the previous post, it is quite simple to implement real sorting in a table. The modified code is here in Pastebin. It is almost identical to the basic code.

The process of adding a proxy is described in the doc page for QSortFilterProxyModel. The proxy model object is given to the table view as its model. The proxy is given the actual table model as its source model. Here is the added code to do the job. First define the proxy class.

from PyQt5.QtCore import QSortFilterProxyModel
class Proxy( QSortFilterProxyModel ) :
    def __init__ ( self, parent=None ) :
        super().__init__( parent )
        self.setSortCaseSensitivity( True )
        self.setSortLocaleAware( True )

In the setup code in the main window, interpose it between the model and the view.

        self.table_view = View( parent=self )
        self.table_model = Model( parent=self )
        self.table_proxy = Proxy( parent=self )
        self.table_proxy.setSourceModel( self.table_model )
        self.table_view.setModel( self.table_proxy )

That's all! Now clicking column heads makes actual sorting happen.

When you run this program it looks just like the basic version. And if you do not click a column head, it performs just like the basic one as you can see in this capture.

Just as with the unsorted table, the view is only fetching the rows it needs to fill the window. The time to complete a refresh is a few milliseconds longer than the database rebuild.

Things change drastically if one simply clicks once on the head of column 1, to request a change of sort order. First, there is an agonizing pause of 9 seconds. The Mac OS "beachball" cursor is on through most of this. Then the data displays in the new sort order.

(I still do not know a good way to insert instrumentation into the process of a column sort. The QHeaderView emits a signal when the sort order changes, but not when the sort ends. Perhaps I could override the sort() method of the proxy? But it is not necessary.)

From now on, with sorting in effect, clicking Refresh causes a very different reaction than before.

I think we have a result here.

If the sort is moved to column 2 (by clicking once in the column 2 header), there is again a 9-second delay. Then clicking Refresh gets similar but not quite the same results:

The number of data() calls is lower, possibly reflecting the presence of a significant number of duplicate values in column 2. The elapsed time is proportional to the fewer calls. But the numbers are still extraordinarily big.

To me there is no way to account for the huge number of calls to the model data() function. A sane implementation would call 10,000 times to fetch all the key values into an array; sort the array using any available standard library routine; save a vector of indexes internally; and make a further 12 calls to fill up the display. Total, 10012 calls to the sorted column and 12 to the others.

That is clearly not what the proxy code is doing. A standard sort should make O(N*log2(N)) comparisons; in this case, about 133,000 comparisons. Even if we suppose that every comparison involved fetching two values from the model—which it certainly should not—that would still be only about 266,000 calls. I simply cannot image what the proxy is doing to require so many calls to the model.

Well, whatever it is doing, it is not doing it because I mis-coded something. This is absolutely minimal code. (Yes, I tried turning off case sensitivity and local-aware sorting. It didn't make a difference to the sorting in column 1, the words. It might have slightly speeded sorting column 2, integers.)

In the next post, I will explore ways to do my own sorting, taking advantage of the abilities of the SortedContainer package.

Building a case against QSortFilterProxy

This is part 1 of a multi-part post on speeding up the sorting of tables in Qt.

I've been disturbed by the apparent slowness of the Words table in PPQT2. It takes 15 or more seconds to refresh the table (rebuild it from scratch), and 8-10 seconds of "spinning beach-ball" cursor to re-sort on any column.

Then this week my α-test user reported that, for a large book, the bookloupe refresh was adding at least 12 seconds over the time that the bookloupe program required when run from the command line. That's consistent with the word-table delay: about a second for every 1000 rows of the table. (Not that I think the delay is a linear function of N; it might well be exponential!)

Nothing that a word-processing app does using local data, should take more than a second of elapsed time. Not on a modern computer. Maybe there are some natural-language algorithms, or neural-network or genetic problems, that might tie up a 64-bit, 2.8gigahertz CPU with eight gigabytes of RAM for substantial time. (Parenthetically, those numbers still boggle my mind; I spent so many hours at the keyboard of a 64-kilobyte CP/M system with a 2megahertz Z80...) A modern laptop should not spend any perceptible time sorting 10,000 rows of 3-column text. It does, and that means something's not right.

I did some initial fiddling around a couple months back, stuck timing statements around the Word table refresh operation and so on. From that I verified that it was taking my code much less than a second to sweep a large document and collect all the words in a vocabulary table. That included a few tens of thousands of calls to a fairly elaborate regex, and execution of another 30-odd lines of Python for each token it found.

Then my code told the QAbstractTableModel that it was time to endModelReset(), i.e. the data is all good now, redisplay the table. And that's when several seconds would elapse.

I didn't find any way to instrument the sort that happens when the user clicks on a column header. But I timed it manually at 8-10 seconds from click to redisplay of the inverted sort.

At the time I posted a query in the Qt forum. The answers I got were that, one, beginResetModel/endResetModel was a bad thing to do and should be avoided, and two, that sortFilterProxy is going to be slow and,

If you need quick sorting and you have access to the raw data in the model, you should just implement the sorting in your model itself. Just reimplement the sort function.

I wasn't very happy with this, because I thought I had revealed some pretty horrendous behavior from the sortFilterProxy. But I didn't have time to really nail the case for the prosecution. So I put the problem off. But now my user has shown the problem exists in the Loupe table also, I've gotta do something.

The first thing to do is to build a simple test-bed where I can experiment with the table code. I want to use that first to prove to myself that Qt's sort is actually slow, and not simply because I've done something stupid to slow it down. If that's the case, then I'll use that code to work out how to do my own sort.

In the next post of this sequence I will introduce that test-bed code.

Scanning the pixels

Last post I described how you can get a "voidptr" through which you can PEEK the bytes of an image. This is needed to implement zoom-to-width and zoom-to-height buttons on the imageview. The code that I wrote for this in V.1 never felt right. It's a pure CPU-burning FORTRAN-style loop process; even more so than the character or word census of a large text. The scan image for a typical page is several megapixels (the test image used below is about 1800x2700, or 5Mpx) and the only process I could find for determining the margin has to access a good fraction of them. Clicking "To Width" or "To Height" on an older laptop incurs a noticeable pause of a second or more. I want to shorten that.

(Note that in what follows, the code for to-width and to-height is virtually the same, just substituting "top" and "bottom" for "left" and "right". I'm writing about to-width; whatever lessons I learn are immediately applicable to to-height.)

Starting point

Let's look at the code as it is now. The point is to find out how much of the left and right margins of the image are all-white, then scale and center the image to exclude them. To find the left margin, I look at the pixels of each row from left to right, stopping at a black spot. Once I've found a black spot, I never have to scan farther to the right than that point. I keep going to successive rows, hoping to find a black spot even more to the left. After looking at all rows I know the pixel count to the left of the leftmost black spot. The same logic applies to the right margin: look at all rows from right to left, in order to find the rightmost black spot.

An early complication was that finding a single black pixel threw up false positives. Scan images often have one-pixel, even two-pixel "fly specks" outside the text area. So I modified the code to stop only on a dark spot of at least 3 pixels, which added some overhead. I added a heuristic. Noting that many pages have large white areas at the top and bottom, I started the scan with the middle row, hoping to quickly find some black pixels nearer the left margin.

The following code is heavily rewritten and refactored. You can view the original if you like, but don't bother. The original has four nearly-identical loops for scanning the left margin, middle to end then top to middle, then the right margin the same. These loops—I realized yesterday—differ only in the start, stop and step values of their controlling ranges. So I factored the inner loops out to this:

    def inner_loop(row_range, col_start, margin, col_step):
        '''
        Perform inner loop over columns of current margin within rows of
        row_range. Look for a better margin and return that value.
        '''
        pa, pb = 255, 255 # virtual white outside column
        for row in row_range:
            for col in range(col_start, margin, col_step):
                pc = color_table[ ord(bytes_ptr[row+col]) ]
                if (pa + pb + pc) < 24 : # black or dark gray trio
                    margin = col # new, narrower, margin
                    break # no need to look further on this row
                pa, pb = pb, pc # else shift 3-pixel window
        return margin

The key statement is pc = color_table[ ord(bytes_ptr[row+col]) ]. From inside, out: bytes_ptr[row+col] peeks the next pixel value which is an index into the color table. ord() is needed because the voidptr access returns a byte value and (for reasons that escape me) Python will not permit a byte type as a list index. The color_table is a list of the possible GG values from RRGGBB, smaller numbers being darker. I'll talk about it in a minute.

The operation of this code should be fairly clear: slide a 3-pixel window along the pixels of one row up to a limit; when they comprise a dark spot, break the loop and set a new, more stringent limit. Return the final limit value.

Now let's look at the code that sets up for and calls that inner loop.

def find_image_margins(image):
    '''
    Determine the left and right margin widths that are (effectively)
    all-white in an image, returning the tuple (left,right). The image is
    presumed to be a scanned book page in the Indexed-8 format, one byte per
    pixel, where a pixel value is an index into a color table with 32-bit
    entries 0xAARRGGBB (AA=alpha channel).
    '''
    rows = image.height() # number of pixels high
    cols = image.width() # number of logical pixels across
    stride = (cols + 3) & (-4) # scan-line width in bytes
    bytes_ptr = image.bits() # uchar * a_bunch_o_pixels
    bytes_ptr.setsize(stride * rows) # make the pointer indexable
    # Get a reduced version of the color table by extracting just
    # the GG values of each entry. If the image is PNG-1, this
    # gives [0,255] but it could have 8, 16, even 256 elements.
    color_table = [ int((image.color(c) >> 8) & 255)
                     for c in range(image.colorCount()) ]

The first five lines of code set up the voidptr to the image bytes. The stride value is used because the Qt documentation notes that every pixel row occupies a whole number of 32-bit words.

Note the remark about the "presumed" image format? In early testing I forgot to force the image to Indexed-8. The calculation stride * rows yielded about 5MB but that was much larger than the true memory size of a compressed 1-bit PNG file. The result was that the first time the inner loop tried to access a byte of a middle row—Python seg-faulted. Yes, you can bring down, not just your own app, but the whole interpreter, by mis-using a voidptr.

If the image file is really monochrome and stored as PNG-1, the color table will have two entries. But I can't require that or assume that. It will be a PNG but it might be a PNG-8 with actual colors. So make a color table of just the GG values (Green is commonly used as a proxy for pixel brightness) and index it by the pixel value.

Now, to work:

    # Some pages start with many lines of white pixels so in hopes of
    # establishing a narrow margin quickly, start at the middle, go to
    # the end, then do the top half. Begin: left side from the middle down.
    left_margin = inner_loop(
                    range(int(rows/2)*stride, (rows-1)*stride, stride),
                    0, int(cols/2), 1
    )
    # With hopefully narrower margin, scan from the top to the middle:
    left_margin = inner_loop(
                    range(0, int(rows/2)*stride, stride),
                    0, left_margin, 1
                    )
    # Now do exactly the same but for the right margin, taking columns
    # from the rightmost, inward.
    right_margin = inner_loop(
                    range(int(rows/2)*stride, (rows-1)*stride, stride),
                    cols-1, int(cols/2), -1
                    )
    right_margin = inner_loop(
                    range(0, int(rows/2)*stride, stride),
                    cols-1, right_margin, -1
                    )
    return left_margin, right_margin

Each call to the inner loop passes a range of rows to examine—in the form of pre-calculated byte offsets—and the three factors for a range of columns. The end result is the width of the white margins of the page.

Timings of this code

When I use the ctime package to time one application of find_image_margins() to a representative page image, I get these not awfully helpful stats:

         871938 function calls in 1.921 seconds
   Ordered by: internal time
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        4    1.815    0.454    1.921    0.480 imagetest.py:20(inner_loop)
   871922    0.106    0.000    0.106    0.000 {built-in method ord}
        1    0.000    0.000    1.921    1.921 {built-in method exec}
        1    0.000    0.000    1.921    1.921 imagetest.py:12(find_image_margins)

The remaining lines are all-zero times. So: running under cprofile, this takes almost two seconds to run. On a 2.8GHz CPU, that's roughly six billion instructions. Wow! This would have been completely infeasible on, say, my old Mac Plus where it would have taken something like 20 minutes to complete on its 8 megahertz CPU. On my current Macbook Pro, it's a minor annoyance.

The count of 871,922 calls to ord tells how many pixels were examined in the inner loop. The total time of 1.815 tells how much time the inner loop spent on those pixels, or about 108,000,000 microseconds on 900,000 pixels giving 120 microseconds per pixel examined.

Optimizing

I see two approaches to optimizing this program. One: reduce the 120μsec spent in the inner loop on each pixel. Two: reduce the number of pixels examined in the inner loop. Reducing either number by half would halve the program execution time.

I believe I will spend a bit of time exploring both approaches, and report in the next post.