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

31–40 of 61 posts

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

#31

Post by empath-nirvana »

jameshart wrote: post #27
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 depe…

In a practical sense, how you define big O depends on what you consider to be the inputs to the function. If the runtime doesn't change depending on the size of the inputs that you care about, it's O(1).

Like, you might have a function with 2 inputs, N and M, and the run time is like O(m2^n), but n is fixed at a low number every time you'll run it in practice, so it's really just O(m) for your purposes.

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

#33

Post by ot »

scott_s wrote: post #19
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…

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

Radix trees are not O(1), they're O(log n). Data structures that support constant-time predecessor lookup do not exist, there is a super-constant lower bound, even in the RAM model [1].

Often I hear people say "well pointer size is constant, so log(64) = O(1)", but that is misleading: if you assume constant pointer size, any function of that is O(1) as well, so any bounded algorithm is O(1). The notation just becomes meaningless.

Asymptotic bounds must be presented and understood in context.

[1] https://en.wikipedia.org/wiki/Predecessor_problem#Mathematic...

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

#34

Post by [deleted] »

scott_s wrote: post #19
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…

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

[deleted]

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

#35

Post by loeg »

couchand wrote: post #22
TrueDuality wrote: post #18

Earlier quoted context omitted.

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…

The presence of interrupts is basically equivalent to not being single threaded, though. There are true single-threaded environments, it's just limited to userspace processes that don't handle signals.

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

#36

Post by SkiFire13 »

orlp wrote: post #6
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…

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

> That's O(1).

A loop over 2^64 elements is also O(1), but I don't think people are ok to label every program that can run on a 64 bit pc as O(1).

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

#37

Post by skybrian »

ot wrote: post #33
scott_s wrote: post #19

Earlier quoted context omitted.

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

Radix trees are not O(1), they're O(log n). Data structures that support constant-time predecessor lookup do not exist, there is a super-constant lower bound, even in the RAM model [1]. Often I hear people say "well pointer size is constant, so log(64) = O(1)", but that is misleading: if you assume constant pointer size, any function of that is O(1) as well, so any bounded algorithm is O(1). The notation just becomes…

Given that pointer size is fixed, maybe asymptotic bounds aren’t what we should care about? Maybe it would be better to ask how the cost increases just going up to 2^64 bytes of address space. The graph after that point is irrelevant.

An O(n^2) algorithm will blow up well before that.

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

#38

Post by Ono-Sendai »

I have a best-fit allocator for this problem (managing GPU resources). It has higher CPU overhead due to using a std::map, but should waste less space due to not using fixed bucket sizes.

https://github.com/glaretechnologies/glare-core/blob/master/... https://github.com/glaretechnologies/glare-core/blob/master/...

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

#40

Post by pcwalton »

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'm also curious about making something like this work as a general purpose allocator (as alluded to by the README).

Besides the reverse mapping, you'd also have to get rid of the Vec use in the allocator, but that's fairly straightforward. Additionally, you'd need some sort of logic about requesting slabs of memory from the OS (and returning them when free), which is some extra work.

Post reply on HN