3 ms·

Unless all objects allocated by the library have one of the fundamental alignment requirements, I'd add a fourth item to the checklist: 4. All functions take

Unless all objects allocated by the library have one of the fundamental alignment requirements, I'd add a fourth item to the checklist: 4. All functions take the alignment requirement as a parameter. The alignment requirement must be a power of 2. The reallocation and deallocation functions must be passed the same alignment requirement value as was passed to the allocation function when the block was first allocated. A common motivation for rolling out your custom allocator is dealing with extended alignment requirements. This should be reflected in the allocator's API.

eqvinox 3y ago
Alternatively, "the allocator should have an equivalent of posix_memalign()". Also the default alignment should be well documented, since 99% of calls won't care about a specific alignment, and then you start hunting why your math routines are slow when the CPU is doing unaligned SIMD loads…
- el_pollo_diablo 3y ago
  C11 has aligned_alloc, which is more standard than posix_memalign, but there is no standard "aligned_realloc". There is no default alignment if all the functions of the allocator take it as a parameter, but it is reasonable for an allocator implementation to be optimized for a particular alignment requirement such as _Alignof(max_align_t).
  - eqvinox 3y ago
    > C11 has aligned_alloc, which is more standard than posix_memalign, I don't have data on this but I feel that posix_memalign might be more widely supported than aligned_alloc. Then again C11 is 12 years old now so hopefully this changed. > There is no default alignment if all the functions of the allocator take it as a parameter, I would assume you can pass 0 as the requested alignment, which makes the allocator use some default. If the allocator always requires an alignment value, it becomes a serious pain to go through all allocations and figure out a reasonable alignment value. Especially since in most cases you really don't care.
    - el_pollo_diablo 3y ago
      > I don't have data on this but I feel that posix_memalign might be more widely supported than aligned_alloc. Possibly. IIRC Microsoft's CRT does not support aligned_alloc() because their implementation of free() cannot deal with extended alignment requirements, so they have separate functions for aligned (de)allocation. To be fair, they probably do not support posix_memalign() either. > it becomes a serious pain to go through all allocations and figure out a reasonable alignment value Sure, you can pass _Alignof(max_align_t) in almost all cases, or have generic (= not reimplemented by each allocator) convenience wrapper functions that do that for you. If you want to pass the least restrictive alignment in all cases, you can enlist the help of a macro, but this is a bit more awkward. For instance: #define ALLOC(ptr, size) ((ptr) = alloc(_Alignof(typeof(*(ptr))), (size))) foo_t *p; ALLOC(p, 42 * sizeof *p); (Note that this uses the typeof() operator, which should become standard with C23.)
      - tlb 3y ago
        max_align_t is only the max for scalar types, typically 8 or 16 bytes. But often math-intensive code wants 16 or 32 byte alignment for float arrays, to enable SIMD operations.
        el_pollo_diablo 3y ago
        > max_align_t is only the max for scalar types, typically 8 or 16 bytes. But often math-intensive code wants 16 or 32 byte alignment for float arrays, to enable SIMD operations. Indeed, but _Alignof(max_align_t) is a good compromise for a default alignment requirement in an allocator interface, which is what eqvinox calls for. Standard C does exactly that: malloc(), realloc(), and calloc() promise that they satisfy _Alignof(max_align_t), but nothing stricter. To reach for extended alignment requirements, your only standard tool is aligned_alloc().
gpvos 3y ago
The context parameter already addresses that need.
- el_pollo_diablo 3y ago
  > The context parameter already addresses that need. How so? The context parameter identifies the allocator instance. What if the library needs to allocate objects with different alignment requirements with the same allocator instance? Alignment requirement is just like allocation size (*). It varies from call to call, and generic allocators need to deal with heterogeneous alignments and sizes. (*) Case in point: Rust's Allocator interface (https://doc.rust-lang.org/std/alloc/trait.Allocator.html https://doc.rust-lang.org/std/alloc/trait.Allocator.html) bundles them up in a single Layout object.
- flohofwoe 3y ago
  Not really I think, the context pointer (I would call it "user data" though since that's more common in the C world) is normally passed around as an opaque pointer which is used by the allocator functions to find their own state, but not for passing additional parameters to the allocator.
  - gpvos 3y ago
    I guess you're right. The alignment parameter may be different per allocation, not per arena/context.
kevincox 3y ago
While you are at it passing the size of the allocation during free can also be valuable and is usually available "for free".
- el_pollo_diablo 3y ago
  Yes, that's item 2 of the checklist in the original article.

eqvinox 3y ago

Alternatively, "the allocator should have an equivalent of posix_memalign()". Also the default alignment should be well documented, since 99% of calls won't care about a specific alignment, and then you start hunting why your math routines are slow when the CPU is doing unaligned SIMD loads…

el_pollo_diablo 3y ago
C11 has aligned_alloc, which is more standard than posix_memalign, but there is no standard "aligned_realloc". There is no default alignment if all the functions of the allocator take it as a parameter, but it is reasonable for an allocator implementation to be optimized for a particular alignment requirement such as _Alignof(max_align_t).
- eqvinox 3y ago
  > C11 has aligned_alloc, which is more standard than posix_memalign, I don't have data on this but I feel that posix_memalign might be more widely supported than aligned_alloc. Then again C11 is 12 years old now so hopefully this changed. > There is no default alignment if all the functions of the allocator take it as a parameter, I would assume you can pass 0 as the requested alignment, which makes the allocator use some default. If the allocator always requires an alignment value, it becomes a serious pain to go through all allocations and figure out a reasonable alignment value. Especially since in most cases you really don't care.
  - el_pollo_diablo 3y ago
    > I don't have data on this but I feel that posix_memalign might be more widely supported than aligned_alloc. Possibly. IIRC Microsoft's CRT does not support aligned_alloc() because their implementation of free() cannot deal with extended alignment requirements, so they have separate functions for aligned (de)allocation. To be fair, they probably do not support posix_memalign() either. > it becomes a serious pain to go through all allocations and figure out a reasonable alignment value Sure, you can pass _Alignof(max_align_t) in almost all cases, or have generic (= not reimplemented by each allocator) convenience wrapper functions that do that for you. If you want to pass the least restrictive alignment in all cases, you can enlist the help of a macro, but this is a bit more awkward. For instance: #define ALLOC(ptr, size) ((ptr) = alloc(_Alignof(typeof(*(ptr))), (size))) foo_t *p; ALLOC(p, 42 * sizeof *p); (Note that this uses the typeof() operator, which should become standard with C23.)
    - tlb 3y ago
      max_align_t is only the max for scalar types, typically 8 or 16 bytes. But often math-intensive code wants 16 or 32 byte alignment for float arrays, to enable SIMD operations.
      - el_pollo_diablo 3y ago
        > max_align_t is only the max for scalar types, typically 8 or 16 bytes. But often math-intensive code wants 16 or 32 byte alignment for float arrays, to enable SIMD operations. Indeed, but _Alignof(max_align_t) is a good compromise for a default alignment requirement in an allocator interface, which is what eqvinox calls for. Standard C does exactly that: malloc(), realloc(), and calloc() promise that they satisfy _Alignof(max_align_t), but nothing stricter. To reach for extended alignment requirements, your only standard tool is aligned_alloc().

gpvos 3y ago

The context parameter already addresses that need.

el_pollo_diablo 3y ago
> The context parameter already addresses that need. How so? The context parameter identifies the allocator instance. What if the library needs to allocate objects with different alignment requirements with the same allocator instance? Alignment requirement is just like allocation size (*). It varies from call to call, and generic allocators need to deal with heterogeneous alignments and sizes. (*) Case in point: Rust's Allocator interface (https://doc.rust-lang.org/std/alloc/trait.Allocator.html https://doc.rust-lang.org/std/alloc/trait.Allocator.html) bundles them up in a single Layout object.
flohofwoe 3y ago
Not really I think, the context pointer (I would call it "user data" though since that's more common in the C world) is normally passed around as an opaque pointer which is used by the allocator functions to find their own state, but not for passing additional parameters to the allocator.
- gpvos 3y ago
  I guess you're right. The alignment parameter may be different per allocation, not per arena/context.

kevincox 3y ago

While you are at it passing the size of the allocation during free can also be valuable and is usually available "for free".

el_pollo_diablo 3y ago
Yes, that's item 2 of the checklist in the original article.