www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - While we're on the subject of escape analysis...

reply Benji Smith <dlanguage benjismith.net> writes:
Consider this code:

    class MyObject {

       public int x() {
          return obj.a().b().c().d();
       }

       public MyObject a() { ... }
       public MyObject b() { ... }
       public MyObject c() { ... }
       public int d() { ... }

    }

This code creates three temporary objects that cannot possibly escape 
the scope of the "x" function. Although the user might be content with 
those object being allocated on the heap, the compiler could decide to 
allocate them on the stack instead, and the programmer would be 
blissfully unaware of the switcharoo.

Of course, this kind of optimization would require an interprocedural 
graph-coloring algorithm to determine whether to use the heap allocator 
or the stack allocator for every allocation. And I don't know whether 
the current optimizer does any interprocedural analysis at all. (Though 
it does inline short methods, which seems roughly equivalent, so I dunno.)

Thoughts?

--benji
Oct 30 2008
next sibling parent reply Hxal <hxal freenode.irc> writes:
Benji Smith Wrote:

 Of course, this kind of optimization would require an interprocedural 
 graph-coloring algorithm to determine whether to use the heap allocator 
 or the stack allocator for every allocation. And I don't know whether 
 the current optimizer does any interprocedural analysis at all. (Though 
 it does inline short methods, which seems roughly equivalent, so I dunno.)
 
 Thoughts?
 
 --benji


This scenario could be optimized by the compiler by the use of a secondary
stack, together with Michel Fortin's ownership type proposal.

By secondary stack I mean a per-thread chunk of memory that works
exactly like the normal stack, but isn't cluttered by function calls.

A function whose return type is a scope reference type could take a hidden
argument that implements an allocator interface. If the call site
determines that the result never leaves its scope, it can pass the
secondary stack allocator, otherwise the regular GC allocator.
The new call which produces the returned object would then call the
hidden argument to allocate memory.

Note that this only works for a single level of nesting.
(Can't return the object up the stack through more steps, that'd require
every scope to allocate its own secondary stack, which requires a heap
allocation and defeats the purpose.)

Example:

class Foo
{
    scope Foo next;

    this (Foo n = null)
    {
        next = n;
    }

    scope Foo prolifoorate ()
    {
        return new Foo (this)
    }
    
    static Foo aGlobal;
}

void main ()
{
    scope Foo foo = new Foo;
    
    foo.prolifoorate().prolifoorate().prolifoorate();
    
    aGlobal = (new Foo).prolifoorate();
}

Would work more less like:

class Foo
{
    scope Foo next;

    this (Foo n)
    {
        next = n;
    }

    scope Foo prolifoorate (void* function (size_t) allocator)
    {
        Foo f = cast(Foo) allocator (sizeof (Foo));
        f.constructor (this);
        return f;
    }

    static Foo aGlobal;
}

void* SS;

void* secondary_stack_allocator (size_t size)
{
    void* x = SS;
    SS = &SS[size];
    return x;
}

void main ()
{
    void* SSmark = SS;
    scope(exit) SS = SSmark;

    // stack allocation
    Foo foo = cast(Foo) alloca (sizeof (Foo));
    foo.constructor ();

    // secondary stack allocations
    foo.prolifoorate(&secondary_stack_allocator)
        .prolifoorate(&secondary_stack_allocator)
        .prolifoorate(&secondary_stack_allocator);

    // heap allocation
    aGlobal = (new Foo).prolifoorate(&GC_allocator);
}

I didn't take multithreading into account because that's not the point of the
example.
It'd be nice if a register could be found to store the pointer, since
pthread_getspecific
might be a tad slow.

I hope D doesn't already have a secondary stack and I'm not looking silly
writing all
this stuff...
Oct 30 2008
next sibling parent Hxal <hxal freenode.irc> writes:
Hxal Wrote:

 A function whose return type is a scope reference type could take a hidden
 argument that implements an allocator interface. If the call site
 determines that the result never leaves its scope, it can pass the
 secondary stack allocator, otherwise the regular GC allocator.
 The new call which produces the returned object would then call the
 hidden argument to allocate memory.


I should have also noted that the secondary stack works better than
the regular stack, because it can accomodate dynamic type sizes.

Example:

scope Foo bar ()
{
    return new FooSubclass;
}


     this (Foo n)
     {
         next = n;
     }


The constructor should have been:

this (scope Foo n = null)
{
    next = n;
}

On a side note though, the scope notation is not perfect,
because it cannot accomodate nested references.
Eg. int** or int*[]
I'd use a postfix type modifier, eg. int* *, int* * , int[] ,
but it's not very pleasing to the eye.
Oct 30 2008
prev sibling parent Hxal <hxal freenode.irc> writes:
Hxal Wrote:

 Note that this only works for a single level of nesting.
 (Can't return the object up the stack through more steps, that'd require
 every scope to allocate its own secondary stack, which requires a heap
 allocation and defeats the purpose.)


Sorry for the multiple posts, that's what I get for posting at 4am.
The above is not true. Since all that ever ends up on the secondary stack
are return values, a function can simply pass the ownership to its
caller, by not cleaning it up its part of the secondary stack.

There's also one gotcha, the programmer needs to take care not to
leak memory. The leak disappers when the outer scope is left, and the
compiler can take steps to reduce it, but there's always the possibility
to create it.

Example:

scope Foo[] bar ()
{
    scope(caller) Foo foo1 = new Foo;
    scope(caller) Foo foo2 = new Foo;
    if (blah) foo1 = null;
    return [foo1, foo2];
}

In this case foo1 eats up secondary stack space, even when it's
not actually used. Its memory cannot be reclaimed until bar's caller
returns. But once that happens everything is OK again.

Please don't attack the syntax, since it's only illustratory.
Oct 30 2008
prev sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2008-10-30 22:20:33 -0400, Benji Smith <dlanguage benjismith.net> said:


 Consider this code:
 
     class MyObject {
 
        public int x() {
           return obj.a().b().c().d();
        }
 
        public MyObject a() { ... }
        public MyObject b() { ... }
        public MyObject c() { ... }
        public int d() { ... }
 
     }
 
 This code creates three temporary objects that cannot possibly escape 
 the scope of the "x" function. Although the user might be content with 
 those object being allocated on the heap, the compiler could decide to 
 allocate them on the stack instead, and the programmer would be 
 blissfully unaware of the switcharoo.
 
 [...]
 Thoughts?


I made a proposal in the other thread that functions could specify the 
requested scope of any parameter used so that the compiler could decide 
if variables need to be allocated on the stack or on the heap. This 
could apply to return values too, but probably only when returning a 
reference to one of the arguments.

In this case MyObject isn't final, and thus the object returned may be 
of a derivative class, which could be of any size, which you can't 
really return on the stack (especially since you're supposed to return 
a reference, not copy the object itself). It should still be possible 
to declare the return value as scope (so that you can put a reference 
to a scope argument in the object), but optimization by placing the 
class on the stack doesn't seem likely to be possible since the object 
is created in a higher scope that will disappear when returning the 
value.

That said, if the object return a pointer to itself, no allocation is 
necessary. Or if the compiler can inline the functions, it may be 
possible for it to optimize away any dynamimc allocation.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Oct 31 2008