For loops in times of C++11 part 1

Regular for

We all know for. It was our friend since time immemorial. It’s simple to understand, it’s easy to convert into efficient assembly and it creates a new scope (and we do like scopes, don’t we?). Can we improve it? Let’s then talk about its deficiencies.

Note: I am assuming you understand that raw loops are something that should be used on the lowest level of implementation and your logic should be based on algorithms.

Tediousness

Writing

for (int i = 0; i < MAX_FOO; ++i)

doesn’t seem to involve many keystrokes, but if you consider that you will write similar code many times in your career that changes the picture a little bit. Because of it people either create their custom macros in Vim or snippets in Visual Studio or in IDEs featuring similar functionality.

Type

for (? idx = 0; ... 

What should be the type of our index? That’s obvious! It should be the same as the sentinel (aka max value). If we get the type wrong we got nice warnings from the compiler:

foo.cpp: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

That’s not a big issue, but why to waste your precious time fixing such stupid mistakes? And what if the conversion (promotion) between types is acceptable, but you will be constantly paying a conversion cost every loop iteration (unless the compiler does its optimizations)?

Performance and risk

Let’s get to something really important: efficiency and safety. If you see following code:

for (int i = 0; i < slotMgr.maxSlots(); ++i) {
    ...
    ...
    ...
}

Can you, without a doubt, quickly tell if:

  • the index (i) won’t be modified inside the loop so that the loop will be executed less/more than maxSlots() times? It might not be the case, but in specific cases one might want to – for instance – retry using a slot in the next loop iteration by decrementing the iterator in the loop body.
  • maxSlots() value won’t change during execution? Maybe some body operation modifies (indirectly or directly) the slots count?

First problem with above scenarios is that for someone who will be reading the code it’s harder to understand (abstract) the loop logic. If you are not sure whether index won’t change, or slots value will be altered – then you will spend more time to understand what’s going on.

Second problem is efficiency. Compiler might have hard time telling whether the maxSlots() call is constants throughout the whole loop. If it isn’t (any many compilers have to assume such scenario) every loop you will be paying a cost of a function call which itself might not be as trivial as simple return this->size;.

Range-based for

With the advent of C++11 we got the lovely range based fors:

for (auto& x : vector_of_T)

What it does it simply uses std::begin() and std::end() free functions that allow you to put even C-style arrays in place of vector_of_T.

That’s all cool, but how does it help us in case of regular loops? Do you expect us to write something like this?

auto v = std::vector<int>{0, 1, 2, 3}; // Madness!

// Imitates for (int i = 0; i < 4; ++i)
for (auto i : v) { 
    ...
}

God forbid! Let’s keep the terseness of this syntactic sugar, add usability (no handwritten vectors) and safety – meet ForRange!

ForRange

The idea is simple. I want:

for (auto i : range(slotMgr.maxSlots())) {
    ...
}

Requirements for range(T):

  • as fast as hand written loop;
  • no need to specify type (auto is enough);
  • hoists the maxSlots() value for efficiency and simplicity;
  • allows arbitrary begin, end and step.

Implementation of ForRange is relatively simple, although a bit of code must be written. Never the less I encourage you to try to implement it on your own. I will come back with my implementation in part 2, together with some discussion about pros and cons of a given design.

Advertisements

Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: