Monday, December 11, 2006

Intrinsic Linked Lists for Static Construction

This is another excuse to make sure the blogger move to beta hasn't killed all m blogs. In the past I ranted about not being able to move to blogger beta (this blog moved, the others did not). Now I am happily united entirely on the beta blogger...web bliss is mine. (It would be nice if
the old posts listed the correct authors, but that's what we get for flirting with WordPress.)

A while ago I wrote a lot trying to explain how the hell global static construction works in C++.
The best simple summary I can give you is:
  • It doesn't do what you think.
  • Your code will explode in ways you didn't expect.
I also tried to explain the joys of intrinsic linked lists, that is structs that contain a next pointer. (Don't pass these up for the STL - sometimes the old-school technique works better, especially when the issue isn't O(n) but how good your implementation is. Are you sure your app isn't bottlenecked by memory allocation?)

Like peanut and chocolate, these two ideas go well together. That is...static construction problems can be fixed by using intrinsic linked lists. This code is guaranteed to make your life hell:

class foo {
static set all_of_me;
foo() { all_of_me.insert(this); }
~foo() { all_of_me.erase(this); }
// more tuff

The idea is that the foo class self-tracks all its members...this is all good until you do this in some other CPP file besides the CPP where all_of_me is defined.

static foo this_static_var_will_kill_me;

First the solution, then why it works. The solution is simply this:
class foo {
static foo * first_of_me;
foo * next;
foo() { this->next = first_of_me; first_of_me = this; }
// more stuff

Now foo uses an intrinsic linked list instead of an STL set and we can declare static global foo objects all the time!

  • The problem with static construction is that C++ doesn't guarantee that static global objects will be initialized in any particular order.
  • When a class has a static member variable that is in turn a complex class, that static member variable is effectively a static global object, and thus it will be constructed in no particular order.*
  • In the case of our "foo" example, if the particular foo object is constructed before the set "all_of_me" is constructed, then foo's constructor will try to stick "this" into a set whose contents are probably entirely zero.
  • If that doesn't crash then when the set is constructed (after the foo object) the set will be fully reinitialized, causing our object to be lost.
(For this reason we hope for the crash - unfortunately some STL containers like vector will often fail quietly when they are used before initialization, as long as they're zero'd out first.)

The beauty of intrinsic lists is: C++ guarantees it will do all of the static initialization (that is, zero-setting, etc.) before any functions or methods are called. So we can be sure our list head pointer is NULL, and that's all we need to get started.

One final note - as I define catagories for this post I see Chris has catagories for both "rants" and "IIS". I can't imagine that you'd ever want IIS without the rant tag.

* Okay, so there are some rules on construction order. Trust me, they won't help you do anything productive!

No comments:

Post a Comment