On 13-06-06 09:03 PM, Bill Myers wrote:
> Reference counting is generally more desirable than garbage collection,
> since it is simple and deterministic, and avoids scanning the whole heap
> of the program, which causes pauses, destroys caches, prevents effective
> swapping and requires to tolerate increasing memory usage by a
> multiplicative factor to allow GC to be amortized to be linear in the
> number of dead objects in the general case.
These are all the exact same arguments I have put forth for RC in the
past. They are why rust has RC presently, and will continue to have
_some_ RC (probably in the form of the libraries alone). Don't get me
wrong, I'm not an RC-hater. But I'm presently working on a tracing GC,
and will probably keep doing so.
Some other things about RC that are less-desirable, that we knew and/or
discovered:
- It leaks cycles. If you want it to not leak cycles, you need a
cycle collector which has the same properties as above, or a scheme
like you're proposing. I have proposed them in the past. Every
single reviewer I showed a "no cycles" variant of rust to told me
it was unacceptable and they would walk away from a language that
prohibited cycles in all cases. All of them. We tried limiting it
within subsets of the type system rather than pervasively: it still
irritated and confused everyone.
- It doesn't do anything about fragmentation. Our longer-term plan for
the gc involves moving to mostly-copying[1], which compacts pages
other than the conservatively-scanned set. And is incremental.
- It actually costs a lot.
- Code size goes up by a good 30% over tracing GC. Lots of writes
and branches. Lots more icache misses. Many ways of reducing this
are hard to implement, have to happen at the LLVM level, are
patented, or all 3.
- You can't tell your codegen that pointees are constant anymore,
since you're going to be writing to them.
- Allocations wind up larger. At least one word extra per. More
if you need to track all the allocations anyways, which you will
want to if you want to be able to free them all on unwind
(rather than rc-- on unwind, which costs much more) and/or if
you want a cycle collector. Current rc boxes cost 4 words extra.
Gc metadata can be stored much more compactly, 1-2 bits per alloc.
- If you want to support weak pointers, you just added another
dynamic failure mode when the pointee is missing, and slowed
all pointer traversals through that edge.
> However, it cannot support cycles (without destroying its advantages
> over GC), so it is a good idea to statically prevent them to avoid leaks.
We tried this; various strategies for it. Ownership cycles even just
within subtrees of well-organized ownership trees are not a rare
occurrence. They are a result both of normal patterns within common data
structures, and normal levels of coupling between subsystems in large
applictions. Especially web browsers.
I appreciate your input and thinking on the matter, but I feel pretty
confident saying we're not going to revisit this part, not going to try
again to modify the type system to prohibit cycles in @-graphs at the
fine-grain level you're describing. If anything, we might retire the
@-sigil[2] in favour of standard library provision of explicit Gc::<T>
and Rc::<T> types, with the current / known limitations.
-Graydon
[1]
http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.37.4037
but with software / non-mprotect write barriers
[2] As Patrick proposed in
http://pcwalton.github.io/blog/2013/06/02/removing-garbage-collection-from-the-rust-language/
recently.
Personally I like the sigil for its terseness; it's not clear to me
anyone else does, and there are certainlyl advantages to be had in
separating construction and allocation. But I think that's orthogonal. I
think keeping `~Foo()` and `@Foo()` as contractions of `Uniq<Foo>` and
`Gc<Foo>` types, and especially keeping `@Foo::new()` as a contraction
of `alloc Gc Foo::new()` is a good thing. We keep `a + b` around as a
contraction of `a.add(&b)` as well.
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
