Three minutes in _computeCallNodeTableHierarchy during loading of a profile with lots of sibling nodes

[mstange]

Loading https://share.firefox.dev/4czHTvb spends an extremely long time building the call node table.

---

When we add a new sibling to the call node table, we try to find an existing sibling node by walking a linked list of siblings. In this profile there's barely any reuse of siblings, so we create a new sibling after every one of these searches. This is O(n^2) in the number of siblings.

Not sure what to do about this - we can't have a hashmap per parent node.

The actual reason for the high number of siblings is that the V8 jitdump info seems to have been incomplete, which resulted in a lot of unsymbolicated JIT addresses.

┆Issue is synchronized with this Jira Task

[mstange]

Oh, we could make it so that _computeCallNodeTableHierarchy keeps siblings ordered by func. So whenever it adds a new node, it would adjust nextSibling and currentLastChild so that following nextSibling gives you the nodes in increasing func order.

This would allow the following:

• If you're looking for a node that's already present, probably no difference - you just have to look at all siblings until you found the one for your func. If your func is lower, you'll have fewer hops before you find the existing node, if it's higher you'll have more.
• If you're looking for a node that's not already present, you know when you can stop looking: As soon as you come across a sibling with a higher func. So for lower funcs you'll save some hops.
• If you're looking for a node that's not already present, and it's higher than all the existing sibling node funcs, you can tell so immediately by looking at the currentLastChild's func - if it's higher you just append immediately.

And if that's still not enough, the ordering probably lets us do some skip-list tricks.

[mstange]

That by itself didn't do the trick, because there's an early-inserted sibling with a high func already present. But turning currentLastChild into lastUsedChild to skip most of the walk did work!