Collecting hints to increase performance in Qt (and apps)
I'm working part time on improving the performance of QtWebKit (memory usage and raw speed) and I have created some tools to create an offline copy of a number of webpages (gmail, yaho mail, google, news sites...).Using these sites I have created special purpose benchmark reductions. E.g. only do the image operations we do while loading, while loading an painting, load all network resources. One thing I have noticed is that with a couple of small things one can achieve a stable and noticable speedup. These include not calling QImage::scanLine from within a loop, avoid using QByteArray::toLower or not use QByteArray::append(char) from a loop without a QByteArray::reserve.
I have created a small guide to Qt Performance, I will keep it updated and would like to hear more small hints that can be used to improve things. If it makes sense I can migrate it to the techbase as well.
Labels: KDE
posted by zecke @ 4:10 AM
9 Comments:
Isn't the QByteArray::append issue a bug in QByteArray? Shouldn't such an operation be amortized O(1)?
For example std::vector::push_back has such an runtime guarantee.
reserve() should be for users that do not want to waste any memory and not for users that want better performance.
Good question. It comes down to the point how you treat qRealloc/qMalloc in your calculations.
In case mmap/sbrk is used, or a new page needs to be mapped the kernel VM subsystem might write out a page to "swap", which means the block layer is hit, one is waiting for the writeout to be complete... is hardly armotizing to a constant time...
Did you ever see anyone taking this into account?
Can you post the performance measurements/data?
@Christoph Bartoschek:
This is afaik not entirely correct, because the linear complexity promise for push_back et al. holds only true if you do not insert too much elements (e.g. size + new elements < capacity). This is at least what I gather from documents like for example the SGI STL reference manual, cf.
http://www.sgi.com/tech/stl/Vector.html , footnote 3
If the capacity has to be increased, typically 2 * capacity has to be allocated and - in general terms - the content of the old vector has to be copied over to the new location, e.g. a O(n) operation.
This, plus the fact that typically all iterators are invalidated after an operation that changes the capacity, are imho good justifications why reserve() should be used whenever you have a good estimate/idea of the necessary capacity of your vector.
Cf. also Scott Meyer, Effective STL, item 14.
It does not build, the repo is missing some xml files.
@simon: I can not post the data as it is real websites that are copyrighted... You can use the "mirror" tool to create your own data: http://trac.webkit.org/wiki/QtWebKitPerformanceUtilities
@pau: Which XML files? Do you have source-highlight installed? I'm converting C++ code to docbook-xml using this tool. If you are missing *.cc.xml files then install source-highlight.
> If it makes sense I can migrate it to the techbase as well.
Yes please! :-) It would make the page more accessable to more developers. Not everyone instantly knows how to use git + docbook compilers.
@zecke I do not understand the problem you are posing. Hitting the VM subsystem will also happen if you call reserve() as soon as you write to the pages.
@setec You are right. Calling reserve() is faster and uses less memory if one knows the target size. However if one does not know the size appending elements should not be a quadratic operation as it appears to be for QByteArray.
Copying all elements over to the new location makes some push_back() calls linear but the amortized runtime over all calls to push_back() is still O(1) per operation.
Post a Comment
<< Home