QVector::reserve() squeezes allocation, can ruin performance on repeated use

This issue was originally posted as a bug against QPainterPath, but the root cause is in QVector::reserve(). The problem is that there are two ways to interpret the argument to QVector::reserve(). Either, it is the future maximum element count, so memory should be allocated for exactly n elements - this is what QVector does. Or, it is a future minimum-needed count, so memory should be allocated for at least this number of elements - following QVector's normal over-allocation strategy to minimize the number of reallocations. There is currently no way ask for the latter. But reserve() calls have been added to some places in Qt where only the latter interpretation makes sense - for example in QPainterPath here. Although that issue has been worked around by just removing the reserve() calls, the base issue may be worth looking into. Original report below:

Calling many times addPolygon on a QPainterPath results in horrible performance degradation the more you call it, especially when the complete path has many points and on 32 bit systems.

In my case I had 400 polygons of ~380 points each; running on 64 bit Linux it worked decently, on a 32 bit Windows build it spent a huge amount of time (hundreds of ms) in my addPolygon loop. Expanding the addPolygon to a moveTo for the first point and a lineTo to the others essentially fixed the performance issue.

I investigated the problem, and it turns out that QPainterPath::addPolygon expands the QPolygonF that it receives to MoveTo/LineTo QPainterPath::Element items in its internal QVector<QPainterPath::Element>, but, unlike calling explicitly moveTo/lineTo, it tries to have better performance by calling reserve(# of existing elements + polygon_size).

Unfortunately, this is what kills the performance. QVector::reserve checks if there's enough space for the requested size, and, if there's not, it calls QVector::reallocData with the default AllocationOptions; these don't include the Grow flag, which means that the underlying QTypedArrayData::allocate (which forwards to QArrayData::allocate, which uses calculateBlockSize) won't grow the memory block using the usual overallocation strategy that provides amortized O(1) behavior, but will just allocate a memory block tightly fit to the reserved size.

Essentially, by calling addPolygon you are in for a reallocation of the QVector<QPainterPath::Element> each time, which in my case meant copying on average 75000 Element.

My current workaround is to drop the last point from the QPolygonF, do the addPolygon and then do the final lineTo; this ensures that, if the addPolygon reserve did in fact reallocate "tightly", the extra lineTo will force a reallocation with the usual strategy (lineTo does no reserve), thus having good performance in the next calls.

I suspect that the 64 bit Linux case did run decently because realloc managed to just add pages at the end, while in a 32 bit process with a busy/somewhat fragmented virtual address space this was not possible; in any case, I don't think that hammering the allocator in this way is acceptable.

IMO what QPainter::addPolygon does is not wrong - passing down to the QVector the fact that I'm going to add N new elements is a perfectly reasonable thing to do; it's QVector::reserve that should pass the "grow flag" to the allocator anyway, thus guaranteeing amortized O(1) performance regardless of the pattern of calls to reserve the client may do.

But even if you decide that reserve must stay as-is, addPolygon should implement some kind of workaround - it's ridiculous that calling manually moveTo/lineTo exhibits better performance than calling the supposedly more optimized addPolygon.