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

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.

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

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

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

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

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

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

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

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.