May 11, 2015 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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 12, 2015 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 12, 2015 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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 15, 2015 Re: New adapter: std.allocator.quantizer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 |
Copyright © 1999-2021 by the D Language Foundation