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

41–50 of 61 posts

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

#41

Post by pcwalton »

joshsyn wrote: post #11

How is this exactly going to be used in bevy?

The goal is to start storing multiple meshes in the same vertex buffer/index buffer. (I already have a decent chunk of this code written in a branch.) This reduces binding overhead, but moreover it allows us to start using multidraw indirect where supported, which should reduce drawcall counts dramatically. I measured a 97% drawcall count reduction for the opaque pass on the Bistro test scene, for example. The benefits are even higher for shadow maps, because they use a single shader and so the drawcall count should drop to the single digits in most cases.

I've said it before, but if drawcall count is a problem in your game, you should complain to the engine vendor. On modern GPUs, there's no reason people should be manually optimizing for drawcall count in 2024. Game engines have the tools to make it a non-issue; they just need to use them.

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

#42

Post by pcwalton »

Someone wrote: post #29
scott_s wrote: post #25

Earlier quoted context omitted.

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

Yes. I believe that the standard workaround for this problem is to place the allocator metadata for an entire block at some fixed address boundary, so you can just mask off the bottom K bits of an address to find the allocator metadata for the block, and from there find the metadata of the allocation you're concerned with.

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

#43

Post by scott_s »

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…

This function is O(1): https://github.com/scotts/streamflow/blob/master/streamflow..... All other tree operations are also constant, because the fact that it is a 3-level tree is hardcoded.

Asymptotic bounds are useful when your input can grow arbitrarily large. When your input is fixed, the bounds become less useful and you should focus on the particulars of your case. In the case I'm presenting, the work done traversing the tree will be the same every time; it is O(1). That doesn't necessarily mean it's fast enough! It still may do too much work for the use case. For instance, I can imagine someone saying that the function above does too much pointer chasing for their use case.

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

#45

Post by jameshart »

empath-nirvana wrote: post #31
jameshart wrote: post #27

Earlier quoted context omitted.

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.

Right. O(f(n)) is literally only defined for situations where n 1: varies between different runs of the algorithm, and 2: can grow arbitrarily large. Even though in practice ‘arbitrarily large’ is always limited by memory, storage, etc.

Talking about algorithms being O(n) in the number of bits in a value is only reasonable if the number of bits in the value actually varies between runs.

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

#46

Post by hinkley »

widdershins wrote: post #26

What's the difference between this and a slab allocator? Is it just that the bin size distribution wastes less memory (assuming the slab allocator used pow2 bin sizes)?

Slab allocators don’t provide real time guarantees. That is arena allocators. The distinction may seem trivial but the requirements are distinct.

In tiny systems all allocations of one type may come from a single operation, but in larger systems what fits in a slab will come from distinct concerns with different priorities. You want a different arena for those allocations.

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

#47

Post by Dylan16807 »

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…

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

It's not meaningless. We're designing for a real machine here, and the actual goal is to bound the runtime to a small known constant.

You're right that big O is not great notation for this. Hell, even O(1) isn't good enough because the constant factor is unspecified.

But the misuse of notation does not invalidate the problem. Taking the worst case for a log leaves you with a feasible runtime. Taking the worst case for n or n^2 or "any bounded algorithm" overwhelmingly does not.

> Asymptotic bounds must be presented and understood in context.

Yes, context is exactly what keeps it meaningful!

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

#48

Post by ComputerGuru »

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…

Have you published your code to GH, by any chance?

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

#49

Post by ot »

scott_s wrote: post #43
ot wrote: post #33

Earlier quoted context omitted.

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…

This function is O(1): https://github.com/scotts/streamflow/blob/master/streamflow.... . All other tree operations are also constant, because the fact that it is a 3-level tree is hardcoded. Asymptotic bounds are useful when your input can grow arbitrarily large. When your input is fixed, the bounds become less useful and you should focus on the particulars of your case. In the case I'm presenting, the work done trav…

> This function is O(1)

I think I addressed that in my comment, but to be more explicit, this function is O(1) too:

  size_t find_sorted(void* object, void** list, size_t size) {
    for (size_t i = 0; i  object) return i;
    }
    return SIZE_MAX;
  }
If O(1) cannot distinguish your function from this function, what is its informational value?

> Asymptotic bounds are useful when your input can grow arbitrarily large

But your inputs can't grow arbitrarily large, that's why you can hardcode 3 levels. O(1) is an asymptotic bound, and my point is that it is not very informative here.

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

#50

Post by fragmede »

ot wrote: post #49
scott_s wrote: post #43

Earlier quoted context omitted.

This function is O(1): https://github.com/scotts/streamflow/blob/master/streamflow.... . All other tree operations are also constant, because the fact that it is a 3-level tree is hardcoded. Asymptotic bounds are useful when your input can grow arbitrarily large. When your input is fixed, the bounds become less useful and you should focus on the particulars of your case. In the case I'm presenting, the work done trav…

> This function is O(1) I think I addressed that in my comment, but to be more explicit, this function is O(1) too: size_t find_sorted(void* object, void** list, size_t size) { for (size_t i = 0; i object) return i; } return SIZE_MAX; } If O(1) cannot distinguish your function from this function, what is its informational value? > Asymptotic bounds are useful when your input can grow arbitrarily large But your inputs…

This is O(n) because you're still doing the i comparison, even though you've moved it out of the for loop.
Post reply on HN