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