[webkit-dev] DOM tree traversal on detached nodes

[Kentaro Hara]

Thanks ggaren!

I filed a bug here: https://bugs.webkit.org/show_bug.cgi?id=88834


> I believe you could achieve (a) (i.e., preserve all reachable nodes without help from the JavaScript garbage collector) with these semantics in the C++ DOM:
>
> ===== Design =====
>
> ref():
>
> ++this->refCount
> ++root()->refCount
>
> deref():
>
> --this->refCount
> --root()->refCount

Actually I've tried the approach yesterday but confirmed 25.9%
performance regression, even if I have TreeShared hold a pointer to
the root. Please look at the WIP patch and the performance test in
https://bugs.webkit.org/show_bug.cgi?id=88834.

What I've learned is that we must not insert any line to ref() and
deref(), which are performance sensitive:)

I am now trying another approach that hacks Node destruction. Let's
discuss the implementation details in the bug.

Thanks!


On Tue, Jun 12, 2012 at 12:18 PM, Geoffrey Garen <ggaren at apple.com> wrote:
>
> IMHO, (a) would be the best semantics.
>
>
> I agree, and I think that the specification actually does require this.
>
> The real issue here is how to fix this bug efficiently. I believe that Geoff Garen has been contemplating this and also has a proposal for how to do it.
>
>
> I believe you could achieve (a) (i.e., preserve all reachable nodes without help from the JavaScript garbage collector) with these semantics in the C++ DOM:
>
> ===== Design =====
>
> ref():
>
> ++this->refCount
> ++root()->refCount
>
> deref():
>
> --this->refCount
> --root()->refCount
>
> if !root()->refCount:
> assert(!this->refCount)
> for each descendent of root():
> delete descendent
> delete root()
>
> Remove 'this' from tree:
>
> assert(this->refCount) // clients must put a node into a RefPtr to remove it from a tree
>
> root()->refCount -= this->refCount
>
> for each descendent of this:
> this->refCount += descendent->refCount
>
> Insert 'this' into tree:
>
> root()->refCount += this->refCount
>
> for each descendent of this:
> this->refCount -= descendent->refCount
>
> What is "root()"?:
>
> If this is in a document:
> root() == document()
>
> else:
> root() == the highest link in the parentNode chain
>
>
> ===== FAQ =====
>
> Cycles?
>
> No cycles are possible because the DOM API does not allow cycles in a DOM tree.
>
> Is O(n) subtree insertion and removal OK?
>
> I believe these operations are already O(n).
>
> Is average case O(log n) access to disconnected root() OK?
>
> If n is small and/or ref/deref of disconnected subnodes are rare, then yes.
>
> Otherwise, we can optimize this case by putting a direct pointer to root() in rare data.
>
> Geoff
>



--
Kentaro Hara, Tokyo, Japan (http://haraken.info)