Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast, simple, hard real time allocator for Rust

github.com

Post reply on HN
Print view View original

21–30 of 61 posts

Re: Fast, simple, hard real time allocator for Rust

#21

Post by CaptainOfCoit »

joshsyn wrote: post #11

How is this exactly going to be used in bevy?

At least one mention of it here https://github.com/bevyengine/bevy/issues/12590

> Use one set of large mesh buffers per vertex attribute layout

> Problem: Index/vertex buffers have to be re-bound when the mesh changes. This adds overhead when encoding draws and when drawing. It also prevents some optimisations like being able to draw all objects for shadow mapping for a light in one draw.

> Solution(s): [...] Use an appropriate allocator like a port of Sebastian Aaltonen's offset allocator [https://github.com/sebbbi/OffsetAllocator] to manage allocation

Where the "port of Sebastian Aaltonen's offset allocator" is what got linked in this HN submission.

Re: Fast, simple, hard real time allocator for Rust

#22

Post by couchand »

TrueDuality wrote: post #18
couchand wrote: post #16

Earlier quoted context omitted.

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.

That doesn't mean that naive single-threaded code is necessarily interrupt-safe. If the allocator is interrupted and the interrupt service routine needs to make use of the allocator's data structures for any reason there could very much be a conflict.

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.

Re: Fast, simple, hard real time allocator for Rust

#23

Post by slashdev »

lionkor wrote: post #3

> 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…

In all x86 this is an instruction that typically takes 3 clock cycles (latency) with 1 clock cycle throughput. That’s as constant time as you get.

Even if that were false, it’s O(k) where k is the number of bits, which is constant. However, in that case it might be slower than the alternatives.

Re: Fast, simple, hard real time allocator for Rust

#24

Post by yvt »

exDM69 wrote: post #4

I 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…

I did this too! Except it was based on the original TLSF paper (on which this work is based) as I wasn't aware of that offset allocator.

> I'm also curious about making something like this work as a general purpose allocator (as alluded to by the README).

In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1). The original TLSF algorithm (as proposed by the paper) was designed this way.

Months later, I also wrote a general purpose implementation of TLSF for Rust `GlobalAlloc`, which, with some rigorous optimizations, turned out to be faster and smaller than every allocator for WebAssembly and embedded environments I tested, and it's still my go-to choice. It didn't fare too bad even when compared against modern thread-caching allocators in normal use cases. Internal fragmentation is probably worse, though.

Re: Fast, simple, hard real time allocator for Rust

#25

Post by scott_s »

yvt wrote: post #24
exDM69 wrote: post #4

I 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…

I did this too! Except it was based on the original TLSF paper (on which this work is based) as I wasn't aware of that offset allocator. > I'm also curious about making something like this work as a general purpose allocator (as alluded to by the README). In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1). The original TLSF algori…

> In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1).

Yes, but the downside is that now allocator metadata pollutes the cache. It's super efficient for the allocator, but it may harm efficiency of the actual use of that memory. I believe most production allocators don't use object headers for this reason.

Re: Fast, simple, hard real time allocator for Rust

#27

Post by jameshart »

lionkor wrote: post #3

> 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…

Any big O discussion usually breaks down (or at least, changes) if you start taking into account the data size of the operands.

You generally assume for big O purposes, when analyzing sorts for example, that comparisons of elements are constant time, and that swapping elements is constant time.

On an n-bit computer, when dealing with m-bit elements, those assumptions are broadly sound. Comparing two ints doesn’t depend on the ints. Reading or writing the int from memory doesn’t take more or less time either.

But the same algorithm, while it has the same big O relationship to the size of a collection, might have a different constant factor on different CPUs and for different values of m. And you might find that some algorithms that constant factor’s relationship to m has its own big O.

One common place this can bite you is when you try to apply big O analysis that has ‘constant time comparison’ assumption built in to, say, sorting arbitrarily long strings, or inserting into a hash table using arbitrary string keys. Comparing strings or calculating hashes of them is not constant time.

Re: Fast, simple, hard real time allocator for Rust

#28

Post by dzaima »

lionkor wrote: post #3

> 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…

Integer addition, and indeed pretty much all operations, are also a loops over all bits, LZCNT is in no way at all unique here.

Re: Fast, simple, hard real time allocator for Rust

#29

Post by Someone »

scott_s wrote: post #25
yvt wrote: post #24

Earlier quoted context omitted.

I did this too! Except it was based on the original TLSF paper (on which this work is based) as I wasn't aware of that offset allocator. > I'm also curious about making something like this work as a general purpose allocator (as alluded to by the README). In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1). The original TLSF algori…

> In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1). Yes, but the downside is that now allocator metadata pollutes the cache. It's super efficient for the allocator, but it may harm efficiency of the actual use of that memory. I believe most production allocators don't use object headers for this reason.

> I believe most production allocators don't use object headers for this reason.

Isn’t the original reason hardening against buffer overflows? Overwriting allocator metadata can be used to attack a system.

Re: Fast, simple, hard real time allocator for Rust

#30

Post by LegionMammal978 »

exDM69 wrote: post #20
jsheard wrote: post #13

Earlier 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.

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?

This is about GlobalAlloc, the trait that actually exists in stable Rust. Only static variables can be marked as the #[global_allocator], and statics are always required to be Send + Sync. Of course, if you're really sure that only a single thread will ever exist, you can pinky-promise it by putting a couple unsafe impls on the allocator type. But then the language won't protect you if you do try to allocate or deallocate from multiple threads.

(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.)

Post reply on HN