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.

Basic table testing framework

To test the table sorting mechanism in a way that was somewhat relevant to my app, I wrote a program that generates a fake database of 10,000 rows with contents that are similar to the PPQT Word table. The code for the program is stored in Pastebin. I will examine parts of it here.

The program starts with several functions to generate random data:

• xdi() returns a list of a given number of random integers from the exponential distribution. I use the Beta value to skew the list in certain ways. For example a Beta of 0.05 and a max of 100 gives a list primarily of small integers. This emulates the distribution of word-counts in a vocabulary: many 1s and 2s and a few 50s or 100s.
• rwt() returns a word-like token with, typically, more vowels than consonants.
• rft() returns a token that looks something like the property flag values of the Word table.

You can pretty much ignore the code of these; they work and that's all I care about.

The database is a SortedDict from the excellent SortedContainers package (that link is to its doc; here it is on PyPI). The SortedContainers package is pure Python, minimizing cross-platform issues, and has performance as good as, and sometimes better than, packages based on C code such as blist. The database is populated with this code:

    col2 = xdi( 0.05, DBS, 100 )
    clear_the_db()
    for k in col2 :
        w = rwt(8)
        f = rft()
        DBM[ w ] = ( w, k, f )
    DBV = DBM.values()

DBS contains 10000. So this makes a dict with 10,000 items, with keys of 8-char random words. The dict is sorted. The values view gives indexed access to the sequence of values. That is, DBV[j] is the jth value in key sequence.

This code, we will see later, takes about 0.7 seconds to complete on a 3.5GHz Core i5. Lotsa computation going on.

You might notice a suspicious redundancy. The primary key (in the SQL sense) is w, and it is being stored both as the dict key and again in the tuple that is is the dict value. There is a reason for this.

The rest of the code is very standard, and minimal, PyQt5. There is a table model implemented in part as follows:

class Model( QAbstractTableModel ):
    def __init__ ( self, parent=None ) :
        super().__init__( parent )
        self.access_counts = [0, 0, 0]
 
    def rowCount( self, index ) :
        global DBM
        if index.isValid() : return 0
        return len(DBM)
  
    def data(self, index, role ) :
        global DBV
        if role != Qt.DisplayRole :
            return None
        row = index.row()
        col = index.column()
        self.access_counts[col] += 1
        return DBV[ row ][ col ]

The data() method counts the number of DisplayRole calls for each column. Its last line demonstrates the usefulness of the redundant storing of the key word in the value. Otherwise there would have to be (and initially was, until I thought of this trick) a test in the code:

        if col : # is 1 or 2,
            return DBV[ row ][ col-1 ]
        else: return DBK[row]

Return either one of two values stored as the dict value, or return the key. But storing the key redundantly in the value allows the data() method to eliminate one test. And with a multi-gigabyte laptop, who cares about a little redundancy? 10,000 extra string values? What's that, 0.00001 of a gig? Pfffffttt!

Below the table model comes the lengthy code needed to create a basic window and populate it with stuff. The only interesting bit is the slot attached to the clicked signal of the Refresh button:

    def do_refresh( self ) :
        self.table_model.clear_counts()
        self.table_model.beginResetModel()
        self.times[0] = time.process_time()
        rebuild_the_db()
        self.times[1] = time.process_time()
        self.table_model.endResetModel()
        QApplication.processEvents()
        self.times[2] = time.process_time()
        self.update_labels()

The update_labels() routine displays the counts of accesses, and the elapsed times for rebuilding the database and for completing the update of the table, in labels at the bottom of the window. Here is what the window looks like, with some typical values.

The values at the bottom of the window are typical. It takes around 0.73 of a second to recreate the database. That's not long enough to justify putting up a progress-bar, although it's close. The time to complete the model reset and redisplay the table is trivial, imperceptible to the user.

The access counts are interesting. Initially they were zero. Then I put the call to QApplication.processEvents() in, and that forced the table display code to run. But even then it only called for 12 rows of data. My first thought was, why not 10,000? Then I realized, oh, it's being clever and only getting enough data to populate the visible rows in the window. And that was proven when I dragged the window taller. Then a Refresh caused it to fetch 29 rows, exactly the number that filled the larger window. Also, it always fetches only that many rows, even when I have scrolled the table to the end. It knows what row indices it needs, and calls the model only for those.

However, this table doesn't sort. The table view initializes itself with

        self.setSortingEnabled( True )
        self.sortByColumn( 0, Qt.AscendingOrder )

That is why the table shows a sort order indicator (small triangle in the Column 1 header). One can click the column headings and the sort order indicator will move around and change as if sorting were happening. And presumably the sort() method of the table model (inherited from QAbstractItemModel) is being called, but it does nothing.

In the next post, I will show what happens when we interpose a sort filter proxy.

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.