5 ms·

I wrote something similar, except using sequential IDs instead of being content addressed. With immutable objects, forward references aren't possible. This mad

I wrote something similar, except using sequential IDs instead of being content addressed. With immutable objects, forward references aren't possible. This made the GC algorithm concurrent for free. You'd take a lock on initiating a GC to record the roots, then release it. From that point onwards, you can take your time doing a mark and sweep on the database, only sweeping objects that have an id less than the highest of your root objects. It also made generational collection pretty easy. If you bound your marking and sweeping with an arbitrary lower limit in addition to the higher limit from the roots, it would collect correctly within that range and waste no energy exploring past it. I used this to aggressively clean up new objects without having to wait for a full GC. The project was storing Clojure style persistent hash maps on disk for real time log analysis, approximately 100gb or so. Unfortunately, none of these tricks would apply to a CAS system. I do wonder if it would help running the speculative collection twice before taking out the lock, though.

MaxBarraclough 6y ago
> With immutable objects, forward references aren't possible. This aligns well with a tree of backup objects (immutable append-only acyclic graph data structure) but this approach wouldn't work for general programming, right? My understanding is that LISP's letrec and the equivalent in other functional languages, means that even seemingly immutable abstractions aren't really immutable from the point of view of the GC, and cycles are a possibility. I don't think it would be possible to properly implement Haskell using ordinary reference-counting, for instance. The purity of the language wouldn't save you from reference-cycles. See also: https://stackoverflow.com/q/791437/ https://stackoverflow.com/q/791437/
- reitzensteinm 6y ago
  Right, that's true that it's possible to "tie the knot" with laziness and build circular or self references in functional languages. I didn't mean to make a claim that extended past the limits of the system I built and it's important to note that.
  - MaxBarraclough 6y ago
    > that's true that it's possible to "tie the knot" with laziness and build circular or self references in functional languages I wonder if it would be possible to construct a practical functional language that never does so. I imagine not. > I didn't mean to make a claim that extended past the limits of the system I built I don't think you did, I was just wondering how much further the idea could be taken.
WJW 6y ago
If you can be guaranteed to have no forward references, wouldn't this mean that you can also not have cycles and therefore could make do with a much simpler refcounting setup?
- reitzensteinm 6y ago
  You could definitely do it with refcounting, but I'm not sure it's simpler when not in memory. You need to be able to defer the cost of freeing objects, otherwise updating a root object will randomly be very expensive as you free 20gb of garbage before acknowledging the write. This deferred queue is going to need to live in the database, and be processed in atomic chunks that pop an item off the queue, update the refcounts, and add any further work items. Otherwise if the power goes out, your refcounts are left in who knows what state. That doesn't exactly sound hard, but the system I built was pretty simple too. And my preference leans towards not mutating object metadata after it's been written to.

MaxBarraclough 6y ago

> With immutable objects, forward references aren't possible. This aligns well with a tree of backup objects (immutable append-only acyclic graph data structure) but this approach wouldn't work for general programming, right? My understanding is that LISP's letrec and the equivalent in other functional languages, means that even seemingly immutable abstractions aren't really immutable from the point of view of the GC, and cycles are a possibility. I don't think it would be possible to properly implement Haskell using ordinary reference-counting, for instance. The purity of the language wouldn't save you from reference-cycles. See also: https://stackoverflow.com/q/791437/ https://stackoverflow.com/q/791437/

reitzensteinm 6y ago
Right, that's true that it's possible to "tie the knot" with laziness and build circular or self references in functional languages. I didn't mean to make a claim that extended past the limits of the system I built and it's important to note that.
- MaxBarraclough 6y ago
  > that's true that it's possible to "tie the knot" with laziness and build circular or self references in functional languages I wonder if it would be possible to construct a practical functional language that never does so. I imagine not. > I didn't mean to make a claim that extended past the limits of the system I built I don't think you did, I was just wondering how much further the idea could be taken.

WJW 6y ago

If you can be guaranteed to have no forward references, wouldn't this mean that you can also not have cycles and therefore could make do with a much simpler refcounting setup?

reitzensteinm 6y ago
You could definitely do it with refcounting, but I'm not sure it's simpler when not in memory. You need to be able to defer the cost of freeing objects, otherwise updating a root object will randomly be very expensive as you free 20gb of garbage before acknowledging the write. This deferred queue is going to need to live in the database, and be processed in atomic chunks that pop an item off the queue, update the refcounts, and add any further work items. Otherwise if the power goes out, your refcounts are left in who knows what state. That doesn't exactly sound hard, but the system I built was pretty simple too. And my preference leans towards not mutating object metadata after it's been written to.