On Aug 19, 2:38 am, Christophe Grand <christo...@cgrand.net> wrote:
> Imagine a persistent data structure S1 with a root node A and two child
> nodes B and C.
> On this data structure you call transient, make some updates and call
> persistent! which yields an updated persistent data structure S2 with the
> root node A' and child nodes B and C' (B isn't updated and is thus shared
> with S1). A' and C' are "transiently created" nodes, B is a "regular" node.
> Now you call transient again on S2. How can one know that A' and C' must be
> cloned before modifying them in place? If one can't tell and modify B' the
> modification is propagated to S2: S2 is no longer persistent :-(
> That's why each node must carry an identifier: to be able to know if a node
> can be updated in place or must be cloned. Actually, once persistent!
> called, this identifier is a nulled AtomicReference. (Granted a simple
> Object would save us a handful of bytes.)
>
> The alternative impls I can think of (a set of owned nodes or performing a
> cleanup on persistent!) would trade the memory overhead for a runtime one.
>
> Christophe
OK, I think that explanation broke through the fog in my brain. I had
been mistakenly thinking that there ought to be a straightforward way
to keep some kind of reference to the mutating thread of a transient
at the root only, forgetting that while it is transient we need a way
to distinguish which nodes we are allowed to mutate in place, and
which we are not.
I also do not see a way that we can do that, and still have an O(1)
persistent! call.
It does seem we could have a persistent! call that is O(# of
temporarily mutable nodes created while the data structure was
transient), by walking the data structure from the root node and
stopping whenever we hit a persistent node that hasn't been mutated,
but in general that could be all of the nodes.
Thanks!
Andy
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
