Saturday, April 11, 2009

How to make foreach loops that don't suck

Calling values in Hashes/Maps/Sets

QHash<QString,Plasma::Meter*> meters;
foreach (Plasma::Meter *w, meters.values()) {
  w->setLabelColor(0, theme->color(Plasma::Theme::TextColor));
}


This code is iterating over the values of a hash and doing something over them. Everything seems ok, but it's not, it's calling values() on the hash and that's causing the creation of a temporary list with all the values of the list, effectively causing a bigger memory usage and iterating over the list twice (one to get the values and other to do something over them).

You can write something that does the same without these two problems doing

QHash<QString,Plasma::Meter*> meters;
foreach (Plasma::Meter *w, meters) {
  w->setLabelColor(0, theme->color(Plasma::Theme::TextColor));
}


So if you are using values() in a foreach, just remove it and your code will be instantaneously faster.

Calling keys in Hashes/Maps


QHash<QString,Plasma::SignalPlotter*> plotters;
foreach (const QString& key, plotters.keys()) {
  plotters.value(key)->setShowLabels(detail == SM::Applet::High);
  plotters.value(key)->setShowHorizontalLines(detail == SM::Applet::High);
}


This is calling keys() over the hash, this, as values(), means going across the container and creating a temporary list containing all the keys of the hash, that's a waste of memory when you could simply use a proper
QHash<QString,Plasma::SignalPlotter*>::const_iterator
and just iterate keys one by one.

Then it does plotters.value(key) twice, ok, accessing a value in a hash is amortized O(1) but still you are going to calculate the qHash of the string twice for no reason.

But more important, what the code is doing is actually iterate over the values, so the proper way is doing

QHash<QString,Plasma::SignalPlotter*> plotters;
foreach (Plasma::SignalPlotter *plotter, plotters) {
  plotter->setShowLabels(detail == SM::Applet::High);
  plotter->setShowHorizontalLines(detail == SM::Applet::High);
}


Probably in this case the net benefit is not much because probably the number of element of plotters is small, but there's no need to write inefficient code when the efficient one is as easy to write.

And of course it could be worse. If plotters was a map instead of a hash, lookup would be O(log(n)).

So if you are using keys() in a foreach, please think twice what you are doing and if you only need the value, iterate of the container and if you really need the key use a proper iterator to avoid constructing the temporary list.

2 comments:

Anonymous said...

If you do not want to change the values, this is also worth a read:

http://labs.trolltech.com/blogs/2009/01/23/iterating-efficiently/

Allen Winter said...

I am adding a Krazy check for this. Should show up soon with the nightly runs on the EBN.