Consider storing each DOM node's list of children as a vec in the node

[nox]

When I implemented NodeList years ago, I wrote a complicated caching system so that iterating from start to finish on the list of children wouldn't start again from the node's first child.

On the other side of the pond, in Firefox, we just store a vec of nodes and access that in O(1). Furthermore, that vec is used in unrelated places too, even in layout.

If we did this in Servo, this could simplify parallel box construction a lot, and given Firefox does it, I'm not sure it's a huge performance hit.

Cc @jdm @SimonSapin

[nox]

(Note that I suggest we do that in addition of the first_child, last_child pointers etc, not as a replacement.)

[pcwalton]

I think if it's good enough for Firefox, it's good enough for us.

[Manishearth]

In that case will we still need the first_child last_child, children_count fields?

At a first glance it does seem to me that we can just switch over. It's not clear to me why we need NodeList to have both a Vec and a magical node-based form.

[nox]

Which fields are you talking about? Node's?

NodeListType::Simple is for static collections of nodes that aren't specific to anything, NodeListType::Children is for live collections of children, I was not your colleague yet and I decided to go fancy.

[SimonSapin]

nextSibling etc are exposed to the DOM. If we only had children: Vec<Node> they would take O(n) time by linear-searching in the parent’s children.

[Manishearth]

@nox yeah i guess i mean that we're using NodeList to store children but we use NodeList::Children instead of just a vec. We should just use a vec directly, and have NodeList::Children read from that vec.

nextSibling etc are exposed to the DOM. If we only had children: Vec<Node> they would take O(n) time by linear-searching in the parent’s children.

Wasn't talking about nextSibling :) Some of these are O(1)

[nox]

@nox yeah i guess i mean that we're using NodeList to store children but we use NodeList::Children instead of just a vec. We should just use a vec directly, and have NodeList::Children read from that vec.

Yeah, 2015 nox didn't want to allocate a vec when he could write some cute code instead. I optimised for the case where you just traverse .childNodes with a for loop, and not have to patch up the vec every time the children change.

[Manishearth]

We could still use that iterator for ChildNodes, actually, if it's a live iterator.

[nox]

If we always maintained that vector of children for each node, style::parallel::traverse_nodes could just use rayon's par_iter method.