www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - TempAlloc review starts now

reply "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
All right, folks, it's time to get the review queue started again.  First 
up is David Simcha's TempAlloc, which, if accepted, is to be included in 
the core.memory module in druntime.

If there are no objections, I suggest we use 3 weeks (until 27 June) for 
the review, followed by one week for voting.  Please post reviews in this 
thread.

Here follows a description of TempAlloc's purpose and functionality.  
Links to the code and documentation are at the bottom.

-Lars


David Simcha wrote:

TempAlloc is a thread-local segmented stack memory allocator
(defined/detailed in the docs) for efficiently allocating temporary
buffers, matrices, etc.  It has the following advantages compared to
allocation on the call stack:

1. Pointers to memory allocated on the TempAlloc stack are still valid
when the function they were allocated from returns. Functions can be
written to create and return data structures on the TempAlloc stack.

2. Since it is a segmented stack, large allocations can be performed with
no danger of stack overflow errors.

It has the following advantages compared to heap allocation:

1. Both allocation and deallocation are extremely fast. Most allocations
consist of verifying enough space is available, incrementing a pointer and
a performing a few cheap bookkeeping operations. Most deallocations
consist decrementing a pointer and performing a few cheap bookkeeping
operations.

2. The segmented stack is thread-local, so synchronization is only needed
when a segment needs to be allocated or freed.

3. Fragmentation is not an issue when allocating memory on the TempAlloc
stack, though it can be an issue when trying to allocate a new segment.

It'd be nice to get this in the next release b/c SciD, which is being
worked on extensively for GSoC, uses it and Don said he wanted to use it
in BigInt.

Code:

https://github.com/dsimcha/TempAlloc/blob/master/tempalloc.d

Docs:

http://cis.jhu.edu/~dsimcha/d/phobos/core_tempalloc.html
Jun 05 2011
next sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
I wish "newVoid" was a language feature. If we have:
int x = void;

It'd also be nice to have a similar form for the new operator:
int[] x = void new int[](size);
x[] = 1;

"int x = void" might not save too much cycles, but initializing a
large array twice.. that's another thing.

newVoid seems to only work for 1-dimensional arrays. I could use
something of this form:
double[][] arr = newVoid!(double[][])(16, 100);

Not a big deal, I could write something like this for my own projects.
I'm just commenting.

I used GC.malloc before but I never once thought about setting the
NO_SCAN flag. Heh. :)
Jun 05 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
On 6/5/2011 6:50 PM, Andrej Mitrovic wrote:

 I wish "newVoid" was a language feature. If we have:
 int x = void;

 It'd also be nice to have a similar form for the new operator:
 int[] x = void new int[](size);
 x[] = 1;

 "int x = void" might not save too much cycles, but initializing a
 large array twice.. that's another thing.

 newVoid seems to only work for 1-dimensional arrays. I could use
 something of this form:
 double[][] arr = newVoid!(double[][])(16, 100);

 Not a big deal, I could write something like this for my own projects.
 I'm just commenting.

 I used GC.malloc before but I never once thought about setting the
 NO_SCAN flag. Heh. :)


newVoid will probably be renamed to something more verbose and explicit 
at Andrei's request.  See 
http://d.puremagic.com/issues/show_bug.cgi?id=3383 .  While I'm at it, I 
guess I could make it support multidimensional.
Jun 05 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrej Mitrovic:


 I wish "newVoid" was a language feature. If we have:
 int x = void;
 
 It'd also be nice to have a similar form for the new operator:
 int[] x = void new int[](size);
 x[] = 1;
 
 "int x = void" might not save too much cycles, but initializing a
 large array twice.. that's another thing.
 
 newVoid seems to only work for 1-dimensional arrays. I could use
 something of this form:
 double[][] arr = newVoid!(double[][])(16, 100);
 
 Not a big deal, I could write something like this for my own projects.
 I'm just commenting.
 
 I used GC.malloc before but I never once thought about setting the
 NO_SCAN flag. Heh. :)


This is kind of off-topic.
There is a very simple syntax, nice and clean:

// doesn't initialize foo1
auto foo1 = new uint[5] = void;

// initializes the dynamic array to 5, avoiding a double initialization
auto foo2 = new uint[5] = 10;

// works for nD arrays too
auto mat1 = new double[][][](n1,n2,n3) = 0.0;

That syntax is inspired by fixed-sized array syntax, so I don't think it will
take lot of time to people to learn it, quite the opposite:

uint[5] a1 = void;
uint[5] a2 = 10;
double[n1][n2][n3] mat2 = 0.0;

The increase of language complexity for the programmer is minimal.

But its usage as expression is not the most nice, so it's probably better to
disallow this usage:

void foo(int[] a) {}
main() {
    foo(new[5] = 5);
}

Bye,
bearophile
Jun 05 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/05/2011 06:22 PM, bearophile wrote:

 Andrej Mitrovic:


 I wish "newVoid" was a language feature. If we have:
 int x = void;

 It'd also be nice to have a similar form for the new operator:
 int[] x = void new int[](size);
 x[] = 1;

 "int x = void" might not save too much cycles, but initializing a
 large array twice.. that's another thing.

 newVoid seems to only work for 1-dimensional arrays. I could use
 something of this form:
 double[][] arr = newVoid!(double[][])(16, 100);

 Not a big deal, I could write something like this for my own projects.
 I'm just commenting.

 I used GC.malloc before but I never once thought about setting the
 NO_SCAN flag. Heh. :)


 This is kind of off-topic.
 There is a very simple syntax, nice and clean:

 // doesn't initialize foo1
 auto foo1 = new uint[5] = void;


Everywhere else in the language, expr1 = expr2 = expr3 means "expr2 gets 
expr3 and then exp1 gets expr2). Cue the slave choir in Nabucodonosor, 
adagio sostenuto, piano ma espressivo: "Special cases are baaaaad... 
special cases are veeery baaaaad...."

new T[size](void) and new T[size](initializer) have been discussed, 
Walter never got around to thinking of implementing them.


Andrei
Jun 05 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Andrei:


 new T[size](void) and new T[size](initializer) have been discussed,


Isn't this syntax:
new int[](15)
already equivalent to this?
new int[15]


The mix of square and round parentheses D uses to define and allocate dynamic
is confusing for me and I don't like it, especially when you want to allocate a
multi-dimensional array where some dimensions are fixed-sized arrays and others
are dynamic. I have never written a bug report on this because I don't think
this syntax will change and because after hundreds of usages I think it's
coherent, despite looking somewhat messy.

Bye,
bearophile
Jun 05 2011
prev sibling next sibling parent reply simendsjo <simen.endsjo pandavre.com> writes:
I have very limited experience with D and haven't taken the time to understood
the code, but here are
some easy nitpicks :)
----
imports: Should stuff in core really depend on phobos? Isn't much of the reason
for core to allow
different "standard" libraries like tango?

177: should 16 be alignBytes?
199/299: unnecessary initializers
246: Move inUse.destroy() up to clearing of inUse?
291: Move assumption comment to assertion. Something like this:

bool isPowerOf(int pow, int num) {
    if(num <= 0 || pow <= 0)
        return false;
    else if(pow == 1)
        return true;
    else if(pow == num)
        return true;
    else {
        double n = cast(double)num / cast(double)pow;
        if(n%1 != 0)
            return false;
        else if(n == pow)
            return true;
        else
            return isPowerOf(pow, cast(int)n);
    }
}
unittest {
    static assert(isPowerOf(1, 0) == false); // num==0
    static assert(isPowerOf(1, 5) == true);  // pow==1
    static assert(isPowerOf(3, 3) == true);  // pow==num
    static assert(isPowerOf(2, 2) == true);
    static assert(isPowerOf(2, 3) == false);

    static assert(isPowerOf(2, 4) == true);
    static assert(isPowerOf(2, 1024) == true);
    static assert(isPowerOf(2, 1023) == false);
}

and in getAligned:
static assert(isPowerOf(2, alignBytes), "getAligned requires alignBytes to be a
power of 2")

383/408/418/428: getState called without () (deprecated behavior, right..?)
686: missing () (same as above)
Jun 06 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
simendsjo wrote:

 I have very limited experience with D and haven't taken the time to
 understood the code, but here are
 some easy nitpicks :)
 ----
 imports: Should stuff in core really depend on phobos? Isn't much of the
 reason for core to allow
 different "standard" libraries like tango?
 [snip.]


Actually the code doesn't depend on phobos. You can change the set of imports
to:

import core.memory, core.exception, core.stdc.string;
static import core.stdc.stdlib;

It will still compile. Good point though. That needs to be changed.


Timon
Jun 06 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 6/6/2011 7:24 AM, Timon Gehr wrote:

 simendsjo wrote:

 I have very limited experience with D and haven't taken the time to
 understood the code, but here are
 some easy nitpicks :)
 ----
 imports: Should stuff in core really depend on phobos? Isn't much of the
 reason for core to allow
 different "standard" libraries like tango?
 [snip.]


 Actually the code doesn't depend on phobos. You can change the set of imports
to:

 import core.memory, core.exception, core.stdc.string;
 static import core.stdc.stdlib;

 It will still compile. Good point though. That needs to be changed.


 Timon


Wow.  I have no idea how these dependencies on Phobos slipped past me. 
Probably because I'm so used to thinking of std.range, std.algorithm, 
etc. as fundamental parts of the language.  They absolutely, 110% must 
be gotten rid of if this is to go into druntime.  This may necessitate 
breaking this proposal up into two:  TempAlloc itself in druntime and 
the higher level convenience functions (tempdup, stackCat, etc.) in 
std.array.
Jun 06 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 06 Jun 2011 08:51:27 -0400, dsimcha <dsimcha yahoo.com> wrote:


 On 6/6/2011 7:24 AM, Timon Gehr wrote:

 simendsjo wrote:

 I have very limited experience with D and haven't taken the time to
 understood the code, but here are
 some easy nitpicks :)
 ----
 imports: Should stuff in core really depend on phobos? Isn't much of  
 the
 reason for core to allow
 different "standard" libraries like tango?
 [snip.]


 Actually the code doesn't depend on phobos. You can change the set of  
 imports to:

 import core.memory, core.exception, core.stdc.string;
 static import core.stdc.stdlib;

 It will still compile. Good point though. That needs to be changed.


 Timon


 Wow.  I have no idea how these dependencies on Phobos slipped past me.  
 Probably because I'm so used to thinking of std.range, std.algorithm,  
 etc. as fundamental parts of the language.  They absolutely, 110% must  
 be gotten rid of if this is to go into druntime.  This may necessitate  
 breaking this proposal up into two:  TempAlloc itself in druntime and  
 the higher level convenience functions (tempdup, stackCat, etc.) in  
 std.array.


Without actually even looking at it (yet), I don't see why this goes into  
druntime in the first place.  From my experience with druntime, things  
should go in there only if the compiler or runtime needs them to work.  Is  
there a proposed usage for TempAlloc in druntime or for the compiler?

-Steve
Jun 06 2011
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article

 On Mon, 06 Jun 2011 08:51:27 -0400, dsimcha <dsimcha yahoo.com> wrote:

 On 6/6/2011 7:24 AM, Timon Gehr wrote:

 simendsjo wrote:

 I have very limited experience with D and haven't taken the time to
 understood the code, but here are
 some easy nitpicks :)
 ----
 imports: Should stuff in core really depend on phobos? Isn't much of
 the
 reason for core to allow
 different "standard" libraries like tango?
 [snip.]


 Actually the code doesn't depend on phobos. You can change the set of
 imports to:

 import core.memory, core.exception, core.stdc.string;
 static import core.stdc.stdlib;

 It will still compile. Good point though. That needs to be changed.


 Timon


 Wow.  I have no idea how these dependencies on Phobos slipped past me.
 Probably because I'm so used to thinking of std.range, std.algorithm,
 etc. as fundamental parts of the language.  They absolutely, 110% must
 be gotten rid of if this is to go into druntime.  This may necessitate
 breaking this proposal up into two:  TempAlloc itself in druntime and
 the higher level convenience functions (tempdup, stackCat, etc.) in
 std.array.


 Without actually even looking at it (yet), I don't see why this goes into
 druntime in the first place.  From my experience with druntime, things
 should go in there only if the compiler or runtime needs them to work.  Is
 there a proposed usage for TempAlloc in druntime or for the compiler?
 -Steve


You may be right.  Someone (I think it was Andrei or Sean) suggested
core.memory.
 I would be fine with moving it to Phobos instead.
Jun 06 2011
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
simendsjo:


 bool isPowerOf(int pow, int num) {


...

 static assert(isPowerOf(2, alignBytes), "getAligned requires alignBytes to be
a power of 2")


I suggest to add something related to this to std.math instead:

bool isPow2(long x) {
    return (x < 1L) ? false : !(x & (x-1L));
}

A similar template is OK too.

Bye,
bearophile
Jun 06 2011
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 6/6/2011 4:56 AM, simendsjo wrote:

 I have very limited experience with D and haven't taken the time to understood
the code, but here are
 some easy nitpicks :)
 ----
 imports: Should stuff in core really depend on phobos? Isn't much of the
reason for core to allow
 different "standard" libraries like tango?

 177: should 16 be alignBytes?


Yes.  Good catch.


 199/299: unnecessary initializers


I prefer to have this explicit in cases where I will actually use the 
zero value.


 246: Move inUse.destroy() up to clearing of inUse?


Good idea.


 291: Move assumption comment to assertion. Something like this:


Good idea.  This can be implemented even more easily for powers of two:

import core.bitop;

bool isPowerOfTwo(size_t num) {
     return bsr(num) == bsf(num);
}


 383/408/418/428: getState called without () (deprecated behavior, right..?)


Unfortunately, yes.


 686: missing () (same as above)


Argh.  Can we **__PLEASE__** go with loose semantics for  property?
Jun 06 2011
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-06-06 05:58, dsimcha wrote:

 On 6/6/2011 4:56 AM, simendsjo wrote:

 686: missing () (same as above)


 
 Argh.  Can we **__PLEASE__** go with loose semantics for  property?


As far as I know, strict enforcement is still where we're going (and honestly, 
I really hope that it stays that way). But we already debated that quite a bit 
recently on the Phobos list, so you know essentially where that stands.

- Jonathan M Davis
Jun 06 2011
prev sibling next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
On Jun 6, 11 06:25, Lars T. Kyllingstad wrote:

 All right, folks, it's time to get the review queue started again.  First
 up is David Simcha's TempAlloc, which, if accepted, is to be included in
 the core.memory module in druntime.

 If there are no objections, I suggest we use 3 weeks (until 27 June) for
 the review, followed by one week for voting.  Please post reviews in this
 thread.

 Here follows a description of TempAlloc's purpose and functionality.
 Links to the code and documentation are at the bottom.

 -Lars


 David Simcha wrote:

 TempAlloc is a thread-local segmented stack memory allocator
 (defined/detailed in the docs) for efficiently allocating temporary
 buffers, matrices, etc.  It has the following advantages compared to
 allocation on the call stack:

 1. Pointers to memory allocated on the TempAlloc stack are still valid
 when the function they were allocated from returns. Functions can be
 written to create and return data structures on the TempAlloc stack.

 2. Since it is a segmented stack, large allocations can be performed with
 no danger of stack overflow errors.

 It has the following advantages compared to heap allocation:

 1. Both allocation and deallocation are extremely fast. Most allocations
 consist of verifying enough space is available, incrementing a pointer and
 a performing a few cheap bookkeeping operations. Most deallocations
 consist decrementing a pointer and performing a few cheap bookkeeping
 operations.

 2. The segmented stack is thread-local, so synchronization is only needed
 when a segment needs to be allocated or freed.

 3. Fragmentation is not an issue when allocating memory on the TempAlloc
 stack, though it can be an issue when trying to allocate a new segment.

 It'd be nice to get this in the next release b/c SciD, which is being
 worked on extensively for GSoC, uses it and Don said he wanted to use it
 in BigInt.

 Code:

 https://github.com/dsimcha/TempAlloc/blob/master/tempalloc.d

 Docs:

 http://cis.jhu.edu/~dsimcha/d/phobos/core_tempalloc.html


Can't access the doc, it's 404.
Jun 06 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 6/6/2011 4:54 AM, KennyTM~ wrote:

 Can't access the doc, it's 404.


It should work, though it doesn't for me either.  The server's being 
weird right now.  If it doesn't work by tonight, I'll move the docs 
somewhere else.
Jun 06 2011
parent KennyTM~ <kennytm gmail.com> writes:
On Jun 6, 11 20:59, dsimcha wrote:

 On 6/6/2011 4:54 AM, KennyTM~ wrote:

 Can't access the doc, it's 404.


 It should work, though it doesn't for me either. The server's being
 weird right now. If it doesn't work by tonight, I'll move the docs
 somewhere else.


OK it's back.
Jun 06 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/5/11 5:25 PM, Lars T. Kyllingstad wrote:

 Code:

 https://github.com/dsimcha/TempAlloc/blob/master/tempalloc.d

 Docs:

 http://cis.jhu.edu/~dsimcha/d/phobos/core_tempalloc.html


I'll get back with a real review, but before I forget, there is one 
thing that I also noticed in the proposal: TempAlloc is good to have but 
the marketing folks should be dialed down a bit. In the documentation 
TempAlloc lists two advantages compared to stack allocation and three 
advantages compared to heap allocation. There's no disadvantage, 
drawback, caveat, etc. listed at all. If we went by the documentation it 
would appear that TempAlloc is the be-all-end-all memory allocator to 
replace all others.

Documentation must clarify when use of TempAlloc is favored and when 
other allocation methods should be chosen instead.


Thanks,

Andrei
Jun 06 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 On 6/5/11 5:25 PM, Lars T. Kyllingstad wrote:

 Code:

 https://github.com/dsimcha/TempAlloc/blob/master/tempalloc.d

 Docs:

 http://cis.jhu.edu/~dsimcha/d/phobos/core_tempalloc.html


 I'll get back with a real review, but before I forget, there is one
 thing that I also noticed in the proposal: TempAlloc is good to have but
 the marketing folks should be dialed down a bit. In the documentation
 TempAlloc lists two advantages compared to stack allocation and three
 advantages compared to heap allocation. There's no disadvantage,
 drawback, caveat, etc. listed at all. If we went by the documentation it
 would appear that TempAlloc is the be-all-end-all memory allocator to
 replace all others.
 Documentation must clarify when use of TempAlloc is favored and when
 other allocation methods should be chosen instead.
 Thanks,
 Andrei


Yeah, I'm really not sure how much marketing these proposals are supposed to
have.
 One criticism of my std.parallelism proposal, IIRC, was too little marketing.
Jun 06 2011
parent Daniel Gibson <metalcaedes gmail.com> writes:
Am 06.06.2011 18:34, schrieb dsimcha:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 On 6/5/11 5:25 PM, Lars T. Kyllingstad wrote:

 Code:

 https://github.com/dsimcha/TempAlloc/blob/master/tempalloc.d

 Docs:

 http://cis.jhu.edu/~dsimcha/d/phobos/core_tempalloc.html


 I'll get back with a real review, but before I forget, there is one
 thing that I also noticed in the proposal: TempAlloc is good to have but
 the marketing folks should be dialed down a bit. In the documentation
 TempAlloc lists two advantages compared to stack allocation and three
 advantages compared to heap allocation. There's no disadvantage,
 drawback, caveat, etc. listed at all. If we went by the documentation it
 would appear that TempAlloc is the be-all-end-all memory allocator to
 replace all others.
 Documentation must clarify when use of TempAlloc is favored and when
 other allocation methods should be chosen instead.
 Thanks,
 Andrei


 
 Yeah, I'm really not sure how much marketing these proposals are supposed to
have.
  One criticism of my std.parallelism proposal, IIRC, was too little marketing.


But probably because it didn't show the advantages - and not because it
showed to many disadvantages ;)
Jun 06 2011
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Lars T. Kyllingstad:


 Here follows a description of TempAlloc's purpose and functionality.  
 Links to the code and documentation are at the bottom.


I like the contents I am seeing in core.tempalloc. A segmented stack-style
allocator is quite useful. In some other situations I have needed a
hyerarchical allocator, that allows to allocate from the C/D heap and
deallocate whole subtrees at once.

Some comments:

1) Regarding the alignedMalloc/alignedFree names: maybe
alignedCMalloc/alignedCFree names are better, because they remind both the
programmer and the person that reads the code the memory comes from the C heap
(I have similar named functions in dlibs1).

2) TempAlloc.slack name: maybe TempAlloc.segmentSlack is better, because it
reminds its meaning better.

3) "The memory returned by this function is not scanned for pointers by the
garbage collector unless GC.addRange is called." I suggest to add a little
in-place example that shows how to do this.

4) Regarding alignedMalloc(size_t size, bool shouldAddRange = false):
I suggest to add a compile-time template argument to specify the alignment,
that defaults to 16, something like:
alignedMalloc(size_t ALIGN=16)(size_t size, bool shouldAddRange = false)
This is more future-proof, if future CPUs will need just 8 bytes alignments, of
even 32 bytes alignments.

5) Regarding newVoid(): I'd like it to allow to allocate 2D arrays too.


5b) And maybe I'd like to use newVoid() to create a 2D matrix and initialize it
all to a fixed value given at runtime, to replace code like:

auto M = new int[][](n,m);
foreach (row; M)
    row[] = 10;


6) As an extra function to add to this bunch of functions, I suggest to add a
templated function to allocate a 2D matrix carved out of a single zone of
memory (from the C or GC heap, or even the stack...). This is not fully safe,
but it's handy, because it reduces a little the memory needed to allocate the
whole matrix, and the memory of the rows is contigous or almost contigous. The
advantage of this function is that the resulting matrix is seen as a standard
array of dynamic arrays, usable in many other functions. This needs a
corresponding free function.

7) Regarding newStack(): I don't like this name, it doesn' return a stack! I
don't know a good name, but I suggest a name that reminds the programmer that
this function returns an array.

8) Regarding TempAlloc.malloc/TempAlloc.free: I am not sure, but I'd like those
functions to remind the programmer and the person that reads the code that
those two functions work on a stack, so they are push-pop pairs. So maybe names
like TempAlloc.stackMalloc/TempAlloc.stackFree are better. I am not sure.

Bye,
bearophile
Jun 06 2011
parent bearophile <bearophileHUGS lycos.com> writes:
 So maybe names like TempAlloc.stackMalloc/TempAlloc.stackFree are better. I am
not sure.


Or pushMalloc/popFree :-) Or pushMem, popMem, etc.

Bye,
bearophile
Jun 06 2011
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 05 Jun 2011 18:25:07 -0400, Lars T. Kyllingstad  
<public kyllingen.nospamnet> wrote:


 All right, folks, it's time to get the review queue started again.  First
 up is David Simcha's TempAlloc, which, if accepted, is to be included in
 the core.memory module in druntime.


newVoid: I don't really like the name of this -- void is a type.  It  
suggests you are allocating a new void array.  I'm not sure we should  
adopt the hacky syntax that D uses to say "don't initialize" as a symbol  
name.

Particularly, this looks odd:

newVoid!double

What the hell does that mean? :)

I suggest a name like newUninit or newRaw or something that means more  
"uninitailized" than "no type".

alignedMalloc:

I seriously question having such a feature.  According to my C++ book  
malloc returns a pointer "suitably aligned for any type".  According to  
Microsoft, malloc is 16-byte aligned (of course, D doesn't use microsoft's  
runtime, DMC doesn't seem to identify alignment in malloc docs).  GNU  
appears to guarantee 8-byte alignment on 32-bit systems, 16 on 64-bit  
systems (making this function mostly useless on 64-bit dmd).

There are also some posix functions that align a malloc to a requested  
size (see memalign).

At the very least, the function should identify what the alignment is if  
you *don't* use it.  I'd like to see a good use case for this feature in  
an example, otherwise, I think it should be killed.

That being said, wrapping malloc might have some nice other features too.   
I like the auto-adding of the range to the GC.

tempdup:

1. If this uses ElemType!(R)[] as the return type, duping a char[] will  
give you a dchar[].  I don't think this is very desirable.
2. What happens for something like immutable(uint *)[]?  Does it become  
uint *[]?  Because that would be bad...

TempAlloc.malloc:

I don't like void * as a return value.  Would it not be more appropriate  
to use at least void[]?  I'd suggest actually for malloc to take a  
template parameter of the type to return, defaulting to void.  i.e.:

T[] malloc(T = void)(size_t size);

auto x = TempAlloc.malloc(50); // allocate a void[] of size 50
auto x = TempAlloc.malloc!int(50); // allocate an int[] of size 50 ints.

Same should go to alignedMalloc if that feature stays.

-Steve
Jun 06 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article

 On Sun, 05 Jun 2011 18:25:07 -0400, Lars T. Kyllingstad
 <public kyllingen.nospamnet> wrote:

 All right, folks, it's time to get the review queue started again.  First
 up is David Simcha's TempAlloc, which, if accepted, is to be included in
 the core.memory module in druntime.


 newVoid: I don't really like the name of this -- void is a type.  It
 suggests you are allocating a new void array.  I'm not sure we should
 adopt the hacky syntax that D uses to say "don't initialize" as a symbol
 name.
 Particularly, this looks odd:
 newVoid!double
 What the hell does that mean? :)
 I suggest a name like newUninit or newRaw or something that means more
 "uninitailized" than "no type".


Seems there's a strong consensus that the "newVoid" name sucks.  I agree in
hindsight.  Will change.


 alignedMalloc:
 I seriously question having such a feature.  According to my C++ book
 malloc returns a pointer "suitably aligned for any type".  According to
 Microsoft, malloc is 16-byte aligned (of course, D doesn't use microsoft's
 runtime, DMC doesn't seem to identify alignment in malloc docs).  GNU
 appears to guarantee 8-byte alignment on 32-bit systems, 16 on 64-bit
 systems (making this function mostly useless on 64-bit dmd).
 There are also some posix functions that align a malloc to a requested
 size (see memalign).


I definitely need it in the implementation of TempAlloc, so it's gonna be there
but it can be made private if there's a consensus that it's not needed in the
public API.


 At the very least, the function should identify what the alignment is if
 you *don't* use it.  I'd like to see a good use case for this feature in
 an example, otherwise, I think it should be killed.


The alignment if you don't use it depends on the C malloc function for your
platform.  A use case might be if you need 16-byte aligned arrays to use SSE
instructions, but that's hard to demonstrate in a short example.


 That being said, wrapping malloc might have some nice other features too.
 I like the auto-adding of the range to the GC.
 tempdup:
 1. If this uses ElemType!(R)[] as the return type, duping a char[] will
 give you a dchar[].  I don't think this is very desirable.


This seems right to me.  tempdup() is supposed to be basically a TempAlloc
version
of array().  IMHO it should **ALWAYS** return a random-access range.  Returning
a
narrow string creates an obscure special case where it doesn't.


 2. What happens for something like immutable(uint *)[]?  Does it become
 uint *[]?  Because that would be bad...


No.  It becomes an immutable(uint*)[].  ElementType!(immutable(uint*)[]) ==
immutable(uint*).


 TempAlloc.malloc:
 I don't like void * as a return value.  Would it not be more appropriate
 to use at least void[]?  I'd suggest actually for malloc to take a
 template parameter of the type to return, defaulting to void.  i.e.:
 T[] malloc(T = void)(size_t size);


Here I'm going to have to strongly disagree.  I want to keep TempAlloc.malloc
consistent with GC.malloc and core.stdc.stdlib.malloc.

Thanks for your review and the points you've raised.
Jun 06 2011
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 06 Jun 2011 15:10:49 -0400, dsimcha <dsimcha yahoo.com> wrote:


 == Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article



 alignedMalloc:
 I seriously question having such a feature.  According to my C++ book
 malloc returns a pointer "suitably aligned for any type".  According to
 Microsoft, malloc is 16-byte aligned (of course, D doesn't use  
 microsoft's
 runtime, DMC doesn't seem to identify alignment in malloc docs).  GNU
 appears to guarantee 8-byte alignment on 32-bit systems, 16 on 64-bit
 systems (making this function mostly useless on 64-bit dmd).
 There are also some posix functions that align a malloc to a requested
 size (see memalign).


 I definitely need it in the implementation of TempAlloc, so it's gonna  
 be there
 but it can be made private if there's a consensus that it's not needed  
 in the
 public API.


What about in the cases where malloc aligns to 16 bits (i.e. on 32-bit  
windows or 64-bit linux)?  Does this not seem like a waste of 16 bytes?


 At the very least, the function should identify what the alignment is if
 you *don't* use it.  I'd like to see a good use case for this feature in
 an example, otherwise, I think it should be killed.


 The alignment if you don't use it depends on the C malloc function for  
 your
 platform.


Which should be minimum 8 byte aligned (required by doubles).  In my C++  
book it says "suitably aligned for any type".  I would say this is likely  
a requirement for any C compiler.

Essentially, I would say that malloc on 32-bit systems must be at least  
8-byte aligned, but could already be 16-byte aligned.


 A use case might be if you need 16-byte aligned arrays to use SSE
 instructions, but that's hard to demonstrate in a short example.


It doesn't have to be complete, just something showing the allocation and  
the usage which requires 16-byte alignment.


 That being said, wrapping malloc might have some nice other features  
 too.
 I like the auto-adding of the range to the GC.
 tempdup:
 1. If this uses ElemType!(R)[] as the return type, duping a char[] will
 give you a dchar[].  I don't think this is very desirable.


 This seems right to me.  tempdup() is supposed to be basically a  
 TempAlloc version
 of array().  IMHO it should **ALWAYS** return a random-access range.   
 Returning a
 narrow string creates an obscure special case where it doesn't.


I expected it to be a TempAlloc version of .dup.

IMO, it should return an array, which char[] is.  Note that an array *is*  
random access, despite what std.range is telling you :)

counter case:

assert(is(typeof(str) == char[]));
str = str.tempdup; // ensure allocation on the tempstack.

Also, note that newStack!char(50) works and seems inconsistent with your  
choice for tempdup.


 2. What happens for something like immutable(uint *)[]?  Does it become
 uint *[]?  Because that would be bad...


 No.  It becomes an immutable(uint*)[].  ElementType!(immutable(uint*)[])  
 ==
 immutable(uint*).


I am looking at Unqual, which according to D's documentation, removes all  
qualifiers.  But testing shows that this isn't the case.  The  
documentation seems very sketchy on that trait, but it appears to be the  
most unqualified (!) implicitly converting type.  So I guess my gripe is  
more with std.traits' documentation than your module.


 TempAlloc.malloc:
 I don't like void * as a return value.  Would it not be more appropriate
 to use at least void[]?  I'd suggest actually for malloc to take a
 template parameter of the type to return, defaulting to void.  i.e.:
 T[] malloc(T = void)(size_t size);


 Here I'm going to have to strongly disagree.  I want to keep  
 TempAlloc.malloc
 consistent with GC.malloc and core.stdc.stdlib.malloc.


I can understand that point of view.  I just would like to avoid using  
pointers where it's not necessary.  And I especially like this:

auto buf = TempAlloc.malloc!uint(1024);

better than this:

auto buf = (cast(uint *)TempAlloc.malloc(1024 * uint.sizeof))[0..1024];

I would actually argue that GC.malloc might be better off returning  
void[].  You can always get the pointer with .ptr.

I'll also point out that as a function that is not constrained by compiler  
requirements, we have more flexibility, such as using templates.

I noticed that newStack does exactly what I'm saying, but then I question  
having two different functions that essentially do the same thing.  Is  
there a reason other than consistency with GC.malloc?

Perhaps TempAlloc.malloc should be private?  That would solve the problem.

I just thought of something else, there's newStack, but no freeStack.  It  
seems odd to use newStack to allocate and then TempAlloc.free to  
deallocate.

-Steve
Jun 06 2011
parent Daniel Gibson <metalcaedes gmail.com> writes:
Am 06.06.2011 21:40, schrieb Steven Schveighoffer:

 On Mon, 06 Jun 2011 15:10:49 -0400, dsimcha <dsimcha yahoo.com> wrote:

 == Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article

 TempAlloc.malloc:
 I don't like void * as a return value.  Would it not be more appropriate
 to use at least void[]?  I'd suggest actually for malloc to take a
 template parameter of the type to return, defaulting to void.  i.e.:
 T[] malloc(T = void)(size_t size);


 Here I'm going to have to strongly disagree.  I want to keep
 TempAlloc.malloc
 consistent with GC.malloc and core.stdc.stdlib.malloc.


 
 I can understand that point of view.  I just would like to avoid using
 pointers where it's not necessary.  And I especially like this:
 
 auto buf = TempAlloc.malloc!uint(1024);
 
 better than this:
 
 auto buf = (cast(uint *)TempAlloc.malloc(1024 * uint.sizeof))[0..1024];
 
 I would actually argue that GC.malloc might be better off returning
 void[].  You can always get the pointer with .ptr.
 


I agree. Why does GC.malloc return void* anyway?
In D1 std.gc.malloc returns void[], so GC.mallocs behaviour seems like a
step backwards to me.

Cheers,
- Daniel
Jun 06 2011
prev sibling next sibling parent Robert Clipsham <robert octarineparrot.com> writes:
On 06/06/2011 20:10, dsimcha wrote:

 Seems there's a strong consensus that the "newVoid" name sucks.  I agree in
 hindsight.  Will change.


If you made it a bit more generic, it could become uninitialized!().

// int a = void;
auto a = uninitialized!int;

// double[] a = newVoid!double(100);
auto a = uninitialized!(double[])(100);

// double[][] a = newVoid!(double[])(100, 100);
auto a = uninitialized!(double[][])(100, 100);

-- 
Robert
http://octarineparrot.com/
Jun 06 2011
prev sibling parent Lutger Blijdestijn <lutger.blijdestijn gmail.com> writes:
dsimcha wrote:


 == Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article

 alignedMalloc:
 I seriously question having such a feature.  According to my C++ book
 malloc returns a pointer "suitably aligned for any type".  According to
 Microsoft, malloc is 16-byte aligned (of course, D doesn't use
 microsoft's
 runtime, DMC doesn't seem to identify alignment in malloc docs).  GNU
 appears to guarantee 8-byte alignment on 32-bit systems, 16 on 64-bit
 systems (making this function mostly useless on 64-bit dmd).
 There are also some posix functions that align a malloc to a requested
 size (see memalign).


 
 I definitely need it in the implementation of TempAlloc, so it's gonna be
 there but it can be made private if there's a consensus that it's not
 needed in the public API.
 

 At the very least, the function should identify what the alignment is if
 you *don't* use it.  I'd like to see a good use case for this feature in
 an example, otherwise, I think it should be killed.


 
 The alignment if you don't use it depends on the C malloc function for
 your
 platform.  A use case might be if you need 16-byte aligned arrays to use
 SSE instructions, but that's hard to demonstrate in a short example.


Maybe it would be more broadly useful if the alignment could be specified, 
turning it into a portable version of posix_memalign?

http://pubs.opengroup.org/onlinepubs/009695399/functions/posix_memalign.html 

It's not my domain and use cases may be niche, but it does fit the systems 
language aspect of D.
Jun 06 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 6/6/11, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 1. If this uses ElemType!(R)[] as the return type, duping a char[] will
 give you a dchar[].  I don't think this is very desirable.


It think auto return could be used here and then inside the body:
static if (isSomeChar!(ElementType!R))
(ElementEncodingType!R)[] result;
return result;

Something like that.
Jun 06 2011
prev sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-06-06 14:47:25 -0400, "Steven Schveighoffer" 
<schveiguy yahoo.com> said:


 Particularly, this looks odd:
 
 newVoid!double
 
 What the hell does that mean? :)
 
 I suggest a name like newUninit or newRaw or something that means more  
 "uninitailized" than "no type".


recycled!double

Allocate from recycled memory (as opposed to new unspoiled memory).


-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Jun 06 2011
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
One thing I just thought of last night:

It would be nice for TempAlloc to provide a wrapper for emplace which  
allocates types on the TempAlloc stack and calls their constructor.  Would  
this be possible to add?

-Steve
Jun 08 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 6/8/2011 8:59 AM, Steven Schveighoffer wrote:

 One thing I just thought of last night:

 It would be nice for TempAlloc to provide a wrapper for emplace which
 allocates types on the TempAlloc stack and calls their constructor.
 Would this be possible to add?

 -Steve


Yeah, I don't imagine this would be hard.  I'll incorporate this and a 
bunch of other changes this weekend and release an updated proposal.
Jun 08 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
dsimcha:


 I'll incorporate this and a 
 bunch of other changes this weekend and release an updated proposal.


Have you seen my posts?
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=137627

Bye,
bearophile
Jun 08 2011
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from bearophile (bearophileHUGS lycos.com)'s article

 dsimcha:

 I'll incorporate this and a
 bunch of other changes this weekend and release an updated proposal.


 Have you seen my posts?


http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=137627

 Bye,
 bearophile


Yes.  Sorry for forgetting to reply.  They have very good suggestions and I'll
implement most of them.
Jun 08 2011