Hi Andy! On Tue, Aug 18, 2009 at 8:43 PM, Andy Fingerhut < andy_finger...@alum.wustl.edu> wrote:
> > On Aug 17, 3:51 am, Christophe Grand <christo...@cgrand.net> wrote: > > Why do you focus on these AtomicReferences? If you contrast pre-transient > > vectors and actual vectors you'll see that the overhead due to instance > of > > PersistentVector$Node is far more important. > > I only focus my questions on AtomicReferences because I noticed them. > I haven't yet taken the time to read through all the source code > related to the implementation of transient data structures. > > It just seems to me that a persistent data structure doesn't _need_ a > reference to the thread that created it. It is now immutable, and it > and all of its "sub-parts" always will be, until and unless they are > deallocated by garbage collection. > It doesn't hold a reference to the thread that created it: the (atomic) reference to the thread has been nulled (but not the references to this reference). But if there is only a single non-null edit reference in the "root > node", then the non-root nodes don't really need a reference to the > thread that is currently mutating the data structure, right? Right, they only need a token (eg a good old (Object.)) to uniquely identify their "transienction". The AtomicReference plays a double role: its identity is the token but its value is useful only for the root transient. That's why its value is nulled when persistent! is called but not references to the AtomicReference itself. > And after a call to peristent!, a different thread could later call > transient on it, and want to make its own modified version. So any > non-null edit references anywhere in the persistent data structure are > useless, aren't they? 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 -- Professional: http://cgrand.net/ (fr) On Clojure: http://clj-me.blogspot.com/ (en) --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
