Qt: QList and loop performance

Recently I was looking for how to reverse a QList and I stumbled over that one-liner on stackoverflow:

The one-liner does what it’s supposed to, but do you see the redundancies that cause poor performance?

Be aware of repeating code in abort conditions

Take a look at the abort condition of the for loop: k < (list.size()/2).
That expression is evaluated with every start of a loop. Having a list with 1 million elements will cause 1 million list.size() calls with the result being divided by 2. Almost every time you need a for loop like that the list will never change in size while iterating through it. So you really should pull the maximum expression out of the abort condition and put it in the loop initialization:

Be aware of repeating code inside the loop

Next, lets take a closer look at the single statement in the loop's body: list.swap(k,list.size()-(1+k)).
It is also calling list.size() with every iteration of the loop. If your compiler ain't smart that call is done 2 million times on a list with a million elements when using the initial one-liner. Luckily, you can apply the same pattern as above and pull that list.size() call into the loop initialization:

Initialize lists with target size if you know it

I wrote a little example application to demonstrate the effect of performance tunings mentioned above. To test the one-liners I created lists of 1 million QTimer objects.

However, as I knew how many objects the lists are going to hold I made use of QList::reserve(int) method to initialize the list with the target size:

The output of my demonstration code is:

As you can see from the numbers pulling redundant expressions into loop initialization gives roughly a 30% performance boost.

When initializing lists with values where you know the target count already gives you roughly a 10% performance boost when using QList::reserve(int).

Summing it up

When coding with loops always take a few seconds to check what you can pull into loop initialization. Usually lists are not iterated only once so there's a great opportunity for boosting performance. If you take the extra mile of calling QList::reserve(int) you can profit from another 10% performance gain.

Leave a Reply




You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>