Solved Simple big-looped program break down
-
@Please_Help_me_D
For presumably similar slowness withQVector
, try creating it empty with justQVector<int> a
and usea.append(i)
in the loop. I anticipate some slowness compared to pre-sizing, but (hopefully) not as bad as it could be:This operation is relatively fast, because
QVector
typically allocates more memory than necessary, so it can grow without reallocating the entire vector each time. -
@JonB very interesting result as for me:
QVector<int> a; clock_t start_time = clock(); for (int i = 0; i < 100000000; i++) { a.append(i); } clock_t end_time = clock(); clock_t d_time = end_time - start_time; cout << d_time << endl;
in Debug mode it takes 5.5-6 seconds
in Release mode it takes 0.7 second (while in Matlab as I previously said it takes 35 seconds)
So QVectror is really fast even if it works with <appending mode>
Thank you for this example! -
@Please_Help_me_D said in Simple big-looped program break down:
So QVectror is really fast even if it works with <appending mode>
As far as I know QVector allocates more memory as currently is need and on resizing it allocates again more than "current_size + 1".
-
@jsulm yes it does.
I tested how much my program weigh with Windows Task Manager for different number of loops (say n) and two mode of QVector (normal and <append>). Here is the result (Debug mode):QVector<int> a(100000000); clock_t start_time = clock(); for (int i = 0; i < 100000000; i++) { a[i] = i; } clock_t end_time = clock(); clock_t d_time = end_time - start_time; cout << d_time << endl;
n = 100000000 -> 392464 kilobytes
n = 100000000/2 -> 196780 kilobytes
n = 100000000/4 -> 98936 kilobytes
n = 100000000/8 -> 50008 kilobytes
!_____________________________!QVector<int> a; clock_t start_time = clock(); for (int i = 0; i < 100000000; i++) { a.append(i); } clock_t end_time = clock(); clock_t d_time = end_time - start_time; cout << d_time << endl;
n = 100000000 -> 527456 kilobytes
n = 100000000/2 -> 264804 kilobytes
n = 100000000/4 -> 133468 kilobytes
n = 100000000/8 -> 67804 kilobytesIf I use simple C++ array insead of QVector then for n = 100000000 -> 391780 kilobytes (almost the same as simple QVector).
So the conclusion I see is that QVector in <append> mode weighs 1.35 times simple QVector or C++ array
-
@Please_Help_me_D said in Simple big-looped program break down:
So the conclusion I see is that QVector in <append> mode weighs 1.35 times simple QVector or C++ array
IIRC, than its 1.5, same as std::vector
-
@jsulm said in Simple big-looped program break down:
@Please_Help_me_D said in Simple big-looped program break down:
So QVectror is really fast even if it works with <appending mode>
As far as I know QVector allocates more memory as currently is need and on resizing it allocates again more than "current_size + 1".
Which is why I originally quoted from https://doc.qt.io/qt-5/qvector.html#append:
This operation is relatively fast, because QVector typically allocates more memory than necessary, so it can grow without reallocating the entire vector each time.
As for the exact timing: if, say, it re-allocates by powers of 2, I make that something
log2(100000000) == 27
reallocations? :) -
@JonB said in Simple big-looped program break down:
As for the exact timing: if, say, it re-allocates by powers of 2, I make that something log2(100000000) == 27 reallocations?
It doesn't. If memory serves me it has a special progression for the first 128 elements or so, and after that it doubles its size on each realloc.
-
@kshegunov
When I wrote this for arealloc()
replacement/interface many years ago, I did it by increasing powers of 2 :-) Either way, the point is it's orderlog2(n)
-ish, -
You do know I'm old, so you mustn't trust me too much. I wouldn't do it by increasing powers of two anyway, more like a percent of the current size, otherwise you're overshooting the needed capacity most of the time.
-
@kshegunov
You wrote:and after that it [Qt] doubles its size on each realloc.
I wrote
I did it by increasing powers of 2
Doesn't "doubling" mean "the next power of 2"? That's what I was trying to convey.
2^n < x < 2^(n +1) => 2^(n + 1) < 2*x < 2^(n + 2)
Right?
-
@JonB said in Simple big-looped program break down:
Doesn't "doubling" mean "the next power of 2"?
Yeah. I'm not at the top of my game, so you can probably safely ignore me.