Quiz Time! Prepending items to QVector

VRonin

I had a case where I found myself with a loop that had to prepend items to a QVector<MyClass*> and I asked myself what would be more efficient:

repeatedly calling QVector::prepend
repeatedly calling QVector::append and then std::reverse at the end

I actually benchmarked it but before sharing the results let's make it a challenge.
The person who gets it right will be praised as holder of infinite wisdom forever.

Before you ask, no this is still not peak nerd!

VRonin

And the answer is:
In Qt5 append+std::reverse is vastly superior, In Qt6 prepend is the much faster one.

aha_1980

Hi @VRonin,

you first have to mention the Qt version you are using.

Are you still on 5.15 or already on a 6.x series where lots of optimizations for that case have been done?

Regards

VRonin

@aha_1980 great question! I ran the benchmark for both 5.15.2 and 6.0.3 so chose your poison

JonB

@VRonin
My guess is that append + reverse is more efficient than prepend.

My reason is why would you even bother to ask this question if prepend is more efficient?

:)

VRonin

@JonB said in Quiz Time! Prepending items to QVector:

My reason is why would you even bother to ask this question if prepend is more efficient?

I asked myself this question before benchmarking, that’s why

Chris Kawa

How many elements? can I use reserve? Are we talking 32 or 64 bits?
My cheat answer would by - it depends ;)

jeremy_k

Am I misreading the problem, or does this also need to have the initial sequence reversed prior to the append + reverse operation?

Chris Kawa

@jeremy_k My understanding was that we're starting from an empty container and only need it in correct order after everything is in, otherwise you'd need to do that double reversal on each addition. I could be wrong though.

fcarney

It depends, I think.
I don't know, but I am putting on depends in case the answer is shocking.

jeremy_k

If the container starts empty, I would expect using a reverse iterator for reading and append for writing would beat both strategies mentioned in the initial post. Unless QVector has become a single linked list (edit: or the consumer demands a QVector).

Kent-Dorfman

My knowledge base is more in line with stl containers, but making the asusmption that QVector works the same, there is implicit preallocation ie reserve(n) involved in append+reverse that probably doesn't exist with the prepend call, so it stands to reason that few memory reallocations may be necesary using append+reverse.

but the larger issue is whether O(1) random access is needed or guaranteeed continuous element allocation...if not, the QList would be a much more efficient container.

J.Hilk

In case you do not reserve memory for the QVector beforehand, I would say append + std::reverse is faster

Because I think, that prepend does not reserve additional memory, compared to append(size / 2 more IIRC). So you end up with an allocation and memory move/copy on each prepend

VRonin

How many elements?

The benchmark tested 10, 50, 100, 500, 1000, 5000 but turns out the answer doesn't change with size

can I use reserve?

Yes, in both cases I first called QVector::reserve

Are we talking 32 or 64 bits?

64

I would expect using a reverse iterator for reading and append for writing would beat both strategies mentioned in the initial post.

Yes, this is obvious but in my use case I can't read with reverse iterator

or does this also need to have the initial sequence reversed prior to the append + reverse operation?

To make it more explicit: If I have the sequence 1, 3, 2, 5 (that I can't reverse iterate) I want the vector to store those as 5, 2, 3, 1

VRonin

And the answer is:
In Qt5 append+std::reverse is vastly superior, In Qt6 prepend is the much faster one.

fcarney

What about just starting at the end of the data first and only appending?

VRonin

@fcarney said in Quiz Time! Prepending items to QVector:

What about just starting at the end of the data first and only appending?

I guess you mean in Qt6. In that case append is slightly better but the difference is really tiny

SimonSchroeder

Is there any article about these specific changes in Qt 6 that I can read? What exactly has changed between Qt 5 and 6?

Christian Ehrlicher

@SimonSchroeder said in Quiz Time! Prepending items to QVector:

What exactly has changed between Qt 5 and 6?

QVector is no longer in Qt6 and an alias for QList. I would guess QList in Qt5 will also show the same fast results for prepend since QList has an optimization for this usecase since ages.

VRonin

From https://wiki.qt.io/New_Features_in_Qt_6.0

QVector and QList are unified. QList is updated and should be used by default when array-like behaviour is needed
QList, QString and QByteArray now have optimized complexity of insertion at the beginning (a.k.a. prepend)

kshegunov

@VRonin I'm late to the party, as usual ...
... and also as usual I probably sound like a broken record, but what your task sounds like is actually a stack, not a vector ... ;)