4 ms·

Java is still slower than C in its memory management for many cases, so we can safely say that this is not a solved problem.

kryptiskt 4y ago
Memory management for C is not itself a solved problem, not only is there a lot of performance to squeeze out of malloc itself (the benchmarks on https://github.com/microsoft/mimalloc https://github.com/microsoft/mimalloc exemplifies the variance between the implementations), but it's up to the programmer to implement memory management in the large in an efficient way, which is not an easy task. One sure mark of a slow C program is one with a ton of mallocs and frees strewn all over.
kaba0 4y ago
If we can know exactly where a particular object’s lifetime ends, then indeed we can write more efficient programs than possible with a GC, but that in the general case is not something we can determine at compile time (Rust’s lifetimes are a strict subset of the general case). Anything more dynamic will require some “ad hoc, informally-specified, bug-ridden, slow implementation of a GC”.
- pron 4y ago
  Rust also relies on a GC for the more dynamic lifetimes in Rust programs (reference counting), it just doesn't call it a GC, and while Rust's GC has a lower footprint than tracing GCs, it has worse performance and it suffers from cycle problems. I wouldn't call it "bug ridden" (perhaps "limited" is a better term), but it is slow. Some think that reference counting gives better performance predictability than a tracing GC, but that is no longer true, certainly compared to the generational ZGC presented here. If you could determine the time where the collection would take place with a refcounting GC, i.e. when the last reference is cleared, you wouldn't need a refcounting GC. It is unpredictable pretty much by definition.
  - kaba0 4y ago
    That last line was just a play on this ( https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule ), but you are right of course.
  - yw3410 4y ago
    It does give better performance predictability! Decrementing a refcount may either be a no-op or expensive but crucially the op can happen only during that particular call, nowhere else.
    - pron 4y ago
      It does not. Maintaining the counter requires more work than tracing GCs do, and you don't know in advance when the last reference is dropped. True, you get more promptness in deallocation (not the same as predictability), which reduces the footprint but comes at the expense of compaction, the lack of which in most refcounting GCs also adds unpredictability. In contrast, in the common case, allocation with a compacting, tracing GC is a pointer bump and there's no overhead at all to copying references or other memory operations. During collection cycles, GC barriers are triggered, which add overheard to things like mutating pointers or reading pointers from objects in the heap. There's a great paper (linked from this post https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unified-theory-gc/ https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unifie...) showing how refcounting GCs can match the performance of tracing GCs -- in fact, how they can each have the properties of the other -- but that requires sophistication in the implementation of refcounting GCs that most of them don't have. So it is true that a sophisticated refcounting GC and a sophisticated tracing GC can exhibit similar behaviour, but while OpenJDK's tracing GCs are very sophisticated (especially ZGC and G1), most refcounting GCs in the wild are quite unsophisticated. It may certainly be true that unsophisticated refcounting GCs have more desirable properties than unsophisticated tracing GCs, but in practice the choice offered is between unsophisticated refcounting GCs and very sophisticated tracing GCs. The latter beat the former on most counts except for footprint overhead.
      - pkolaczk 4y ago
- pkolaczk 4y ago
  Rust's lifetimes is a strict subset of the general case, but it covers a good majority of use-cases with affine types - which means trivial allocation and deallocation. The number of times I had to use lifetime specifiers or dynamic lifetimes (RefCell/Rc/Arc) is extremely low, so low that it is not even a blip on the profile. Also, unlike most GC languages, Rust favors stack allocation over heap allocation, which makes most Rust program allocation rates several orders of magnitude lower than any Java program I saw (at the expense of more inter-stack copying, but that is extremely cheap because the top of the stack is almost always in L1 cache).
  - kaba0 4y ago
    In my experience most applications do need an escape hatch from a strictly tree-like lifetime pattern, it really is limiting. Object layout is the primary reason for the performance differences between low-level languages and manages ones — Java uses a thread local allocation buffer, which is for all practical purposes just as hot as the stack. What is more expensive is arrays of references and such, but that will be solved by value types once, hopefully. EDIT: What I’m trying to say is that there is very little overhead to creating short-lived objects in Java.
    - pkolaczk 4y ago
      > EDIT: What I’m trying to say is that there is very little overhead to creating short-lived objects in Java. I've been working on high performance Java software (databases) for many years now and the overhead of creating short lived objects is bearable only because we're going so far trying not to create those objects, writing Java in a kinda C-style - no objects, just primitives as much as you can. The total overhead is not just bumping up the pointer and zeroing memory but actually all what happens when the GC runs out of the slab. By allocating short lived objects youre making GC collect earlier and overall doing more work. Also the faster you allocate, the more objects survive the collection and more objects must be copied. That process is very expensive and also very complex.

kryptiskt 4y ago

Memory management for C is not itself a solved problem, not only is there a lot of performance to squeeze out of malloc itself (the benchmarks on https://github.com/microsoft/mimalloc https://github.com/microsoft/mimalloc exemplifies the variance between the implementations), but it's up to the programmer to implement memory management in the large in an efficient way, which is not an easy task. One sure mark of a slow C program is one with a ton of mallocs and frees strewn all over.

kaba0 4y ago

If we can know exactly where a particular object’s lifetime ends, then indeed we can write more efficient programs than possible with a GC, but that in the general case is not something we can determine at compile time (Rust’s lifetimes are a strict subset of the general case). Anything more dynamic will require some “ad hoc, informally-specified, bug-ridden, slow implementation of a GC”.

pron 4y ago
Rust also relies on a GC for the more dynamic lifetimes in Rust programs (reference counting), it just doesn't call it a GC, and while Rust's GC has a lower footprint than tracing GCs, it has worse performance and it suffers from cycle problems. I wouldn't call it "bug ridden" (perhaps "limited" is a better term), but it is slow. Some think that reference counting gives better performance predictability than a tracing GC, but that is no longer true, certainly compared to the generational ZGC presented here. If you could determine the time where the collection would take place with a refcounting GC, i.e. when the last reference is cleared, you wouldn't need a refcounting GC. It is unpredictable pretty much by definition.
- kaba0 4y ago
  That last line was just a play on this ( https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule ), but you are right of course.
- yw3410 4y ago
  It does give better performance predictability! Decrementing a refcount may either be a no-op or expensive but crucially the op can happen only during that particular call, nowhere else.
  - pron 4y ago
    It does not. Maintaining the counter requires more work than tracing GCs do, and you don't know in advance when the last reference is dropped. True, you get more promptness in deallocation (not the same as predictability), which reduces the footprint but comes at the expense of compaction, the lack of which in most refcounting GCs also adds unpredictability. In contrast, in the common case, allocation with a compacting, tracing GC is a pointer bump and there's no overhead at all to copying references or other memory operations. During collection cycles, GC barriers are triggered, which add overheard to things like mutating pointers or reading pointers from objects in the heap. There's a great paper (linked from this post https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unified-theory-gc/ https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unifie...) showing how refcounting GCs can match the performance of tracing GCs -- in fact, how they can each have the properties of the other -- but that requires sophistication in the implementation of refcounting GCs that most of them don't have. So it is true that a sophisticated refcounting GC and a sophisticated tracing GC can exhibit similar behaviour, but while OpenJDK's tracing GCs are very sophisticated (especially ZGC and G1), most refcounting GCs in the wild are quite unsophisticated. It may certainly be true that unsophisticated refcounting GCs have more desirable properties than unsophisticated tracing GCs, but in practice the choice offered is between unsophisticated refcounting GCs and very sophisticated tracing GCs. The latter beat the former on most counts except for footprint overhead.
    - pkolaczk 4y ago
pkolaczk 4y ago
Rust's lifetimes is a strict subset of the general case, but it covers a good majority of use-cases with affine types - which means trivial allocation and deallocation. The number of times I had to use lifetime specifiers or dynamic lifetimes (RefCell/Rc/Arc) is extremely low, so low that it is not even a blip on the profile. Also, unlike most GC languages, Rust favors stack allocation over heap allocation, which makes most Rust program allocation rates several orders of magnitude lower than any Java program I saw (at the expense of more inter-stack copying, but that is extremely cheap because the top of the stack is almost always in L1 cache).
- kaba0 4y ago
  In my experience most applications do need an escape hatch from a strictly tree-like lifetime pattern, it really is limiting. Object layout is the primary reason for the performance differences between low-level languages and manages ones — Java uses a thread local allocation buffer, which is for all practical purposes just as hot as the stack. What is more expensive is arrays of references and such, but that will be solved by value types once, hopefully. EDIT: What I’m trying to say is that there is very little overhead to creating short-lived objects in Java.
  - pkolaczk 4y ago
    > EDIT: What I’m trying to say is that there is very little overhead to creating short-lived objects in Java. I've been working on high performance Java software (databases) for many years now and the overhead of creating short lived objects is bearable only because we're going so far trying not to create those objects, writing Java in a kinda C-style - no objects, just primitives as much as you can. The total overhead is not just bumping up the pointer and zeroing memory but actually all what happens when the GC runs out of the slab. By allocating short lived objects youre making GC collect earlier and overall doing more work. Also the faster you allocate, the more objects survive the collection and more objects must be copied. That process is very expensive and also very complex.