One of the improvements which were mentioned in the recent announcement of Trojitá, a fast Qt e-mail client, were substantial memory savings and speed
improvements. In the rest of this post, I would like to explain what exactly we have done and how it matters. This is
going to be a technical post, so if you are not interested in C++ or software engineering, you might want to skip this
article.
Planting Trees
At the core of Trojitá's IMAP implementation is the TreeItem, an abstract class whose basic layout will
be familiar to anyone who has worked with a custom QAbstractItemModel reimplementation. In short, the
purpose of this class is to serve as a node in the tree of items which represent all the data stored on a remote IMAP
server.
The structure is tree-shaped because that's what fits both the QAbstractItemModel's and the IMAP way of
working. At the top, there's a list of mailboxes. Children of these mailboxes are either other, nested mailboxes, or
lists of messages. Below the lists of messages, one can find individual e-mails, and within these e-mails, individual
body parts as per the recursive nature of the MIME encapsulation. (This is what enables messages with pictures attached,
e-mail forwarding, and similar stuff. MIME is fun.) This tree of items is used by the QAbstractItemModel
for keeping track of what is where, and for issuing the QModelIndex instances which are used by the rest of
the application for accessing, requesting and manipulating the data.
When a QModelIndex is used and passed to the IMAP Model, what matters most is its
internalPointer(), a void * which, within Trojitá, always points to an instance of some
TreeItem subclass. Everything else, like the row() and column(), are actually not
important; the pointer itself is enough to determine everything about the index in question.
Each TreeItem has to store a couple of interesting properties. Besides the usual Qt-mandated stuff like
pointer to the parent item and a list of children, there are also application-specific items which enable the code to,
well, actually do useful things like printing e-mail subjects or downloading mail attachments. For a mailbox, this
crucial information might be the mailbox name. For a message, the UID of the message along with a pointer
to the mailbox is enough to uniquely identify everything which is needed.
Lazy Loading
Enter the lazy loading. Many people confirm that Trojitá is fast, and plenty of them are not afraid to say
that it is blazingly fast. This speed is enabled by the fact that Trojitá will only do the smallest amount of
work required to bring the data over the network (or from disk, for that matter). If you open a huge mailbox with half a
million messages, perhaps the GMail's "All messages" account, or one's LKML archive, Trojitá will not start
loading half a million of subjects. Instead, the in-memory TreeItem nodes are created in a special state
"no data has been requested yet". Trojitá still creates half a million items in memory, but these items are rather
lightweight and only contain the absolute minimum of data they need for proper operation.
Some of these "empty" nodes are, eventually, consulted and used for item display -- perhaps because a view is
attached to this model, and the view wants to show the recent mail to the user. In Qt, this usually happens via the
data() method of the QAbstractItemModel, but other methods like rowCount() have a
very similar effect. Whenever more data are needed, the state of the tree node changes from the initial "no data have
been requested" to "loading stuff", and an asynchronous request for these data is dispatched. An important part of the
tale is that the request is indeed completely asynchronous, so you won't see any blocking whatsoever in the GUI. The
QTreeView will show an animation while a subtree is expanded, the message viewer might display a spinner,
and the mail listing shows greyed-out "Loading..." placeholder instead of the usual message subjects.
After a short while, the data arrive and the tree node is updated with the extracted contents -- be it e-mail
subject, or perhaps the attached image of dancing pigs. As the requested data are now here, the status of the tree node
is updated from the previous "loading stuff" into "done". At the same time, an appropriate signal, like
dataChanged or rowsInserted, is emitted. Requesting the same data again via the classic MVC
API will not result in network requests, but everything will be accommodated from the local cache.
What we see now is that there is just a handful of item states, yet the typical layout of the TreeItem looks roughly
like this:
enum class FetchingStatus {
INITIAL_NOTHING_REQUESTED_YET,
LOADING,
DONE,
FAILED
};
class TreeItem {
TreeItem *m_parent;
QList<TreeItem*> m_children;
FetchingStatus m_status;
};
On a 64bit system, this translates to at least three 64bit words being used -- one for the painter to the parent
item, one (or much more) for storage of the list of children, and one more for storing the enum
FetchingStatus. That's a lot of space, given we have just created half a million of these items.
Tagged Pointers
An interesting property of a modern CPU is that the data structures must be aligned properly. A very common
rule is that e.g. a 32bit integer can only start at memory offset which is a multiple of four. In hex, this means that
an address, or a pointer value, could end with 0x0, or 0x4, or 0x8, or
0xc. The detailed rules are platform-specific and depend on the exact data structure which we are pointing
to, but the important message is that at least some of the low bits in the pointer address are always going to be zero.
Perhaps we could encode some information in there?
Turns out this is exactly what pointer tagging is about.
Instead of having two members, one TreeItem * and one FetchingStatus, these are squashed into
a single pointer-sized value. The CPU can no longer use the pointer value directly, all accesses have to go via an
inlined function which simply masks away the lowest bits which do bring a very minor performance hit, but the memory
conservation is real.
For a real-world example, see this commit in
Trojitá.
Using Memory Only When Needed
Back to our example of a mailbox with 500k messages. Surely a user is only going to see a small subset of them at
once, right?
That is indeed the case. We still have to at least reserve space for 500k items for technical reasons, but there is
certainly no need to reserve space for heavy stuff like subjects and other headers. Indeed, in Trojitá, we track the
From/To/Cc/Bcc headers, the subjects, various kinds of timestamps, other envelope items and similar stuff, and this
totals a couple hundred bytes per each message. A couple hundred bytes is not much (pun intended), but "a couple
hundred bytes" times "half a million" is a ton of memory.
This got implemented here. One
particular benchmark which tests how fast Trojitá resynchronizes a mailbox with 100k of messages showed immediate
reduction in memory usage from previous 45 MB to 25 MB. The change, again, does come with a cost; one now has
to follow one more pointer redirection, and one has to perform one more dynamic allocation for each message which is
actually visible. That, however, proves to be negligible during typical usage.
Measure, Don't Guess
As usual with optimizing, the real results might sometimes be surprising. A careful reader and an experienced Qt
programmer might have noticed the QList above and shuddered in horror. In fact, Trojitá now uses
QVector in its place, but when I was changing the code, using std::vector sounded like a
no-brainer. Who needs the copy-on-write semantics here anyway, so why should I pay its price in this context? These data
(list of children of an item) are not copied that often, and copying a contiguous list of pointers is pretty cheap
anyway (it surely is dwarfed by dynamic allocation overhead). So we should just stick with std::vector,
right?
Well, not really. It turned out that plenty of these lists are empty most of the time. If we are looking at
the list of messages in our huge mailbox, chances are that most of these messages were not loaded yet, and therefore the
list of children, i.e. something which represents their inner MIME structure, is likely empty. This is where the
QVector really shines. Instead of using three pointers per vector, like the GCC's std::vector
does, QVector is happy with a single pointer pointing to a shared null instance, something which is
empty.
Now, factor of three on an item which is used half a million times, this is something which is going to hurt.
That's why Trojitá eventually settled on
using QVector for the m_children member. The important lesson here is "don't assume,
measure".
Wrapping up
Thanks to these optimization (and a couple more, see the git log), one particular test case now runs ten times faster
while simultaneously using 38% less memory -- comparing the v0.4 with v0.3.96. Trojitá was pretty fast even before, but
now it really flies. The sources of memory diet were described in today's blog post; the explanation on how the time
was cut is something which will have to wait for another day.
