7 ms·

JVM Anatomy Park – 11: Moving GC and Locality

138 points by hyperpape 9y ago

notamy 9y ago
Love these. Even after reading over the JVM spec, these writeups still show how much I don't know.
- pvg 9y ago
  This might be because these are about (important) implementation details the spec quite deliberately does not specify.
deleted 9y ago
[deleted]
fauigerzigerk 9y ago
>Be ever so slightly wary when someone sells you the non-moving GC or no-GC solutions And you should also be wary whenever someone uses the JVM to make a general point about GC strategies. The importance of a moving/compacting GC varies hugely depending on whether or not a language/runtime lets developers define the memory layout of objects. In a language like Java (and other JVM based languages) that doesn't let you do that relying on the GC is the only way to fix locality. But that is not the case in languages that have structured value types (C#, Go, Swift, ...).
- pizlonator 9y ago
  Totally! Java is in a class of languages that encourages a high allocation rate. I think that each language has a kind of "average" allocation rate that is an indirect outcome of the various design decisions in the language. I think you're right that C# probably has a lower average allocation rate because of structs. It's true that languages with lower average allocation rates benefit less from compaction, because they benefit less from any GC optimization.
- geodel 9y ago
  You might have checked but here is IanT's reply on "Why golang garbage-collector not implement Generational and Compact gc? There is also interesting discussion in thread. https://groups.google.com/d/msg/golang-nuts/KJiyv2mV2pU/wdBUH1mHCAAJ https://groups.google.com/d/msg/golang-nuts/KJiyv2mV2pU/wdBU... "However, modern memory allocation algorithms, like the tcmalloc-based approach used by the Go runtime, have essentially no fragmentation issues. And while a bump allocator can be simple and efficient for a single-threaded program, in a multi-threaded program like Go it requires locks. In general it's likely to be more efficient to allocate memory using a set of per-thread caches, and at that point you've lost the advantages of a bump allocator. So I would assert that, in general, with many caveats, there is no real advantage .."
  - pizlonator 9y ago
    Bump allocators don't require locks. Bump allocators are especially effective in the presence of thread-local caches. Whoever wrote that must not be very familiar with how memory management works.
  - pcwalton 9y ago
    > And while a bump allocator can be simple and efficient for a single-threaded program, in a multi-threaded program like Go it requires locks. In general it's likely to be more efficient to allocate memory using a set of per-thread caches, and at that point you've lost the advantages of a bump allocator. Ian is extremely confused here. Every production multithreaded generational GC uses thread-local allocation buffers (edit: thanks to Filip for correcting my terminology).
    - pizlonator 9y ago
      Very few production multithreaded generational GCs use per-thread nurseries. But probably all of them use thread-local caches, or what you might call per-thread caches. I think that's what you might have meant. Per-thread nurseries is a shit idea unless your language has extra-super-high levels of infant mortality. Remember that in a per-thread nursery genGC, the write barrier has to infect the pointed-to object with the global heap so that future stores to that object also trigger the barrier. In a normal genGC, the pointed-to object is unaffected; the stored-to object is merely shaded (or card-marked, or logged, or whatever) for revisiting. Humorously for parent's post, to my knowledge the first instance of a thread-local cache was the idea that a multithreaded compacting GC can chop off a slice of memory from the global bump allocator and then use it to service a thread-local allocator. Not 100% sure though because maybe Boehm and friends beat everyone to it.
- pcwalton 9y ago
  > The importance of a moving/compacting GC varies hugely depending on whether or not a language/runtime lets developers define the memory layout of objects. Far from varying "hugely", the programmer-specified memory layout of objects empirically barely has any effect at all on locality. This meme is cited a lot but doesn't actually hold up in reality. We've probably done one of the few actual studies of this in Rust, because we started reordering struct fields in the compiler instead of using the field order the developer wrote (though this can be turned off), and it barely affected locality at all. Memory usage was slightly improved (which argues against your point that developers, left to their own devices, specify optimal layouts).
  - pizlonator 9y ago
    I thought he was talking about the existence (or lack) of struct types, not the ability to lay things out in a struct. The presence of struct types reduces allocation churn, so all memory management things become less important.
    - pcwalton 9y ago
      Yeah, if "letting developers define the memory layout of objects" means "value types" then that's obviously true. But C# has value types, and the generational hypothesis certainly holds for C#. So while good memory management becomes less important, it doesn't change what the optimal MM approach is.
      - pizlonator 9y ago
        Of course it changes the MM approach if allocation rate goes down. The higher the allocation rate, the larger the throughput advantage of compacting collectors. But compacting collectors have all sorts of other costs - complexity, hard to make them concurrent, potential for high barrier overheads. So, if your allocation rate is low enough, then the throughput advantage of the compacting collector might be low enough that you might think to use some other kind of collector. JSC is a great example. I should say that the allocation rate that matters is really the allocation rate scaled against the GC's speed; in classic terms we're talking about the cons/mark ratio. JS has a low cons/mark ratio (low relative allocation rate) because the JS collector is fundamentally no slower than any other one but the JS mutator is significantly slower than something like Java. So JS's allocation rate relative to the GC is lower than Java's allocation rate relative to the GC. This means that all GC throughput effects are dampened, which is one of the big reasons why JSC can get away with a collector that doesn't compact. Also, the generational hypothesis has nothing to do with whether compaction is profitable. These are orthogonal things. (EDIT: replaced "fundamentally now slower" with "fundamentally no slower", above)
pizlonator 9y ago
I think that the main reason why compacting GCs improve performance is that they obviate the need for a sweep phase, which always has some cost even if you optimize the hell out of it. I believe that from a scientific standpoint, it is still an open question exactly how much of the compacting GC speed-up is due to not sweeping versus improved locality. It's hard to construct a good experiment of this, because non-compacting GCs always have at least some kind of sweep phase. For example, if the non-compacting collector experiences fragmentation, then is its reduced performance due to the cache misses experienced by the sweeper (which have nothing to do with locality per se - they are just an inherent cost of sweeping) or because of cache misses experienced by accesses within the program due to the changed ordering of objects? The experiments in this post are super interesting, but it's not a good idea to extrapolate from microbenchmarks. In my experience big programs always have some chaotic subtlety, which can sometimes even make its behavior be the opposite of what the microbenchmark tells you. It's worth noting that GCs are tuned so that the typical program will typically allocate objects so as to maximize the locality of object accesses. Non-compacting GCs tend to allocate objects of the same type next to each other (so if you allocate O, P, Q where O and Q have type T and P bas type S, then Q will be right next to O but P will be elsewhere) while compacting GCs tend to allocate objects in sequence (so O and P will be adjacent, and then after P will be Q). There's no guarantee that any particular program will prefer one ordering over the other.
- panic 9y ago
  It's hard to construct a good experiment of this, because non-compacting GCs always have at least some kind of sweep phase. For example, if the non-compacting collector experiences fragmentation, then is its reduced performance due to the cache misses experienced by the sweeper (which have nothing to do with locality per se - they are just an inherent cost of sweeping) or because of cache misses experienced by accesses within the program due to the changed ordering of objects? What about adding a dummy sweep phase to the compacting collector? Then you could compare compacting + dummy sweep with non-compacting + real sweep.
  - pizlonator 9y ago
    There is no way to implement a dummy sweep that has the behavior of a real sweep if the collector is doing compaction. Maybe it isn't obvious: compaction isn't a plug-in that you put into a collector. It's a different way of writing a collector. For example, compacting collectors often avoid having any mark bits. You need mark bits to sweep (among other things).
openasocket 9y ago
OT, but I'm curious if there's any manual memory management analogue for moving GC. Generally in that setting if you want to allocate a bunch of objects with good locality you use a slab allocator. But what if you want to compact that slab after a certain period of time because of fragmentation, or you have a bunch of object already on the heap you want to move together onto a single slab? The complexity is you have to have a way to update all the references to those objects. I'm curious if anyone knows of such work that has been done?
- gwbas1c 9y ago
  Doubtful, because compaction requires updating the pointers to the new locations. In manual memory management, the compactor would have to stop the world, know enough about each structures' internal layouts to know where the pointers are, and then update all of them. That would be impossible when trying to interoperate among different languages. Manual memory management has its place, but if you need compaction, you should use a garbage collector. Manual memory management, (and reference counting,) aren't always faster than GC. (Malloc has overhead too, and can run slower than GC.)
BenoitP 9y ago
I ran the 3 visualizations at the end of the article and made imgur albums: Images are in order. JOLSample_22_Compaction: http://imgur.com/a/agJaR http://imgur.com/a/agJaR JOLSample_23_Defragmentation: http://imgur.com/a/A74k9 http://imgur.com/a/A74k9 JOLSample_24_Colocation: http://imgur.com/a/RTrhL http://imgur.com/a/RTrhL In JOLSample_22_Compaction, Aleksey writes: "It happens because many temporary objects are allocated while populating the list.". I'm having trouble knowing exactly what are the temporary objects. Is it the implicit c.toString()? Maybe also the "int minCapacity" in ensureCapacityInternal in ArrayList[1]? Is there more? Also, in JOLSample_22_Compaction it is kind of nice to see some gaps spaced by growing powers of 2 in http://imgur.com/4T5dBi8 http://imgur.com/4T5dBi8 ; it must be the actual pointer arrays of the ArrayList, replaced successively to grow in size. And the current one being in green color. Or am I mistaken? Fascinating. [1] http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#222 http://grepcode.com/file/repository.grepcode.com/java/root/j...
deleted 9y ago
[deleted]

138 points by hyperpape 9y ago

notamy 9y ago

Love these. Even after reading over the JVM spec, these writeups still show how much I don't know.

pvg 9y ago
This might be because these are about (important) implementation details the spec quite deliberately does not specify.

deleted 9y ago

[deleted]

fauigerzigerk 9y ago

>Be ever so slightly wary when someone sells you the non-moving GC or no-GC solutions And you should also be wary whenever someone uses the JVM to make a general point about GC strategies. The importance of a moving/compacting GC varies hugely depending on whether or not a language/runtime lets developers define the memory layout of objects. In a language like Java (and other JVM based languages) that doesn't let you do that relying on the GC is the only way to fix locality. But that is not the case in languages that have structured value types (C#, Go, Swift, ...).

pizlonator 9y ago
Totally! Java is in a class of languages that encourages a high allocation rate. I think that each language has a kind of "average" allocation rate that is an indirect outcome of the various design decisions in the language. I think you're right that C# probably has a lower average allocation rate because of structs. It's true that languages with lower average allocation rates benefit less from compaction, because they benefit less from any GC optimization.
geodel 9y ago
You might have checked but here is IanT's reply on "Why golang garbage-collector not implement Generational and Compact gc? There is also interesting discussion in thread. https://groups.google.com/d/msg/golang-nuts/KJiyv2mV2pU/wdBUH1mHCAAJ https://groups.google.com/d/msg/golang-nuts/KJiyv2mV2pU/wdBU... "However, modern memory allocation algorithms, like the tcmalloc-based approach used by the Go runtime, have essentially no fragmentation issues. And while a bump allocator can be simple and efficient for a single-threaded program, in a multi-threaded program like Go it requires locks. In general it's likely to be more efficient to allocate memory using a set of per-thread caches, and at that point you've lost the advantages of a bump allocator. So I would assert that, in general, with many caveats, there is no real advantage .."
- pizlonator 9y ago
  Bump allocators don't require locks. Bump allocators are especially effective in the presence of thread-local caches. Whoever wrote that must not be very familiar with how memory management works.
- pcwalton 9y ago
  > And while a bump allocator can be simple and efficient for a single-threaded program, in a multi-threaded program like Go it requires locks. In general it's likely to be more efficient to allocate memory using a set of per-thread caches, and at that point you've lost the advantages of a bump allocator. Ian is extremely confused here. Every production multithreaded generational GC uses thread-local allocation buffers (edit: thanks to Filip for correcting my terminology).
  - pizlonator 9y ago
    Very few production multithreaded generational GCs use per-thread nurseries. But probably all of them use thread-local caches, or what you might call per-thread caches. I think that's what you might have meant. Per-thread nurseries is a shit idea unless your language has extra-super-high levels of infant mortality. Remember that in a per-thread nursery genGC, the write barrier has to infect the pointed-to object with the global heap so that future stores to that object also trigger the barrier. In a normal genGC, the pointed-to object is unaffected; the stored-to object is merely shaded (or card-marked, or logged, or whatever) for revisiting. Humorously for parent's post, to my knowledge the first instance of a thread-local cache was the idea that a multithreaded compacting GC can chop off a slice of memory from the global bump allocator and then use it to service a thread-local allocator. Not 100% sure though because maybe Boehm and friends beat everyone to it.
pcwalton 9y ago
> The importance of a moving/compacting GC varies hugely depending on whether or not a language/runtime lets developers define the memory layout of objects. Far from varying "hugely", the programmer-specified memory layout of objects empirically barely has any effect at all on locality. This meme is cited a lot but doesn't actually hold up in reality. We've probably done one of the few actual studies of this in Rust, because we started reordering struct fields in the compiler instead of using the field order the developer wrote (though this can be turned off), and it barely affected locality at all. Memory usage was slightly improved (which argues against your point that developers, left to their own devices, specify optimal layouts).
- pizlonator 9y ago
  I thought he was talking about the existence (or lack) of struct types, not the ability to lay things out in a struct. The presence of struct types reduces allocation churn, so all memory management things become less important.
  - pcwalton 9y ago
    Yeah, if "letting developers define the memory layout of objects" means "value types" then that's obviously true. But C# has value types, and the generational hypothesis certainly holds for C#. So while good memory management becomes less important, it doesn't change what the optimal MM approach is.
    - pizlonator 9y ago
      Of course it changes the MM approach if allocation rate goes down. The higher the allocation rate, the larger the throughput advantage of compacting collectors. But compacting collectors have all sorts of other costs - complexity, hard to make them concurrent, potential for high barrier overheads. So, if your allocation rate is low enough, then the throughput advantage of the compacting collector might be low enough that you might think to use some other kind of collector. JSC is a great example. I should say that the allocation rate that matters is really the allocation rate scaled against the GC's speed; in classic terms we're talking about the cons/mark ratio. JS has a low cons/mark ratio (low relative allocation rate) because the JS collector is fundamentally no slower than any other one but the JS mutator is significantly slower than something like Java. So JS's allocation rate relative to the GC is lower than Java's allocation rate relative to the GC. This means that all GC throughput effects are dampened, which is one of the big reasons why JSC can get away with a collector that doesn't compact. Also, the generational hypothesis has nothing to do with whether compaction is profitable. These are orthogonal things. (EDIT: replaced "fundamentally now slower" with "fundamentally no slower", above)

pizlonator 9y ago

I think that the main reason why compacting GCs improve performance is that they obviate the need for a sweep phase, which always has some cost even if you optimize the hell out of it. I believe that from a scientific standpoint, it is still an open question exactly how much of the compacting GC speed-up is due to not sweeping versus improved locality. It's hard to construct a good experiment of this, because non-compacting GCs always have at least some kind of sweep phase. For example, if the non-compacting collector experiences fragmentation, then is its reduced performance due to the cache misses experienced by the sweeper (which have nothing to do with locality per se - they are just an inherent cost of sweeping) or because of cache misses experienced by accesses within the program due to the changed ordering of objects? The experiments in this post are super interesting, but it's not a good idea to extrapolate from microbenchmarks. In my experience big programs always have some chaotic subtlety, which can sometimes even make its behavior be the opposite of what the microbenchmark tells you. It's worth noting that GCs are tuned so that the typical program will typically allocate objects so as to maximize the locality of object accesses. Non-compacting GCs tend to allocate objects of the same type next to each other (so if you allocate O, P, Q where O and Q have type T and P bas type S, then Q will be right next to O but P will be elsewhere) while compacting GCs tend to allocate objects in sequence (so O and P will be adjacent, and then after P will be Q). There's no guarantee that any particular program will prefer one ordering over the other.

panic 9y ago
It's hard to construct a good experiment of this, because non-compacting GCs always have at least some kind of sweep phase. For example, if the non-compacting collector experiences fragmentation, then is its reduced performance due to the cache misses experienced by the sweeper (which have nothing to do with locality per se - they are just an inherent cost of sweeping) or because of cache misses experienced by accesses within the program due to the changed ordering of objects? What about adding a dummy sweep phase to the compacting collector? Then you could compare compacting + dummy sweep with non-compacting + real sweep.
- pizlonator 9y ago
  There is no way to implement a dummy sweep that has the behavior of a real sweep if the collector is doing compaction. Maybe it isn't obvious: compaction isn't a plug-in that you put into a collector. It's a different way of writing a collector. For example, compacting collectors often avoid having any mark bits. You need mark bits to sweep (among other things).

openasocket 9y ago

OT, but I'm curious if there's any manual memory management analogue for moving GC. Generally in that setting if you want to allocate a bunch of objects with good locality you use a slab allocator. But what if you want to compact that slab after a certain period of time because of fragmentation, or you have a bunch of object already on the heap you want to move together onto a single slab? The complexity is you have to have a way to update all the references to those objects. I'm curious if anyone knows of such work that has been done?

gwbas1c 9y ago
Doubtful, because compaction requires updating the pointers to the new locations. In manual memory management, the compactor would have to stop the world, know enough about each structures' internal layouts to know where the pointers are, and then update all of them. That would be impossible when trying to interoperate among different languages. Manual memory management has its place, but if you need compaction, you should use a garbage collector. Manual memory management, (and reference counting,) aren't always faster than GC. (Malloc has overhead too, and can run slower than GC.)

BenoitP 9y ago

I ran the 3 visualizations at the end of the article and made imgur albums: Images are in order. JOLSample_22_Compaction: http://imgur.com/a/agJaR http://imgur.com/a/agJaR JOLSample_23_Defragmentation: http://imgur.com/a/A74k9 http://imgur.com/a/A74k9 JOLSample_24_Colocation: http://imgur.com/a/RTrhL http://imgur.com/a/RTrhL In JOLSample_22_Compaction, Aleksey writes: "It happens because many temporary objects are allocated while populating the list.". I'm having trouble knowing exactly what are the temporary objects. Is it the implicit c.toString()? Maybe also the "int minCapacity" in ensureCapacityInternal in ArrayList[1]? Is there more? Also, in JOLSample_22_Compaction it is kind of nice to see some gaps spaced by growing powers of 2 in http://imgur.com/4T5dBi8 http://imgur.com/4T5dBi8 ; it must be the actual pointer arrays of the ArrayList, replaced successively to grow in size. And the current one being in green color. Or am I mistaken? Fascinating. [1] http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#222 http://grepcode.com/file/repository.grepcode.com/java/root/j...

deleted 9y ago

[deleted]