copy-on-write in Ruby

[oleg dashevskii]

Hello,

I've got a big object that holds references to other objects which,
in turn, hold references to other objects, which.....

Now I change this object, but need a possibility to revert the change. This could be
achieved by deep-copying the object, but that's too expensive (changes
are mostly minor and 99% copy operations will be redundant).

Is there any simple solution to this, employing the copy-on-write
principle?

 

[Idan Sofer]

I've got a big object that holds references to other objects which,

in turn, hold references to other objects, which.....

Now I change this object, but need a possibility to revert the change. This
could be achieved by deep-copying the object, but that's too expensive
(changes are mostly minor and 99% copy operations will be redundant).

From your description it's not really clear what the class is doing(does it
has methods to perform operations, or it provide access to the other objects
via attributes?).

In anycase, what you can possibly do is to define some sort of "transaction"
flag, so when raised, the object's method will create copies of the relevant
objects on-demand(and keep references to the old ones).

Then either you commit the transaction, or rollback to the previous state.

 

[Dan Doel]

I don't know what your object looks like exactly, but you might want to
look a little at Purely Functional
Data Structures by Chris Okasaki (should be available online if you do
search google).

For example, when you make a binary search tree structure in a
functional manner, to insert, you have to
duplicate the path to the newly inserted node. This doesn't require
cloning the whole tree, though, so you
only need to clone log n objects.

Seems like this strategy would work for your object (and I believe there
are other examples in the book of
similar operations). You probably need a similar algorithm.

- Dan

P.S.: a little Ruby to get the ideas flowing (written in a more
functional style out of ease)

class Node
attr_reader :v, :l, :r
def initialize(v, l, r)
@value = v
@l = l
@r = r
end
end

def insert(value, tree)
if tree.nil?
new Node value, nil, nil
elsif value < tree.v
Node.new(tree.v, insert value tree.l, tree.r)
else
Node.new(tree.v, tree.l, insert value tree.r)
end
end