perf(genadds) traverse children in reverse order

[mdellanoce]

I noticed when you add a deep/complex tree as part of a mutation, a large portion of the tree ends up being added to the addList. This is because genAdds traverses the children of each node in order, but serialization in pushAdd wants each node to have a serialized parent and nextSibling. Reversing the order of traversal in genAdds makes it more likely to avoid adding nodes to the addList.

I ran the benchmarks before/after and this was a pretty small improvement across the board.

[changeset-bot[bot]]

🦋 Changeset detected

Latest commit: ecabd349058475efa05ffa28a327a87174f4d76a

The changes in this PR will be included in the next version bump.

This PR includes changesets to release 8 packages

Name	Type
rrweb	Patch
rrweb-snapshot	Patch
rrdom	Patch
rrdom-nodejs	Patch
rrweb-player	Patch
@rrweb/types	Patch
@rrweb/web-extension	Patch
rrvideo	Patch

Not sure what this means? Click here to learn what changesets are.

Click here if you're a maintainer who wants to add another changeset to this PR

[mdellanoce]

this might have an impact on performance when things do make it to the addList though, since the node order is reversed, and addList is traversed from the tail node to the head. I haven't found a case where that happens yet...

Update: i think this^ shouldn't be a problem b/c the addList already accounts for next/previous sibling relationships

[eoghanmurray]

You ran the ./packages/rrweb/test/benchmark/dom-mutation.test.ts benchmark? Is there any addition you could make to those benchmarks that would demonstrate worse case for what you experienced?

The only possible objection I can think of is whether this could makes things worse for different types of data sets, but really your write-up makes a great case that the existing approach is worst-case.

[colingm]

For now thinking we will abandon this PR, it seems to most likely be addressed anyways by #1277 and so we can always revisit it after that one goes through