Аномальное использование памяти QVector ⇐ C++

[Anonymous]

I few years back I tested QVector and std::vector side by side, and was living with the impression the two are in the same ballpark of performance, in fact in some cases QVector was edging out.

Until yesterday, when I ran a quick compliance test for a custom container, just to discover some major performance regression.

class TestQVector { QVector data; public: uint count() const { return data.size(); } uint size(uint d) const { return data[d].size(); } uint create() { uint res = count(); data.push_back({}); return res; } void add(uint d, uint i, uint v) { data[d].insert(i, v); } void set(uint d, uint i, uint v) { data[d] = v; } void rem(uint d, uint i) { data[d].remove(i); } uword sum() { uword res = 0; for (const auto & dt : data) { for (const auto & it : dt) { res += it; } } return res; } }; class TestVector { std::vector data; public: uint count() const { return data.size(); } uint size(uint d) const { return data[d].size(); } uint create() { uint res = count(); data.push_back({}); return res; } void add(uint d, uint i, uint v) { data[d].insert(data[d].begin() + i, v); } void set(uint d, uint i, uint v) { data[d] = v; } void rem(uint d, uint i) { data[d].erase(data[d].begin() + i); } uword sum() { uword res = 0; for (const auto & dt : data) { for (const auto & it : dt) { res += it; } } return res; } }; The actual test uses a persistent pseudo-random sequence to execute 100M data operations, with the ratio odds of 1/3/3/2 to respectively allocate new data, insert element in random data, modify an element or insert a new if empty, and to remove a value if not empty. And the respective results:

std::vector: test 1 completed in 4902ms checksum: 79149386424587854, data count: 13725497, sum time: 30ms 723mb qvector: test 1 completed in 5259ms checksum: 79149386424587854, data count: 13725497, sum time: 80ms 1141mb custom dense: test 1 completed in 15314ms checksum: 79149386424587854, data count: 13725497, sum time: 33ms 641mb The largest difference here is the testing time for the custom container, but that's expected since it doesn't use any spare capacity, it does a lot more reallocation.

The second largest difference is that QVector takes almost 3 times as much time to traverse.. for reasons unknown...

And last but certainly not least, there's the memory use...

The dense container object is 16 bytes, as opposed to 24 bytes for std::vector, so at the given number of containers, I expect ~100mb of overhead over the dense container, which is precisely the result.

But QVector ends up using nearly twice as much memory. And even if all the vectors are trimmed to their actual capacity during the summing stage, only about half of the unexpected overhead goes away.

Is this some performance degradation? Has QVector dramatically changed? Note that in Qt6, QVector is just an alias for QList, and QList in Qt5 wasn't great, and I was under the impression it underwent some improvement for Qt6.

Furthermore, even if QVector::squeeze() isn't for some reason releasing all over-provisioned memory, that shouldn't be a major factor contributor to the slow iterating...

It doesn't seem to be leaking the memory, as after the test object is destroyed I am getting back the expected amount of memory.

There's no implicit sharing taking place at any time, there's no code path in the test interface.

Clarification:

This question is not about what's wrong with my code. It is a question directed at people who dabble in Qt and keep up with its design changes.

The test interface is provided in full, there's nothing else taking place aside from a pseudo random sequence of those operations. The test has external dependencies on unrelated stuff like project related macroses and PRNGs, that constitute an above trivial amount to make a portable example, and even then - it would not produce the exact test sequence.

The issue at hand is not the test itself, but the performance discrepancies exhibited during basic and logically correct use of the particular container.

There's no shame in not knowing and moving away, not so sure about complaining about stuff that is outside the scope of the question.

Update:

As expected, throwing in a run of the mill PRNG polluted the timing results into significantly mitigating the disadvantage of the dense container.

std::vector test completed in 13095 checksum 47700646824865431 12497917 114 652mb qvector test completed in 12178 checksum 47700646824865431 12497917 103 1030mb custom dense test completed in 17133 checksum 47700646824865431 12497917 104 561mb I was also able to trace the iteration overhead to something I overlooked when I was testing the effect on squeezing:

for (/*const*/ auto & dt : data) { // dt.squeeze(); Step 1 - commented out the const in order to test squeeze Step 2 - commented out the squeeze when it didn't help Step 3 - forget to out-comment-out the const Addressing that and the iteration performance is back to expectations. But the memory bloat issue remains. Here's a dependency-free (excluding Qt obviously) version of the test itself:
template class DataTest { Test test; uint randIndex(uint c) { return c ? gen.bounded(c - 1) : 0; } QRandomGenerator gen; public: void run() { gen.seed(); uint rep = 100000000; test.create(); test.create(); test.create(); test.create(); test.create(); test.create(); QElapsedTimer tt; tt.start(); while (rep--) { uint v = gen.generate(); uint op = v % 8; uint target, i, s; if (!op) { target = test.create(); s = 0; i = 0; } else { target = randIndex(test.count()); s = test.size(target); i = randIndex(s); } if (!(rep % (1024 * 1024 * 16))) ulog

Источник: https://stackoverflow.com/questions/781 ... memory-use