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?

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.)

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

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

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.

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.)

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.

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

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.

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