On 16/05/2011 10:40 AM, Tim Chevalier wrote:
Ah. I wasn't claiming anything about the relationship about GC and
ref-counting. But I found Graydon's assertion that "GC trashes the
whole cache regularly" to be rather strong, as there are many kinds of
GC, not just copying.
True. I was too simplistic, apologies. In truth, automatic memory
management has dozens of dimensions and I was only commenting on, er,
three of them them, and somewhat generally.
- When the scheme is based on an algorithm that is effectively based
on some O(fraction-of(live data)) step, average-case latency grows
as heap size grows.
- Not only latency, but cache pressure: visiting O(live data) tends
to flush everything hot in favour of live-but-cold stuff, as heaps
grow.
- When the scheme is based on an algorithm that defers a lot of
reclamation, there will be heap overhead. Copying definitely
doubles, but it's not uncommon for mark-sweep collectors to
carry similar orders of "dead but not yet reclaimed" heap
overheads.
It's true that generational collectors, concurrent collectors,
compacting collectors, hybrid-RC collectors, arena collectors, and all
manner of other systems can mitigate the constant factors in these
considerations, and I certainly don't mean to imply they never work.
Just serve a bit of an antidote to the "GC always wins" position I
sometimes hear. It sometimes does, sometimes doesn't, and often requires
careful analysis of domain requirements.
I've really not seen any single answer for the "best" storage management
system; automatic or manual. Apologies if it sounds like I'm proposing
RC as that champion. It's surely got flaws (code footprint, cache write
traffic and acyclicality; nontrivial issues!) My experience is merely
that it's predictable, has low latency and heap overhead, scales well
with large heaps, and hybridizes acceptably with other schemes such as
the mark/sweep we'll probably be using for cyclic data. And it's simple!
There's not much to tune so you don't spend much time "tuning the GC".
There's really only one knob: how many rc operations the compiler can
elide by static analysis. Makes it comparatively easy to reason about.
Anyway, if this all falls apart in practice of course we'll revisit. I'm
amenable to data much more than hypotheticals, even my own :) We have
complete type information and are going to be building a cycle-scanning
GC anyways. It's just a matter of trying to do better than it, when we
think we can. If we never can, I'll give up.
-Graydon
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
