Crypton's Blog

Have you ever tried to implement foreach loop macro in C++? If you tried, you know that it's almost impossible to do it, because you have to initialize the reference to iterated value in the initialization section of the for loop (i.e. immediately after "for" keyword), so you cannot change the reference (i.e. make it point to different object), therefore you must split the foreach loop into two for loops. It's common to implement foreach as two for loops, most of the implemetation I've seen (e.g. Qt or this) do it this way.

What's wrong on this implementation? it's slow! Not only that there must be some helper container constructed with a variables whose purpose is to keep the foreach state (to switch and interupt second for loop), but also, for every iterated element, there are several useless condition tests and var assignments, only to make it working.

That's a way slower than normal for/while loop with iterators.

How can we speedup the foreach loop? Can't we somehow remove the second for loop and the helper container? Surely we can, but it won't be easy (and for someone nice).

I spent all day researching and implementing different foreach loops, but in the end, I had to split it into two for loops anyway.

It's almost impossible to implement it to work with references. Pointers are easy thing, task for 5 min, but it isn't as convenient as foreach with references.

Anyway, that way the portable-way attempt, later I managed to implement the foreach loop as one for loop by hacking the reference via templated asm function. Someone may consider it as ugly hack, but who cares, when it's a way faster than other implementations, and you can always easily switch to generic implementation, because it's nothing more than a macro.

So how did I implemented it? Have a look at this picture:

This picture shows how my foreach implementation works, before I converted it to macro. It consist of 4 variables:

1. -First variable is containter's iterator object. Nothing special about it, use your own or stl implementation.

   
   

2. -Second is pointer to current iterated element. While iterating, it's compared to NULL, so it's very fast.

   
   

3. -Third variable (reference) is the most important one. It's actually pointer to fourth variable ("element"), which is reference to currently iterated element, so it's pointer to pointer to "element" reference. After calling pointerToReferenceEx, it will point to variable reference, so we can change reference's address to point to different (next) element.

   
   

4. -Fouth variable is currently iterated element, it will always point to new element after every for loop iteration.

   
   

As you can see, I'm using new Cpp0x features, auto and decltype, to determine type of variables, because C++ doesn't have any typeof operator (GCC has it as extension, which is used by Qt foreach loop as well).

That's nothing special, the magic relies in the pointerToReferenceEx function (I'm not going to release the implementation yet), which takes as first argument a pointer to element you want to dereference, and which is able to determine address of reference on the left side (varible "element") of the expression and assign it to variable "reference" before the function returns! In other words, the function is able to determine the address of reference where the input pointer will be dereferenced and assigned.

Using this function, we don't need second for loop, nor any other helper container, since we define the variables out of scope.

Yes, we can define the variables before for loop, and still be able to have more foreach loops in one scope without any variable name collisions!

How? Piece of cake, we make the variable names unique, by appending the current source code line number to them!

This can be done automatically by using predefined macro __LINE__ and using some helper macro for concating the variable names with the lines number.

Here's the final macro:

#define _ArgConcat(a, b) a##b
#define ArgConcat(a, b) _ArgConcat(a, b)

#define AppendCurrentLine(x) ArgConcat(x, __LINE__)

Usage example (must be on same line!):
bool AppendCurrentLine(myBool); if(AppendCurrentLine(myBool)) return;

So this way, the variables are unique, and we can have more foreach loops in one scope! Final foreach macro might look like this:

#define ForEach(Variable, Container) ...

ADynamicArray<AInt32u> array;
...
ForEach(x, array) // x is defined as AInt32u&
{
// do something fancy
}

Out of interest, in the AGate engine, there are also more advanced foreach loops, to allow to take control over more features, so there are several foreach macros:

#define ContainerIterateEx(Container, Variable, Iterator, Direction, Seek) ...
#define ContainerIterate(Container, Variable, Iterator) ...
#define ContainerForEach(Container, Variable) ...

That's it. Nothing more to add, maybe I'll only note that I'm not using any foreach loops in C++ at all :) I think that it's feature suitable for scripting languages only, but I did provided foreach loops in AGate engine for those who would like to uses them.

That's all for now. Crypton's out! :)