FOR_EACH and LOCK

FOR_EACH and LOCK

By Eric Niebler and Anson Tsao

C# introduced a couple of new constructs to make some common tasks easier. One is the lock keyword, which makes it trivial to synchronize thread access to an object. Another is the foreach keyword, which makes iterating over collections easy and intuitive.

Since the introduction of foreach and lock, some C++ programmers have clamored for the addition of similar facilities to C++. A purist might say, "There are already more general facilities in the C++ language to enable these programming constructs." But these "general facilities" lack the ease-of-use of their C# counterparts. As we've discovered, C++ can have the equivalent of lock and foreach — all it takes is a dose of templates, a pinch of obscure language features, and a dash of the preprocessor. Although this article focuses primarily on managed collections, the FOR_EACH code is applicable to both native C++ and Managed C++. The final version of FOR_EACH goes far beyond what C#'s foreach keyword can do — it is an extensible iteration solution that seamlessly handles native arrays and even STL containers, in addition to a host of managed collection types.

C#'s lock Keyword

All C++ programmers know how to manage locks for thread synchronization. You use the C++ idiom of "resource acquisition is initialization," acquiring the lock in a constructor, and releasing it in a destructor. This guarantees that every lock is unlocked. Deterministic finalization is what makes it work so well in C++, but what about C#? Without deterministic finalization, C# needs another solution — the lock keyword. You use lock to acquire a lock on an object and hold it for the duration of the following lexical scope (that is, block). It looks like this:

lock( this )


{

    // this is locked here

}


   // this is unlocked here

Some C++ programmers see this and think it's an ugly hack. Others look at it and want it. If you are in the second camp, take heart. There is a simple way to implement C#'s locking semantics in Managed C++. This technique also serves as our first stop on the way to a more elusive goal — the implementation of C#'s foreach keyword.

MC++ LOCK macro

It is a litle-known fact that, in C++, you can declare and initialize a variable in an if statement. According to Bjarne Stroustrup in The Design and Evolution of C++ (Addison-Wesley, 1994), this idea was introduced to support dynamic_cast, and usually looks like this:

if(Foo *f=dynamic_cast<Foo*>(this))

{

    // dynamic_cast succeeded! f!=0

}

The variable f is declared, initialized, and compared to NULL all in the condition of the if statement. What is of interest is that f is "injected" into the scope of the block following the if. You can use this to implement lock (and foreach) in C++. But first you need a helper class.

Locking and unlocking are best done in constructors and destructors. The gclock class (Listing 1) handles this chore. With this class, the LOCK macro is trivial:

#define LOCK(obj) \

    if(gclock _lock_=(object))

First, you take an object and use it to initialize an instance of gclock. The gclock constructor uses Monitor::Enter to acquire the lock for the object. Then, _lock_ is evaluated in Boolean context. The purpose of the operator bool becomes clear — all gclock objects evaluate to True in Boolean context, causing the if block to execute. After the block has finished executing, the gclock object goes out of scope, and the destructor releases the lock. The LOCK macro is used like this:

LOCK( this )

{

    // this is locked here

}
    // this is unlocked here

There is one problem with the LOCK macro as currently written. Consider the following code:

if( some_condition )

   LOCK( this )

      do_something();

else

      do_something_else();

After macro substitution, this becomes:

if( some_condition )

   if( gclock _lock_=(this) )

      do_something();

else

      do_something_else();

The if statement in the LOCK macro got greedy and gobbled up the trailing else clause. You can see that the else clause never executed — probably not your intention. This "greedy if" problem raises its ugly head again in the implementation of FOR_EACH. For now, the problem is easily solved by changing the LOCK macro to:

#define LOCK(obj) \

   if(gclock _lock_=(obj)) {} else

and changing gclock::operator bool() to return False instead of True.

There is one detail in the gclock implementation that we have not discussed — the use of the gcroot<> smart pointer. gcroot<> is a template provided with the .NET Framework that allows references to garbage-collected types to be embedded in unmanaged types (see "Using the C++ Standard Library with Managed Types," by Jonathan Cave, CUJ, November 2002).

C#'s foreach Keyword

Writing loops can be a pain. To make it easier, C++ takes the approach of using generic algorithms like std::for_each. C# went a different route — utilizing the foreach keyword. With foreach, you can easily loop over elements in collections, characters in strings, or items in arrays. What's more, with foreach you can make the code execute right where you need it. For instance:

foreach( Foo f in fooArray ) 

   { /* do something with f */ }

Unlike STL containers, the collections in the .NET Framework are heterogeneous, storing all the elements polymorphically as System::Object*. As an added convenience, the C# foreach loop casts the collection elements to the desired type during enumeration.

C++ FOR_EACH Macro

Unlike C#'s foreach keyword, std::for_each requires you to define your "loop body" in a predicate that must be defined at namespace scope, far from where it will be used. That's inconvenient, but looping over .NET Framework collections in Managed C++ is even worse. C++ programmers must resort to explicitly using enumerators, and the following verbose code often results:

IEnumerator *pEnum = fooArray->GetEnumerator();

while( pEnum->MoveNext() )

{

    Foo *f = __try_cast<Foo*>( 

        pEnum->Current );

    /* do something with f */

}

When faced with the prospect of writing loops like this time and again, it's easy to see why some C++ programmers cast a jealous eye at C#'s foreach keyword. What you would like is some way in C++ to write code like this:

FOR_EACH( Foo *, f, fooArray ) 

    { /* do something with f */ }

Can you apply the tricks you used to implement the LOCK macro to create a FOR_EACH macro?

FOR_EACH, Take 1

There are two obstacles to turning the preceding while loop into a FOR_EACH macro. First, since the enumerator variable pEnum is outside of the while loop, it clashes with any other FOR_EACH loop in the same scope. Second, the loop body needs to act as a real block, so the FOR_EACH macro should not introduce an unmatched opening brace.

The LOCK macro declared a variable in an if statement, injecting it into the following scope. The FOR_EACH macro can use the same trick. In Listing 2 (which is incomplete), you might wonder what belongs in "/* magic happens here */"? Whatever the magic is, it must:

• Move to the next item in the collection.
• Evaluate to False if the sequence is exhausted.

• Evaluate to True otherwise, and assign the current element to the loop variable, casting it as appropriate.

You can accomplish this with the move_next() helper function in Listing 3. move_next() is a template function. Notice how the compiler deduces the type of the loop variable and uses the type in the __try_cast statement. (__try_cast is the managed equivalent of dynamic_cast.)

This leads to the first snag: What if the compiler deduces T to be a value type, such as int? In the .NET Framework, you must first "box" a value (convert it to System::Object*) before you can put it in a collection. To retrieve the value out of the collection, you must "unbox" it. The move_next() function does not account for that. With a bit of template metaprogramming, you can detect at compile time if T is a value type or a GC (garbage collected) type by checking if it is convertible to System::Object*. If it is a GC type, then a simple cast to T is correct. If T is a value type, however, it must be cast to a T __box*, then dereferenced. The auto_unbox<> template in Listing 4 embodies this logic. It is interesting that you can apply many of the advanced C++ template techniques to managed types. We are using our auto_unbox<> template in move_next() to do the appropriate cast from System::Object*.

But even with this new-and-improved move_next(), the FOR_EACH macro still has a problem. If you look at the FOR_EACH implementation in Listing 2, you see that it suffers from the same "greedy if" problem as our first LOCK macro. That is, it is possible for the if to gobble up a trailing else that doesn't rightfully belong to it. Back to the drawing board.

FOR_EACH, Take 2

With the LOCK macro, the "greedy if" problem was easily solved by providing an else and making sure the if condition evaluates to False. FOR_EACH can use the same trick, but it needs the helper function init_enum():

bool init_enum( 

   IEnumerator *& num,

   IEnumerable * coll )

{

   num = coll->GetEnumerator();

   return false;

}

#define FOR_EACH(type,var,coll)\

if( IEnumerator *_num_=0 ) {}\

else if( init_enum(_num_,coll) ) {}\

else for( /* ... */ )

Putting all the pieces together gives you a nice FOR_EACH macro that iterates over any collection that implements the IEnumerable interface. But C#'s foreach keyword lets you loop over arrays and strings as well.

FOR_EACH, Take 3

The FOR_EACH macro works with .NET Framework collections, but it should also work with strings and arrays. Ideally, FOR_EACH should be extensible so that it can iterate over any collection, even an STL container. To solve this problem, the compiler must detect the type of collection being enumerated and select the proper implementation at compile time. This calls for more template metaprogramming.

The first step is to detect the type of the collection. A set of overloaded functions solves this problem nicely:

typedef char (&num_type)[1];

typedef char (&arr_type)[2];

typedef char (&str_type)[3];


num_type select( IEnumerable* );

arr_type select( System::Array* );

str_type select( System::String* );

The compiler selects the overloaded function based on its argument. To find out which overloaded function the compiler selected, we use the "sizeof" trick. When applied to an expression, sizeof evaluates to the size in bytes of that expression. If the expression is a function call, sizeof evaluates to the size of the function's return value. This conveniently lets you map a collection type to an integer at compile time. To provide specialized behavior for each collection type, you write an enumerator<> template that accepts a size_t as a nontype template parameter. This template has specializations for sizeof(num_type), sizeof(arr_type), and sizeof(str_type). Each specialization has:

• enum_type, a nested typedef indicating the type of the enumerator variable. enum_type is: IEnumerator* for num_type; int for arr_type and str_type (for indexing into the array or string).
• init_enum(), a static member function that initializes the enumeration variable and returns False.

• move_next(), a static member function that: Moves to the next element in the sequence; returns False if the sequence is exhausted; or returns True otherwise, and assigns the current element to the loop variable.

• For the full implementation of the enumerator<> template, see the code accompanying this article at http://www.cuj.com/code/. With enumerator<>, you can finally implement a proper FOR_EACH macro; see Listing 5.

• The enumerator<> template is an extensible mechanism for customizing FOR_EACH behavior for different types of collections. As you can see in the final FOR_EACH code, we've used this mechanism to extend FOR_EACH to iterate over STL containers as well as native arrays.

Additional Considerations

Now that you've gone through the details of implementing the C++ FOR_EACH loop, how does it compare with the C# compiler's implementation?

We examined the intermediate language (IL) generated by our FOR_EACH loop with full optimizations enabled. We found that FOR_EACH generates nearly optimal IL that is virtually indistinguishable in performance from the C# compiler-generated version.

Our implementation, however, is still missing one feature from the C# version. For enumerators that implement IDisposable, C# guarantees that Dispose is called after the enumeration is complete. IDisposable is the design pattern that mimics C++ deterministic finalization, guaranteeing that resources are released immediately instead of at the next garbage-collection cycle. The FOR_EACH macro does not call Dispose() on the enumerator. Is this a serious problem? The enumerators for Framework collections do not implement IDisposable, so they are not affected by this deficiency. A few enumerators such as MessageQueueEnumerator do implement IDisposable, so you should be careful when using FOR_EACH with these collections. With more work, it is possible to address even this deficiency in the implementation, but the solution incurs significant overhead that we didn't feel was justified.

The final version of FOR_EACH has a few other optimizations. ArrayList enumeration uses an index instead of the enumerator for performance reasons. Also, evaluating ArrayList's end-of-sequence condition involves a virtual call that is hoisted out of the loop.

Conclusion

In this article, we've described how to match the functionality and ease-of-use of C#'s lock and foreach keywords in C++. The final version of FOR_EACH takes these ideas further by applying them to native C++ types and STL containers, and by providing a mechanism for extending FOR_EACH to work with other types of collections.