3 ms·

> Reference counting and mark-sweep go together. You mean the sweep phase goes through and cleans out all the objects with zero reference counts? I always tho

> Reference counting and mark-sweep go together. You mean the sweep phase goes through and cleans out all the objects with zero reference counts? I always thought the point of reference counting was to deallocate the object once the count goes to zero (which is why people complain it is slow as it can lead to cascading effects). As to “most GC's are based on the mark-sweep algorithm” — I have a whole folder of papers on different GC algorithms, probably not the rabbit hole you want to go down if you have something you’re happy with. The minischeme interpreter I poke at every once in a while has a super simple GC that I have to resist messing with because it Just Works™ and I’d be chasing my tail for who knows how long getting another one working.

ryanmccullagh 5y ago
I thought that the mark-sweep isn't even necessary, if you don't have cycles. Reference counting can be a sufficient GC strategy but when cycles are introduced, I think that's the problem that mark-sweep solves. That's awesome. Which papers do you find the most useful?
carapace 5y ago
Have you read, and if so what do you think of, "A Unified Theory of Garbage Collection"? https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-garbage.pdf https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... > Tracing and reference counting are uniformly viewed as being fun- damentally different approaches to garbage collection that possess very distinct performance properties. We have implemented high- performance collectors of both types, and in the process observed that the more we optimized them, the more similarly they behaved — that they seem to share some deep structure. > We present a formulation of the two algorithms that shows that they are in fact duals of each other. Intuitively, the difference is that tracing operates on live objects, or “matter”, while reference count- ing operates on dead objects, or “anti-matter”. For every operation performed by the tracing collector, there is a precisely correspond- ing anti-operation performed by the reference counting collector. > Using this framework, we show that all high-performance col- lectors (for example, deferred reference counting and generational collection) are in fact hybrids of tracing and reference counting. We develop a uniform cost-model for the collectors to quantify the trade-offs that result from choosing different hybridizations of trac- ing and reference counting. This allows the correct scheme to be selected based on system performance requirements and the ex- pected properties of the target application.

ryanmccullagh 5y ago

I thought that the mark-sweep isn't even necessary, if you don't have cycles. Reference counting can be a sufficient GC strategy but when cycles are introduced, I think that's the problem that mark-sweep solves. That's awesome. Which papers do you find the most useful?

carapace 5y ago

Have you read, and if so what do you think of, "A Unified Theory of Garbage Collection"? https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-garbage.pdf https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... > Tracing and reference counting are uniformly viewed as being fun- damentally different approaches to garbage collection that possess very distinct performance properties. We have implemented high- performance collectors of both types, and in the process observed that the more we optimized them, the more similarly they behaved — that they seem to share some deep structure. > We present a formulation of the two algorithms that shows that they are in fact duals of each other. Intuitively, the difference is that tracing operates on live objects, or “matter”, while reference count- ing operates on dead objects, or “anti-matter”. For every operation performed by the tracing collector, there is a precisely correspond- ing anti-operation performed by the reference counting collector. > Using this framework, we show that all high-performance col- lectors (for example, deferred reference counting and generational collection) are in fact hybrids of tracing and reference counting. We develop a uniform cost-model for the collectors to quantify the trade-offs that result from choosing different hybridizations of trac- ing and reference counting. This allows the correct scheme to be selected based on system performance requirements and the ex- pected properties of the target application.