I too was disappointed with the proposed resolution for issue 270.  When
submitting the defect report I proposed language which I hoped amounted to
"do the right thing".  The proposed resolution amounts to "explicitly state
that the behavior is undefined".  The last thing we need is more undefined
behavior pitfalls.

One thing I do not understand is the statement "Enforcing an order of
initialization on static data members of class templates will result in
substantial overhead on access to such variables".  The resolution I had in
mind certainly adds overhead to compilers and/or linkers, but should not
have any run-time overhead.

I'm not a compiler or linker author, but my understanding is that in every
translation unit for which a static data member of a template must be
instantiated, the compiler is going to place the storage for that member in
an area from which the linker can choose one implementation, these used to
be called COMDAT segments.  I was just proposing that the linker be required
to prefer the instantiation from the translation unit which is the first one
of the potential set for which statics will be initialized.

"Brian McNamara!" <gt5163b@prism.gatech.edu> wrote in message
news:9j3epj$3de$1@news-int.gatech.edu...
> Brief summary:
>
> In this post, I
>
>  - argue that the proposed resolution to core language issue 270
>    unintentionally breaks otherwise-well-behaved programs
>
>  - suggest a new resolution which settles the issue without breaking
>    these programs; the new resolution incurs no extra overhead


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Brief summary:

In this post, I

 - argue that the proposed resolution to core language issue 270
   unintentionally breaks otherwise-well-behaved programs

 - suggest a new resolution which settles the issue without breaking
   these programs; the new resolution incurs no extra overhead

I apologize in advance for the length of the post; I lack the time to
make it shorter (and still preserve its readability/understandability).

----------------------------------------------------------------------

I recently became aware of core language issues 269 and 270, regarding
the order of initialization of static data members of class templates.

   http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/cwg_active.html#269
   http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/cwg_active.html#270

There are "real" issues with order-of-initialization across TUs that the
existing standard is ambiguous about.  Specifically, there is a code
example in the body of issue #269 (henceforth, I shall call this example
"Ex269") that illustrates the issue.  The proposed resolution (at the
end of issue #270) states

> Replace the following sentence in 3.6.2  basic.start.init paragraph 1:
>
>   Objects with static storage duration defined in namespace scope in
>   the same translation unit and dynamically initialized shall be
>   initialized in the order in which their definition appears in the
>   translation unit.
>
> with
>
>   Dynamic initialization is either ordered or unordered. Explicit
>   specializions of class template static data members have ordered
>   initialization. Other class template static data member instances
>   have unordered initialization. Other objects defined in namespace
>   scope have ordered initialization. Objects defined within a single
>   translation unit and with ordered initialization shall be
>   initialized in the order of their definitions in the translation
>   unit. The order of initialization is unspecified for objects with
>   unordered initialization and for objects defined in different
>   translation units.

The goal appears to have been to be explicit about the behavior of code
like the example "Ex269".


However, I believe that the current resolution "throws out the baby with
the bathwater".  That is, it resolves the issue with "Ex269" at the
expense of also making otherwise well-behaved code become
not-well-behaved.  For example, this program

   #include <iostream>

   struct Foo {
      int x;
      Foo() : x(3) {}
   };

   template <class T>
   struct Bummer { static Foo foo; };

   template <class T> Foo Bummer<T>::foo;

   struct Qux {
      Qux() { std::cout << Bummer<int>::foo.x << std::endl; }
   } qux;

   int main() {
   }

would print "3" under the existing standard, but with the proposed
resolution to issue #270, it might not, as "Bummer<int>::foo" has become
an object with "unordered" initialization, and thus might be
initialized after "qux" is.  I do not believe that effects like this
were the intent of the proposed resolution.


The example above is contrived to illustrate the basic issue.  A more
realistic example (that actually occurs in some code I have used in the
real world) is sketched next.

I have a class for representing linked lists which looks something like

   template <class T>
   class List {
      ...  static List<T>* sentinel; ...
   };

   template <class T>
   List<T>* List<T>::sentinel( new List<T> ); // static member definition

The sentinel list node is used to represent "nil" (the null pointer
cannot be used with my implementation, for reasons which are immaterial
to this discussion).  All of the List's non-static member functions and
constructors depend upon the value of the sentinel.  Under the proposed
resolution for issue #270, Lists cannot be safely instantiated before
main() begins, as the sentinel's initialization is "unordered".

(Some readers may propose that I should use the "singleton pattern" in the
List class.  This is undesirable, for reasons I shall describe at the
end of this post at the location marked "[*]".  For the moment, indulge
me by assuming that "singleton" is not an adequate solution.)

Though this is a particular example from my own experience, I believe it
is representative of a general class of examples.  It is common to use
static data members of a class to represent the "distinguished values"
which are important to instances of that class.  It is imperative that
these values be initialized before any instances of the class are
created, as the instances depend on the values.

These examples motivate the need for an ordering of initializations for
static data members of class templates.  Nevertheless, we still have
"Ex269" to contend with.  Therefore, I propose a new resolution which
 - gives an ordering that enables classes like "List" to work
 - still resolves "Ex269" by saying the behavior is explicitly ambiguous
 - does not incur extra overhead
I sketch this new resolution next.


The essence of the issue is this.  The reason we have a core language
defect in the first place is because of the ordering of initialization
that occurs _across translation units_.  The problem with the proposed
resolution is that it makes ordering explicitly ambiguous, even _within
a single translation unit_.  The new resolution preserves some of the
ordering within a TU, even though initialization across TUs is still
unordered.

Unfortunately, I have not yet found a "declarative" specification of the
new resolution.  As a result, I must resort to an "operational"
specification.  It will be helpful to consider an example:

----------------------------------------------------------------------
normal.h
   struct Normal { Normal(int) {} };
----------------------------------------------------------------------
prob.h
   template <class T>
   struct Prob { static int X; };

   template <class T>
   int Prob<T>::X( 3 );  // static data initialization

   template <class T>              // Note: calling g() forces template
   int g() { return Prob<T>::X; }  // instantiation of Prob<T>
----------------------------------------------------------------------
tu1.cc
   #include "normal.h"
   Normal A(3);
   #include "prob.h"
   Normal B(3);
----------------------------------------------------------------------
tu2.cc
   #include "normal.h"
   Normal C(3);
   #include "prob.h"
   Normal D( g<int>() );   // Note call to g()
----------------------------------------------------------------------
tu3.cc
   #include "normal.h"
   Normal E(3);
   #include "prob.h"
   Normal F( g<int>() );   // Note call to g()
   int main() {}     // where main() goes is irrelevant to this example
----------------------------------------------------------------------

The existing standard suggests that these ordering dependencies must
hold among the 7 global objects (A,B,C,D,E,F,X):

   R(A,B), R(C,X), R(X,D), R(E,X), R(X,F)

where R(y,z) denotes the relation "y must be initialized before z".
The "problem" with the existing standard is easily seen by drawing the
dependencies out in a diagram:

   A ---> B

   C ---__          __---> D
          -->     --
               X
          /->     -\
   E ----/          \----> F

X creates an inter-TU initialization dependency (henceforth abbreviated
as "ITUID").  ITUIDs are undesirable (they are hard to implement
efficiently).  The proposed resolution to issue #270 gets rid of the
ITUIDs by saying that objects like X (static data members of class
templates) cannot have _any_ dependencies.  In other words, the
initialization relation becomes

   R(A,B), R(C,D), R(E,F)

and the diagram becomes

   A ---> B
   C ---> D
   E ---> F
   X  // no relationships with the others

This resolution fixes the ITUID problem at the expense of breaking
examples like "List".


There is a practical "middle ground".  Indeed, I suspect this middle
ground describes how compilers today actually work.  It is this.
Dependencies are defined to only exist _within_ TUs; a C++ program
cannot express ITUIDs.  The whole-program initialization is the
catenation of the initializations of the individual TUs (in any order)
with the rule that any attempt to initialize an object for the second
(or third, or fourth...) time is ignored (initialization is
idempotent).  To illustrate with the program above, the dependency
relationship is described as

   tu1:   A ---> B
   tu2:   C ---> X ---> D
   tu3:   E ---> X ---> F

and then any one of these six initialization orders is legal for the
whole program (whitespace used merely to enhance readability):

   AB CXD EXF    ( == AB CXD EF )   // Equalities are due to the
   AB EXF CXD    ( == AB EXF CD )   // idempotency of initialization
   CXD AB EXF    ( == CXD AB EF )
   CXD EXF AB    ( == CXD EF AB )
   EXF AB CXD    ( == EXF AB CD )
   EXF CXD AB    ( == EXF CD AB )

Note that every single one of these six initialization orders breaks an
intra-TU dependency (either the C--->X or the E--->X one).  However,
the rule chooses carefully to only break dependencies that still enable
us to have the behavior I desire.  If we work on the practical
assumption that the only reason that certain entities (namely: static
data members of templates) are defined in multiple TUs is because we
are allowed to #include header files that contain template definitions
in multiple TUs, then we realize that the only dependencies that are
broken by this scheme are those dependencies where a template static
data member depends on some other object _which was not initialized in
the same header file_.  In practice, no one would ever do this "on
purpose".  If you do, you end up with a well-deserved undefined
ordering.  For instance, under my newly proposed scheme, the behavior
of "Ex269" is still undefined.  However examples like "qux" and "List"
now have well-defined behavior.


To summarize:

 - The current language standard apparently allows for the creation of
   ITUIDs, which is undesirable.

 - The proposed resolution to core language issue #270 removes the
   ITUIDs, at the expense of making even some single-translation-unit
   programs needlessly have undefined behavior.

 - The new proposal (described in this post) shows a better way to
   resolve the issue.  Rather than simply break all ITUIDs by saying
   that template static data members cannot have any dependencies, it
   describes a mechanism which selectively breaks dependencies so as to
   solve the ITUID issue, while still retaining those dependencies which
   well-intentioned programs require in order to function.

If you have read this far, thank you.  Please let me know if you see any
problems with my idea.  If not, let me know if I need to turn this into
an official defect report in order to ensure that the matter is taken up
(again) by the committee.

----------------------------------------------------------------------

[*] Why "singleton" is undesirable for "List"

If you read the notes on core language issue 270, you see

> Enforcing an order of initialization on static data members of class
> templates will result in substantial overhead on access to such
> variables.

Presumably the overhead to which they refer is the same kind of overhead
that you get when you use the singleton pattern thusly:

   class A;

   A& getA() {
       static A rep = /* some initialisation quantity */;
       return rep;
   }

The implementation of this language construct (local statics) is
typically something approximately like

   bool not_first_time;   // zero-initialized
   A rep;
   A& getA() {
       if( !not_first_time ) {
          rep = /* some initialisation quantity */;
          not_first_time = 1;
       }
       return rep;
   }

In my example "List" class, the reason I chose a static data member
instead of a singleton was precisely because I wanted to avoid this
overhead.  I use List in applications that need to access the sentinel
value tens of millions of times per second.  The overhead of using the
singleton pattern in my applications is great (I have actually measured,
and using singleton makes my programs 50% slower).

Note that, under an interpretation of the existing standard, my List
class is fine (and indeed it does work on my implementation).  Proposed
resolution to issue #270 makes my solution no longer work.  I could make
it work again, but at the cost of using a singleton.  This cost is
mentioned as the motivation for proposed resolution #270!  Apparently
the committee intended to avoid this cost for template static data
members, but they merely "shifted the lump in the carpet".  They came up
with a resolution which fixes the ambiguity with respect to ITUIDs, at
the cost of making my existing program "undefined", forcing me to use a
singleton, which puts me right back in square one (I am forced to cope
with "substantial overhead on access" to my variables).

--
 Brian M. McNamara   lorgon@acm.org  :  I am a parsing fool!
   ** Reduce - Reuse - Recycle **    :  (Where's my medication? ;) )

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]