News for hackers. Stuff that matters.
Re:Modernizing the DOM Tree in Microsoft Edge by taeric on Wednesday April 19, 2017 @03:24PM (#14150901)
At a gut shot, only concern for this would be highly dynamic trees that are not either appending or prepending elements to children. I'd be curious to see benchmarks checking that.

With this, I'm always bemused that there are not more discussions on algorithms for doing tree traversal that don't use a queue or a stack. I think you have everything you need here to accomplish that.

Re:Modernizing the DOM Tree in Microsoft Edge by jdmichal on Wednesday April 19, 2017 @04:34PM (#14151506)
Even prepending... One would have to touch every sibling to update the index. So prepends are now a linear operation on the count of siblings. Prepend a few hundred items to a node, and I'm sure one would see the pain in profiling.

Now, whether that's a realistic use case is another question. But at the same time, you know someone on the Internet is doing it that way...

Re:Modernizing the DOM Tree in Microsoft Edge by taeric on Wednesday April 19, 2017 @04:41PM (#14151565)
I was assuming you'd use a standard deque that could hide the complexity of prepending. I didn't consider that the ordinal actually matters from the parent, though. So great point! :)

And yes, this was essentially my question. What are the realistic numbers in either scenario.

Re:Modernizing the DOM Tree in Microsoft Edge by jdmichal on Wednesday April 19, 2017 @04:58PM (#14151709)
Right. If you don't cache the ordinal, than "next sibling" and "previous sibling" operations have to scan the array.

But it's a relatively easy performance enhancement to have a validity flag for the ordinals, and only rewrite them when a read requires them. That way, write-heavy workloads won't be punished.

Re:Modernizing the DOM Tree in Microsoft Edge by c-smile on Wednesday April 19, 2017 @03:58PM (#14151200)
It was discussed quite a loot actually.

ArrayList (sciter's children list) vs LinkedList (Edge children list) : http://stackoverflow.com/questions/322715/when-to-use-linked...

Re:Modernizing the DOM Tree in Microsoft Edge by taeric on Wednesday April 19, 2017 @04:20PM (#14151393)
I meant specifically in modeling the Dom. Apologies if that wasn't clear.

The specific questions would be how often are the trees of a site dynamic and how often they insert instead of prepend or append.

Edit: And, of course, I'm still interested in why more people don't use stackfree algorithms for DFS.

Re:Modernizing the DOM Tree in Microsoft Edge by c-smile on Wednesday April 19, 2017 @04:52PM (#14151654)
Well, almost all HTML/CSS layout algorithms are O(N) complex so number of immediate children of an element is naturally limited by, say, 500-1000 sub-nodes. Otherwise the whole thing will not move. Note that GMail uses pagination with 500-800 elements on the page.

So we are speaking about vectors of pointers that contain 1000 elements. memmove() performance (used for quite rare operation of insertion of elements in the middle) on modern CPU is comparable with the need to access left/right elements in DL-lists for insertion. Consider cache misses, etc.

Re:Modernizing the DOM Tree in Microsoft Edge by taeric on Wednesday April 19, 2017 @06:59PM (#14152541)
This all makes sense, but I have become ridiculously empirical in my old age. Actual data wins many arguments in ways that surprise reasoning.