Andrei Alexandrescu wrote:
> grauzone wrote:
>> Andrei Alexandrescu wrote:
>>> grauzone wrote:
>>>> Andrei Alexandrescu wrote:
>>>>> grauzone wrote:
>>>>>> Andrei Alexandrescu wrote:
>>>>>>> The idea is that the API offers a means to define and use temporary buffers without compromising memory safety. Even if you escape data allocated via getBuffer that persists after releaseBuffer, that will not cause undefined behavior. (It may, however, cause data to be overwritten because another call to getBuffer will reuse memory.) Leaks are also possible if you don't release the buffer. That can be solved by not offering getBuffer and releaseBuffer as they are, but instead only encapsulated in a struct with the appropriate constructor and destructor.
>>>>>>
>>>>>> That's an interesting point. You can have two things:
>>>>>> 1. Correct memory managment (one can never access an object that's supposed to be free'd)
>>>>>> 2. Safe memory managment (event if you access an object that's supposed to be free'd, it's memory safe)
>>>>>>
>>>>>> In safe mode, 1. can't be allowed, and 2. is better than nothing. In normal D, I'd say 2. is quite useless, except as an debugging option.
>>>>>
>>>>> Normal D must be debuggable D.
>>>>
>>>> That isn't the case right now and never will be.
>>>
>>> Then if I were you and I really believed that, I wouldn't waste one more minute hanging out in this group.
>>
>> Don't worry, I won't leave so easily.
> 
> I know. Clearly there is something in D that you find irresistibly attractive; I wonder what that is :o).

It's like a narcotic drug.

>> That said, if you use "delete" (or GC.free) incorrectly, you may end up with an undebuggable program. Plus there's no way manual free will ever be removed from D. I'm sure you know that, but it sounds like you're denying that. Whatever.
> 
> Of course I'm denying it because it's false. SafeD will not allow programs containing manual free. And SafeD is quickly becoming a reality, your pessimism notwithstanding.

Does this imply you'Re going to make SafeD default, and discourage use of "unsafe" D?

> 
> Andrei

On 01/11/2010 11:33 AM, 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 :-)
>
> Bye,
> bearophile

That's good, but the newsgroup is hardly an archive and a post is not the same as a PEP. You put a lot of time in here, but this kind of information is fleeting and will be lost in the future. When you want this you should take yourself seriously and organise your posts in the wiki with a link to the ng.

Walter Bright:
> One of the problems is they can easily lead to stack exhaustion. Stack sizes for a thread must all be preallocated.

Yes, that's of course a problem. It's meaningful to allocate arrays on the stack only if they are small. You can exhaust the/a stack even with normal fixed-sized arrays too:

int foo(int n) {
  int[100] a;
  ...
  y = foo(k);
  ...
}

The main difference is that here you can see better that each nested call to foo() burns 400+ bytes of stack (but as in the variable-length case, it's possible that you don't statically know how many nested calls to foo() will happen at runtime, so the end result is the same: you don't know if you will have a stack overflow at runtime).
In truth we can live without variable-length stack allocated arrays, mine may be just feature envy, and I prefer variable-length stack allocated arrays over the raw alloca().
Thank you very much for showing up in this thread, I appreciate a small answer too a lot :-)

Bye,
bearophile

dsimcha wrote:
> == Quote from Chad J (chadjoan@__spam.is.bad__gmail.com)'s article
>> 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.
> 
> The optional buffer idiom is great for stuff that's returned from a function.  I
> use it all the time.  On the other hand, for temporary buffers that are used
> internally, whose mere existence is an implementation detail, having the caller
> maintain and pass in a buffer is a horrible violation of encapsulation and good
> API design, even by the standards of performance-oriented APIs.  Even if you know
> it's never going to change, it's still annoying for the caller to even have to
> think about these kinds of details.

The design I'm using for SciD is just that,

  double[] algo(params, double[] buffer=null, double[] workspace=null);

and it's already starting to annoy me.  I never remember how much workspace memory is required for each algorithm, and constantly have to look it up.  I definitely have to do something about it.

(The worst are the LAPACK linear algebra functions. There you have a minimum workspace size, which is easily found in the docs, but for many of them you also have an *optimal* workspace size, which you have to make LAPACK calculate for you.  And even the minimum size depends on a lot of factors, like matrix size (naturally), whether the matrix is real or complex, symmetric or hermitian, triangular, etc.)


>> 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).
> 
> Yeah, for about the past year I've been playing around with TempAlloc, wich was
> basically me taking Andrei's SuperStack idea when it was first proposed and
> running with it because I needed it sooner rather than later.  It's basically
> encapsulated in dstats.alloc
> (http://svn.dsource.org/projects/dstats/docs/alloc.html).

TempAlloc looks really interesting.  I was actually thinking about writing some kind of "preallocated memory pool" mechanism myself, to get rid of all the workspace[]s. If you don't mind, I'll look into using TempAlloc for SciD.


> [...]
> It's got the following advantages over alloca:
> 
> 1.  Can't overflow unless you're completely out of address space.  As a last
> resort, it allocates another chunk of memory from the heap.

When all chunks in a block have been TempAlloc.free()'ed, is the block GC.free()'ed as well?  Or is the memory retained for future use?  (And if the answer to the last question is 'no', is there a reason not to retain the memory until the program exits, or at least to include an option to?)

-Lars

bearophile, el 12 de enero a las 04:18 me escribiste:
> Walter Bright:
> > One of the problems is they can easily lead to stack exhaustion. Stack sizes for a thread must all be preallocated.
> 
> Yes, that's of course a problem. It's meaningful to allocate arrays on the stack only if they are small. You can exhaust the/a stack even with normal fixed-sized arrays too:
> 
> int foo(int n) {
>   int[100] a;
>   ...
>   y = foo(k);
>   ...
> }

Or with structs:

struct S {
	int[100000] a;
}

void foo() {
	S s;
}

See this post: http://www.yosefk.com/blog/the-c-sucks-series-petrifying-functions.html

For a nice real story about this problem ;)

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
This homeless guy asked me for some money the other day.
And I was gonna give it to him but then I thought you're
just gonna use it on drugs or alcohol.
And then I thought, that's what I'm gonna use it on.
Why am I judging this poor bastard.

== Quote from Lars T. Kyllingstad (public@kyllingen.NOSPAMnet)'s > > It's got the following advantages over alloca:
> >
> > 1.  Can't overflow unless you're completely out of address space.  As a last resort, it allocates another chunk of memory from the heap.
> When all chunks in a block have been TempAlloc.free()'ed, is the block
> GC.free()'ed as well?  Or is the memory retained for future use?  (And
> if the answer to the last question is 'no', is there a reason not to
> retain the memory until the program exits, or at least to include an
> option to?)
> -Lars

The memory is freed according to heuristics.  Here's a brief description:

1.  All state is thread-local.  Unless TempAlloc needs to go to the main heap, there is never any type of synchronization.

2.  Each chunk is 4 MB.  I've realized that this may be overkill and am thinking of reducing it to 1 MB or 512K.  This is controlled by an enum, so it would be a trivial change.

3.  Chunks are stored in a stack (yes, a stack of stacks).  Half of the unused chunks are freed anytime there are 2x as many unused chunks as used chunks. Usually 4MB per thread in temp buffer space is plenty, though.

dsimcha wrote:
> == Quote from Lars T. Kyllingstad (public@kyllingen.NOSPAMnet)'s > > It's got the
> following advantages over alloca:
>>> 1.  Can't overflow unless you're completely out of address space.  As a last
>>> resort, it allocates another chunk of memory from the heap.
>> When all chunks in a block have been TempAlloc.free()'ed, is the block
>> GC.free()'ed as well?  Or is the memory retained for future use?  (And
>> if the answer to the last question is 'no', is there a reason not to
>> retain the memory until the program exits, or at least to include an
>> option to?)
>> -Lars
> 
> The memory is freed according to heuristics.  Here's a brief description:
> 
> 1.  All state is thread-local.  Unless TempAlloc needs to go to the main heap,
> there is never any type of synchronization.
> 
> 2.  Each chunk is 4 MB.  I've realized that this may be overkill and am thinking
> of reducing it to 1 MB or 512K.  This is controlled by an enum, so it would be a
> trivial change.

I suppose it depends on what you're using it for. For maximum flexibility, you could do this:

  struct CustomTempAlloc(uint blockSize)
  { // current TempAlloc code here }

  // Default is 4MB
  alias CustomTempAlloc!(4U * 1024U * 1024U) TempAlloc;


> 3.  Chunks are stored in a stack (yes, a stack of stacks).  Half of the unused
> chunks are freed anytime there are 2x as many unused chunks as used chunks.
> Usually 4MB per thread in temp buffer space is plenty, though.

Thanks for the explanation!

-Lars

Lars T. Kyllingstad:
>    struct CustomTempAlloc(uint blockSize)
>    { // current TempAlloc code here }
> 
> 
>    alias CustomTempAlloc!(4U * 1024U * 1024U) TempAlloc;

Or:

struct TempAlloc(uint blockSize=4U * 1024U * 1024U) {
    // Default is 4MB
    // current TempAlloc code here }

Bye,
bearophile

Andrei Alexandrescu wrote:
> template SuperStack(T) {
>     private T[] buffer;
>     private enum slackfactor = 2.5;
> 
>     T[] getBuffer(size_t n) {
>         buffer.length = buffer.length + n;
>         return buffer[$ - n .. $];
>     }
> 
>     void releaseBuffer(T[] b) {
>         enforce(b is buffer[$ - b.length .. $]);
>         buffer.length = buffer.length - b.length;
>         if (gc.capacity(buffer) > buffer.length * slackfactor) {
>             // Reallocate buffer to allow collection of slack
>             buffer = buffer.dup;
>         }
>     }
> }

Broken design is broken.

SuperStack!int stack;
auto buffer0 = stack.getBuffer(100);
auto buffer1 = stack.getBuffer(10000000); // Reallocates internal array.
stack.releaseBuffer(buffer1);
stack.releaseBuffer(buffer0); // Assertion failure.


-- 
Rainer Deyke - rainerd@eldwood.com

Rainer Deyke wrote:
> Andrei Alexandrescu wrote:
>> template SuperStack(T) {
>>     private T[] buffer;
>>     private enum slackfactor = 2.5;
>>
>>     T[] getBuffer(size_t n) {
>>         buffer.length = buffer.length + n;
>>         return buffer[$ - n .. $];
>>     }
>>
>>     void releaseBuffer(T[] b) {
>>         enforce(b is buffer[$ - b.length .. $]);
>>         buffer.length = buffer.length - b.length;
>>         if (gc.capacity(buffer) > buffer.length * slackfactor) {
>>             // Reallocate buffer to allow collection of slack
>>             buffer = buffer.dup;
>>         }
>>     }
>> }
> 
> Broken design is broken.
> 
> SuperStack!int stack;
> auto buffer0 = stack.getBuffer(100);
> auto buffer1 = stack.getBuffer(10000000); // Reallocates internal array.
> stack.releaseBuffer(buffer1);
> stack.releaseBuffer(buffer0); // Assertion failure.

Yikes, thanks. Now something happened with my news reader - the part of your message containing your improved solution got cut off :o).

Andrei