4 ms·

You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. Having lots of cores a

You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. Having lots of cores and lots of RAM just means you can eat the cost more easily. It just means you can afford to let the VM do the work instead of the programmer. Also, no matter how much RAM you have, cache sizes are more or less the same, and cache line misses hurt.

pron 11y ago
> You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. That's not at all how it works. The generational hypothesis means that most objects die young. Allocating them is a simple, uncontended pointer bump in the thread-local allocation buffer (as fast as stack allocation), and freeing them is free, as they are never traversed. They are much, much (much) faster than malloc/free. They do however increase the frequency of young-gen so they have an indirect cost. When it comes to throughput (i.e. total time the application spends doing memory management), modern GCs handily beat malloc/free. What you can do, however, with manual memory management is all sorts of arena allocations, but then you have to be careful when sharing pointers (Rust helps with that). Then there's the question of concurrent data structures, that are very, very hard to do well without a GC. > cache line misses hurt. What does that have to do with GCs? If anything, copying GCs bring related objects together, so the prefetcher can help. What affects cache misses (in Java) is the lack of arrays-of-structs, which is scheduled to be fixed, with the addition of value types, in Java 10.
- banachtarski 11y ago
  Comparing to malloc and free directly isn't very useful because that's pretty much the worst way to manage memory. Aside from memory arenas, you can just pool memory or preallocate too. I think concurrent data structures have very niche usage in practice (compared to say, a thread safe system). >> cache line misses hurt. > What does that have to do with GCs? Everything. Sure you can use a copying GC and hope related objects go together. I tell the compiler to lump them together and exploit the prefetcher wherever possible.
  - pron 11y ago
    > I tell the compiler to lump them together and exploit the prefetcher wherever possible. That's a memory layout issue. What does a GC have to do with that? .NET and Go already allow good memory layout control, and Java will, too, once it gets value types. Conversely, one could create a manually-managed language that doesn't support object/array embedding, either. Memory layout control and GCs are completely orthogonal issues.
- vitalyd 11y ago
  I really dislike the comparisons of TLAB to stack allocation. Stack, by its nature, is going to be hot in cache. TLAB, once filled up, will be retired and possibly assigned to a different thread. But even if it's not assigned, it's constantly moving forwards, and not revisiting the same space. You'd need prefetch to be perfect, and then on top of that, you'd need to make sure that by the time you go to allocate again, the prefetched cachelines have not been evicted. Languages/platforms with a GC should still use, support, and encourage stack allocation for temporary memory -- this is your TLAB! There is a cost to traversing references; card marking and generational collectors just reduce the amount of references you need to visit, but it doesn't mean reference chasing isn't requiring extra instructions. Finally, don't forget that card marking requires write barriers, which is extra instructions (and possible cache misses) on each reference store (modulo trivial ones, such as new allocations, where JIT knows it's not required).
  - mkpankov 11y ago
    A stupid question: what's TLAB?
    - Jweb_Guru 11y ago
      Thread local allocation buffer.
  - deleted 11y ago
    [deleted]
  - pron 11y ago
    While everything you say is 100% true, it is also a second-order effect, with a much lower magnitude than the primary GC performance behavior for short-lived objects. Obviously stack allocation is preferable to TLAB allocation (and there's no reason to allocate objects with stack scope on the heap), if only for the fact that it never triggers a collection. Nevertheless, Java allocation/collection of short-lived object is much closer in cost to stack allocation than to malloc/free.
    - 11y ago
- dumael 11y ago
  I have to completely disagree. Generation GC beats malloc/free in the case of 'all objects allocated on the heap' when: sizeof(survivors) + cost of traversing survivors pointer fields + rewriting the remembered set < traversing malloc/free trees for allocation/freeing. Freeing objects in Generational GC requires computing the transitive closure relation of the stack and any "global variable" for the set of objects in the generational allocation arena so that all live objects there can be identified. I. E. For the stack, all "Global" variables, and the set of marked cards/(The record of objects updated with old to new references) : Find all live objects, copy them into the next arena while rewriting references. Oh, were write barriers that not mentioned? Generation GC requires write barriers. Every update through a pointer unless provably required by a compiler turns "a->b = c"; into "if(b is in generational region) { record update of b;} a->b = c". If you want to be able to move objects arounds cheaply, writes through pointers transform into small subroutines. For some GCs, reads through pointers are also small subroutines. And some Generational GCs do card marking over object marking. Let's traverse $CHUNKOFMEMORY on the probabilistic notion that if something was updated, something close by was updated. (Otherwise we can have Sequential Store Buffers which record exactly which objects were changed) Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas. Full disclosure: Despite my whining about GCs, I did do my Phd in them.
  - pron 11y ago
    You mean sizeof(survivors whose references changed since last collection). You pay for those write barriers for a reason. > Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas. I agree, but on large servers with lots of RAM, the total amount of memory that can possibly be managed on stacks is < 3% of total RAM. What do you do then? Most of the RAM will be filled with database data, with arbitrary lifetime and concurrent access for both reads or writes, because that's precisely the kind of data that would most significantly help the program's performance if it's in RAM. Now you can say that with all that data in RAM, the GC heap is a huge waste of RAM and the worst-case GC pause would be terrible, to which I say (I write in-memory databases in Java) that most of that data is user data and is kept off heap. Its lifetime is indeed arbitrary, but objects are deleted precisely when the user chooses to delete them, and that happens when they're protected by a lock. The much more interesting data is the indices, for which a GC helps greatly by allowing optimistic locking and other forms of scalable concurrency, and only those are kept on the heap.
alkonaut 11y ago
The pragmatic solution is to write the critical parts of the code either completely allocation-free or using some kind of automatic memory management. To write large amounts of boilerplate and non performance sensitive code using manual memory management is likely time that could be better spent elsewhere. Similarly, tweaking a compute intensive part of a CLR/Jvm/Python/ruby program to fix GC performance is probably more work than just rewriting that particular piece of code with allocations in mind, in C if necessary.
- banachtarski 11y ago
  The great thing about stack unwinding and constructor/destructor semantics is that they are automatic. Except they are done at compile time instead of runtime. Write the performance critical system that needs to do the bookkeepping. Then write the easy stuff on top of that.

pron 11y ago

> You will never beat a tuned system without GC with a GC system because of all the instructions necessary to traverse references and such. That's not at all how it works. The generational hypothesis means that most objects die young. Allocating them is a simple, uncontended pointer bump in the thread-local allocation buffer (as fast as stack allocation), and freeing them is free, as they are never traversed. They are much, much (much) faster than malloc/free. They do however increase the frequency of young-gen so they have an indirect cost. When it comes to throughput (i.e. total time the application spends doing memory management), modern GCs handily beat malloc/free. What you can do, however, with manual memory management is all sorts of arena allocations, but then you have to be careful when sharing pointers (Rust helps with that). Then there's the question of concurrent data structures, that are very, very hard to do well without a GC. > cache line misses hurt. What does that have to do with GCs? If anything, copying GCs bring related objects together, so the prefetcher can help. What affects cache misses (in Java) is the lack of arrays-of-structs, which is scheduled to be fixed, with the addition of value types, in Java 10.

banachtarski 11y ago
Comparing to malloc and free directly isn't very useful because that's pretty much the worst way to manage memory. Aside from memory arenas, you can just pool memory or preallocate too. I think concurrent data structures have very niche usage in practice (compared to say, a thread safe system). >> cache line misses hurt. > What does that have to do with GCs? Everything. Sure you can use a copying GC and hope related objects go together. I tell the compiler to lump them together and exploit the prefetcher wherever possible.
- pron 11y ago
  > I tell the compiler to lump them together and exploit the prefetcher wherever possible. That's a memory layout issue. What does a GC have to do with that? .NET and Go already allow good memory layout control, and Java will, too, once it gets value types. Conversely, one could create a manually-managed language that doesn't support object/array embedding, either. Memory layout control and GCs are completely orthogonal issues.
vitalyd 11y ago
I really dislike the comparisons of TLAB to stack allocation. Stack, by its nature, is going to be hot in cache. TLAB, once filled up, will be retired and possibly assigned to a different thread. But even if it's not assigned, it's constantly moving forwards, and not revisiting the same space. You'd need prefetch to be perfect, and then on top of that, you'd need to make sure that by the time you go to allocate again, the prefetched cachelines have not been evicted. Languages/platforms with a GC should still use, support, and encourage stack allocation for temporary memory -- this is your TLAB! There is a cost to traversing references; card marking and generational collectors just reduce the amount of references you need to visit, but it doesn't mean reference chasing isn't requiring extra instructions. Finally, don't forget that card marking requires write barriers, which is extra instructions (and possible cache misses) on each reference store (modulo trivial ones, such as new allocations, where JIT knows it's not required).
- mkpankov 11y ago
  A stupid question: what's TLAB?
  - Jweb_Guru 11y ago
    Thread local allocation buffer.
- deleted 11y ago
  [deleted]
- pron 11y ago
  While everything you say is 100% true, it is also a second-order effect, with a much lower magnitude than the primary GC performance behavior for short-lived objects. Obviously stack allocation is preferable to TLAB allocation (and there's no reason to allocate objects with stack scope on the heap), if only for the fact that it never triggers a collection. Nevertheless, Java allocation/collection of short-lived object is much closer in cost to stack allocation than to malloc/free.
  - 11y ago
dumael 11y ago
I have to completely disagree. Generation GC beats malloc/free in the case of 'all objects allocated on the heap' when: sizeof(survivors) + cost of traversing survivors pointer fields + rewriting the remembered set < traversing malloc/free trees for allocation/freeing. Freeing objects in Generational GC requires computing the transitive closure relation of the stack and any "global variable" for the set of objects in the generational allocation arena so that all live objects there can be identified. I. E. For the stack, all "Global" variables, and the set of marked cards/(The record of objects updated with old to new references) : Find all live objects, copy them into the next arena while rewriting references. Oh, were write barriers that not mentioned? Generation GC requires write barriers. Every update through a pointer unless provably required by a compiler turns "a->b = c"; into "if(b is in generational region) { record update of b;} a->b = c". If you want to be able to move objects arounds cheaply, writes through pointers transform into small subroutines. For some GCs, reads through pointers are also small subroutines. And some Generational GCs do card marking over object marking. Let's traverse $CHUNKOFMEMORY on the probabilistic notion that if something was updated, something close by was updated. (Otherwise we can have Sequential Store Buffers which record exactly which objects were changed) Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas. Full disclosure: Despite my whining about GCs, I did do my Phd in them.
- pron 11y ago
  You mean sizeof(survivors whose references changed since last collection). You pay for those write barriers for a reason. > Stack allocation (either explicit or deduced) is probably the fastest method of object allocation there is. Generational GC is on average going to be fast but can suffer horrendous worst case scenarios unless you GC is designed/engineered to switch between thread local allocation arenas. I agree, but on large servers with lots of RAM, the total amount of memory that can possibly be managed on stacks is < 3% of total RAM. What do you do then? Most of the RAM will be filled with database data, with arbitrary lifetime and concurrent access for both reads or writes, because that's precisely the kind of data that would most significantly help the program's performance if it's in RAM. Now you can say that with all that data in RAM, the GC heap is a huge waste of RAM and the worst-case GC pause would be terrible, to which I say (I write in-memory databases in Java) that most of that data is user data and is kept off heap. Its lifetime is indeed arbitrary, but objects are deleted precisely when the user chooses to delete them, and that happens when they're protected by a lock. The much more interesting data is the indices, for which a GC helps greatly by allowing optimistic locking and other forms of scalable concurrency, and only those are kept on the heap.

alkonaut 11y ago

The pragmatic solution is to write the critical parts of the code either completely allocation-free or using some kind of automatic memory management. To write large amounts of boilerplate and non performance sensitive code using manual memory management is likely time that could be better spent elsewhere. Similarly, tweaking a compute intensive part of a CLR/Jvm/Python/ruby program to fix GC performance is probably more work than just rewriting that particular piece of code with allocations in mind, in C if necessary.

banachtarski 11y ago
The great thing about stack unwinding and constructor/destructor semantics is that they are automatic. Except they are done at compile time instead of runtime. Write the performance critical system that needs to do the bookkeepping. Then write the easy stuff on top of that.