31–40 of 245 posts
Earlier quoted context omitted.
i did google search for "refcount meme", and found out your comment as 3rd result, so it's not that popular...
I figured he was talking about Rust, given that it is basically a refcount system but with the added constraint that the refcount can not exceed 1. It's the only language that is anywhere close to meme status that I know of.
The memory mapping trick they use on x86 to avoid masking only works up to the maximum 48 bits of addressable virtual memory, so there is much less than 22 free bits in that case. It's also not quite free since it takes up TLB space.
Agreed - I'd go farther to say it only works for addresses in the userspace half, so on Linux you lose an extra bit and only get 47 (I don't know how the mappings are setup for Windows/OSX, sorry). It also might be worth pointing out that you now need 16x the page mappings (Since every mapping needs 15 duplicates for the possible flag states) - I don't know how Java does it's memory management but if it does lots of…
It doesn't. The article mentions it's only 3 mappings since those bits are colors, not arbitrary combinations of flags.
> I don't know how Java does it's memory management but if it does lots of small mappings (Which I'm guessing it does not) then that could be a concern.
openjdk generally uses large contiguous mappings but it may punch holes in the middle of the heap if it's configured to yield back memory to the OS. But applications that dynamically shrink and expand their heaps are not necessarily those that are concerned about the last quantum of page table overhead.
> And like you mentioned with the TLB
On the other hand it does support huge pages to mitigate costs of TLB entries.
Earlier quoted context omitted.
Could you elaborate? Why would refcount be a bad idea ? (genuine question)
Many think that refcount isn't a GC algorithm and that it is faster than GC. Well, refcounting is the basic way of implementing GC and is listed as GC algorithm in any serious CS book about GC algorithms like "The Garbage Collection Handbook". What many refer as GC is actually the GC algorithms that fall under the umbrella of tracing GC. Then refcounting is only faster than GC in very constrained scenarios: - no shar…
That is not true. Most atomic refcount implementations are lockfree (you do need synchronization though). This optimization has nothing to do with tracing. Given that you also need synchronization for tracing garbage collection (including frequent stop the world pauses in most cases, albeit brief ones), I don't think this is even really an advantage of tracing at all.
> - no deep datastructures, otherwise the call stack of cascading deletions will produce a stop similar to tracing GC
If your program has data structures that live through several collections, refcounting can be faster than tracing GC because it only traces objects once (when they die) instead of several times. Additionally, you can defer the refcount updates in ways that avoid the need to do lots of work on deallocation, and optimize for short-lived objects, to get many of the effects of generational GC. This also has little to do with tracing (except inasmuch as a reference counter with this optimization has to "trace" new objects to make them initially live, but in some sense this work to update the reference counter for the first time is just moved from object initialization time to a later point in the program). The reason it's not usually done is that it requires precise liveness information by an ambient collector, which complicates the implementation, but "exploiting liveness information" is not the same as "being a tracing GC."
> - implementations need to be clever about nested deletions when refcount reaches 0, otherwise a stack overflow might happen
This is extremely trivial to avoid (if you need to) and has nothing to do with tracing. It's really more a product of user-defined destructors than anything else, which you don't need to provide in order to implement reference counting. In fact, a lot of the supposedly inevitable slowness of reference counting compared to tracing goes away when you ban nontrivial destructors (and conversely, nontrivial destructors make tracing perform much worse).
> This is only relevant for naive refcount implementations, there are many optimisations, which endup turning a refcounting implementation into a tracing GC in disguise.
The most optimized versions of refcounting I'm aware of get their wins from things like precise knowledge about live references and update coalescing--not tracing, except for some young object optimizations as I alluded to above which are more about satisfying the generational hypothesis (they generally have a backup tracer in order to break cycles, but if you're willing to live without that they usually don't need tracing to reclaim all memory). Many optimizations people commonly associate with tracing (e.g. cache friendliness due to compaction) are in practice only relevant for young generations most of the time; for older ones both tracing and reference counted implementations tend to benefit more from a really smart allocator with intelligent memory layout and partial reclamation.
I agree that optimized versions of refcounting are difficult and the fact that you still need a backup tracer for most code discourages people from using it, as well as that tracing doesn't negate a lot of systems optimizations. But a lot of the stuff you're saying is pretty misleading: the things that make tracing efficient can mostly be applied to make reference counting efficient without "turning it into tracing," with the cost that optimized tracing and optimized reference counting both need much more invasive knowledge about the user program (and correspondingly restrict the users) compared to the less optimized versions.
Earlier quoted context omitted.
i did google search for "refcount meme", and found out your comment as 3rd result, so it's not that popular...
I figured he was talking about Rust, given that it is basically a refcount system but with the added constraint that the refcount can not exceed 1. It's the only language that is anywhere close to meme status that I know of.
Earlier quoted context omitted.
Could you elaborate? Why would refcount be a bad idea ? (genuine question)
Many think that refcount isn't a GC algorithm and that it is faster than GC. Well, refcounting is the basic way of implementing GC and is listed as GC algorithm in any serious CS book about GC algorithms like "The Garbage Collection Handbook". What many refer as GC is actually the GC algorithms that fall under the umbrella of tracing GC. Then refcounting is only faster than GC in very constrained scenarios: - no shar…
As usual, people are confused by improper use of terminology. It's like async in Python, three quarters of the complexity is in abuse of terminology.
The memory mapping trick they use on x86 to avoid masking only works up to the maximum 48 bits of addressable virtual memory, so there is much less than 22 free bits in that case. It's also not quite free since it takes up TLB space.
Agreed - I'd go farther to say it only works for addresses in the userspace half, so on Linux you lose an extra bit and only get 47 (I don't know how the mappings are setup for Windows/OSX, sorry). It also might be worth pointing out that you now need 16x the page mappings (Since every mapping needs 15 duplicates for the possible flag states) - I don't know how Java does it's memory management but if it does lots of…
Nope. They went into this in the article:
> Since by design only one of remap, mark0 and mark1 can be 1 at any point in time, it’s possible to do this with three mappings. There’s a nice diagram[1] in the ZGC source for this.
[1]: http://hg.openjdk.java.net/zgc/zgc/file/59c07aef65ac/src/hot...
That might not be totally current, as it doesn't cover the finalizable flag, but if it works the same, that would only be four mappings. If it works differently, then it would be a maximum of 6 mappings. Not 16.
Earlier quoted context omitted.
Many think that refcount isn't a GC algorithm and that it is faster than GC. Well, refcounting is the basic way of implementing GC and is listed as GC algorithm in any serious CS book about GC algorithms like "The Garbage Collection Handbook". What many refer as GC is actually the GC algorithms that fall under the umbrella of tracing GC. Then refcounting is only faster than GC in very constrained scenarios: - no shar…
> - no sharing across threads, otherwise locking is required for refcount updates That is not true. Most atomic refcount implementations are lockfree (you do need synchronization though). This optimization has nothing to do with tracing. Given that you also need synchronization for tracing garbage collection (including frequent stop the world pauses in most cases, albeit brief ones), I don't think this is even really…
I know Python, objective-c, and swift all use refcounting, but just for my own reading, what language has the most optimized ref counting right now?
> GC’s SPECjbb 2015 throughput numbers are roughly comparable with the Parallel GC (which optimises for throughput) but with an average pause time of 1ms and a max of 4ms. This is in contrast to G1 and Parallel who had average pause times in excess of 200ms. Not bad! Looking forward to seeing how this performs with a diverse range of workloads as it matures.
Earlier quoted context omitted.
> - no sharing across threads, otherwise locking is required for refcount updates That is not true. Most atomic refcount implementations are lockfree (you do need synchronization though). This optimization has nothing to do with tracing. Given that you also need synchronization for tracing garbage collection (including frequent stop the world pauses in most cases, albeit brief ones), I don't think this is even really…
> The most optimized versions of refcounting I'm aware of get their wins from things like precise knowledge about live references and update coalescing- I know Python, objective-c, and swift all use refcounting, but just for my own reading, what language has the most optimized ref counting right now?
There may have been further developments in improving RC throughput since 2013, but I'm not familiar with them; outside of Apple, there's very little modern research into optimizing reference counting. I know Swift does many cool optimizations of its own, but I'm not sure how restricted they are by having to remain compatible with Objective C.