VLAs bring a little bit of C++ to C, along with a host of uncertainties.
Copyright © 1998 Robert H. Schmidt
A short column this month. I'm putting together plans to move my home, possibly back to where I grew up (and perilously close to where Dan Saks lives now). The logistics of a house sale and cross-country move are overwhelming my time. Watch for a longer column next time around.
Last Month's Quiz
Last month I surveyed several aspects of variable-length arrays or VLAs, a feature of C9X (the emerging new C language standard). Along the way I left you with this thought problem:
int main() { size_t n = 10; int a[++n]; /* What is n? And what is sizeof(a)? */ return 0; }For insight, you may be tempted to consider the apparently related variation
int main() { size_t n = 10; int *a = new int[++n]; return 0; }Here ++n is evaluated before the (implicit) call to operator new. Once the dust settles, n is 11, and a points to an array of 11 integers. Does this second example imply that, in the original example, both n and sizeof(a) end up as 11?
Before you say "yes," consider a third example (courtesy of the ISO C committee email reflector):
int n = 5; int a[n++]; printf("%d\n", n); for (int i = 0; i < 10; ++i) printf("%d\n", (int) sizeof(a));Should this code increment n 0, 1, 10, or 11 times? The answer depends on how the expression n++ "binds" to the type of a, and whether side effects even take place for sizing expressions such as n++. In particular, does n++ get implicitly evaluated each time sizeof(a) is evaluated?
But wait, it gets better:
size_t n = 5; typedef int Array[n++]; Array a1; Array a2; Array a3;What are the sizes of the three arrays and the ending value of n? The answer really depends on a broader question: does the typedef hold a numerical value (the result of n++ evaluated at the point of the Array typedef) or an expression (the result of n++ each time an Array is defined)?
And finally, consider
(int (*)[n++]) NULLPresumably the size argument n++ need not be evaluated to make this cast work, suggesting it should be ignored. Yet in other well-established C constructs like
i = (n++, 1)n++ is evaluated and n incremented, even though the value of n is not needed to determine the value of i.
What to Do
As you can see, the apparently simple addition of run-time array sizing creates a host of conflicting extrapolations from prior C art. In the end, the committee members settled on this (from section 6.5.5.2 paragraph 3 of the current public C9X draft):
If the size expression is not a constant expression, and it is evaluated at program execution time, it shall evaluate to a value greater than zero. It is unspecified whether side effects are produced when the size expression is evaluated.
So for constructs like
size_t n = 5; int a[n++];the value of n may be either 5 or 6, depending on the whims of your implementation.
I'm not sure if this gives a definite answer for
size_t n = 5; typedef int Array[n++]; Array a1; Array a2; Array a3;If you think of typedefs as quasi-macros that "capture" the expression n++, you could interpret the above as
size_t n = 5; int a1[n++]; int a2[n++]; int a3[n++];If this interpretation is correct, then based on the Standard passage cited above, we'd have several possible values of n and lengths of arrays.
I can't find language in the Standard speaking to this directly. However, the following example (section 6.5.7, paragraph 4, example 6) hints at the answer [1]:
The size expression that is part of the variable length array type named by typedef name B is evaluated each time function copyt is entered. However, the size of the variable length array type does not change if the value of n is subsequently changed.
void copyt(int n) { typedef int B[n]; // B is n ints, // n evaluated now. n += 1; // new block { B a; // a is n ints, // n without += 1. int b[n]; // a and b are different sizes for (i = 1; i < n; i++) a[i-1] = b[i]; } }This example implies that the size expression in a VLA typedef is evaluated exactly once, where the flow of execution encounters the typedef. If I'm reading the tea leaves correctly, this rule applies for typedefs like
typedef int B[n++];as well.
Wools and Linens
In that last paragraph I mentioned the "flow of execution" and its relation to VLA interpretation. In the examples I've shown so far, all that flow has been forward with no jumps. But what about flow that contains jumps, such as the (possibly surprising) example
size_t n = 1; goto label; int a[n]; label:Is a ever created here?
You might be thinking "of course a is never created, since such mixed C code and declarations can never compile." Were this Standard C, you'd be right. But like C++, C9X allows mixing of code and declarations.
Normally this mixing is straightforward — C9X has no constructor calls or other hidden declaration side effects. The complication comes with VLAs, since the meanings of declarations can depend on the flow of code leading to them.
Removing the code/declaration mix by
size_t n = 1; // goto label; int a[n]; label:or
size_t n = 1; goto label; // int a[n]; label:makes the ambiguity go away. However, this approach is not a cure-all. Consider
size_t n = 1; label: int a[n]; // ... if (n++ < 10) goto label;Here we have no mixing of code and declarations, yet an ambiguity remains: by the time this code exits, what is the size of a? And how many times is a created and destroyed?
In all these examples, the real culprit is a jump relative to a VLA declaration. The relevant C9X rules, summarized from section 6.6.6.1 and section 6.1.2.4 paragraph 3:
- If you jump forward or backward into the scope of a VLA, the result is undefined behavior (as in our first example).
- You can jump forward within the scope of a VLA with impunity.
- You can jump backward within the scope of a VLA, but the VLA's storage may not be preserved. In our last example, the storage for a may be created and destroyed with each pass through (up to 10 times).
Segue
I invite you to compare the C9X declaration vs. jump rules to those for C++ constructors and destructors in the face of similar jumps. I think you'll find that VLAs act disturbingly like C++ objects, further supporting last month's allegation that C programmers now get to see how the other half lives.
Next time, I'll compare VLA traits to those of C++ container classes, including our evolving Array class. This should slide me back into the groove of making Array more like Standard Template Library (STL) containers.
Marvin, Wendy, and Wonder Dog
For two months I've been promising evidence of Scott Meyers' terminal boredom. I was so sure I had email from him proving he had too much time on his hands. I lied. I can't find the mail to save my life, and now I'm thinking I dreamt it up.
I plan to drop in on Scott, Nancy, and Persephone "The Best Dog In The World" [2] this summer; maybe then I'll catch some juicy goss (like how he secretly longs for COBOL's return). Until then, you'll have to accept my lame apology.
Threads
But I didn't dream up all my email. Several months ago, Diligent Reader Simeon Simeonov sent this missive (edited for clarity and brevity):
In the February '98 issue of CUJ I read your comments to Bill Palladino regarding his problems with the initialization order of non-local static variables. You suggested that he use a function and thus convert a non-local to a local static variable. This is the standard solution that works in most, but not all cases. In particular, the behavior in multithreaded applications is undefined.
A simple function does solve the problem if (a) the application is not multithreaded, or (b) the function gets called at least once in a single-threaded environment before it is called from a multithreaded environment. (Satisfying this latter case forces developers to think about the order of calls and can lead to subtle bugs if/when the code is changed.)
For all other cases, I suggest the following singleton template:
template<class T> class Singleton { public: static T &get() { static T t; return t; } private: struct Initializer { Initializer() { Singleton<T>::get(); } }; static Initializer dummy_; Singleton() { } // // purposely left // unimplemented Singleton(Singleton const &); Singleton & operator=(Singleton const &); };Thank you for providing both knowledge and laughs in your column!
Regards,
Simeon Simeonov
Manager, Language Technology, AllaireHow It All Works
Singleton has a single private static member, which I've called dummy_ here to reinforce its role as a placeholder. Because dummy_ is a static class member, and because such members have external linkage, dummy_ initializes before main is entered. dummy_'s constructor calls Singleton<T>::get, which in turns forces the initialization of get's private static object t. The net result: t is properly constructed before any thread can reference it.
Simeon knows of two ways this solution could fail:
- The compiler may optimize away the call to get in dummy_'s constructor.
- The linker may not complain if you never define dummy_ in any translation unit.
To get around the first problem, you may have to try different hacks to defeat your compiler's aggressive optimization. Simeon suggests changing dummy_'s constructor to cache away get's address:
Initializer() { T &(*another_dummy)() = Singleton<T>::get; Singleton<T>::get(); }For the second problem, Simeon recommends "waking the linker up" with a similar trick
static T &get() { &dummy_; // new static T t; return t; }Reflections
As I told Simeon in my email reply, I've purposely avoided multithreading in my columns, especially since the C and C++ Standards don't address it. Indeed, from what I can see, the languages were really designed for synchronous single-thread design. About the only concession the Standards make to asynchronous events is the volatile keyword, and even that's more for low-level hardware support. Certainly the notion of static entities collides with threading.
On a more abstracted level, what it means to be a unique object becomes more murky with threads. The normal ideas of object scope, lifetime, visibility, and so on, as enforced in the compile-time domain, don't necessarily work in a multithreaded run-time domain. It's like being a script writer for Star Trek Voyager — one must be comfortable trafficking in parallel universes, able to keep the plot elements self-consistent, and not allowing the same characters from different realities to intermix.
Perhaps with threads we are pushing C++ beyond the boundaries of what it should be. My experience with threading suggests it can't be grafted on as an afterthought, but must be intrinsic to the design from its conception. Languages like Ada and Java, which have innate genetic awareness of concurrency, seem better hosts, at least from a distance.
I'll have have to ponder this more. Meanwhile, feel free to let me know your thoughts about and experiences with C or C++ as a multithreading platform.
Notes
[1] C++ // comments are now availalbe in C9X. From now on, I'll use them in my C9X examples where they make sense.
[2] Lest you think I exaggerate, take a Dramamine, then point your browser to http://www.aristeia.com/Persephone/index.html.
Bobby Schmidt is a freelance writer, teacher, consultant, and programmer. He is also a member of the ANSI/ISO C standards committee, an alumnus of Microsoft, and an original "associate" of (Dan) Saks & Associates. In other career incarnations, Bobby has been a pool hall operator, radio DJ, private investigator, and astronomer. You may summon him at 14518 104th Ave NE, Bothell, WA 98011; by phone at +1-425-488-7696, or via Internet e-mail as rschmidt@netcom.com.