How to optimize Containers
Performance Tip: Optimizing Containers
The developers of the Qt framework spend a lot of time packing performance into their code. The Qt 4 release back in 2008 focused on performance, and they released some documentation at the time to help developers leverage the upgrade. Some of the discussions at the time are still worth reviewing, including a discussion about container optimization summarized here. A detailed discussion of performance issues is available in the Maximizing Performance with Qt [qt.nokia.com] white paper.
Container selection
Let’s start with the obvious: containers are fundamental building blocks of software applications. How quickly data can be moved into and out of containers is a critical factor in the application’s overall performance. Qt 4.5 included optimizations which sped up the performance of most containers, which means better performance for all Qt applications. The optimization of containers has continued through the 4.6 and upcoming 4.7 releases.
Let’s continue with three representative container classes and how container type impacts performance.
- QVector is optimized for accessing data at the expense of slowing the process of data insertion and deletion. The QVector class stores an array of values of a given type at adjacent positions in memory. Inserting at the front or in the middle of a vector can be quite slow, because it can lead to large numbers of items having to be moved by one position in memory.
- QLinkedList is optimized for the other extreme: this classic linked list pattern makes insertion and deletion of items lightning quick, but accessing an item requires iteration over the list.
- QList is by far the most commonly used container class. More than any other container class, QList is highly optimized to expand to as little code as possible in the executable. It stores a list of values of a given type that can be accessed by index. Internally, the QList is implemented using an array, ensuring that index-based access is very fast.
Additional reading
- Maximizing Performance with Qt [qt.nokia.com] white paper.
- Container class documentation from 4.6 release [doc.trolltech.com]
- Inside the Qt 4 Containers [doc.qt.nokia.com] – Qt Quarterly #19 article about internal implementation