News for hackers. Stuff that matters.
Re:Modernizing the DOM Tree in Microsoft Edge by amelius on Wednesday April 19, 2017 @02:54PM (#14150642)
Isn't this something one could abstract away?
Re:Modernizing the DOM Tree in Microsoft Edge by c-smile on Wednesday April 19, 2017 @03:01PM (#14150701)
It is about this part in the article:

> The new tree structure is simple and straightforward; it uses four pointers instead of the usual five to maintain connectivity: parent, first-child, next, and previous sibling

That straightforward four pointers structure is not the best for HTML DOM. Neither memory wise nor for typical algorithms applied to it.

Re:Modernizing the DOM Tree in Microsoft Edge by smitherfield on Wednesday April 19, 2017 @04:31PM (#14151470)
With all due respect (it looks like some seriously impressive work you've done), how do you know they're using "typical algorithms?" Maybe they've devised something new or uncommon, or significant new optimizations of the "typical algorithms." In general I'd give a company like Microsoft the benefit of the doubt that they know what they're doing, and have considered and rejected alternative approaches — at least when it comes to objectively-measurable technical goals like "create a fast data structure to represent a DOM tree," if not always subjective big-picture goals like "make a good web browser" (even in that case, IE was, for its time, a good web browser — the best — until Ballmer let it languish).

Your data structure looks to me like it's roughly optimal for the case where the DOM tree is generated once and then is never or rarely modified, and nodes have several children relatively frequently and no children relatively rarely. But in the age of single-page-apps and other Javascript-heavy jQuery/Angular/React-type sites filled with DOM manipulation and AJAX, it's more important (especially in the exponentially-increasingly-common pathological case) to make it inexpensive to insert, delete and move nodes within the DOM tree.

With your data structure, every time you create a new `Node`, even one without any children, you have to allocate a new `vector`, which is a lot more expensive than just three pointers. Every time you insert or move a Node to an arbitrary location means an extremely expensive random-access insert into a vector (especially if it triggers a realloc), and every insertion, move or deletion in an arbitrary location requires updating the `node_index` of every sibling (old and new, in the case of a move), which also defeats the advantage of vectors over linked lists (avoiding indirection).

Re:Modernizing the DOM Tree in Microsoft Edge by c-smile on Wednesday April 19, 2017 @06:46PM (#14152469)
"Your data structure looks to me like it's roughly optimal for the case where the DOM tree is generated once and then is never or rarely modified"

Check gmail for example. It has just one list - element that has 100 children. Other elements have from 0 to 10 children.

And that 100 list is normally populated as a whole.

"even one without any children, you have to allocate a new `vector`"

You don't need to allocate anything if vector is empty ...

Vectors's data buffer gets allocated only when you put something in the vector. At least in my case. So empty vector is just one pointer - nothing to write home about it.

"every insertion, move or deletion in an arbitrary location requires updating the `node_index` of every sibling"

On any DOM insertion you need to scan all siblings almost always anyway. For quite many reasons, e.g. to reset styles that could use `this ~ that` or something like `:nth-child(odd)`

Re:Modernizing the DOM Tree in Microsoft Edge by hsivonen on Wednesday April 19, 2017 @03:26PM (#14150910)
What’s better in your opinion?
Re:Modernizing the DOM Tree in Microsoft Edge by Someone on Wednesday April 19, 2017 @04:01PM (#14151233)
I would guess what (s)he writes in https://news.ycombinator.com/item?id=14150628, except that, maybe,

    vector<node*> children;
is a typo, and should be

    vector<node>* children;
Reason: I don't see how the former enforces "e) yet the structure ensures that there are no loops in the tree."

The latter would mean more copying of nodes, but would have excellent cache locality, so I can see it could well be faster, too.

Re:Modernizing the DOM Tree in Microsoft Edge by c-smile on Wednesday April 19, 2017 @04:42PM (#14151569)
It is precisely

   vector<node*> children;
yet this

    vector<node>* children;
makes little sense in DOM case.
Re:Modernizing the DOM Tree in Microsoft Edge by hsivonen on Thursday April 20, 2017 @01:50AM (#14154272)
Gecko had that but migrated to neighbor pointers, so that's a data point of one real engine moving from a child array to neighbor pointers.
Re:Modernizing the DOM Tree in Microsoft Edge by smitherfield on Wednesday April 19, 2017 @04:47PM (#14151621)
That does seem like it makes more sense; you could then implement `node_index` as a fast, stateless inline method like so:

  constexpr vector<Node>::difference_type node_index() const noexcept
  {

          return parent ? this - parent->children->begin()
                        : -1; // is a root node
  }
Re:Modernizing the DOM Tree in Microsoft Edge by c-smile on Wednesday April 19, 2017 @05:20PM (#14151895)
This does not work, element/node shall have stable address so to be O(1) addressable.

Elements/nodes can participate in multiple lists at the same time. Rendering lists (a.k.a. rendering tree) and things like Document.querySelectorAll() that returns NodeList.

Re:Modernizing the DOM Tree in Microsoft Edge by Someone on Thursday April 20, 2017 @03:17AM (#14154598)
Can I conclude that your earlier statement "yet the structure ensures that there are no loops in the tree." isn't correct? I could easily create a loop like this:

   this.children[0] = this;
Re:Modernizing the DOM Tree in Microsoft Edge by c-smile on Thursday April 20, 2017 @07:10PM (#14161721)
That case is easily manageable: you cannot insert/appendNode that has non-null parent. So you need to remove that node from its former parent first.

Problem is that their solution by design contains loops.

So on each tree traversal iteration you will need to access parent:

    Node* get_next_node(Node* that) {
      that = that->next;
      return that == that->parent->first_child ? nullptr :  that;
    }
Re:Modernizing the DOM Tree in Microsoft Edge by wtetzner on Thursday April 20, 2017 @04:09PM (#14160367)
How could that happen, given that children isn't a pointer?

    vector<node*> children;
Re:Modernizing the DOM Tree in Microsoft Edge by Someone on Friday April 21, 2017 @01:03PM (#14167306)
It is C++, and std::vector has an operator[] that makes a vector behave like a convention C 'pointer to data' for array accesses (in fact, the compiler likely will optimize the access to exactly what you would get if the declaration were of a C array of pointers to node)