3 ms·

Forget garbage collection in the sense of any variant of mark-and-sweep. For an operating system latency is more important than through put, so you really want

Forget garbage collection in the sense of any variant of mark-and-sweep. For an operating system latency is more important than through put, so you really want real time memory management. Is the assumption that mark and sweep is slower than real-time memory management? It's actually been proven false, e.g. the .NET CLR runs faster than native C code in certain situations. If you use reference counting, then there is a lazy variant that gives you just that; no pauses due to reclaiming free memory. Reference counting is extremely slow because of how memory caching works. Whenever you update reference counts, you're trashing the CPU cache. It seems like there's no way refcounting could be faster than mark and sweep due to this. What am I missing?

cwzwarich 13y ago
Tracing garbage collection has better throughput than reference counting, but reference counting has lower and more predictable latency. If you were actually going to try do tracing GC on the operating system level, you would probably have to use one of the more involved GC algorithms that require kernel support like Azul's C4 collector.
- procrastitron 13y ago
  "Tracing garbage collection has better throughput than reference counting, but reference counting has lower and more predictable latency." Exactly this. I would actually back off a bit and only claim that reference counting has more predictable latency, but the point is to sacrifice throughput in order to reduce worst case latency.
- lmm 13y ago
  > you would probably have to use one of the more involved GC algorithms that require kernel support like Azul's C4 collector Which shouldn't be such a problem if you're already writing an OS? Also AIUI the only "hard part" of C4 is making sure objects don't get modified while they're being moved (that's what the barrier's there to detect) - which isn't a problem if everything's immutable.
  - cwzwarich 13y ago
    > Which shouldn't be such a problem if you're already writing an OS? I guess that could've used more context. I was trying to point out that in the larger landscape of GC algorithms, the one used by .NET is not that advanced, even though it's better than the GC used by common scripting languages. > Also AIUI the only "hard part" of C4 is making sure objects don't get modified while they're being moved (that's what the barrier's there to detect) - which isn't a problem if everything's immutable. Would absolutely everything be immutable? How would you implement lazy evaluation with the correct time complexity? The expensive part of any garbage collector with short pause times is bound to be the read barrier, which is still needed with only immutable data. If the GC is compacting and wants to relocate an object, it has to rewrite all references to point to the new copy of the object. C4 uses a read barrier to enforce the invariant that all references point to the up-to-date copy on a load of a reference, not just on a use of a reference. It relies on its ability to immediately update all references to reuse compacted pages during compaction, which means that gratuitous amounts of free memory are not required (a common problem with moving collectors). You might be able to come up with alternate collector design that uses some of the same ideas as C4 while exploiting immutability, but if you loosen the healing read barrier you weaken your ability to reuse memory and put a bound on memory growth, since a reference to an old copy might always escape to the next round of collection.
banachtarski 13y ago
throughput != latency
wfunction 13y ago
> It's actually been proven false, e.g. the .NET CLR runs faster than native C code in certain situations. [citation needed] and by citation I mean example code that "proves" this.

cwzwarich 13y ago

Tracing garbage collection has better throughput than reference counting, but reference counting has lower and more predictable latency. If you were actually going to try do tracing GC on the operating system level, you would probably have to use one of the more involved GC algorithms that require kernel support like Azul's C4 collector.

procrastitron 13y ago
"Tracing garbage collection has better throughput than reference counting, but reference counting has lower and more predictable latency." Exactly this. I would actually back off a bit and only claim that reference counting has more predictable latency, but the point is to sacrifice throughput in order to reduce worst case latency.
lmm 13y ago
> you would probably have to use one of the more involved GC algorithms that require kernel support like Azul's C4 collector Which shouldn't be such a problem if you're already writing an OS? Also AIUI the only "hard part" of C4 is making sure objects don't get modified while they're being moved (that's what the barrier's there to detect) - which isn't a problem if everything's immutable.
- cwzwarich 13y ago
  > Which shouldn't be such a problem if you're already writing an OS? I guess that could've used more context. I was trying to point out that in the larger landscape of GC algorithms, the one used by .NET is not that advanced, even though it's better than the GC used by common scripting languages. > Also AIUI the only "hard part" of C4 is making sure objects don't get modified while they're being moved (that's what the barrier's there to detect) - which isn't a problem if everything's immutable. Would absolutely everything be immutable? How would you implement lazy evaluation with the correct time complexity? The expensive part of any garbage collector with short pause times is bound to be the read barrier, which is still needed with only immutable data. If the GC is compacting and wants to relocate an object, it has to rewrite all references to point to the new copy of the object. C4 uses a read barrier to enforce the invariant that all references point to the up-to-date copy on a load of a reference, not just on a use of a reference. It relies on its ability to immediately update all references to reuse compacted pages during compaction, which means that gratuitous amounts of free memory are not required (a common problem with moving collectors). You might be able to come up with alternate collector design that uses some of the same ideas as C4 while exploiting immutability, but if you loosen the healing read barrier you weaken your ability to reuse memory and put a bound on memory growth, since a reference to an old copy might always escape to the next round of collection.

banachtarski 13y ago

throughput != latency

wfunction 13y ago

> It's actually been proven false, e.g. the .NET CLR runs faster than native C code in certain situations. [citation needed] and by citation I mean example code that "proves" this.