Posts Tagged ‘containers’

Qt or STL containers in zkanji

June 5, 2015 Leave a comment

This post is not exactly about what I planned the last time, but I’m sure nobody will be angry about it.

Instead of relying on STL to handle the storage of data, Qt has its own container classes. STL wasn’t standardized at the time Qt started out so this is somewhat understandable, though it still happened in ancient times. When I started writing the Qt version of zkanji, I had to decide which set of container classes to use. I originally developed zkanji in an entirely different framework that didn’t use STL itself, so now when I’m rewriting everything, it really means rewriting everything. This put me in the position where I had to choose one set of the container classes.

Because the Qt documentation is full of QList this and QList that, and they also say that QList is the recommended container ‘cos it’s so great, at first I put QLists everywhere. (It is not like std::list, but rather a vector holding pointers.) I can’t say whether it was a mistake or not, but it turned out that the QList implementation is very slow in the VS debugger. The debugger is notorious of being slow anyway, but when it sees a lot of asserts, memory allocations and access, it’s even slower. (Also if you use iterators a lot it can be very slow.) Once I replaced QList at some key locations with QVector, my program sped up in the debugger. I don’t know the reason behind it, but I was lazy to check out their source code.

This was the point when I started looking for comparisons of the Qt and the STL container classes, and only found a few, like this and this. Apart from these I only saw half sentences about the inefficiency of Qt and, from others, how great it is.

Qt containers are really convenient. They hold an internal pointer which is the real container, and only that pointer gets copied if you copy the containers. The real copy only happens if you modify their contents. This can also be seen as a drawback because you never know when the “hard copy” happens. A single mistake when accessing the container elements can cause this to happen too, so be careful.

What gave me the final push was when I made some of my classes movable but non-copyable (as it’s bad when there are multiple copies of them all over the place even if only by mistake), and removed the default constructor of others. The compiler immediately scolded me that it’s not good, how could it instantiate a QList with them this way? As it turns out, Qt is not very friendly with C++11 features, even if they claim otherwise. This unfortunate detail made me switch to STL, and if some containers are STL, it’s not a good practice to mix them with QT containers in a single code. For example I would have to use the at() function of Qt lists but avoid that in STL for speed (they do different things…), and that would cause a lot of confusion later.

Phew, this was a long introduction!

QList, as I mentioned above, is like an std::vector holding pointers, with the difference that it leaves some space in front of the allocated data, so insertion and removal from the first half of the container is faster than with std::vector. Because it internally holds pointers, it also manages them. You pass in a value and it allocates a new object for it. No more need for smart pointers when the list does the allocation and deletion. When I switched to a pure STL implementation this convenience was lost. But worry not! (You didn’t worry? Sorry.) I just had to create a new container class derived from std::vector that works like a list of smart pointers. Erasing an element also deletes the object via its pointer that was stored there. In general, deriving from STL containers is a mistake because they don’t have virtual destructors. I don’t plan passing them as pointers to the base vector’s type when handling my “smartvector” (as I named it) so no problems there. It’s all for convenience because this way VS shows the list of elements in the debugger, and I don’t have to add a natvis extension to it.

String storage? I had wchar_t all over zkanji originally while it was Windows only. This data type holds a 2 bytes wide character when compiled on Windows, and a 4 bytes wide one on linux implementations. Obviously I had to get rid of it in the new code. I was eyeing QString at first, and it’s probably a good choice usually, but I just don’t like the idea of storing unnecessary data, like reference counting, inner pointer for fast copy etc., when the average size of the strings is 3-5 characters (for kana / kanji) and maybe 20 for English definitions. std::string was out of question in the first place, because I could at most use UTF-8 with them, and string comparison and the like would be a pain.

At first I replaced every wchar_t* with QChar*. QChar is the character type used in arrays inside QString, and an array of QChar can be easily converted to QString where the Qt GUI code needs it. I tested it myself and found that using arrays of QChar or using unsigned short (which it holds internally) has exactly the same speed. QChar also has its convenience with its built in functions so it was an obvious choice. I also found out by testing that comparing strings with the QString comparison functions is 1.3 times slower than writing my own function that compares characters one by one in a QChar array. (Yes I tried this in release code as well.)

As a real solution, I finally got off my lazy bum and wrote a container class for QChar arrays that frees up the data when it gets deleted. I also made the natvis extension for it so the debugger correctly shows my strings, and not just the first character in the array. This string is designed like an array: it shouldn’t be modified too often, so it’s purely for holding the data, but because of that it can be very fast and memory efficient as well.

With this I have everything that satisfies my (current) container needs. I can’t give a real conclusion or judge which is better, Qt or STL containers. I found Qt containers to be much more convenient than STL containers, and not as much slower that would make them useless (when you are not handling huge amounts of data), but they are not as c++11 friendly as I wish they were, so I waved them good bye.

Next time I’ll write about… something. I can’t see the future it seems.

Categories: Development, Rant Tags: , ,