std.allocator needs your help

[Manu]

On 24 September 2013 09:21, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

> On 9/23/13 3:12 PM, Peter Alexander wrote:
>
>> On Monday, 23 September 2013 at 21:27:36 UTC, Andrei Alexandrescu wrote:
>>
>>> That allocator would allocate more memory (I suspect there's a gcd
>>> calculation somewhere :o)) and then adjust the starting pointer of the
>>> allocated block to reach the requested alignment.
>>>
>>
>> That's quite an inefficient use of memory for large alignment sizes.
>>
>
> I don't see a way around it unless the allocator natively provides a large
> alignment size, which it would then advertise in its "alignment" constant.
> The problem is independent of this particular design.


There's an important distinction between an allocator advertising a large
allocation size (which it always uses), and an allocator being capable of
allocating a larger aligned block if requested.
Surely the advertised alignment is the alignment you will get in all cases,
even if you request a small alignment.
You should advertise a minimum and maximum alignment if that is your
solution.

 Also, how does it work with your deallocate interface? Suppose I request
>> an 0x100 aligned block of 0x100 bytes. Your alignment allocator requests
>> 0x200 from the GC, which maybe returns [0xffff0040-0xffff0240] and then
>> returns an aligned buffer from that [0xffff0100-0xffff0200]. Later, I
>> try to deallocate that buffer, which means your alignment allocator has
>> to deallocate the original buffer. Where does the alignment allocator
>> store the original GC-provided buffer ptr + size? It cannot be
>> determined from the buffer I gave it.
>>
>
> Walter noted the same issue. I'd need to think about it. A simple solution
> is to simply store the size just before the pointer returned, in a dope
> block manner.


This means if the allocator returns you memory that is already of the
desired alignment, you need to waste an entire aligned block just to store
the offset, which would have been 0.
I solve this problem by storing my allocation table in a separate hash
table, and entries in that table associate the size and also the alignment
offset. But it's not a good solution, it's still wasteful. It's just the
best option you have if you don't have any control over the system
allocator.

I also use large alignments which I've detailed in prior discussions.
Common ones are cache line (~64-256 bytes), and gpu memory page (~4k).
You can't go wasting GPU memory by overallocating every block.
It's definitely important that allocator's are able to receive an alignment
request, and give them the opportunity to fulfill a dynamic alignment
request without always resorting to an over-allocation strategy.

 I'd need a handful of good examples where the alignment must be known
>>> at runtime. Can you link to some?
>>>
>>
>> mprotect requires a pointer that is a multiple of the system page size,
>> which isn't constant.
>>
>> http://linux.die.net/man/2/**mprotect<http://linux.die.net/man/2/mprotect>
>>
>
> Thanks! I see posix_memalign is a corresponding call that returns a
> page-aligned chunk of memory. I assume calls like mmap also return
> page-aligned chunks. Indeed it is a problem for the current design that the
> alignment must be known during compilation.
>
>
>  Reading a file without buffering on Windows requires that you align the
>> destination buffer on volume sector size boundaries, which is not known
>> at compile time (although many just assume 4096).
>>
>         >
>
>> http://msdn.microsoft.com/en-**us/library/windows/desktop/**
>> cc644950(v=vs.85).aspx<http://msdn.microsoft.com/en-us/library/windows/desktop/cc644950(v=vs.85).aspx>
>>
>
> I see there's a difference between x86 and Itanium in page size...
>
> I'm trying to lean toward handling these as rare/exotic cases without
> outright eliminating them, while providing simple and efficient handling of
> alignment for the frequent cases (i.e. allocate ints at addresses multiple
> of 4 etc).
>
>
>  As I mentioned previously, you may want to also align to the cache line
>> size (for performance). This is not known at compile time (although
>> again, is often assumed in practice).
>>
>
> Indeed.
>
>
> Andrei
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20130924/8617db20/attachment.html>