digitalmars.D - New adapter: std.allocator.quantizer

Andrei Alexandrescu (4/4) May 07 2015 Helps an allocator without good reallocation capabilities:

Timon Gehr (3/7) May 09 2015 quantizer.d is not in the commit:

Andrei Alexandrescu (4/17) May 09 2015 How embarrassing. Thanks for letting me know.

Timon Gehr (20/40) May 09 2015 Thanks! Looks good, except:

Timon Gehr (2/4) May 09 2015 (Note that those code snippets also occur in their documentation.)

Andrei Alexandrescu (2/8) May 09 2015 Can't find "gs" in the doc comments, is it there? -- Andrei

Timon Gehr (3/12) May 10 2015 (They don't appear verbatim, but they call the parent functions with the...

Timon Gehr (4/5) May 09 2015 (Note that monotone increasing is implied by piecewise constant with one...

Andrei Alexandrescu (15/21) May 09 2015 I think the only requirements are (a) roundingFunction is pure, (b)

Timon Gehr (22/44) May 10 2015 size_t brokenRoundingFunction(size_t siz){

Andrei Alexandrescu (2/7) May 10 2015 Say no more, got it. I'll change the docs. -- Andrei

Andrei Alexandrescu (14/30) May 09 2015 Let's see, this is a tad tricky. "needed" is the needed size, i.e.

Timon Gehr (15/32) May 10 2015 Yes, but 'expand' expects a _full_ block that was allocated by that

Timon Gehr (7/15) May 10 2015 Actually, reading that snippet of the documentation, I notice more

Andrei Alexandrescu (2/19) May 10 2015 Will fix. -- Andrei
Andrei Alexandrescu (5/22) May 11 2015 Thanks again for the great review. Just updated quantizer.d, I think

Timon Gehr (9/33) May 11 2015 Unfortunately,

Timon Gehr (9/46) May 11 2015 Oh, and

Timon Gehr (2/3) May 11 2015 (Same thing further down, line 167.)
Andrei Alexandrescu (7/14) May 11 2015 Well I do find it awesome actually...

Timon Gehr (7/16) May 11 2015 Nope.

Andrei Alexandrescu (7/18) May 11 2015 Somebody shoot me :o).

Timon Gehr (4/22) May 12 2015 Missed alignedReallocate. :o)

Andrei Alexandrescu (8/33) May 15 2015 Missed this, thanks for the email! I've simplified matters a bit by

Timon Gehr (3/17) May 15 2015 I have just noticed that all the calls to alignedAllocate do not pass

Andrei Alexandrescu (3/5) May 15 2015 Crikey, that must have something to do with all that missing test

Andrei Alexandrescu (8/14) May 11 2015 Got it. That's a rather subtle requirement, so I changed the code to

Timon Gehr (5/19) May 11 2015 OK. It can make things unnecessarily slow though. (Is there any

Timon Gehr (2/9) May 11 2015 (Scrap that.)

Andrei Alexandrescu (2/4) May 10 2015 Ah, now I understand. Thanks, will fix! -- Andrei

Marco Leise (35/43) May 10 2015 I haven't tested it, but it seems useful for the cases you

Andrei Alexandrescu (16/42) May 10 2015 Yah, about that... I introduced this property as an OS interface

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

Helps an allocator without good reallocation capabilities:

http://erdani.com/d/phobos-prerelease/std_experimental_allocator_quantizer.html

Destruction welcome.


Andrei

May 07 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/07/2015 11:12 PM, Andrei Alexandrescu wrote:
 Helps an allocator without good reallocation capabilities:

 http://erdani.com/d/phobos-prerelease/std_experimental_allocator_quantizer.html


 Destruction welcome.


 Andrei

quantizer.d is not in the commit: 
https://github.com/andralex/phobos/commit/1b75d3e9dfc37f1d074e217dee2931463dec5191

May 09 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/9/15 6:27 AM, Timon Gehr wrote:
 On 05/07/2015 11:12 PM, Andrei Alexandrescu wrote:
 Helps an allocator without good reallocation capabilities:

 http://erdani.com/d/phobos-prerelease/std_experimental_allocator_quantizer.html



 Destruction welcome.


 Andrei

 quantizer.d is not in the commit:
 https://github.com/andralex/phobos/commit/1b75d3e9dfc37f1d074e217dee2931463dec5191

How embarrassing. Thanks for letting me know.

https://github.com/D-Programming-Language/phobos/commit/c23913b9082a4dda9156314645e011eaa0a3af8c

Andrei

May 09 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/09/2015 06:09 PM, Andrei Alexandrescu wrote:
 On 5/9/15 6:27 AM, Timon Gehr wrote:
 On 05/07/2015 11:12 PM, Andrei Alexandrescu wrote:
 Helps an allocator without good reallocation capabilities:

 http://erdani.com/d/phobos-prerelease/std_experimental_allocator_quantizer.html




 Destruction welcome.


 Andrei

 quantizer.d is not in the commit:
 https://github.com/andralex/phobos/commit/1b75d3e9dfc37f1d074e217dee2931463dec5191

 How embarrassing. Thanks for letting me know.

 https://github.com/D-Programming-Language/phobos/commit/c23913b9082a4dda9156314645e011eaa0a3af8c


 Andrei

Thanks! Looks good, except:

106| if (!parent.expand(b, goodAllocSize(needed) - b.length))

142| return parent.reallocate(b, gs);

172| return parent.alignedReallocate(b, gs, a);

Those should be more like:

182| parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)]);


Another point is that the documented/checked constraints on the rounding 
function are too weak. A rounding function should be monotone increasing 
and piecewise constant with one fixed point per piece.

In case the given function does not have those properties, a call to 
'expand' can destroy the invariant that the memory block of b is always 
of size goodAllocSize(b.length).




And then, there's this, of course:

size_t goodAllocSize(size_t n);
     Returns roundingFunction(n). It is required that 
roundingFunction(n) >= n. For efficiency reasons, this is only asserted 
(checked in debug mode).

Is this meant to be a complete specification of 'assert'? :o)
What is 'debug mode'?

May 09 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/10/2015 12:38 AM, Timon Gehr wrote:
 142| return parent.reallocate(b, gs);

 172| return parent.alignedReallocate(b, gs, a);

(Note that those code snippets also occur in their documentation.)

May 09 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/9/15 3:41 PM, Timon Gehr wrote:
 On 05/10/2015 12:38 AM, Timon Gehr wrote:
 142| return parent.reallocate(b, gs);

 172| return parent.alignedReallocate(b, gs, a);

 (Note that those code snippets also occur in their documentation.)

Can't find "gs" in the doc comments, is it there? -- Andrei

May 09 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/10/2015 05:32 AM, Andrei Alexandrescu wrote:
 On 5/9/15 3:41 PM, Timon Gehr wrote:
 On 05/10/2015 12:38 AM, Timon Gehr wrote:
 142| return parent.reallocate(b, gs);

 172| return parent.alignedReallocate(b, gs, a);

 (Note that those code snippets also occur in their documentation.)

 Can't find "gs" in the doc comments, is it there? -- Andrei

(They don't appear verbatim, but they call the parent functions with the 
plain 'b' in the documentation as well.)

May 10 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/10/2015 12:38 AM, Timon Gehr wrote:
 monotone increasing and piecewise constant with one fixed point per piece.

(Note that monotone increasing is implied by piecewise constant with one 
fixed point per piece, so it does not necessarily need to be documented 
separately.)

May 09 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/9/15 3:54 PM, Timon Gehr wrote:
 On 05/10/2015 12:38 AM, Timon Gehr wrote:
 monotone increasing and piecewise constant with one fixed point per
 piece.

 (Note that monotone increasing is implied by piecewise constant with one
 fixed point per piece, so it does not necessarily need to be documented
 separately.)

I think the only requirements are (a) roundingFunction is pure, (b) 
roundingFunction(n) >= n. E.g. the identity function works, although 
it's not terribly useful.

These could be enforced by Quantizer, but it doesn't feel right. A 
designer who is at the same time sophisticated enough to need Quantizer 
yet naïve enough to choose a lousy one is quite unlikely. On the other 
hand, I can imagine stuff like this could be useful to some:

__gshared uint SMALL_ALLOC = 64;
... configure it via an application-level flag...
alias MyAlloc = Quantizer!(
     FreeTree!GCAllocator,
     n => n.roundUpToMultipleOf(n <= SMALL_ALLOC ? 64 : 4096));

That's technically not pure but works, and might be appreciated.


Andrei

May 09 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/10/2015 05:38 AM, Andrei Alexandrescu wrote:
 On 5/9/15 3:54 PM, Timon Gehr wrote:
 On 05/10/2015 12:38 AM, Timon Gehr wrote:
 monotone increasing and piecewise constant with one fixed point per
 piece.

 (Note that monotone increasing is implied by piecewise constant with one
 fixed point per piece, so it does not necessarily need to be documented
 separately.)

 I think the only requirements are (a) roundingFunction is pure, (b)
 roundingFunction(n) >= n. E.g. the identity function works, although
 it's not terribly useful.

 These could be enforced by Quantizer, but it doesn't feel right. A
 designer who is at the same time sophisticated enough to need Quantizer
 yet naïve enough to choose a lousy one is quite unlikely. On the other
 hand, I can imagine stuff like this could be useful to some:

 __gshared uint SMALL_ALLOC = 64;
 ... configure it via an application-level flag...
 alias MyAlloc = Quantizer!(
      FreeTree!GCAllocator,
      n => n.roundUpToMultipleOf(n <= SMALL_ALLOC ? 64 : 4096));

 That's technically not pure but works, and might be appreciated.


 Andrei

size_t brokenRoundingFunction(size_t siz){
     if(siz==10) return 40;
     if(siz==20) return 30;
     return siz;
}

alias BrokenAlloc = Quantizer!(
     SomeAllocatorThatReliesOnProvidedBlockSize,
     brokenRoundingFunction
);

void main(){
     BrokenAlloc borked;
     // allocate buffer of size 40, slice 10 bytes off it:
     auto b=borked.allocate(10);
     // awesome, can expand in-place since 20 <= 40:
     borked.expand(a,10);
     // oops, now we try to deallocate a block of size 30
     // from the parent, even though the allocated size
     // is 40:
     borked.deallocate(a);
}

(Untested, but it should wreak some havoc.)

May 10 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/10/15 5:02 AM, Timon Gehr wrote:
 size_t brokenRoundingFunction(size_t siz){
      if(siz==10) return 40;
      if(siz==20) return 30;
      return siz;
 }

Say no more, got it. I'll change the docs. -- Andrei

May 10 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/9/15 3:38 PM, Timon Gehr wrote:
 Thanks! Looks good, except:

 106| if (!parent.expand(b, goodAllocSize(needed) - b.length))

Let's see, this is a tad tricky. "needed" is the needed size, i.e. 
b.length + delta. We want to expand to a final size of 
goodAllocSize(needed). So we need to pass the appropriate delta to 
expand, i.e. goodAllocSize(needed) - b.length.

(recall that expand() takes the delta, not the new size)

 142| return parent.reallocate(b, gs);

gs is precomputed at the top of the function to be goodAllocSize(s), so 
this seems to be in good shape.

 172| return parent.alignedReallocate(b, gs, a);

Same here, the intent is to reallocate to goodAllocSize(s), which is 
precomputed in gs.

 Those should be more like:

 182| parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)]);


 Another point is that the documented/checked constraints on the rounding
 function are too weak. A rounding function should be monotone increasing
 and piecewise constant with one fixed point per piece.

Agreed, I see there's a bit of follow-up so I'll reply to that.

 And then, there's this, of course:

 size_t goodAllocSize(size_t n);
      Returns roundingFunction(n). It is required that
 roundingFunction(n) >= n. For efficiency reasons, this is only asserted
 (checked in debug mode).

 Is this meant to be a complete specification of 'assert'? :o)
 What is 'debug mode'?

Good point. Fixed the docs: 
https://github.com/andralex/phobos/blob/allocator/std/experimental/allocator/quantizer.d


Andrei

May 09 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/10/2015 05:29 AM, Andrei Alexandrescu wrote:
 On 5/9/15 3:38 PM, Timon Gehr wrote:
 Thanks! Looks good, except:

 106| if (!parent.expand(b, goodAllocSize(needed) - b.length))

 Let's see, this is a tad tricky. "needed" is the needed size, i.e.
 b.length + delta. We want to expand to a final size of
 goodAllocSize(needed). So we need to pass the appropriate delta to
 expand, i.e. goodAllocSize(needed) - b.length.

 (recall that expand() takes the delta, not the new size)
 ...

Yes, but 'expand' expects a _full_ block that was allocated by that 
allocator:

"bool expand(ref void[] b, size_t delta);
Post: !result || b.length == old(b).length + delta 	Expands b by delta 
bytes. If delta == 0, succeeds without changing b. If b is null, the 
call evaluates b = allocate(delta) and returns b !is null. Otherwise, *b 
must be a buffer previously allocated with the same allocator*. If 
expansion was successful, expand changes b's length to b.length + delta 
and returns true. Upon failure, the call effects no change upon the 
allocator object, leaves b unchanged, and returns false."

 142| return parent.reallocate(b, gs);

 gs is precomputed at the top of the function to be goodAllocSize(s), so
 this seems to be in good shape.

 172| return parent.alignedReallocate(b, gs, a);

 Same here, the intent is to reallocate to goodAllocSize(s), which is
 precomputed in gs.
 ...

I think there has been a misunderstanding here, probably I wasn't 
specific enough. 'b' is a slice of the block that was allocated by the 
parent allocator. Its size will generally be smaller than what the 
parent allocator expects.

May 10 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/10/2015 01:48 PM, Timon Gehr wrote:
 "bool expand(ref void[] b, size_t delta);
 Post: !result || b.length == old(b).length + delta     Expands b by
 delta bytes. If delta == 0, succeeds without changing b. If b is null,
 the call evaluates b = allocate(delta) and returns b !is null.
 Otherwise, *b must be a buffer previously allocated with the same
 allocator*. If expansion was successful, expand changes b's length to
 b.length + delta and returns true. Upon failure, the call effects no
 change upon the allocator object, leaves b unchanged, and returns false."

Actually, reading that snippet of the documentation, I notice more 
problems in the implementation of expand/the documentation of the 
rounding function.

If the rounding function returns a non-zero result for a zero argument, 
expand can return invalid memory (starting from address 0) if given an 
empty block 'b'.

May 10 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/10/15 5:08 AM, Timon Gehr wrote:
 On 05/10/2015 01:48 PM, Timon Gehr wrote:
 "bool expand(ref void[] b, size_t delta);
 Post: !result || b.length == old(b).length + delta     Expands b by
 delta bytes. If delta == 0, succeeds without changing b. If b is null,
 the call evaluates b = allocate(delta) and returns b !is null.
 Otherwise, *b must be a buffer previously allocated with the same
 allocator*. If expansion was successful, expand changes b's length to
 b.length + delta and returns true. Upon failure, the call effects no
 change upon the allocator object, leaves b unchanged, and returns false."

 Actually, reading that snippet of the documentation, I notice more
 problems in the implementation of expand/the documentation of the
 rounding function.

 If the rounding function returns a non-zero result for a zero argument,
 expand can return invalid memory (starting from address 0) if given an
 empty block 'b'.

Will fix. -- Andrei

May 10 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/10/15 5:08 AM, Timon Gehr wrote:
 On 05/10/2015 01:48 PM, Timon Gehr wrote:
 "bool expand(ref void[] b, size_t delta);
 Post: !result || b.length == old(b).length + delta     Expands b by
 delta bytes. If delta == 0, succeeds without changing b. If b is null,
 the call evaluates b = allocate(delta) and returns b !is null.
 Otherwise, *b must be a buffer previously allocated with the same
 allocator*. If expansion was successful, expand changes b's length to
 b.length + delta and returns true. Upon failure, the call effects no
 change upon the allocator object, leaves b unchanged, and returns false."

 Actually, reading that snippet of the documentation, I notice more
 problems in the implementation of expand/the documentation of the
 rounding function.

 If the rounding function returns a non-zero result for a zero argument,
 expand can return invalid memory (starting from address 0) if given an
 empty block 'b'.

Thanks again for the great review. Just updated quantizer.d, I think 
I've addressed all points:

https://github.com/andralex/phobos/blob/allocator/std/experimental/allocator/quantizer.d


Andrei

May 11 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/11/2015 05:28 PM, Andrei Alexandrescu wrote:
 On 5/10/15 5:08 AM, Timon Gehr wrote:
 On 05/10/2015 01:48 PM, Timon Gehr wrote:
 "bool expand(ref void[] b, size_t delta);
 Post: !result || b.length == old(b).length + delta     Expands b by
 delta bytes. If delta == 0, succeeds without changing b. If b is null,
 the call evaluates b = allocate(delta) and returns b !is null.
 Otherwise, *b must be a buffer previously allocated with the same
 allocator*. If expansion was successful, expand changes b's length to
 b.length + delta and returns true. Upon failure, the call effects no
 change upon the allocator object, leaves b unchanged, and returns
 false."

 Actually, reading that snippet of the documentation, I notice more
 problems in the implementation of expand/the documentation of the
 rounding function.

 If the rounding function returns a non-zero result for a zero argument,
 expand can return invalid memory (starting from address 0) if given an
 empty block 'b'.

 Thanks again for the great review.

No problem!

 Just updated quantizer.d, I think I've addressed all points:

 https://github.com/andralex/phobos/blob/allocator/std/experimental/allocator/quantizer.d


Unfortunately,

- If the rounding function is not piecewise constant with one fixed 
point per piece, it can happen that 'allocated >= needed' but 'allocated 
< goodAllocSize(needed)'. Then, the allocated size will be inconsistent 
with goodAllocSize. (This is why I recommended to require the rounding 
function to have this property, which is stronger than monotonicity.)

- If b.ptr is null, then line 113 is bad in case goodAllocSize(0) > 0.

May 11 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/11/2015 08:06 PM, Timon Gehr wrote:
 On 05/11/2015 05:28 PM, Andrei Alexandrescu wrote:
 On 5/10/15 5:08 AM, Timon Gehr wrote:
 On 05/10/2015 01:48 PM, Timon Gehr wrote:
 "bool expand(ref void[] b, size_t delta);
 Post: !result || b.length == old(b).length + delta     Expands b by
 delta bytes. If delta == 0, succeeds without changing b. If b is null,
 the call evaluates b = allocate(delta) and returns b !is null.
 Otherwise, *b must be a buffer previously allocated with the same
 allocator*. If expansion was successful, expand changes b's length to
 b.length + delta and returns true. Upon failure, the call effects no
 change upon the allocator object, leaves b unchanged, and returns
 false."

 Actually, reading that snippet of the documentation, I notice more
 problems in the implementation of expand/the documentation of the
 rounding function.

 If the rounding function returns a non-zero result for a zero argument,
 expand can return invalid memory (starting from address 0) if given an
 empty block 'b'.

 Thanks again for the great review.

 No problem!

 Just updated quantizer.d, I think I've addressed all points:

 https://github.com/andralex/phobos/blob/allocator/std/experimental/allocator/quantizer.d


 Unfortunately,

 - If the rounding function is not piecewise constant with one fixed
 point per piece, it can happen that 'allocated >= needed' but 'allocated
 < goodAllocSize(needed)'. Then, the allocated size will be inconsistent
 with goodAllocSize. (This is why I recommended to require the rounding
 function to have this property, which is stronger than monotonicity.)

 - If b.ptr is null, then line 113 is bad in case goodAllocSize(0) > 0.

Oh, and

- The assertion in line 141 may fail. (expand can return false.)
   (Rant: Go on, conflate assert and assume in -release and then, when a 
sufficiently smart optimizer runs, suddenly expand will always return 
true and user code that checks for success of expand will be removed. 
Awesome.)

- 'expand' ought to call 'allocate' when passed an empty buffer in case 
the parent does not define 'expand', no?

May 11 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/11/2015 08:31 PM, Timon Gehr wrote:
 - The assertion in line 141 may fail. (expand can return false.)

(Same thing further down, line 167.)

May 11 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/11/15 11:31 AM, Timon Gehr wrote:
 - The assertion in line 141 may fail. (expand can return false.)

OK, it seems the previous commit should take care of that.

    (Rant: Go on, conflate assert and assume in -release and then, when a
 sufficiently smart optimizer runs, suddenly expand will always return
 true and user code that checks for success of expand will be removed.
 Awesome.)

Well I do find it awesome actually...

 - 'expand' ought to call 'allocate' when passed an empty buffer in case
 the parent does not define 'expand', no?

Yah, in fact it suffices to call allocate() whether or not the parent 
defines expand(). So I did so in 
https://github.com/andralex/phobos/commit/9307b9f8969b7bfd0906e0441a13cbbded7f8418.


Andrei

May 11 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/11/2015 08:48 PM, Andrei Alexandrescu wrote:
 On 5/11/15 11:31 AM, Timon Gehr wrote:
 - The assertion in line 141 may fail. (expand can return false.)

 OK, it seems the previous commit should take care of that.
 ...

Nope.

Well, yes, in the sense that there is no longer a possibly failing 
assertion on line 141.

In any case, 'allocate' within 'expand' may fail, and if it does, b.ptr 
will still be null throughout the body of reallocate/alignedReallocate.

 - 'expand' ought to call 'allocate' when passed an empty buffer in case
 the parent does not define 'expand', no?

 Yah, in fact it suffices to call allocate() whether or not the parent
 defines expand(). So I did so in
 https://github.com/andralex/phobos/commit/9307b9f8969b7bfd0906e0441a13cbbded7f8418.

OK.

May 11 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/11/15 4:59 PM, Timon Gehr wrote:
 On 05/11/2015 08:48 PM, Andrei Alexandrescu wrote:
 On 5/11/15 11:31 AM, Timon Gehr wrote:
 - The assertion in line 141 may fail. (expand can return false.)

 OK, it seems the previous commit should take care of that.
 ...

 Nope.

 Well, yes, in the sense that there is no longer a possibly failing
 assertion on line 141.

 In any case, 'allocate' within 'expand' may fail, and if it does, b.ptr
 will still be null throughout the body of reallocate/alignedReallocate.

Somebody shoot me :o).

https://github.com/andralex/phobos/commit/18d5cd9526db5057cacff5832a6246d1f84ada2a

My code is not up with my ambitions, I wonder how many bugs I have in 
the as-of-yet not reviewed allocator work.


Thanks,

Andrei

May 11 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/12/2015 04:54 AM, Andrei Alexandrescu wrote:
 On 5/11/15 4:59 PM, Timon Gehr wrote:
 On 05/11/2015 08:48 PM, Andrei Alexandrescu wrote:
 On 5/11/15 11:31 AM, Timon Gehr wrote:
 - The assertion in line 141 may fail. (expand can return false.)

 OK, it seems the previous commit should take care of that.
 ...

 Nope.

 Well, yes, in the sense that there is no longer a possibly failing
 assertion on line 141.

 In any case, 'allocate' within 'expand' may fail, and if it does, b.ptr
 will still be null throughout the body of reallocate/alignedReallocate.

 Somebody shoot me :o).

 https://github.com/andralex/phobos/commit/18d5cd9526db5057cacff5832a6246d1f84ada2a
 ...

Missed alignedReallocate. :o)

On a related note, alignedReallocate is now also buggy in that it does 
not necessarily align the allocated memory if b.ptr is null.

May 12 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/12/15 12:57 PM, Timon Gehr wrote:
 On 05/12/2015 04:54 AM, Andrei Alexandrescu wrote:
 On 5/11/15 4:59 PM, Timon Gehr wrote:
 On 05/11/2015 08:48 PM, Andrei Alexandrescu wrote:
 On 5/11/15 11:31 AM, Timon Gehr wrote:
 - The assertion in line 141 may fail. (expand can return false.)

 OK, it seems the previous commit should take care of that.
 ...

 Nope.

 Well, yes, in the sense that there is no longer a possibly failing
 assertion on line 141.

 In any case, 'allocate' within 'expand' may fail, and if it does, b.ptr
 will still be null throughout the body of reallocate/alignedReallocate.

 Somebody shoot me :o).

 https://github.com/andralex/phobos/commit/18d5cd9526db5057cacff5832a6246d1f84ada2a

 ...

 Missed alignedReallocate. :o)

 On a related note, alignedReallocate is now also buggy in that it does
 not necessarily align the allocated memory if b.ptr is null.

Missed this, thanks for the email! I've simplified matters a bit by 
testing for null up front:

https://github.com/andralex/phobos/commit/af0abf6adb325cf57f2ef0f07bf787ebb1351288

I suspect the other allocators have similar issues though... I'll need 
to make a careful pass.


Thanks!!

Andrei

May 15 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/15/2015 06:58 PM, Andrei Alexandrescu wrote:
 On 5/12/15 12:57 PM, Timon Gehr wrote:
 ...

 Missed alignedReallocate. :o)

 On a related note, alignedReallocate is now also buggy in that it does
 not necessarily align the allocated memory if b.ptr is null.

 Missed this, thanks for the email! I've simplified matters a bit by
 testing for null up front:

 https://github.com/andralex/phobos/commit/af0abf6adb325cf57f2ef0f07bf787ebb1351288


 I suspect the other allocators have similar issues though... I'll need
 to make a careful pass.


 Thanks!!

 Andrei

I have just noticed that all the calls to alignedAllocate do not pass 
the alignment argument.

May 15 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/15/15 1:28 PM, Timon Gehr wrote:
 I have just noticed that all the calls to alignedAllocate do not pass
 the alignment argument.

Crikey, that must have something to do with all that missing test 
coverage :o). -- Andrei

May 15 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/11/15 11:06 AM, Timon Gehr wrote:
 - If the rounding function is not piecewise constant with one fixed
 point per piece, it can happen that 'allocated >= needed' but 'allocated
 < goodAllocSize(needed)'. Then, the allocated size will be inconsistent
 with goodAllocSize. (This is why I recommended to require the rounding
 function to have this property, which is stronger than monotonicity.)

Got it. That's a rather subtle requirement, so I changed the code to 
keep things simple for the user:

https://github.com/andralex/phobos/commit/9307b9f8969b7bfd0906e0441a13cbbded7f8418

 - If b.ptr is null, then line 113 is bad in case goodAllocSize(0) > 0.

That should be fixed in the same commit; I just handle expansion of null 
blocks up front in expand().


Thanks,

Andrei

May 11 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/11/2015 08:45 PM, Andrei Alexandrescu wrote:
 On 5/11/15 11:06 AM, Timon Gehr wrote:
 - If the rounding function is not piecewise constant with one fixed
 point per piece, it can happen that 'allocated >= needed' but 'allocated
 < goodAllocSize(needed)'. Then, the allocated size will be inconsistent
 with goodAllocSize. (This is why I recommended to require the rounding
 function to have this property, which is stronger than monotonicity.)

 Got it. That's a rather subtle requirement, so I changed the code to
 keep things simple for the user:

 https://github.com/andralex/phobos/commit/9307b9f8969b7bfd0906e0441a13cbbded7f8418
 ...

OK. It can make things unnecessarily slow though. (Is there any 
compelling use case for a Quantizer that always leaves some unused slack 
space, no matter the allocation size?)

 - If b.ptr is null, then line 113 is bad in case goodAllocSize(0) > 0.

 That should be fixed in the same commit; I just handle expansion of null
 blocks up front in expand().
 ...

OK.

May 11 2015

Timon Gehr <timon.gehr gmx.ch> writes:

On 05/12/2015 01:38 AM, Timon Gehr wrote:
 - If b.ptr is null, then line 113 is bad in case goodAllocSize(0) > 0.

 That should be fixed in the same commit; I just handle expansion of null
 blocks up front in expand().
 ...

 OK.

(Scrap that.)

May 11 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/10/15 4:48 AM, Timon Gehr wrote:
 Yes, but 'expand' expects a _full_ block that was allocated by that
 allocator:

Ah, now I understand. Thanks, will fix! -- Andrei

May 10 2015

Marco Leise <Marco.Leise gmx.de> writes:

Am Thu, 07 May 2015 14:12:40 -0700
schrieb Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:

 Helps an allocator without good reallocation capabilities:
 
 http://erdani.com/d/phobos-prerelease/std_experimental_allocator_quantizer.html
 
 Destruction welcome.
 
 
 Andrei

I haven't tested it, but it seems useful for the cases you
listed in the documentation. While writing dynamic arrays I
remember I had some thoughts about features you used as well:

* "zeroesAllocations"
  I called it "elementsAreInited" and as the name suggests, it
  tells whether new elements receive their T.init
  automatically.
  Now std.allocator deals mostly with raw memory, so zeroing
  is the only option, but I can see some friction coming up
  when typed allocators are built on those.
  Typed allocators backed by a "zeroesAllocations"
  allocator could overwrite the memory 3 times: zeroing,
  T.init, ctor assignments.
  
  a) Could the parent allocator be informed that it does not
     need to zero initialize because we will blit T.init over
     the memory anyways?

  b) If we get zeroed memory, can the typed allocator know at
     compile-time that T.init is all zeroes and elide the blit?

* "roundingFunction"
  This is like a growth function, right? I often have some
  default lying around, but it is sure good to be able to
  provide your own. My default is: n' = n + (n >> 1) + 4
  One thing that could go wrong is that on 32-bit you pick a
  new size like n'=2*n and you just don't find enough
  contiguous virtual memory.
  
  a) On allocation failure the growth function is ignored and
     the minimal required size used.

  b) The growth function needs to be designed more carefully,
     putting the effort on the user.

-- 
Marco

May 10 2015

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 5/10/15 12:52 AM, Marco Leise wrote:
 * "zeroesAllocations"
    I called it "elementsAreInited" and as the name suggests, it
    tells whether new elements receive their T.init
    automatically.
    Now std.allocator deals mostly with raw memory, so zeroing
    is the only option, but I can see some friction coming up
    when typed allocators are built on those.
    Typed allocators backed by a "zeroesAllocations"
    allocator could overwrite the memory 3 times: zeroing,
    T.init, ctor assignments.

    a) Could the parent allocator be informed that it does not
       need to zero initialize because we will blit T.init over
       the memory anyways?

    b) If we get zeroed memory, can the typed allocator know at
       compile-time that T.init is all zeroes and elide the blit?

Yah, about that... I introduced this property as an OS interface 
courtesy - there are functions that already zero memory so it's wasteful 
to zero it again if that's all that's needed.

Sadly I found little if any interesting properties of this, and for 
anything that's not zero there's no gain - either the allocator does it 
or emplace() etc. does.

Long story short is I'm considering just dropping that.

 * "roundingFunction"
    This is like a growth function, right? I often have some
    default lying around, but it is sure good to be able to
    provide your own. My default is: n' = n + (n >> 1) + 4
    One thing that could go wrong is that on 32-bit you pick a
    new size like n'=2*n and you just don't find enough
    contiguous virtual memory.

    a) On allocation failure the growth function is ignored and
       the minimal required size used.

    b) The growth function needs to be designed more carefully,
       putting the effort on the user.

This is not growth. Growth is "I have an array of size n and plan to 
append an unspecified number of elements to it, what's a good function 
that takes n and gives me a larger number?"

Quantization is different. What's happening here is you're reducing a 
large set of integer to a smaller number of quantas. That way you are 
overallocating (so indeed growth properties are nicer) but also reducing 
the total set of distinct sizes that the allocator needs to deal with.


Andrei

May 10 2015

D Programming

C/C++ Programming

Other

digitalmars.D - New adapter: std.allocator.quantizer