Partially Destructive Garbage Collection | Hacker News Reader

Partially Destructive Garbage Collection

daeken.com

24 pointsdaeken18 comments

There are already frameworks that support lazy loading object data (e.g. Hibernate).

The other part of what you described is having the runtime do the actual unloading of the objects and replacing them with stubs to conserve memory. IMO this would be an extremely difficult problem to do well. A primitive version of this already exists at a lower level than the runtime in the form of paging/swapping.

This seems like an inverse of what you get when haskell's laziness is an advantage, namely that with haskell you defer computing stuff until its needed in a certain sense, whereas in this case, we're considering eager computations where whenever the code path for generating some data is purely functional in some sense, the runtime heuristically deletes the data and if it comes to be needed again, it gets once again computed.

This woudn't end well unless there was some way for the runtime/compiler to know the complexity of the computation.

On the other hand, this does remind me of work on what's called "self-adjusting computation" by several folks at uchicago and cmu, (http://ttic.uchicago.edu/~umut/research/) which winds up being a really slick way of converting certain offline algorithms into online algorithms that in some cases have runtime complexity comparable or the same as the best known explicit online algorithms

Thanks for your input -- I just started thinking about it earlier today, so I'm really looking for a lot of feedback.

As for the Haskell reference, I agree. I'm thinking about lazy evaluation in terms of the way objects are recreated.

As for knowing the complexity of the computation, I don't really think that's necessary. If the PDGC is part of the runtime, it can track the cost (in terms of time to create the object).

I'll give the linked research a read over, thanks, and if you can think of any other related research I'd love to see it.

PDGC would make a lot of sense as the GC system for Haskell.

The key change you need to make to the RTS is, when you evaluate a thunk, rather than overwriting it with the final value, instead append the evaluated value to the thunk. Then, the GC should be free at any time to erase the "evaluated" part of the thunk if doing so would allow it to free up a lot of memory.

When a thunk is entered it should return the evaluated value if present, otherwise it should use the code pointer and closure data to create the evaluated value again.

The key challenge is designing the algorithm that decides what is beneficial to lose references to. Probably you want to keep some stats around about frequency of access of thunks and so on.

I haven't seen anything like this proposed for Haskell, so I would be interested in reading a paper, should you implement it :-)

Thunks can be arbitrarily bigger than their evaluated value. (Say, the value is an Int.) So expanding and replacing thunks usually even saves memory and gets rid of live references.

The key change you need to make to the RTS is, when you evaluate a thunk, rather than overwriting it with the final value, instead append the evaluated value to the thunk.

This already happens in GHC.

Any thunk that is to get updated has one word reserved as a slot for the update result. This is necessary for proper operation in SMP systems, when two processors race to evaluate the same thunk. The only data that gets overwritten is the thunk's code pointer. There is one standard routine in the binary, known as the indirection code, which just returns the value in the update slot of the currently active thunk. The thunk's pointer is set to point to the well-known address of the indirection code. In all this, the thunk's payload remains untouched.

GHC's GC short circuits these indirection nodes, and ignores pointers in the thunk payload (since the thunk payload has become effectively unreachable). In order to accomplish your goal, we would have to recover the original value of the code pointer. This can be done by storing a copy of this value in the payload (similar to what you are suggesting). A way to do this without increasing the size of any heap object is for the compiler to generate a copy of the indirection code per thunk code block... such that the original thunk code address can be recovered from the particular indirection code address via a lookup (or potentially, via arithmetic). This bloats the emitted code by a small fraction, but may be worth it.

You could probably make a lot of headway on something like this using existing technologies. Serialization for example. If an object impelements serializable (in java), then the caching mechanism could hold it in memory, remember how long it has been since the last access and then serialize to disk when it hasn't been accessed in a long time.

In a way, as well, the OS handles a lot of this with virtual memory on a page by page basis. If you have a web app that caches a lot in application state, it'll grow in memory size and then start swapping out that app to disk when it gets stale.

It's a good idea. Programming tends toward laziness so lazy caching is probably almost definitely going to happen. Isn't this kind of what memcache is? Couldn't memcache automatically let go of some of its cached queries?

You essentially get something like this with Terracotta http://www.terracotta.org/

You can even stop a Terracotta backed JVM and start it back up to continue where you left off without any manual caching code or special weak reference APIs (which is the heart of the question I gather, no intervention).

this sounds just like weak references to me

Combined with finalizers, yes.

This is a rather interesting example of a space-time tradeoff. In this case you are trading time for more space.

You can get everything you want with weak references.

Weak references can be used for the base of this, but it doesn't handle the actual recreation of the objects, nor is it an automatic thing. My goal with this idea is to reduce the cost of implementing such schemes, and shifting them into the compiler/runtime.

True. But I think the smarter thing would be to build this using weak references than to hope someone puts this into their GC or to write your own. At least your first version should be done so.

Agreed. I actually plan on building it on top of .NET initially, as it's quite flexible in this respect. Thanks for your feedback.

A GC wouldn't be able to auto-recreate the object without either an indirection (and thus no better than using a weak reference in a kind of smart pointer), or rather costly logic.

Suppose an instantiated object is 512K in size. You've got a reference to it from 50 places. The GC decides to evict it but still has the construction logic which, say, takes up 128 bytes. All the 50 references now need to be updated, but what will they point to? Presumably some kind of proxy or stub which, when touched, inflates to the size of the original object.

The problem is that this thing can't inflate in-place, otherwise it wouldn't actually be saving any address space. So, the re-instantiation must occur somewhere else, and 50 locations need to be updated. Since a GC isn't currently in flight, finding those 50 locations is going to be very expensive. It's going to have a similar cost to the mark phase of a GC.

The best approach for the GC would be to use an indirection, to treat all references to evictable objects as smart pointers of some kind, with an extra indirection between the reference and the object which may or may not have to be re-instantiated. But this is easily implementable using weak references in runtimes like JVM or CLR.

I see this as being very difficult to implement well, but I think it's interesting enough to warrant further research. I really don't know if it'll end up working out, but I'm planning on prototyping it on top of .NET.

It may not be a good idea to shift such unpredictable costs to the compiler/runtime. Your program could potentially become much harder to profile.

Reply on news.ycombinator.com