Windreamer Is Not a DREAMER


发件人: Andrei Alexandrescu (See Website For Email)  
日期: 2006年3月18日(星期六) 下午12时13分
电子邮件: "Andrei Alexandrescu (See Website For Email)" <>
论坛: comp.lang.c++.moderated

The recent thread "Can GC be beneficial" was quite beneficial :o) - to
me at least. I've reached a number of conclusions that allow me to
better place the conciliation between garbage collection and
deterministic finalization in the language design space - in C++ and in

The following discussion focuses on C++-centric considerations, with
occasional escapes into "the right thing to do if we could break away
with the past.

Basic Tenets, Constraints, and Desiderata

Garbage collection is desirable because:

(1) It automates a routine and error-prone task

(2) Reduces client code

(3) Improves type safety

(3) Can improve performance, particularly in multithreaded environments

On the other hand, C++ idioms based on constructors and destructors,
including, but not limited to, scoped resource management, have shown to
be highly useful. The large applicability of such idioms might actually
be the single most important reason for which C++ programmers shy away
from migrating to a garbage-collected C++ environment.

It follows that a set of principled methods that reconcile C++-style
programming based on object lifetime, with garbage collection, would be
highly desirable for fully exploiting garbage collection's advantages
within C++. This article discusses the challenges and to suggests
possible designs to address the challenges.

The constraints include compatibility with existing C++ code and styles
of coding, a preference for type safety at least when it doesn't
adversely incur a performance hit, and the functioning of today's
garbage collection algorithms.

A Causal Design

Claim #1: The lifetime management of objects of a class is a decision of
the class implementer, not of the class user.

In support of this claim we come with the following examples:

a) A class such as complex<double> is oblivious to destruction
timeliness because it does not allocate scarce resource that need timely

b) A class such as string doesn't need to worry about destruction
timeliness within a GC (Garbage Collected) environment;

c) A class such as temporary_file does need to worry about destruction
timeliness because it allocates scarce resources that transcend both the
lifetime of the object (a file handle) and the lifetime of the program
(the file on disk that presumably temporary_file needs to delete after

In all of these examples, the context in which the objects are used is
largely irrelevant (barring ill-designed types that employ logical
coupling to do entirely different actions depending on their state).
There is, therefore, a strong argument that the implementer of a class
decides entirely what the destruction regime of the class shall be. This
claim will guide design considerations below.

We'll therefore assume a C++ extension that allows a class definition to
include its destruction regime:


//  garbage collected  
class [collected] Widget {...}
// deterministically destroyed  
class [deterministic] Midget {...}


These two possible choices could be naturally complemented by the other
allowed storage classes of a class:


//  garbage collected or on stack  
class [collected, auto] Widget {...}
// deterministically destroyed, stack, or static storage  
class [deterministic, auto, static] Midget {...}

It is illegal, however, that a class specifies both collected and
deterministic regime:


//  illegal  
class [collected, deterministic] Wrong {...}


Claim #2: Collected types cannot define a destruction-time action.

This proposal makes this claim in wake of negative experience with
Java's finalizers.

Claim #3: Collected types can transitively only embed fields of
collected types (or pointers thereof of any depth), and can only derive
from such types.

If a collected type would have a field of a non-collected type, that
type could not be destroyed (as per Claim #2).

If a collected type would have a field of pointer to a non-collected
type, one of two things happens:

a) A dangling pointer access might occur;

b) The resource is kept alive indeterminately and as such cannot be
destroyed (as per claim #2).

If a collected type would have a field of pointer to pointer to (notice
the double indirection) deterministic type, inevitably that pointer's
destination would have to be somehow accessible to the garbage-collected
object. This implies that at the some place in the points-to chain, a
"jump" must exist from the collected realm to the uncollected realm (be
it automatic, static, or deterministic) that would trigger either
post-destruction access, or would prevent the destructor to be called.

Design fork #1: Weak pointers could be supported. A collected type could
hold fields of type weak pointer to non-collected types. The weak
pointers are tracked and are zeroed automatically during destruction of
the resource that they point to. Further dereference attempts accesses
from the collected realm become hard errors.

Claim #4: Deterministic types must track all pointers to their
respective objects (via a precise mechanism such as reference counting
or reference linking).

If deterministic types did allow untracked pointer copying, then
post-destruction access via dangling pointers might occur. The recent
discussion in the thread "Can GC be beneficial" has shown that it is
undesirable to define post-destruction access, and it's best to leave it
as a hard run-time error.

Design branch #2: For type safety reasons, disallow type-erasing
conversions from/to pointers to deterministic types:


   class [deterministic] Widget {...}
* p = new Widget; 
   void * p1 = p; // error  
= static_cast<Widget *>(p1); // error, too 

Or: For compatibility reasons, allow type-erasing conversion and incur
the risk of dangling pointer access.

Design branch #3: For purpose of having a type that stands in as a
pointer to any deterministic type (a sort of "deterministic void*"), all
deterministic classes could be thought as (or required to) inherit a
class std::deterministic.

Design branch #3.1: std::deterministic may or may not define virtuals,
and as such confines or not all deterministic classes to have virtuals
(and be suitable for dynamic_cast among other things).

Claim #5: When an object of deterministic type is constructed in
automatic or static storage, its destructor will automatically issue a
hard error if there are any outstanding pointers to it (e.g., the
reference count is greater than one).

If that didn't happen, dangling accesses to expired stack variables
might occur:


 class [deterministic] Widget {...}
* p; 
int Fun() 
    Widget w; 
= &w; 
// hard runtime error upon exiting this scope 



Discussion of the basic design

The desiderata set up and the constraints of the current C++ language
created a causal chain that narrowly guided the possible design of an
integrated garbage collection + deterministic destruction in C++:

* The class author decides whether the class is deterministic or garbage

* As a natural extension, the class author can decide whether objects of
that type are allowed to sit on the stack or in static storage. (The
regime of automatic and static storage will be discussed below.)

* Depending on whether a type is deterministic versus collected, the
compiler generates different code for copying pointers to the object.
Basically the compiler automates usage of smart pointers, a
widely-followed semiautomatic discipline in C++.

* The heap is conceptually segregated into two realms. You can hold
unrestricted pointers to objects in the garbage-collected realm, but the
garbage-collected realm cannot hold pointers outside of itself.

* The operations allowed on pointers to deterministic objects are

Regime of Automatic Storage

Claim 6: Pointers to either deterministic or collected objects that are
actually stack allocated should not escape the scope in which their
pointee object exists.

This obvious claim prompts a search in look for an efficient solution to
a class of problems. Here is an example:


 class [auto, collected] Widget {...}
void Midgetize(Widget & obj) 


void Foo() 
    Widget giantWidget; 



To make the example above work, Foo is forced to heap-allocate the
Widget object even though the Midgetize function works on it
transitorily and stack allocation would suffice.

To address this problem a pointer/reference modifier, "auto", can be
defined. Its semantics allow only "downward copying": an
pointer/reference to auto can only be copied to lesser scope, never to
object of larger scope. Examples:


void foo() 
    Widget w; 
*auto p1 = &w1; // fine, p1 has lesser scope 
*auto p2 = &w; // fine 
      p2 = p1; // fine 
      p1 = p2; // error! Escaping assignment! 



Then the example above can be made modularly typesafe and efficient like


 class [auto, collected] Widget {...}
void Midgetize(Widget &auto obj) 


void Foo() 
    Widget giantWidget; 
// fine 



Claim #6: "auto"-modified pointers cannot be initialized or assigned
from heap-allocated deterministic objects.

If "auto"-modified pointers manipulated the reference count, their
efficiency advantage would be lost. If they didn't, a type-unsafe
situation can easily occur.

Does operator delete still exist?

For collected objects, delete is inoperant, as is for static or
automatic objects. On a heap-allocated deterministic object, delete can
simply check if the reference count is 1, and if so, reassign zero to
the pointer. If the reference count is greater than one, issue a hard  

Note that this makes delete entirely secure. There is no way to have a
working program that issues a dangling access after delete has been  

Regime of Static Storage

Static storage has the peculiarity that it can easily engender
post-destruction access. This is because the order of module
initialization is not defined, and therefore cross-module dependencies
among objects of static duration are problematic.

This article delays discussion of the regime of static storage.
Hopefully with help from the community, a workable solution to the
cross-module initialization would ensue.


Claim #7: The collection regime of any type must be accessible during
compilation to templated code.

Here's a simple question: is vector<T> deterministic or collected?

If it were collected, it couldn't hold deterministic types (because at
the end of the day vector<T> must embed a T*). If it were deterministic,
collected types couldn't hold vectors of pointers to collected types,
which would be a major and gratuitous restriction.

So the right answer is: vector<T> has the same regime as T.


template <class T, class A> 
class [T::collection_regime] vector // or some other syntax 



The New World: How Does it Look Like?

After this design almost happening as a natural consequence of an
initial set of constraints, the natural question arises: how would
programs look like in a C++ with these amenities?

Below are some considerations:

* Pointer arithmetic, unions, and casts must be reconsidered (a source
of unsafety not thoroughly discussed)

* Most types would be [collected]. Only a minority of types, those that
manage non-memory resources, would live in the deterministic realm.

* Efficiency of the system will not degrade compared to today's C++. The
reduced need for reference-counted resources would allow free and fast
pointer copying for many objects; the minority that need care in
lifetime management will stay tracked by the compiler, the way they
likely were manipulated (by hand) anyway.

* Given that the compiler can apply advanced analysis to eliminate
reference count manipulation in many cases, it is likely that the
quality of built-in reference counting would be superior to
manually-implemented reference counting, and on a par with advanced
manual careful manipulation of a mix of raw and smart pointers.


Whew! Please send any comments you have to this group. Thanks!


      [ See for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

posted @ 2006-03-21 10:01 Windreamer Is Not DREAMER 阅读(564) | 评论 (1)编辑 收藏


Is it a mistake in TAOCP  
Maggie McLoughlin <> to Windreamer

Sequences with n=0 are empty. It's important in mathematics
to deal with empty sets and strings etc in a meaningful way.
If n = 0 and you're supposed to do something for 1 <= j <= n,
you don't have to do anything.

Thanks for your interest in my book! -- Don Knuth

posted @ 2005-12-16 10:05 Windreamer Is Not DREAMER 阅读(535) | 评论 (1)编辑 收藏




        《The Art of Computer Programming》的第一卷,大理石花纹的封皮,拿在手里沉甸甸的,这部书给我的第一印象就是这样--"厚重"--带有着神秘感和历史感。


        从Algorithm到Euclid's Algorithm也就是我们熟悉的辗转相除求最大公约数法,我这个算法小白开始进入了他打开的算法世界......











j Theta_j Phi_j a_j b_j
0 a a 5 1
1 ab c 3 2
2 bc cb 1 2
3 b a 4 3
4 c b 0 4
5 c c 5 5


 1#include    <iostream>
 2#include    <string>
 4using namespace std;
 5int main ( int argc, char *argv[] )
 7    //                   0,     1,     2,     3,     4,     5
 8    string theta[]={   "a",  "ab",  "cb",      "b",   "c",   "c"};
 9    string phi  []={   "a",   "c",  "bc",    "a",   "b",   "c"};
10    int    a    []={     5,     3,     1,     4,     0,     5};
11    int    b    []={     1,     2,     2,     3,     4,     5};
13    int j=0;
14    int i=0;
15    string stat;
16    getline (cin,stat);
17    while(true)
18    {
19        unsigned int loc=stat.find(theta[j],0);
20        if (loc==string::npos)
21        {
22            j=a[j];
23        }

24        else
25        {
26            string temp=stat.substr(0,loc)+phi[j]+stat.substr(loc+theta[j].length());
27            stat=temp;
28            j=b[j];
29        }

30        cout<<i++<<":\tj("<<j<<")\tloc("<<loc<<")\t"<<stat<<endl;
31        cin.get();
32    }

33    return EXIT_SUCCESS;
                /* ----------  end of function main  ---------- */







First Step——Euclid GCD的一个实现

 2#ifndef _GAlgo_Euclid_GCD_H_
 3#define _GAlgo_Euclid_GCD_H_
 4namespace GAlgo
 6    namespace Generic
 7    {
 8        template <typename T>
 9        T Euclid_GCD(const T& a,const T& b)
10        {
11            return ((a%b)==0)?b:Euclid_GCD(b,a%b);
12        }

13    }

14    namespace Meta
15    {
16        template <int A,int B>
17        struct Euclid_GCD
18        {
19            static const int value=Euclid_GCD<B,A%B>::value;
20        }
22        template <int A>
23        struct Euclid_GCD<A,0>
24        {
25            static const int value=A;
26        }
27    }




 1#include "GAlgo_Euclid_GCD.hpp" 
 2#include <iostream>
 3using namespace std;
 4int main()
 6    cout<<GAlgo::Generic::Euclid_GCD(6,9)<<endl;
 7    cout<<GAlgo::Meta::Euclid_GCD<6,9>::value<<endl;
 8    return 0;



posted @ 2005-12-12 21:48 Windreamer Is Not DREAMER 阅读(1392) | 评论 (4)编辑 收藏


终于无聊到来写书评,最近的项目一直都没和C++有什么关系,不过看的书却都是C++方面的,而最近看到的几本书中感觉最好的莫过于这本《C++ Templates》

Nicolai M. Josuttis的书我很喜欢,从他的那本《The C++ Standard Template Library》就看出了他很多独特的风格,令我爱不释手,所以这本《C++ Template》   也进入了我的必看书单。粗读之后,感觉整本书绝对将成为C++泛型领域的圣经级著作

  1. 这本书角度选得很好,全书分三个部分,分别介绍模板基础、模版的编译器实现、模板的高级技巧,三个部分相辅相成、相互照应,由浅入深而又自然而然,还方便分开阅读(比如我就重点看了第一第三部分,模版实现被我略过了)却又全面覆盖了这一领域
  2. 这本书英文很浅显(比《Modern C++ Design》浅显了不知多少倍),语言严谨而又不晦涩,尤其要赞的就是废话尤其地少!
  3. 章节安排很合理,很方别作为工具书应急查阅(《C++STL》就有这个优点,与这本书科学家+工程师的组合不无关系)
  4. 书中好多技术,我是闻所未闻,惊为天人,尤其第三部分,可以算得上眼花缭乱,而且给出的实现感觉既符合标准、实用、而且没有炫技的成分



  1. (P12) [Argument Deducion] If we pass two ints to the parameter type T const&  the C++ compiler must conclude that T must be int. Note that no automatic type conversion is allowed here,Each T must match exactly.

    template <typename T>
    inline T 
    const& max (T const& a,T const& b);

    4,7)//OK:T is int for both arguments
    max(4,4.2)//ERROR:first T is int,second T is double

  2. (P13)[Template Parameters] In function templates(unlike class template) no default template arguments can be specified
  3. (P14)[Template Parameters]Deducation can be seen as part of  overlaod resolution-a process tha is not based on selection of return type either.The sole exception is the return type of conversion operator members.
  4. (P18)[Overloading Function Template] The fact that not all overloaded functions are visible when a corresponding function call is made may or may not matter.
  5. (P39)[Nontype Function Template Parameters] Function templates are considered to name a set of overloaded function.However,according to the current standard,sets of overload functions cannot be used for template parameter deducation.Thus you have to cast to the exactly type of the function template arguments

    template <typename T,int VAL>
    T addValue (T 
    const& x)
    return x+VAL

    //start and end of source
    dest.begin(),//start of destination
    (int(*)(int  const&))addValue<int,5>);//operation

  6. (P40)[Restrictions for Nontype Template Parameters] 太长了,略过
  7. (P44)[The .template Construct]

    template <int N>
    void printBitset (std::bitset<N> const& bs)
    <<bs.to_string<char,char_traits<char>,allacator<char> >();//ERROR:can't recogonize the template

    <int N>
    void printBitset (std::bitset<N> const& bs)
    <<bs.template to_string<char,char_traits<char>,allacator<char> >();//OK

  8. (P45)[Using this->]

    template <typename T>
    class Base
    void bar();

    <typename T>
    class Derived : Base<T>
    void foo()
    //call external bar() or error


    <typename T>
    class Derived : Base<T>
    void foo()


  9. 同样精彩的还有(P57)[Using String Literals as Arguments for Function Templates]
  10. 令我惊异的SFINE技术(substitution-failure-is-not-an-error)

    template <typename T>
    class IsClassT
    char One;
    struct {char a[2];} Two;
    <typename C> static One test (int::C*);
    <typename C> static Two test();
    enum {Yes=sizeof(IsClassT<T>::test<T>(0))==1};
    enum {No=!Yes};

posted @ 2005-12-10 12:36 Windreamer Is Not DREAMER 阅读(558) | 评论 (3)编辑 收藏





<int Val>
struct IntType
const static int value = Val ;
<bool flag, typename T, typename U>
struct Select
 typedef T Result;

<typename T, typename U>
struct Select<false, T, U>
 typedef U Result;
<unsigned int N,unsigned int x>
struct FindRoot
const static int value=Select<(N/x)==x||((N/x+x)/2==x),IntType<x>,FindRoot<N,(N/x+x)/2> >::Result::value;

<unsigned int N>
struct Sqrt
const static int value=FindRoot<N,N/2>::value;

struct Sqrt<0> ;

<int N,int divider>
struct TestPrime
const static int value=Select<(N%divider)==0,IntType<0>,TestPrime<N,divider-1> >::Result::value;

<int N>
struct TestPrime<N,1>
const static int value=1;

<unsigned int N>
struct IsPrime
const static int value=TestPrime<N,Sqrt<N>::value+1>::value;

struct IsPrime<2>
const static int value=1;

struct IsPrime<1>;

int printf(const char*,);

int main()
const int yes=IsPrime<123127>::value;

posted @ 2005-12-05 09:45 Windreamer Is Not DREAMER 阅读(342) | 评论 (1)编辑 收藏