3 ms·

> If you have a lot of microallocations, then your program is going to be slow regardless of you using manual memory management, RAII or a tracing GC. No, that

> If you have a lot of microallocations, then your program is going to be slow regardless of you using manual memory management, RAII or a tracing GC. No, that's no true. Tracing GC is mainly O(f(live stuff)), not O(f(dead stuff)), so there is basically no problem making lot's of garbage if you don't have any exotic latency requirements. > Another reason is eliminating unnecessary pointer indirection, which helps make sure that instead of loading data with two MOVs from memory polluting the cache, you need only one. Uh, that is locality, what I started with, no? > I'm leaning towards a GC-based design that relies a lot on value types. That sounds good. Compacting GC makes locality less of a problem than one that would think with the old Java/Haskell style, but yes we in Haskell also want unboxed types (the name I prefer) to have more control. In cases where if one traverses the parent they almost certainly traverse the child (e.g. from map nodes to their keys (not child maps nodes) they area good fit, as with long live objects. ---- The overall lesson here is that Haskell/Java programs can be surprising fast and not memory thrashing, but for reasons that are quite surprising. Two Haskell and Rust programs can feel similar in what they mean and how they are written, but then be fast for very, very different reasons.

yakubin 5y ago
> No, that's no true. Tracing GC is mainly O(f(live stuff)), not O(f(dead stuff)), so there is basically no problem making lot's of garbage if you don't have any exotic latency requirements. That's true for copying generational garbage collectors. You only need to copy the live stuff and forget everything else. But in e.g. a mark-sweep collector, sweeping dead stuff takes time. In particular, e.g. Chromium's Oilpan can take a long time in the sweeping phase, when there are lot of dead objects. But when there are a lot of microallocations, you also have a lot of live objects, which could otherwise be just a single object in the case of e.g. big arrays. >> Another reason is eliminating unnecessary pointer indirection, which helps make sure that instead of loading data with two MOVs from memory polluting the cache, you need only one. > Uh, that is locality, what I started with, no? Hmm, seems I highlighted the wrong aspect. It's not just locality, but also size of the data you're dealing with. Those pointers take space. Another aspect of it is that arrays of unboxed elements have more predictable access patterns. Iterating over an array of unboxed elements is friendly to cache prefetching. CPUs recognize this (linear) pattern. With boxed elements and a compacting garbage collector locality may be fine, i.e. elements of the array may be close in memory, but the order in which you fetch elements is pretty random. When the cumulative size of the elements of the array is significantly larger than 64 bytes (the usual size of a cache line), then you're going to be prefetching the wrong regions of the array. There are situations where the order is going to be right, because e.g. the elements were created in the same order in which they are in the array, but that will be destroyed after some sorting, filtering or whatever.
- Ericson2314 5y ago
  > That's true for copying generational garbage collectors. You only need to copy the live stuff and forget everything else. But in e.g. a mark-sweep collector, sweeping dead stuff takes time. In particular, e.g. Chromium's Oilpan can take a long time in the sweeping phase, when there are lot of dead objects. Sure. I got confused why people do these designs which seem to me to be an awkward compromise, but yes they exist. > But when there are a lot of microallocations, you also have a lot of live objects, which could otherwise be just a single object in the case of e.g. big arrays. Not necessary in general. Sure with the array, and I agree that is a bit silly. But there is no general law that more microallocations means more live data. > Hmm, seems I highlighted the wrong aspect.... Sure those things sound sensible. I don't mean to disagree with any of that.

yakubin 5y ago

> No, that's no true. Tracing GC is mainly O(f(live stuff)), not O(f(dead stuff)), so there is basically no problem making lot's of garbage if you don't have any exotic latency requirements. That's true for copying generational garbage collectors. You only need to copy the live stuff and forget everything else. But in e.g. a mark-sweep collector, sweeping dead stuff takes time. In particular, e.g. Chromium's Oilpan can take a long time in the sweeping phase, when there are lot of dead objects. But when there are a lot of microallocations, you also have a lot of live objects, which could otherwise be just a single object in the case of e.g. big arrays. >> Another reason is eliminating unnecessary pointer indirection, which helps make sure that instead of loading data with two MOVs from memory polluting the cache, you need only one. > Uh, that is locality, what I started with, no? Hmm, seems I highlighted the wrong aspect. It's not just locality, but also size of the data you're dealing with. Those pointers take space. Another aspect of it is that arrays of unboxed elements have more predictable access patterns. Iterating over an array of unboxed elements is friendly to cache prefetching. CPUs recognize this (linear) pattern. With boxed elements and a compacting garbage collector locality may be fine, i.e. elements of the array may be close in memory, but the order in which you fetch elements is pretty random. When the cumulative size of the elements of the array is significantly larger than 64 bytes (the usual size of a cache line), then you're going to be prefetching the wrong regions of the array. There are situations where the order is going to be right, because e.g. the elements were created in the same order in which they are in the array, but that will be destroyed after some sorting, filtering or whatever.

Ericson2314 5y ago
> That's true for copying generational garbage collectors. You only need to copy the live stuff and forget everything else. But in e.g. a mark-sweep collector, sweeping dead stuff takes time. In particular, e.g. Chromium's Oilpan can take a long time in the sweeping phase, when there are lot of dead objects. Sure. I got confused why people do these designs which seem to me to be an awkward compromise, but yes they exist. > But when there are a lot of microallocations, you also have a lot of live objects, which could otherwise be just a single object in the case of e.g. big arrays. Not necessary in general. Sure with the array, and I agree that is a bit silly. But there is no general law that more microallocations means more live data. > Hmm, seems I highlighted the wrong aspect.... Sure those things sound sensible. I don't mean to disagree with any of that.