Hacker News Reader

Comment by amelius | Hacker News Reader

Reference counting can be a useful memory management technique. But reference counting may cause unpredictable pauses when large amounts of objects suddenly need to be freed (e.g. when dropping the last reference to a large array holding many references).

At least a carefully written garbage collector can free objects incrementally, and concurrently.

So memory management in Rust is certainly not a solved problem.

EDIT: Removed mention of RefCell.

View on HN

> So memory management in Rust is certainly not a solved problem.

This looks like nay-saying just for the sake of it, but in case you're actually just confused:

Rust isn't reference counted unless you yourself add reference counting. Rust tracks ownership in the compiler so it knows statically, at compile time, when an object needs to be freed, and the compiler emits the code to do the freeing in that spot. Rc is a utility function: you can choose to opt into reference counting on a per object basis. But if you're not actually typing Rc yourself then it's not happening. Rust is no more reference counted than the ability to build the same thing in C makes C a reference counted language.

> But reference counting may cause unpredictable pauses when large amounts of objects suddenly need to be freed (e.g. when dropping the last reference to a large array holding many references).

Then again so does manual memory management if you're freeing a large object graph at once.

> At least a carefully written garbage collector can free objects incrementally, and concurrently.

You could get that with refcounting, stashing Rc0 objects in a list of items to free incrementally rather than freeing it all at once and synchronously.

Since refcounting only happens expicitly it should be pretty clear where possible drops happen that lead to large pauses.

It wouldn't be too hard to replace that Rc with an Rc that performs deferred drops by putting them in a queue and performing a number of drops at an oppurtune time (eg. using an idle-hook in a event loop).

It might even be possible to send all drops to a thread dedicated to dropping, but that would probably only work if the contents are Sync or Send. This form of async drops should always be possible for Arc.

But big pauses should rarely occur since refcounting is something that has to be added explicitly, Rust is a language where compound types are used extensively instead of building dynamic structures using collections for trivial things and the use of Drop trait is not something that can be fully relief upon (making that most solutions try to go without using it). This should make most drops pretty lightweight, even when dropping large numbers of items.

> But reference counting may cause unpredictable pauses when large amounts of objects suddenly need to be freed (e.g. when dropping the last reference to a large array holding many references).

That's still a predictable pause: it's the number of references contained within the array. If you know your array will hold at most ten references, it will take at most the time to free the ten references. Also, you know this will happen when the last reference is dropped - no earlier, no later. If your program can't handle the pause at that moment, you hold the reference until it can. If you know another component (perhaps in your own call stack) holds a reference, you know it won't be freed. And so on.

> If you know your array will hold at most ten references, it will take at most the time to free the ten references.

True. But if those references themselves contain references, it may become tricky to manage all of this. You basically don't want to think about it.

But, like others mentioned, you can put the objects in a queue, and free them in the background. It would be interesting to know how such a solution stacks up, performancewise, against an incremental, concurrent garbage collector.

Note that you don't need a GC to do that; the allocator can do it for you.

A lot of folks think that optimizations like having allocation arenas and spreading out deallocation pauses are unique to garbage collectors, but they're completely orthogonal to GC. You can have GCs with these optimizations, and GCs without. You can have regular allocators with these optimizations, and regular allocators without. Jemalloc does have arenas and stuff for allocation (I'm unsure if it spreads out deallocation loads). Of course, with a GC you can also defer the cost of iterating through large vectors and calling destructors.

But anyway, this only becomes a problem when you have large complicated Rc-trees in your application, which tends to not be the case in Rust.

An exception (large complicated Rc-trees) is the rope in xi-editor. If you load a very large file, the operation of letting go of the last reference is potentially a large enough pause to have an effect on UI responsiveness. I've considered adding a mechanism that moves the object into a deallocation thread (or a deallocation task running in a thread pool) for this reason, although I'm not sure how important it is in the grand scheme of things.

In a GC'ed language such as Go, this would not be a problem. The flip-side is that I can safely and efficiently do updates in place, because Rust's reference counted type has a way to determine when you're holding the only reference.

> I've considered adding a mechanism that moves the object into a deallocation thread (or a deallocation task running in a thread pool) for this reason, although I'm not sure how important it is in the grand scheme of things.

The one time I've done this in C++, delayed deallocation actually made major loads/unloads worse for us on mass batch operations - more cache thrashing perhaps? Since this involved GPU resources, perhaps some bad interaction with the driver? I did keep around the "optimization" conditionally for smaller operations as this let us get rid of some hitching.

> In a GC'ed language such as Go, this would not be a problem.

In C# this traditionally manifested as lengthy GC pauses you had to jump through hoops to workaround. Modern GCs are much better these days, but it's not 100% solved.

Hmm, yeah cache thrashing sounds a likely culprit - agreed. Perhaps before dropping all the references they should be sorted by memory address, so that page faults are minimised.

I'm hoping for something like this a few years down the line:

http://manishearth.github.io/blog/2016/08/18/gc-support-in-r...

Allowing Rust to generically adapt to an arbitrary Gc that it is nested inside of would be awesome.

Yes, that would be amazing.

To be clear, RefCell does not do reference counting, Rc does. RefCell does runtime borrow checking.

>Reference counting can be a useful memory management technique. But reference counting may cause unpredictable pauses when large amounts of objects suddenly need to be freed (e.g. when dropping the last reference to a large array holding many references).

How is it compared to other forms of GC?

More performant, generally, particularly considering the fine-grained control it offers. However, cyclic datastructures may be problematic (similar to how they are in typical GC, but often worse). Of course, exceptions abound; the "better" choice is extremely use-case dependent.

It's generally predictable pauses, fwiw.

Well, a different kind of unpredictability from other GCs.

And Rc is rare enough (IME) that this doesn't usually matter.

Reply on news.ycombinator.com