How is this exactly going to be used in bevy?
Fast, simple, hard real time allocator for Rust
11–20 of 61 posts
Re: Fast, simple, hard real time allocator for Rust
#12> Please note that offset-allocator isn't a Rust allocator conforming to the GlobalAlloc trait Aw. Why not? > find the next available bin using 2x LZCNT instructions to make all operations O(1) Isn't that sort of implementation defined? The LZCNT operation itself is a loop over all bits -- the fact that the number of bits is constant doesn't make this O(1), it just makes it O(n) where n := 64. But if it was 16 or 32…
Whether you call that O(1) or O(n) depends on the level of abstraction you want to talk about, and what you want to analyse.
For example, in some sense, anything you can do on a finite computer is O(1) (or alternatively, it's an infinite loop). But that is a very boring sense, and seldom useful for analysis.
There's a formal definition for big-O notation, but most of the parameters to that formal definition are only implied in casual discussions.
Re: Fast, simple, hard real time allocator for Rust
#13> Please note that offset-allocator isn't a Rust allocator conforming to the GlobalAlloc trait Aw. Why not? > find the next available bin using 2x LZCNT instructions to make all operations O(1) Isn't that sort of implementation defined? The LZCNT operation itself is a loop over all bits -- the fact that the number of bits is constant doesn't make this O(1), it just makes it O(n) where n := 64. But if it was 16 or 32…
> Aw. Why not? 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…
GlobalAlloc is also required to be thread safe, and TLSF doesn't even attempt to handle that. I suppose you could get away with it on single-threaded platforms like microcontrollers or (vanilla) WebAssembly but it wouldn't generalize unless you wrapped it in a mutex, and then the performance would be terrible.
Re: Fast, simple, hard real time allocator for Rust
#14> Please note that offset-allocator isn't a Rust allocator conforming to the GlobalAlloc trait Aw. Why not? > find the next available bin using 2x LZCNT instructions to make all operations O(1) Isn't that sort of implementation defined? The LZCNT operation itself is a loop over all bits -- the fact that the number of bits is constant doesn't make this O(1), it just makes it O(n) where n := 64. But if it was 16 or 32…
> It just makes it O(n) where n := 64 That's O(1). > The LZCNT operation itself is a loop over all bits That's not how circuits work. You can easily make a circuit of O(log n) depth that returns base-2 encoded index of the first 1 bit in a n-bit register. But since n is just 64 here, you're looking at a circuit of AND/OR depth ~8, so it's no surprise that modern CPUs can compute the LZCNT / TZCNT of a 64-bit integer…
Note that rustc will not emit this instruction by default, to support older CPUs. Without `target-cpu=haswell` or similar, the operation will be quite slow, but still O(1) of course.
Re: Fast, simple, hard real time allocator for Rust
#15Earlier quoted context omitted.
> It just makes it O(n) where n := 64 That's O(1). > The LZCNT operation itself is a loop over all bits That's not how circuits work. You can easily make a circuit of O(log n) depth that returns base-2 encoded index of the first 1 bit in a n-bit register. But since n is just 64 here, you're looking at a circuit of AND/OR depth ~8, so it's no surprise that modern CPUs can compute the LZCNT / TZCNT of a 64-bit integer…
Note that rustc will not emit this instruction by default, to support older CPUs. Without `target-cpu=haswell` or similar, the operation will be quite slow, but still O(1) of course.
It's not that bad, all x86 processors have the BSR instruction which can be mapped to LZCNT semantics with just a few extra instructions.
Left to right - modern x86-64, baseline x86-64, baseline i686:
https://rust.godbolt.org/z/nGsM35TEo
Maybe you're thinking of POPCNT, which hurts a lot more if it doesn't compile down to the native instruction:
Re: Fast, simple, hard real time allocator for Rust
#16Earlier quoted context omitted.
> Aw. Why not? 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…
GlobalAlloc is also required to be thread safe, and TLSF doesn't even attempt to handle that. I suppose you could get away with it on single-threaded platforms like microcontrollers or (vanilla) WebAssembly but it wouldn't generalize unless you wrapped it in a mutex, and then the performance would be terrible.
Any uc worth programming on has interrupts!
Re: Fast, simple, hard real time allocator for Rust
#17> Please note that offset-allocator isn't a Rust allocator conforming to the GlobalAlloc trait Aw. Why not? > find the next available bin using 2x LZCNT instructions to make all operations O(1) Isn't that sort of implementation defined? The LZCNT operation itself is a loop over all bits -- the fact that the number of bits is constant doesn't make this O(1), it just makes it O(n) where n := 64. But if it was 16 or 32…
> Aw. Why not? 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…
OTOH, I think this would be a good fit for the "Store" proposal [1] which uses handles rather than addresses to refer to allocations.
[1] https://github.com/matthieu-m/storage/blob/main/etc/rfc.md
Re: Fast, simple, hard real time allocator for Rust
#18Earlier quoted context omitted.
GlobalAlloc is also required to be thread safe, and TLSF doesn't even attempt to handle that. I suppose you could get away with it on single-threaded platforms like microcontrollers or (vanilla) WebAssembly but it wouldn't generalize unless you wrapped it in a mutex, and then the performance would be terrible.
Any uc worth programming on has interrupts!
Even with interrupts there is almost always a single execution unit, and thus single-threaded. An interrupt is just a jump instruction to a predefined handler. The code that was running is entirely stopped until the system decides to resume from that point.
Re: Fast, simple, hard real time allocator for Rust
#19I wrote almost the exact same thing after seeing Sebastian Aaltonen's original offset allocator repo which inspired me to write my own clone in Rust. It's possible to further improve the fragmentation characteristics if the maximum size of the memory to be allocated is known ahead of time. The original used a 5.3 "floating point" scheme for the free bins, but given the maximum size you can opt for 4.4 or 6.2 or whate…
> For that it would be necessary to make a reverse lookup from pointer address to allocation handle, which would require something like a red-black tree covering the address space, which would no longer be 0(1). If anyone has ideas on this front, I would be happy to hear them.
A radix tree can solve this: https://en.wikipedia.org/wiki/Radix_tree
I used one way, way back to do exactly the same thing: upon a free, I needed to look up all of the metadata for an address. For a 32-bit address space, you can just allocate a giant array up front, and use the address as an index. For a 64-bit address space, it's obviously way too big to statically allocate it up front. A radix tree neatly solves the problem. An arbitrarily sized radix tree is not constant lookup, but for reasons I honestly cannot remember, for a 64-bit address space, it's guaranteed to only be 3 levels deep.
See my implementation, which (I believe) I borrowed from tcmalloc: https://github.com/scotts/streamflow/blob/master/streamflow....
Re: Fast, simple, hard real time allocator for Rust
#20Earlier quoted context omitted.
> Aw. Why not? 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…
GlobalAlloc is also required to be thread safe, and TLSF doesn't even attempt to handle that. I suppose you could get away with it on single-threaded platforms like microcontrollers or (vanilla) WebAssembly but it wouldn't generalize unless you wrapped it in a mutex, and then the performance would be terrible.
Correct me if I'm wrong but can't you put a Rc> in your std::alloc::Allocator implementation for interior mutability?
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?