Helps an allocator without good reallocation capabilities:

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

Destruction welcome.


Andrei

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

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

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

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

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

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

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

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

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