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