4 ms·

Definitely up because realloc. Yes, the article mentions this, but it bears repeating. I wasn't aware that optimizers were so much better though! That said, th

by o11c 3y ago

Definitely up because realloc. Yes, the article mentions this, but it bears repeating. I wasn't aware that optimizers were so much better though! That said, there's one useful feature that regrettably is poorly supported in most allocator discussion - where some higher alignment is wanted but not at the exact start of the object. Microsoft has the only major allocator that I'm aware of that supports this; it uses the "align at offset" sense (which simplifies the case of prepending a header to an aligned object). GCC has some minimal support and uses the "align with offset" sense (which IMO makes literally everything else much easier). As a minimal example, if 0x4 is the low nybble of your pointer, Microsoft calls that "align 16 at offset 12", whereas GCC calls it "align 16 with offset 4". Note that regardless of sense, you can store both the alignment and the offset in a single integer-sized variable by using your compiler's "find highest bit" or "round down to a power of 2" intrinsic. By exclusively using wrapper objects you can in fact hide the internally-chosen sense and support both publicly. This does however remove the possibility of only passing the log of the alignments, popular on BSD allocators. Limiting `align` to positive `isize` is useful, but further restrictions can reduce the number of overflow checks you often need. I have never found a practical use (mostly: considering huge pages) for more than 3/4 of the bits to be used on alignment - that is, 6 bits (64, a typical cacheline nowadays) for 8-bit pointers, 12 bits (4K, a typical non-huge page nowadays) for 16-bit pointers, 24 bits (16M - suported on many ISAs, just not x86) for 32-bit pointers, and 48 bits (256T - theoretically available on RISC-V) for 64-bit pointers. You'll likely want a +1 when you use this, at least if you implement the logic the way I did.

JonChesterfield 3y ago
Requiring alignment some distance into a contiguous allocation is interesting. The other variant is returning a pointer to the end instead of the start. Putting those together, the generic interface would be "get a pointer with minimum alignment A, with at least N bytes available before the pointer and at least M bytes available after". Usually N=0, but N=4 would give you a word to store a size before the data etc. That's also easy to implement on a bump allocator. I think it's a reasonable choice for the implementation with convenience wrappers for the common cases.
- o11c 3y ago
  For the sake of branch prediction, the ABI really needs to include several functions rather than the "obvious" one allocator/deallocator function to rule them all with mere convenience wrappers. The only thing "one function" simplifies is writing interceptor libraries, and that's not sufficiently motivating (especially given that OO is a better idea). Note that it's possible for partial interception to be detected and fall back to the generic method via `if (unlikely(interposer_detected))` in every ABI-exposed implementation function. My initial design signature for this was: auto utopia_alloc(Allocation, AlignAndSkew, Size, Flags) -> Allocation; But when I actually implemented this I ended up adding an `Allocator *this` argument, then making this an inline function with fixed logic dispatching to malloc/realloc/free-like functions (but with more arguments) as needed (including a fallback if realloc isn't implemented). Unfortunately it turns out recent versions of both GCC and Clang are gratuitously buggy regarding `malloc_usable_size` (and libcs took "advantage" of it then retroactively changed their documentation, breaking userland). Also, it turns out to be extremely useful if your libc supply a "realloc in place only" function, usually named something like "expand", but this too is not widely supported at all. Thus to make this useful I would have to implement a complete allocator, not a shim. So I kind of quit in disgust/exhaustion.
bewaretheirs 3y ago
See Bonwick & Adams, "Magazines and Vmem: extending the slab allocator to many CPUs and arbitrary resources" from 2001: https://www.usenix.org/conference/2001-usenix-annual-technical-conference/magazines-and-vmem-extending-slab-allocator-many https://www.usenix.org/conference/2001-usenix-annual-technic... The most general allocator interface described, vmem_xalloc(), includes a "phase" parameter (their name for "align at offset"), as well as a "nocross" parameter (in case you want your oddly-aligned object to not cross a page boundary).
- o11c 3y ago
  Hmm, paying a whole extra register for `nocross` is pretty expensive ... though representing it as a logarithm means it only needs to represent 62 values (2^1 is meaningless for both 1-byte and 2-byte allocations, 2^64 cannot be crossed regardless), which is 6 bits, so we could stuff it in the flags or even the high bits of the alignment on 32-bit-or-larger platforms. That seems like the way to do it ... unless it is instead specified as part of the allocator itself. Anyway, added that and other flags in that paper to my central list at https://gist.github.com/o11c/6b08643335388bbab0228db763f99219#file-memory-allocation-api-md https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...
  - bewaretheirs 3y ago
    not sure if it was a factor in the API design, but SPARC's fixed-size register windows give you space for 8 parameters. Perhaps it's just coincidence, but vmem_xalloc() takes exactly 8 parameters!
NobleExpress 3y ago
Using microbenchmarks to measure allocation performance is a bit misleading. The optimizations that occurred in the microbenchmarks may not actually occur for real-world code. Three branches vs two branches also makes no real difference as you are better served optimizing inefficiencies/performance somewhere else. Also realloc'ing the most recently allocated object is not a common operation, at least in my experience building memory management systems.
- o11c 3y ago
  Every time you stream the creation of an object, you're doing a recent-object-realloc. This shows up all the time for serialization, strings, vectors, etc. If you don't think you're doing it, you're probably using a library that hides it from you - or else doing something completely inefficient (in some languages, repeated string concatenation is O(n²)). If your allocator exposes a "give me an arbitrarily large buffer up front to use, and I will give back what I don't need" that can beat realloc but otherwise you really do need it. I suppose on platforms without `mremap` you might want ? The other alternative of course is "keep a list of small fragments, and join them at the end", but that just moves the `realloc` up a level, and is likely to give you fragmentation (which in some cases might even prevent the final allocation from succeeding).

by o11c 3y ago

JonChesterfield 3y ago

Requiring alignment some distance into a contiguous allocation is interesting. The other variant is returning a pointer to the end instead of the start. Putting those together, the generic interface would be "get a pointer with minimum alignment A, with at least N bytes available before the pointer and at least M bytes available after". Usually N=0, but N=4 would give you a word to store a size before the data etc. That's also easy to implement on a bump allocator. I think it's a reasonable choice for the implementation with convenience wrappers for the common cases.

o11c 3y ago
For the sake of branch prediction, the ABI really needs to include several functions rather than the "obvious" one allocator/deallocator function to rule them all with mere convenience wrappers. The only thing "one function" simplifies is writing interceptor libraries, and that's not sufficiently motivating (especially given that OO is a better idea). Note that it's possible for partial interception to be detected and fall back to the generic method via `if (unlikely(interposer_detected))` in every ABI-exposed implementation function. My initial design signature for this was: auto utopia_alloc(Allocation, AlignAndSkew, Size, Flags) -> Allocation; But when I actually implemented this I ended up adding an `Allocator *this` argument, then making this an inline function with fixed logic dispatching to malloc/realloc/free-like functions (but with more arguments) as needed (including a fallback if realloc isn't implemented). Unfortunately it turns out recent versions of both GCC and Clang are gratuitously buggy regarding `malloc_usable_size` (and libcs took "advantage" of it then retroactively changed their documentation, breaking userland). Also, it turns out to be extremely useful if your libc supply a "realloc in place only" function, usually named something like "expand", but this too is not widely supported at all. Thus to make this useful I would have to implement a complete allocator, not a shim. So I kind of quit in disgust/exhaustion.

bewaretheirs 3y ago

See Bonwick & Adams, "Magazines and Vmem: extending the slab allocator to many CPUs and arbitrary resources" from 2001: https://www.usenix.org/conference/2001-usenix-annual-technical-conference/magazines-and-vmem-extending-slab-allocator-many https://www.usenix.org/conference/2001-usenix-annual-technic... The most general allocator interface described, vmem_xalloc(), includes a "phase" parameter (their name for "align at offset"), as well as a "nocross" parameter (in case you want your oddly-aligned object to not cross a page boundary).

o11c 3y ago
Hmm, paying a whole extra register for `nocross` is pretty expensive ... though representing it as a logarithm means it only needs to represent 62 values (2^1 is meaningless for both 1-byte and 2-byte allocations, 2^64 cannot be crossed regardless), which is 6 bits, so we could stuff it in the flags or even the high bits of the alignment on 32-bit-or-larger platforms. That seems like the way to do it ... unless it is instead specified as part of the allocator itself. Anyway, added that and other flags in that paper to my central list at https://gist.github.com/o11c/6b08643335388bbab0228db763f99219#file-memory-allocation-api-md https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...
- bewaretheirs 3y ago
  not sure if it was a factor in the API design, but SPARC's fixed-size register windows give you space for 8 parameters. Perhaps it's just coincidence, but vmem_xalloc() takes exactly 8 parameters!

NobleExpress 3y ago

Using microbenchmarks to measure allocation performance is a bit misleading. The optimizations that occurred in the microbenchmarks may not actually occur for real-world code. Three branches vs two branches also makes no real difference as you are better served optimizing inefficiencies/performance somewhere else. Also realloc'ing the most recently allocated object is not a common operation, at least in my experience building memory management systems.

o11c 3y ago
Every time you stream the creation of an object, you're doing a recent-object-realloc. This shows up all the time for serialization, strings, vectors, etc. If you don't think you're doing it, you're probably using a library that hides it from you - or else doing something completely inefficient (in some languages, repeated string concatenation is O(n²)). If your allocator exposes a "give me an arbitrarily large buffer up front to use, and I will give back what I don't need" that can beat realloc but otherwise you really do need it. I suppose on platforms without `mremap` you might want ? The other alternative of course is "keep a list of small fragments, and join them at the end", but that just moves the `realloc` up a level, and is likely to give you fragmentation (which in some cases might even prevent the final allocation from succeeding).