Avoid mem allocs by using stack allocated initializer lists
ClosedPublic

Authored by dkurz on Aug 3 2017, 7:11 PM.

Details

Reviewers
dvratil
Group Reviewers
KDE PIM: KMail
Summary

The old code has one allocation in QList::operator<< per action.
The new code avoids heap allocs completely.

Diff Detail

Repository
R206 KMail
Lint
Lint Skipped
Unit
Unit Tests Skipped
dkurz created this revision.Aug 3 2017, 7:11 PM
Restricted Application added a subscriber: KDE PIM. · View Herald TranscriptAug 3 2017, 7:11 PM

Are you sure that there is an improvement as it's just some enum ?
it's an improvement when it's a class but for an enum not sure .

dkurz added a comment.Aug 4 2017, 10:44 AM

It's the size of the container itself (and its heap allocations) that we reduce. The old code constructs an empty array list, and then calls operator<< n times. For every such call, QList allocates a new array on the heap, one element larger in size than the last one, and then moves the old contents to the new location. That's what I figured out by looking at QList's source code (QList::operator(t)<< calls QList::append(t) calls QListData::append() calls QListData::append(1), which does exactly what I just described) , but maybe I missed some mechanism that batch allocates more space than needed, just as QVector does. But even if it did, QList cannot know at the beginning of the << sequence how much space it would need eventually. So even with vectors' trick to allocate some constant fraction of the previously used amount of memory when size hits capacity, we would have log(n) memory allocations for n insertions. Using the ctor directly reduces this to only one heap allocation.

Using the initializer list ctor of QList might be just as efficient in this case. Frankly, I'm not an expert on Qt containers. I just watched Milians CppCon15 talk on Qt yesterday, where he said that QList should probably die in favor of QVector, and only be used where it has to be passed to some function that only excepts QList, so I switched.

Technically, since the list here is only created so that it can be effectively iterated over, you could just do

const auto myActions = { .....  };

The deduced type will be std::initializer_list<T>, which is just a light wrapper for an array which can be iterated over in range-based loops. This is probably even more light-weight and faster than using QVector.

Also for QList<T> where sizeof(T) <= sizeof(void*), QList uses an optimization and stores the values directly in the contigous pointer array, thus behaving the same way as QVector more or less.

dkurz added a comment.Aug 4 2017, 10:58 AM

Yes, I saw the optimization for types that are not ::isLarge, but we still require the array. And your auto version removes the last three heap allocations, which is great. I'll update my diff accordingly.

dkurz updated this revision to Diff 17705.Aug 4 2017, 11:45 AM
dkurz retitled this revision from Reduce heap allocs by using QVector instead of QList to Avoid mem allocs by using stack allocated initializer lists.
dkurz edited the summary of this revision. (Show Details)
dvratil accepted this revision.Aug 14 2017, 7:57 AM
This revision is now accepted and ready to land.Aug 14 2017, 7:57 AM
dkurz closed this revision.Aug 21 2017, 6:04 PM