This particular algorithm is focused on GPUs, so I'm not clear on the applicability. However I did want to clear up the idea that there are no concurrency concerns for single-threaded library code, an assumption that's been the source of many bugs.
Some algorithms are both thread safe and reentrancy safe, but generally this is not the case.
This make a non-thread safe allocator, with the (desired) side effect of making anything allocating from it (e.g. Vec) a !Send.
Or is there a requirement that Allocators must be Sync and Send?
(More practically, you can just write a GlobalAlloc that forwards to an instance of a thread-local allocator. Though that runs the risk of thread-local deinitialization running in an unexpected order.)
[1] https://github.com/matthieu-m/storage/blob/main/etc/rfc.md
Not necessarily. If you are able to map a block of normal memory in a known location relative to the GPU memory that you are managing with an "offset allocator", it should be possible to directly calculate the metadata location for each "offset". This is how most allocators find arenas/buckets (whatever you want to call them) for an allocation by a pointer.
Something like this:
+-------------------------+ 0x000000 (start of managed memory)
| Metadata |
| |
| |
| ... |
+-------------------------+ 0x001000
| Padding ... |
+-------------------------+ 0x010000
| GPU Memory Block |
| |
| |
| | ~2MB block
| |
| |
| |
+-------------------------+ 0x210000
With this layout, to get to a metadata for an allocation, all you need to do is to align down the allocation pointer and calculate the appropriate location in the metadata page.This obviously won't work in all scenarios, but it's a simple and practical way around a map lookup.
If you have a large allocation you have to mark every "page" in metadata table which makes allocation O(size in bytes / page size).
The overhead might still be practically acceptable, even if it is not constant time.
Well, another solution is enlarging each allocation by 8 bytes and storing the buffer handle in front of the returned allocation. So `free(ptr)` would get the handle as `*((ptr as *const u64) - 1)`.
This kind of allocators are usually used for suballocating GPU buffers, so hiding a few bytes of metadata "in-band" can mess up your alignment requirements and not all kinds of GPU memory are even accessible by CPU. Due to false sharing cache problems you would probably want a full cache line (64 bytes) to store the metadata.
For a CPU-only memory allocator your idea could work quite well. It can also be implemented on top of this code without any modifications.
Because the global allocator API is defined as free(pointer address) and this used free(buffer handle).
It would require a reverse lookup structure from address to buffer handle, e.g. red-black tree. Maintaining it would no longer be O(1).
> the fact that the number of bits is constant doesn't make this O(1), it just makes it O(n) where n := 64
O(n) when n is constant is equal to O(1).
But lzcnt uses a fixed number of clock cycles so it's not really O(n) either.