5 ms·

For new objects, a lot of GC systems use a memory slab. Essentially, a buffer where you just allocate new data at the end, and then perform garbage collection o

For new objects, a lot of GC systems use a memory slab. Essentially, a buffer where you just allocate new data at the end, and then perform garbage collection once the slab is filled up. With this allocation is basically just a pointer bump. When your program requires lots of small allocations that all go out of use at around the same time, GC will significantly out-perform a naive malloc/free for every piece of data.

scott_s 11y ago
I am still just as skeptical as JoeAltmaier was. The fast-path for modern memory allocators are also just pointer-bumps in slabs. And if you keep mallocing and freeing something of the same size on the same thread, you are very likely to keep getting the same memory location on each allocation, which has excellent cache behavior. For an excellent paper on state-of-the-art memory allocation techniques (which also has a good overview of prior techniques, and how their works builds on that), see "Fast, Multicore-Scalable, Low-Fragmentation Memory Allocation through Large Virtual Memory and Global Data Structures" from OOSPLA 2015: http://2015.splashcon.org/event/oopsla2015-fast-multicore-scalable-low-fragmentation-memory-allocation-through-large-virtual-memory-and-global-data-structures http://2015.splashcon.org/event/oopsla2015-fast-multicore-sc... If you're aware of published works which show garbage collection consistently outperforming manual memory management for the reasons you explained, I'm very interested in reading them.
- JoeAltmaier 11y ago
  Agreed, except for the 'excellent cache behavior'. If you're getting cache hits on reallocated memory, you're looking at uninitialized data!
  - cfallin 11y ago
    Stores access the cache too. When you initialize your newly malloc()'d memory, ignoring the previous data, you still benefit from having the cache block present in-cache.
    - scott_s 11y ago
      To build on what you said: we're interested in the cache line, not the data in that cache line. Both reads and stores access the cache line, and both can see misses. It's not that you're seeing cached data, it's that your store instruction does not have to wait for the cache line to come into the L1.
    - deleted 11y ago
      [deleted]
  - deleted 11y ago
    [deleted]
- openasocket 11y ago
  Some of the state-of-the-art allocators close the performance gap pretty significantly, I was comparing to the classic Doug Lea style allocator. I imagine with something like your link the difference will be much less noticeable for allocation speed. However, not having an explicit free can lead to performance benefits, though it seems counter-intuitive. Imagine you are allocating a large number of small, short-lived objects. In the manual case, you have to explicitly call free() for each object as it goes out of scope. The free() call is rather fast for slab allocators, and free-ing everything runs in time O(dead_objects). A well-designed generational GC uses a copy collector for the eden generation, which essentially allocates a new slab and copies over all the live objects, and then frees the old slab. Copying objects is relatively fast for small objects, and this algorithm runs in time O(live_objects), which is much much smaller than the number of dead objects. Plus The copying step moves all the live objects together on the slab which reduces memory fragmentation.
  - scott_s 11y ago
    You're discounting the cost of the GC approach necessarily having more live objects at once. That will require hitting more slow-path parts of the GC's allocation algorithms (either finding free slabs, finding freed new slabs from a global cache, or allocating new ones from the OS), and it will have poor cache behavior. The manual memory allocator will be on the fast path for malloc and free, as long the number of live objects is less than that of a slab. There may be a crossover point where the GC algorithms are better (say, a pathological case where you keep forcing the manual memory allocator to hit its slow paths by allocating just one more than the size of a slab, freeing all of them, then repeat). But I would also not be surprised if there never is a crossover point.
    - openasocket 11y ago
      > You're discounting the cost of the GC approach necessarily having more live objects at once. No, by live objects I don't mean the objects that currently exist in the heap, I mean the objects currently reachable by the program, which is the same whether or not you are using GC. But you are right that GC will use much more heap on average than manual allocation. I agree that you can probably always beat GC using manual allocation if you are sufficiently smart about it. For instance, if you have some data structure you know is going to allocate a bunch of small objects, and none of the small objects can outlive the data structure, you can have that data structure create a special slab just for its objects, so when you free the data structure you just need to call one free() on the slab instead of a bunch of free() calls on every object.

scott_s 11y ago

I am still just as skeptical as JoeAltmaier was. The fast-path for modern memory allocators are also just pointer-bumps in slabs. And if you keep mallocing and freeing something of the same size on the same thread, you are very likely to keep getting the same memory location on each allocation, which has excellent cache behavior. For an excellent paper on state-of-the-art memory allocation techniques (which also has a good overview of prior techniques, and how their works builds on that), see "Fast, Multicore-Scalable, Low-Fragmentation Memory Allocation through Large Virtual Memory and Global Data Structures" from OOSPLA 2015: http://2015.splashcon.org/event/oopsla2015-fast-multicore-scalable-low-fragmentation-memory-allocation-through-large-virtual-memory-and-global-data-structures http://2015.splashcon.org/event/oopsla2015-fast-multicore-sc... If you're aware of published works which show garbage collection consistently outperforming manual memory management for the reasons you explained, I'm very interested in reading them.

JoeAltmaier 11y ago
Agreed, except for the 'excellent cache behavior'. If you're getting cache hits on reallocated memory, you're looking at uninitialized data!
- cfallin 11y ago
  Stores access the cache too. When you initialize your newly malloc()'d memory, ignoring the previous data, you still benefit from having the cache block present in-cache.
  - scott_s 11y ago
    To build on what you said: we're interested in the cache line, not the data in that cache line. Both reads and stores access the cache line, and both can see misses. It's not that you're seeing cached data, it's that your store instruction does not have to wait for the cache line to come into the L1.
  - deleted 11y ago
    [deleted]
- deleted 11y ago
  [deleted]
openasocket 11y ago
Some of the state-of-the-art allocators close the performance gap pretty significantly, I was comparing to the classic Doug Lea style allocator. I imagine with something like your link the difference will be much less noticeable for allocation speed. However, not having an explicit free can lead to performance benefits, though it seems counter-intuitive. Imagine you are allocating a large number of small, short-lived objects. In the manual case, you have to explicitly call free() for each object as it goes out of scope. The free() call is rather fast for slab allocators, and free-ing everything runs in time O(dead_objects). A well-designed generational GC uses a copy collector for the eden generation, which essentially allocates a new slab and copies over all the live objects, and then frees the old slab. Copying objects is relatively fast for small objects, and this algorithm runs in time O(live_objects), which is much much smaller than the number of dead objects. Plus The copying step moves all the live objects together on the slab which reduces memory fragmentation.
- scott_s 11y ago
  You're discounting the cost of the GC approach necessarily having more live objects at once. That will require hitting more slow-path parts of the GC's allocation algorithms (either finding free slabs, finding freed new slabs from a global cache, or allocating new ones from the OS), and it will have poor cache behavior. The manual memory allocator will be on the fast path for malloc and free, as long the number of live objects is less than that of a slab. There may be a crossover point where the GC algorithms are better (say, a pathological case where you keep forcing the manual memory allocator to hit its slow paths by allocating just one more than the size of a slab, freeing all of them, then repeat). But I would also not be surprised if there never is a crossover point.
  - openasocket 11y ago
    > You're discounting the cost of the GC approach necessarily having more live objects at once. No, by live objects I don't mean the objects that currently exist in the heap, I mean the objects currently reachable by the program, which is the same whether or not you are using GC. But you are right that GC will use much more heap on average than manual allocation. I agree that you can probably always beat GC using manual allocation if you are sufficiently smart about it. For instance, if you have some data structure you know is going to allocate a bunch of small objects, and none of the small objects can outlive the data structure, you can have that data structure create a special slab just for its objects, so when you free the data structure you just need to call one free() on the slab instead of a bunch of free() calls on every object.