8 ms·

I recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of

I recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of their scenes. One of the interesting bits about the article was their memory allocation scheme. Each game frame they'd allocate a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool. I think this is what you describe as a slab allocator, because they never free()'d their allocations, they just recycled the pool after each frame had been rendered. I kindof see slab allocator as a happy middle ground between allocating temporary memory from the stack and full-blown free-list allocator (or whatever your classic malloc implementation is.) Are there any high level languages that have the ability to provision fast memory allocation pools like a slab where garbage collection occurs when the slab is no longer accessible, for instance?

JoshTriplett 10y ago
> Are there any high level languages that have the ability to provision fast memory allocation pools like a slab where garbage collection occurs when the slab is no longer accessible, for instance? Rust has several slab allocation libraries, such as the "slab" crate. They use lifetimes to ensure that the slab outlives the objects stored in it.
- EdSharkey 10y ago
  This is so rad.
codr4life 10y ago
The slab reference allocator from the challenge does that, but adds a segmented approach where the memory is allocated in N sized blocks. Go has decent support for doing these kinds of tricks; but nothing really runs faster since there's still too much magic behind the scenes. I suspect the story is the same in Rust land but I honestly never got passed the lifetime hump, too much ceremony for me.
- Jweb_Guru 10y ago
  There's not really much runtime magic in Rust (pretty comparable to C++), and arenas are definitely a performance benefit in many cases.
fulafel 10y ago
You are describing an arena allocator. Slab is more like a set of free lists per object size.
- wahern 10y ago
  IME arena doesn't really have a fixed definition. The term can and has been used to refer to something like an object stack or bump allocator, but also to something that supports deallocation and reallocation. The term goes back over 30 years and nothing specific has really stuck. I think the most you can say of an arena is that it's usually a contiguous region of memory from which smaller allocations are made, and which can be efficiently freed as a whole. An arena may only support fixed-size allocations, or a range of sizes; it may or may not support deallocation. However, in many cases it's natural to require multiple regions to satisfy all allocation requests for a particular context (task, generation, etc), so don't be surprised if an implementation labels a collection of contiguous regions an "arena". The term pool is similarly ambiguous, but usually implies support for deallocation and recycling of memory. It does not necessarily imply a contiguous region, but that's a natural optimization in a language like C. Slab is less ambiguous because it has a very specific origin in SunOS--allocation and deallocation of fixed-size, often typed objects (to optimize initialization).
  - codr4life 10y ago
    They're all out there floating around :) What I refer to as a pool allocator is a set of separate allocations, could be same size. While a slab is a single block of memory that's dished out as separate pointers, that could likewise be same size.
- toolslive 10y ago
  names vary. It's also called a scratchpad or region.
- kazinator 10y ago
  The GNU people call this "obstacks"; they are in the "iberty" library. (So named because it spells -liberty on a Unixy linker command line). https://gcc.gnu.org/onlinedocs/libiberty/Obstacks.html https://gcc.gnu.org/onlinedocs/libiberty/Obstacks.html Obstacks provide objects by drawing them from a linear piece of memory incrementally. Additionally, this is treated like a stack: you can free an object, but that also pops all objects allocated since that one.
nullc 10y ago
> a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool Maybe a register could be used to keep track of the current pointer into this pool, and every time you called into a new function the call could increment the pointer enough for all the usage in a function, and when the function returns it could set it back, automatically deallocating the usage with almost no cost at all?
- to3m 10y ago
  But not popping the last allocation when the function returns is kind of the whole point... it is (or certainly was...) common to double-buffer these, so that one frame's data is built up, and then consumed by another thread/the GPU/etc. while the corresponding data for the next frame is being filled in.
rwmj 10y ago
This is how the minor heap in many garbage collection schemes works. eg. In OCaml (the GC I'm too intimately familiar with) allocation is just decrementing a pointer and testing whether you've hit the beginning of the minor heap, so it's extremely fast. When the minor heap is exhausted you then take the hit of scanning the heap for objects which are still live and moving those to the major heap. If you're doing it right then most objects on the minor heap will be dead by this point so only a few will need to be moved. A fairly common trick for games or any code with little tolerance for GC pauses is to size the minor heap large enough that every allocation required in a single frame can be satisfied from the minor heap, and then do an explicit sweep of that heap at the end of the frame / before waiting for a network message / while waiting for user interaction.
Narishma 10y ago
http://www.gdcvault.com/play/1022186/Parallelizing-the-Naughty-Dog-Engine http://www.gdcvault.com/play/1022186/Parallelizing-the-Naugh... This might be the talk you're referring to.
- EdSharkey 10y ago
  This is it! Great presentation, thought provoking.

JoshTriplett 10y ago

> Are there any high level languages that have the ability to provision fast memory allocation pools like a slab where garbage collection occurs when the slab is no longer accessible, for instance? Rust has several slab allocation libraries, such as the "slab" crate. They use lifetimes to ensure that the slab outlives the objects stored in it.

EdSharkey 10y ago
This is so rad.

codr4life 10y ago

The slab reference allocator from the challenge does that, but adds a segmented approach where the memory is allocated in N sized blocks. Go has decent support for doing these kinds of tricks; but nothing really runs faster since there's still too much magic behind the scenes. I suspect the story is the same in Rust land but I honestly never got passed the lifetime hump, too much ceremony for me.

Jweb_Guru 10y ago
There's not really much runtime magic in Rust (pretty comparable to C++), and arenas are definitely a performance benefit in many cases.

fulafel 10y ago

You are describing an arena allocator. Slab is more like a set of free lists per object size.

wahern 10y ago
IME arena doesn't really have a fixed definition. The term can and has been used to refer to something like an object stack or bump allocator, but also to something that supports deallocation and reallocation. The term goes back over 30 years and nothing specific has really stuck. I think the most you can say of an arena is that it's usually a contiguous region of memory from which smaller allocations are made, and which can be efficiently freed as a whole. An arena may only support fixed-size allocations, or a range of sizes; it may or may not support deallocation. However, in many cases it's natural to require multiple regions to satisfy all allocation requests for a particular context (task, generation, etc), so don't be surprised if an implementation labels a collection of contiguous regions an "arena". The term pool is similarly ambiguous, but usually implies support for deallocation and recycling of memory. It does not necessarily imply a contiguous region, but that's a natural optimization in a language like C. Slab is less ambiguous because it has a very specific origin in SunOS--allocation and deallocation of fixed-size, often typed objects (to optimize initialization).
- codr4life 10y ago
  They're all out there floating around :) What I refer to as a pool allocator is a set of separate allocations, could be same size. While a slab is a single block of memory that's dished out as separate pointers, that could likewise be same size.
toolslive 10y ago
names vary. It's also called a scratchpad or region.
kazinator 10y ago
The GNU people call this "obstacks"; they are in the "iberty" library. (So named because it spells -liberty on a Unixy linker command line). https://gcc.gnu.org/onlinedocs/libiberty/Obstacks.html https://gcc.gnu.org/onlinedocs/libiberty/Obstacks.html Obstacks provide objects by drawing them from a linear piece of memory incrementally. Additionally, this is treated like a stack: you can free an object, but that also pops all objects allocated since that one.

nullc 10y ago

> a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool Maybe a register could be used to keep track of the current pointer into this pool, and every time you called into a new function the call could increment the pointer enough for all the usage in a function, and when the function returns it could set it back, automatically deallocating the usage with almost no cost at all?

to3m 10y ago
But not popping the last allocation when the function returns is kind of the whole point... it is (or certainly was...) common to double-buffer these, so that one frame's data is built up, and then consumed by another thread/the GPU/etc. while the corresponding data for the next frame is being filled in.

rwmj 10y ago

This is how the minor heap in many garbage collection schemes works. eg. In OCaml (the GC I'm too intimately familiar with) allocation is just decrementing a pointer and testing whether you've hit the beginning of the minor heap, so it's extremely fast. When the minor heap is exhausted you then take the hit of scanning the heap for objects which are still live and moving those to the major heap. If you're doing it right then most objects on the minor heap will be dead by this point so only a few will need to be moved. A fairly common trick for games or any code with little tolerance for GC pauses is to size the minor heap large enough that every allocation required in a single frame can be satisfied from the minor heap, and then do an explicit sweep of that heap at the end of the frame / before waiting for a network message / while waiting for user interaction.

Narishma 10y ago

http://www.gdcvault.com/play/1022186/Parallelizing-the-Naughty-Dog-Engine http://www.gdcvault.com/play/1022186/Parallelizing-the-Naugh... This might be the talk you're referring to.

EdSharkey 10y ago
This is it! Great presentation, thought provoking.