Mon, 11 Jan 2010 05:26:28 -0500, bearophile wrote:

> grauzone:
>> Why are you making such proposals, when one of the core developers even thought about removing normal "scope"?
> 
> I have a nice implementation of Barnes-Hut algorithm translated from Java. Its running time goes from 18.1 seconds to 7.6 s adding "scope" where some classes are initialized (those classes are 3D vectors, that can also become structs).
> 
> If scope classes are removed, then it may be necessary to add struct inheritance to D2, because in several situations objects can't be used (and by the way, the very latest Java HotSpot

latest = 17.0-b05 ?

> needs about 10.9 s to run
> the same code, despite it performs Escape Analysis, probably because
> such Analysis is not as good as my manual scope annotations). On request
> I can show all the code discussed here.
> 
> Bye,
> bearophile

retard:
> latest = 17.0-b05 ?

It was introduced in 1.6.0_14, but you need to add -XX:+DoEscapeAnalysis to activate it. I am using build 1.7.0-ea-b76 where I think EA is activated by default. Look at Sun docs for more info, I am not an expert on this.

Bye,
bearophile

bearophile wrote:
> grauzone:
>> Why are you making such proposals, when one of the core developers even thought about removing normal "scope"?
> 
> And by the way, in the Python community one of the purposes of PEPs is to act as an archive of refused proposals, so people can avoid wasting brain energy over and over again about permanently refused ideas :-)
> Sometimes it's worth doing well even wrong things :-)

You could try to write a real DIP: http://prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs

> Bye,
> bearophile

Andrei Alexandrescu wrote:
> grauzone wrote:
>> Andrei Alexandrescu wrote:
>>> grauzone wrote:
>>>> Andrei Alexandrescu wrote:
>>>>> grauzone wrote:
>>>>>> bearophile wrote:
>>>>>>> void bar(int n) {
>>>>>>>   scope int[] a = new int[n]; // stack-allocated
>>>>>>>   foo(a);
>>>>>>> }
>>>>>>
>>>>>> Why are you making such proposals, when one of the core developers even thought about removing normal "scope"? It's almost 100% guaranteed that nobody will listen.
>>>>>>
>>>>>> I personally find it a good idea to find new ways to reduce producing memory garbage. The D GC is slow and bad, so you'd better avoid it.
>>>>>>
>>>>>> Let's make this claim: it is impossible to write high performance applications (that need to make use of dynamic memory allocation) in D without resorting to "unsafe" techniques. That would include allocating memory on the stack, or manually freeing memory.
>>>>>
>>>>> I write high-performance code in D without resorting to unsafe techniques. Much of my code allocates arrays only in the beginning and uses them throughout.
>>>>
>>>> I intended to exclude this case with applications "that need to make use of dynamic memory allocation". But I guess this doesn't apply to programs that only allocate on initialization.
>>>>
>>>> So, how about programs that allocate/release memory while doing computations?
>>>
>>> "Oil is found in the minds of men."
>>
>> Can you explain what this means in the context of the problem mentioned above?
> 
> It means that if you start with the goal of making high performance applications safe, you may achieve that. One guaranteed way to not get there is to start with a claim that it can't be done.

I just wanted to leave that "claim" for anybody to attack. But in the end, solutions to this problem will only be workarounds, and programs will possibly be more convoluted than their C/C++ counterparts. E.g. you could just use freelists (reusing memory without going through the runtime memory manager), but then you'd lose constructors, etc...

> That being said, I like stack-allocated and I asked Walter for a long time to introduce them in the language. They have their problems though.

They can just be disabled in safe mode, if that's the problem.

> 
> Andrei

grauzone wrote:
> Andrei Alexandrescu wrote:
>> grauzone wrote:
>>> Andrei Alexandrescu wrote:
>>>> grauzone wrote:
>>>>> Andrei Alexandrescu wrote:
>>>>>> grauzone wrote:
>>>>>>> bearophile wrote:
>>>>>>>> void bar(int n) {
>>>>>>>>   scope int[] a = new int[n]; // stack-allocated
>>>>>>>>   foo(a);
>>>>>>>> }
>>>>>>>
>>>>>>> Why are you making such proposals, when one of the core developers even thought about removing normal "scope"? It's almost 100% guaranteed that nobody will listen.
>>>>>>>
>>>>>>> I personally find it a good idea to find new ways to reduce producing memory garbage. The D GC is slow and bad, so you'd better avoid it.
>>>>>>>
>>>>>>> Let's make this claim: it is impossible to write high performance applications (that need to make use of dynamic memory allocation) in D without resorting to "unsafe" techniques. That would include allocating memory on the stack, or manually freeing memory.
>>>>>>
>>>>>> I write high-performance code in D without resorting to unsafe techniques. Much of my code allocates arrays only in the beginning and uses them throughout.
>>>>>
>>>>> I intended to exclude this case with applications "that need to make use of dynamic memory allocation". But I guess this doesn't apply to programs that only allocate on initialization.
>>>>>
>>>>> So, how about programs that allocate/release memory while doing computations?
>>>>
>>>> "Oil is found in the minds of men."
>>>
>>> Can you explain what this means in the context of the problem mentioned above?
>>
>> It means that if you start with the goal of making high performance applications safe, you may achieve that. One guaranteed way to not get there is to start with a claim that it can't be done.
> 
> I just wanted to leave that "claim" for anybody to attack. But in the end, solutions to this problem will only be workarounds, and programs will possibly be more convoluted than their C/C++ counterparts.

C++ doesn't have stack-allocated arrays.

Andrei

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
> grauzone wrote:
> > bearophile wrote:
> >> void bar(int n) {
> >>   scope int[] a = new int[n]; // stack-allocated
> >>   foo(a);
> >> }
> >
> > Why are you making such proposals, when one of the core developers even thought about removing normal "scope"? It's almost 100% guaranteed that nobody will listen.
> >
> > I personally find it a good idea to find new ways to reduce producing memory garbage. The D GC is slow and bad, so you'd better avoid it.
> >
> > Let's make this claim: it is impossible to write high performance applications (that need to make use of dynamic memory allocation) in D without resorting to "unsafe" techniques. That would include allocating memory on the stack, or manually freeing memory.
> I write high-performance code in D without resorting to unsafe techniques. Much of my code allocates arrays only in the beginning and uses them throughout.

One thing I've always wondered about people who operate this way is, how do you do it without violating tons of encapsulation?  For example, let's say you want foo() to be a well-encapsulated free function:

int foo(int num) {
    int[] temp = new int[num];
    // Do stuff.
}

Now how do you draw a line of abstraction that reuses temp in a well-encapsulated way, one that is invisible to the caller of foo()?

Since bugs that occur at higher levels of abstraction are often caused by poor encapsulation and programs that are too hard to reason about, I'd rather have a well-encapsulated "unsafe" speed hack than a poorly encapsulated "safe" one.

bearophile wrote:
> You can see of this as a small DEP :-)
> 
> Small variable-length arrays allocated on the stack can be somewhat useful in D. They avoid most usages of alloca() and are a bit safer than alloca() because no pointer casting is needed.
> 
> alloca() gives some performance improvement compared to normal dynamic arrays if the array is small and the function (here bar()) is called many times (I have experimentally seen this in the Levenshtein distance function, that needs to allocate a temporary buffer. If the length of the two input strings is small I use a fixed-sized array as buffer, this improves performance some in code that needs to compute this distance over many small strings. I think a variable-length array is a bit better here. In this situation often Tango adopts the strategy of adding an extra function argument that allows to give a preallocated buffer to a function).
> 

Tango adopting that convention is interesting to me because it seems like a convention that could be used very commonly to make things run faster.  Note that it is more general than alloca: it allows one to allocate stack memory in the /caller's/ stack frame.

char[] stringModify( char[] someStr, char[] buffer )
{
	// Expand the buffer, but only if necessary.
	size_t len = calculateNeededLengthFrom(someStr);
	if ( buffer.length < len )
		buffer = new buffer[len];

	// Sometimes you can't calculate the buffer size needed ahead
	//   of time, so you figure it out as you go and use the
	//   buffer until you run out.

	// Do stuff with someStr, putting the result into buffer.

	return buffer; // You can do this.  buffer is in parent frame.
}

So, is there any way to allocate memory in the caller's stack frame in D right now?  Can an abstraction be made to do this for both the caller and callee without a lot of boilerplate?

> 
> ... (btw hijacking ur thread)
> 
> Bye,
> bearophile


- Chad

Chad J wrote:
> bearophile wrote:
>> You can see of this as a small DEP :-)
>>
>> Small variable-length arrays allocated on the stack can be somewhat useful in D. They avoid most usages of alloca() and are a bit safer than alloca() because no pointer casting is needed.
>>
>> alloca() gives some performance improvement compared to normal dynamic arrays if the array is small and the function (here bar()) is called many times (I have experimentally seen this in the Levenshtein distance function, that needs to allocate a temporary buffer. If the length of the two input strings is small I use a fixed-sized array as buffer, this improves performance some in code that needs to compute this distance over many small strings. I think a variable-length array is a bit better here. In this situation often Tango adopts the strategy of adding an extra function argument that allows to give a preallocated buffer to a function).
>>
> 
> Tango adopting that convention is interesting to me because it seems like a convention that could be used very commonly to make things run faster.  Note that it is more general than alloca: it allows one to allocate stack memory in the /caller's/ stack frame.
> 
> char[] stringModify( char[] someStr, char[] buffer )
> {
> 	// Expand the buffer, but only if necessary.
> 	size_t len = calculateNeededLengthFrom(someStr);
> 	if ( buffer.length < len )
> 		buffer = new buffer[len];
> 
> 	// Sometimes you can't calculate the buffer size needed ahead
> 	//   of time, so you figure it out as you go and use the
> 	//   buffer until you run out.
> 
> 	// Do stuff with someStr, putting the result into buffer.
> 
> 	return buffer; // You can do this.  buffer is in parent frame.
> }
> 
> So, is there any way to allocate memory in the caller's stack frame in D right now?

Err, I mean without explicit help from the caller.

> Can an abstraction be made to do this for both the caller and callee without a lot of boilerplate?
> 
>> ... (btw hijacking ur thread)
>>
>> Bye,
>> bearophile
> 
> 
> - Chad

Chad J wrote:
> Chad J wrote:
>> bearophile wrote:
>>> You can see of this as a small DEP :-)
>>>
>>> Small variable-length arrays allocated on the stack can be somewhat useful in D. They avoid most usages of alloca() and are a bit safer than alloca() because no pointer casting is needed.
>>>
>>> alloca() gives some performance improvement compared to normal dynamic arrays if the array is small and the function (here bar()) is called many times (I have experimentally seen this in the Levenshtein distance function, that needs to allocate a temporary buffer. If the length of the two input strings is small I use a fixed-sized array as buffer, this improves performance some in code that needs to compute this distance over many small strings. I think a variable-length array is a bit better here. In this situation often Tango adopts the strategy of adding an extra function argument that allows to give a preallocated buffer to a function).
>>>
>> Tango adopting that convention is interesting to me because it seems
>> like a convention that could be used very commonly to make things run
>> faster.  Note that it is more general than alloca: it allows one to
>> allocate stack memory in the /caller's/ stack frame.
>>
>> char[] stringModify( char[] someStr, char[] buffer )
>> {
>> 	// Expand the buffer, but only if necessary.
>> 	size_t len = calculateNeededLengthFrom(someStr);
>> 	if ( buffer.length < len )
>> 		buffer = new buffer[len];
>>
>> 	// Sometimes you can't calculate the buffer size needed ahead
>> 	//   of time, so you figure it out as you go and use the
>> 	//   buffer until you run out.
>>
>> 	// Do stuff with someStr, putting the result into buffer.
>> 	
>> 	return buffer; // You can do this.  buffer is in parent frame.
>> }
>>
>> So, is there any way to allocate memory in the caller's stack frame in D
>> right now?  
> 
> Err, I mean without explicit help from the caller.

First, it's good to use the idiom

buffer.length = len;

instead of

buffer = new buffer[len];

so there's a chance for in-place expansion of buffer.

There's no organized way to do what you want at the moment, but a small API could be provided. For example the STL has get_temporary_buffer() and release_temporary_buffer():

http://www.sgi.com/tech/stl/get_temporary_buffer.html

There was a discussion on this group, google for superstack site:digitalmars.com. I wanted to implement that, it just fell through the cracks. I think it should be added to bugzilla so it's not forgotten.


Andrei

Andrei Alexandrescu wrote:
> 
> First, it's good to use the idiom
> 
> buffer.length = len;
> 
> instead of
> 
> buffer = new buffer[len];
> 
> so there's a chance for in-place expansion of buffer.
> 

Ah.  Good to know.

> There's no organized way to do what you want at the moment, but a small
> API could be provided. For example the STL has get_temporary_buffer()
> and release_temporary_buffer():
> 
> http://www.sgi.com/tech/stl/get_temporary_buffer.html
> 
> There was a discussion on this group, google for superstack site:digitalmars.com. I wanted to implement that, it just fell through the cracks. I think it should be added to bugzilla so it's not forgotten.
> 
> 
> Andrei

That does sound very useful.

http://d.puremagic.com/issues/show_bug.cgi?id=3696

I'm realizing now that returning an object allocated on this stack is a tricky task unless there is help from the caller.  The lifetime of the object has to be determined somehow.  The Tango convention makes it fairly explicit that the parent's scope will be the beginning and the end for the memory.  If it needs to live longer then the caller just passes a buffer that isn't stack/scoped memory.  Only the caller really knows how long the memory needs to hang around.  hmmmmm.

Still that SuperStack thing would be useful.  It's like alloca but
better (look ma, no cast) and slightly more general (ex: it can be freed
in parent's scope, if you are willing to play it risky).