QListView with millions of items slow with keyboard

Question

I'm using a QListView with a custom model derived from QAbstractItemModel. I have on the order of millions of items. I have called listView->setUniformItemSizes(true) to prevent a bunch of layout logic from being called when I'm adding items to the model. So far, everything works as expected.

The problem is that using the keyboard to navigate the list is slow. If I select an item in the list, then press up/down, the selection moves fast until the selection needs to scroll the list. Then it becomes extremely laggy. Pressing page-up or page-down is also very laggy. The problem seems to be when an item is selected (aka the "current item") with the keyboard and the list is also scrolled up/down.

If I use the mouse, navigating the list is fast. I can use the mouse wheel, which is fast. I can drag the scroll bar up/down as fast as I want--from the top of the list to the bottom--and the list view updates wickedly fast.

Any ideas on why the combination of changing selections and scrolling the list is so slow? Is there a viable work-around?

Update 9/9/15

In order to better illustrate the issue, I'm providing amplifying information in this update.

Performance Issues with KEYBOARD + SCROLLING

This is mostly a performance question, although it does tie in with the user experience (UX) somewhat. Check out what happens as I use the keyboard to scroll through a QListView:

Notice the slow-down near the bottom? This is the focal point of my question. Let me explain how I am navigating the list.

Explanation:

1. Starting at the top, the first item in the list is selected.
2. Pressing and holding the down arrow key, the current item (selection) is changed to the next item.
3. Changing selection is fast for all of the items that are currently in view.
4. As soon as the list needs to bring the next item into view, the selection rate slows down significantly.

I expect that the list should be able to scroll as fast as the typematic rate of my keyboard--in other words, the time it takes to select the next item should not slow down when the list is scrolled.

Fast Scrolling with MOUSE

Here's what it looks like when I use the mouse:

Explanation:

1. Using the mouse, I select the scroll bar handle.
2. Quickly dragging the scroll bar handle up and down, the list is scrolled accordingly.
3. All movements are extremely fast.
4. Note that no selections are being made.

This proves two main points:

1. The model is not the problem. As you can see, the model has no problem whatsoever performance-wise. It can deliver the elements faster than they can be displayed.

2. Performance is degraded when selecting AND scrolling. The "perfect storm" of selecting and scrolling (as illustrated by using the keyboard to navigate through the list) causes the slowdown. As a result, I surmise that Qt is somehow doing a lot of processing when selections are being made during scrolling that aren't normally performed.

Non-Qt Implementation is FAST

I want to point out that my issue seems to be specific to Qt.

I have already implemented this type of thing before using a different framework. What I am trying to do is within the scope of model-view theory. I can do exactly what I am describing at blazing fast speeds using juce::ListBoxModel with a juce::ListBox. It's stupid fast (plus, there's no need to create a duplicate index such as a QModelIndex for every single item when each item already has a unique index). I get that Qt needs a QModelIndex for each item for its model-view architecture, and although I don't like the overhead cost, I think I get the rational and I can live with it. Either way, I don't suspect that these QModelIndexes are what is causing my performance slow-down.

With a JUCE implementation, I can even use the page-up & page-down keys to navigate the list, and it just blazes through the list. Using the Qt QListView implementation, it chugs along and is laggy, even with a release build.

A model-view implementation using the JUCE framework is extremely fast. Why is the Qt QListView implementation such a dog?!

Motivating Example

Is it hard to imagine why you'd need so many items in a list view? Well, we've all seen this kind of thing before:

This is the Visual Studio Help Viewer index. Now, I haven't counted all of the items--but I think we'd agree that there are a lot of them! Of course to make this list "useful," they added a filter box that narrows down what is in the list view according to an input string. There aren't any tricks here. It's all practical, real-world stuff we've all seen for decades in desktop applications.

But are there millions of items? I'm not sure it matters. Even if there were "only" 150k items (which is roughly accurate based on some crude measurements), it's easy to point out that you have to do something to make it useable--which is what a filter will do for you.

My specific example uses a list of German words as a plain text file with slightly more than 1.7 million entries (including inflected forms). This is probably only a partial (but still significant) sample of words from the German text corpus that was used to assemble this list. For linguistic study, this is a reasonable use case.

Concerns about improving the UX (user experience) or filtering are great design goals, but they are out of the scope of this question (I'll certainly address them later in the project).

Code

Want a code example? You got it! I'm not sure how useful it will be; it's as vanilla as it gets (about 75% boilerplate), but I suppose it will provide some context. I realize that I'm using a QStringList and that there is a QStringListModel for this, but the QStringList that I'm using to hold the data is a placeholder--the model will eventually be somewhat more complicated, so in the end, I need to use a custom model derived from QAbstractItemModel.

//
// wordlistmodel.h ///////////////////////////////////////
//
class WordListModel : public QAbstractItemModel
{
    Q_OBJECT
public:
    WordListModel(QObject* parent = 0);

    virtual QModelIndex index(int row, int column, const QModelIndex& parent = QModelIndex()) const;
    virtual QModelIndex parent(const QModelIndex& index) const;
    virtual int rowCount(const QModelIndex& parent = QModelIndex()) const;
    virtual int columnCount(const QModelIndex & parent = QModelIndex()) const;
    virtual QVariant data(const QModelIndex& index, int role = Qt::DisplayRole) const;

public slots:
    void loadWords();

signals:
    void wordAdded();

private:
    // TODO: this is a temp backing store for the data
    QStringList wordList;
};


//
// wordlistmodel.cpp ///////////////////////////////////////
//
WordListModel::WordListModel(QObject* parent) :
    QAbstractItemModel(parent)
{
    wordList.reserve(1605572 + 50); // testing purposes only!
}

void WordListModel::loadWords()
{
    // load items from file or database

    // Due to taking Kuba Ober's advice to call setUniformItemSizes(true),
    // loading is fast. I'm not using a background thread to do
    // loading because I was trying to visually benchmark loading speed.
    // Besides, I am going to use a completely different method using
    // an in-memory file or a database, so optimizing this loading by
    // putting it in a background thread would obfuscate things.
    // Loading isn't a problem or the point of my question; it takes
    // less than a second to load all 1.6 million items.

    QFile file("german.dic");
    if (!file.exists() || !file.open(QIODevice::ReadOnly))
    {
        QMessageBox::critical(
            0,
            QString("File error"),
            "Unable to open " + file.fileName() + ". Make sure it can be located in " +
                QDir::currentPath()
        );
    }
    else
    {
        QTextStream stream(&file);
        int numRowsBefore = wordList.size();
        int row = 0;
        while (!stream.atEnd())
        {
            // This works for testing, but it's not optimal.
            // My real solution will use a completely different
            // backing store (memory mapped file or database),
            // so I'm not going to put the gory details here.
            wordList.append(stream.readLine());    

            ++row;

            if (row % 10000 == 0)
            {
                // visual benchmark to see how fast items
                // can be loaded. Don't do this in real code;
                // this is a hack. I know.
                emit wordAdded();
                QApplication::processEvents();
            }
        }

        if (row > 0)
        {
            // update final word count
            emit wordAdded();
            QApplication::processEvents();

            // It's dumb that I need to know how many items I
            // am adding *before* calling beginInsertRows().
            // So my begin/end block is empty because I don't know
            // in advance how many items I have, and I don't want
            // to pre-process the list just to count the number
            // of items. But, this gets the job done.
            beginInsertRows(QModelIndex(), numRowsBefore, numRowsBefore + row - 1);
            endInsertRows();
        }
    }
}

QModelIndex WordListModel::index(int row, int column, const QModelIndex& parent) const
{
    if (row < 0 || column < 0)
        return QModelIndex();
    else
        return createIndex(row, column);
}

QModelIndex WordListModel::parent(const QModelIndex& index) const
{
    return QModelIndex(); // this is used as the parent index
}

int WordListModel::rowCount(const QModelIndex& parent) const
{
    return wordList.size();
}

int WordListModel::columnCount(const QModelIndex& parent) const
{
    return 1; // it's a list
}

QVariant WordListModel::data(const QModelIndex& index, int role) const
{
    if (!index.isValid())
    {
        return QVariant();
    }    
    else if (role == Qt::DisplayRole)
    {
        return wordList.at(index.row());
    }
    else
    {    
        return QVariant();
    }
}


//
// mainwindow.h ///////////////////////////////////////
//    
class MainWindow : public QMainWindow
{
    Q_OBJECT

public:
    explicit MainWindow(QWidget *parent = 0);
    ~MainWindow();

public slots:
    void updateWordCount();

private:
    Ui::MainWindow *ui;
    WordListModel* wordListModel;
};

//
// mainwindow.cpp ///////////////////////////////////////
//
MainWindow::MainWindow(QWidget *parent) :
    QMainWindow(parent),
    ui(new Ui::MainWindow)
{
    ui->setupUi(this);
    ui->listView->setModel(wordListModel = new WordListModel(this));

    // this saves TONS of time during loading,
    // but selecting/scrolling performance wasn't improved
    ui->listView->setUniformItemSizes(true);

    // these didn't help selecting/scrolling performance...
    //ui->listView->setLayoutMode(QListView::Batched);
    //ui->listView->setBatchSize(100);

    connect(
        ui->pushButtonLoadWords,
        SIGNAL(clicked(bool)),
        wordListModel,
        SLOT(loadWords())
    );

    connect(
        wordListModel,
        SIGNAL(wordAdded()),
        this,
        SLOT(updateWordCount())
    );
}

MainWindow::~MainWindow()
{
    delete ui;
}

void MainWindow::updateWordCount()
{
    QString wordCount;
    wordCount.setNum(wordListModel->rowCount());
    ui->labelNumWordsLoaded->setText(wordCount);
}

As noted, I've already reviewed and taken Kuba Ober's advice:

QListView takes too long to update when given 100k items

My question is not a duplicate of that question! In the other question, the OP was asking about loading speed, which as I've noted in my code above, is not a problem due to the call to setUniformItemSizes(true).

Summary Questions

1. Why is navigating a QListView (with millions of items in the model) using the keyboard so slow when the list is scrolled?
2. Why does the combination of selecting and scrolling items cause a slow-down?
3. Are there any implementation details that I am missing, or have I reached a performance threshold for QListView?

Answer 1

1. Why is navigating a QListView (with millions of items in the model) using the keyboard so slow when the list is scrolled?

Because when you navigate through your list using the keyboard, you enter the internal Qt function QListModeViewBase::perItemScrollToValue, see stack:

Qt5Widgetsd.dll!QListModeViewBase::perItemScrollToValue(int index, int scrollValue, int viewportSize, QAbstractItemView::ScrollHint hint, Qt::Orientation orientation, bool wrap, int itemExtent) Ligne 2623    C++
Qt5Widgetsd.dll!QListModeViewBase::verticalScrollToValue(int index, QAbstractItemView::ScrollHint hint, bool above, bool below, const QRect & area, const QRect & rect) Ligne 2205  C++
Qt5Widgetsd.dll!QListViewPrivate::verticalScrollToValue(const QModelIndex & index, const QRect & rect, QAbstractItemView::ScrollHint hint) Ligne 603    C++
Qt5Widgetsd.dll!QListView::scrollTo(const QModelIndex & index, QAbstractItemView::ScrollHint hint) Ligne 575    C++
Qt5Widgetsd.dll!QAbstractItemView::currentChanged(const QModelIndex & current, const QModelIndex & previous) Ligne 3574 C++
Qt5Widgetsd.dll!QListView::currentChanged(const QModelIndex & current, const QModelIndex & previous) Ligne 3234 C++
Qt5Widgetsd.dll!QAbstractItemView::qt_static_metacall(QObject * _o, QMetaObject::Call _c, int _id, void * * _a) Ligne 414   C++
Qt5Cored.dll!QMetaObject::activate(QObject * sender, int signalOffset, int local_signal_index, void * * argv) Ligne 3732    C++
Qt5Cored.dll!QMetaObject::activate(QObject * sender, const QMetaObject * m, int local_signal_index, void * * argv) Ligne 3596   C++
Qt5Cored.dll!QItemSelectionModel::currentChanged(const QModelIndex & _t1, const QModelIndex & _t2) Ligne 489    C++
Qt5Cored.dll!QItemSelectionModel::setCurrentIndex(const QModelIndex & index, QFlags<enum QItemSelectionModel::SelectionFlag> command) Ligne 1373    C++

And this function does:

itemExtent += spacing();
QVector<int> visibleFlowPositions;
visibleFlowPositions.reserve(flowPositions.count() - 1);
for (int i = 0; i < flowPositions.count() - 1; i++) { // flowPositions count is +1 larger than actual row count
    if (!isHidden(i))
        visibleFlowPositions.append(flowPositions.at(i));
}

Where flowPositions contains as many items as your QListView, so this basically iterates through all your items, and this will definitely take a while to process.

2. Why does the combination of selecting and scrolling items cause a slow-down?

Because "selecting and scrolling" makes Qt call QListView::scrollTo (to scroll the view to a specific item) and this is what ends up calling QListModeViewBase::perItemScrollToValue. When you scroll using the scroll bar, the system does not need to ask the view to scroll to a specific item.

3. Are there any implementation details that I am missing, or have I reached a performance threshold for QListView?

I'm afraid you are doing the things right. This is definitely a Qt bug. A bug report must be done to hope having this fixed in later releases. I submitted a Qt bug here.

As this code is internal (private data classes) and not conditionnal to any QListView setting, I see no way to fix it except by modifying and recompiling the Qt source code (but I don't know exactly how, this would require more investigation). The first function overidable in the stack is QListView::scrollTo but I doubt it would be easy to oevrride it without calling QListViewPrivate::verticalScrollToValue...

Note: The fact that this function goes through all items of the view was apparently introduced in Qt 4.8.3 when this bug was fixed (see changes). Basically, if you don't hide any items in your view, you could modify Qt code as below:

/*QVector<int> visibleFlowPositions;
visibleFlowPositions.reserve(flowPositions.count() - 1);
for (int i = 0; i < flowPositions.count() - 1; i++) { // flowPositions count is +1 larger than actual row count
    if (!isHidden(i))
        visibleFlowPositions.append(flowPositions.at(i));
}*/
QVector<int>& visibleFlowPositions = flowPositions;

Then you'll have to recompile Qt and I'm pretty sure this will fix the issue (not tested however). But then you'll see new problems if you one day hide some items...to support filtering for instance!

Most likely the right fix would have been to have the view maintain both flowPositions and visibleFlowPositions to avoid creating it on the fly...

Answer 2

I have made the following test:

First of all i create a class to check in the calls:

struct Test
{
  static void NewCall( QString function, int row )
  {
    function += QString::number( row );

    map[ function ]++;
  }

  static void Summary( )
  {
    qDebug() << "-----";
    int total = 0;
    QString data;
    for( auto pair : map )
    {
      data = pair.first + ": " + QString::number( pair.second );
      total += pair.second;
      qDebug( ) << data;
    }

    data = "total: " + QString::number( total ) + " calls";
    qDebug() << data;
    map.clear();
  }

  static std::map< QString, int > map;
};

std::map<QString,int> Test::map;

Then I insert a call to NewCall in index, parent and data methods of WordListModel. Finally i add a QPushButton in the dialog, the clicked signal is linked to a method which call to Test::Summary.

The steps of the test are the next:

1. Select the last showed item of the list
2. Press the Summary button to clear the calling list
3. With tab key select the list view again
4. Perform a scroll with the direction keys
5. Press Summary button again

The printed list shows the problem. QListView widget makes a big number of calls. It seems the widget is reloading all the data from the model.

I don't know if it can be improved but you can't do anything but filter the list to limit the number of items to show.