News for hackers. Stuff that matters.
Re:Modernizing the DOM Tree in Microsoft Edge by userbinator on Wednesday April 19, 2017 @09:02PM (#14153169)
more compact and faster

This is more of a general comment and may not necessarily be true in your implementation, but I see this argument brought up a lot: "vectors are arrays, therefore smaller (because only one pointer is needed per element) and faster than linked lists". However, one must remember that vectors are not statically sized arrays --- they dynamically size to hold their contents, and for the resizing to be (amortised) constant-time, there will on average always be some amount of unused space in the dynamic array, and you still need the (one) pointer to this dynamic array in the node itself, plus additional overhead to keep track of size/used. That's the "smaller" argument debunked. As for faster, that's not always true either, since simple forward/backward scans will require two indirections, one to get the dynamic array's address and another to get the pointer to the node itself. That's two memory accesses to areas which might not be close together at all. Compare this to one indirection (follow the next pointer) for a linked list, that is also made to an address in the vicinity of the rest of the node.

In summary: the linked-list will be faster for forward/backward scans and inserts/deletes and slower at indexing, while the vector will be faster for indexing and slower for forward/backward scans. The linked list will be smaller too.

Re:Modernizing the DOM Tree in Microsoft Edge by yorwba on Thursday April 20, 2017 @12:42AM (#14154026)
If no insertions or deletions happen between accesses, a vector scan can also be done with only a single indirection, by simply incrementing the pointer to the node. This also means better locality than a linked list, where the next pointer may be close to the current node, while the next node can be anywhere. In a vector, they are simply next to each other.
Re:Modernizing the DOM Tree in Microsoft Edge by jdmichal on Thursday April 20, 2017 @11:15AM (#14157404)
That's true when you have a `vector<node>`, but the structure was described as a `vector<node*>`. So what's adjacent to your current position is the pointer to the next node, not the node itself.

Which one is optimal depends a lot on the size of a `node`, as moving elements around in the DOM will require memory copies in the first case.

Re:Modernizing the DOM Tree in Microsoft Edge by c-smile on Wednesday April 19, 2017 @10:58PM (#14153572)
struct Node does not need first_child pointer when it is TextNode/CommentNodes/etc. as they are just terminals.

Yet text node here

   <div>text</text>    
does not need next/previous pointers as it is lone child.

In case of DOM tree children-vector case takes always less than "children-dl-list" case. With only one exception - element with single child node when size of memory needed is the same as in "children-dl-list".

Re:Modernizing the DOM Tree in Microsoft Edge by emmab on Wednesday April 19, 2017 @11:52PM (#14153800)
> As for faster, that's not always true either, since simple forward/backward scans will require two indirections, one to get the dynamic array's address and another to get the pointer to the node itself.

Can this be stored in a register when you're accessing multiple locations in the array in sequence?