1847616 - Pack AvlTree::Node more tightly

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement, P3)

Description

[Justin Link]

I noticed AvlTree insertions and traversals showing up fairly prominently in some profiles of Ion compilation. The disassembly looked pretty good and the code is mainly just jumping around through memory so I suspected that the performance here might get better if we packed things better.

Comment 1

[Nicolas B. Pierron [:nbp]]

The AvlTree is only used of the register allocator in IonCompilation. The register allocator is storing the ranges associated with the liveness of registers.

Julian would certainly know better what might be going on.

Comment 2

[Julian Seward [:jseward]]

The AvlTrees are used by Ion's register allocator to keep track of register
commitments. There has already been considerable effort expended to make the
allocator as a whole faster, including improving the behaviour of the trees;
see for example bug 1814204.

More broadly, in bug 1758274 there was a lot of work on the allocator done,
none of which (directly) landed. There may a couple of optimisations that we
can pull from that work, which could be landed in the existing allocator. I
could have a look, but the results would be minor.

We know that the allocator is not cache friendly -- it causes a lot of misses
when processing large functions. That could be improved by changing the core
data structure(s) from linked lists to vectors, but that would be a major
piece of work. We know at least approximately what would need to happen
though, and Chris Fallin's RA2 allocator for Cranelift shows this is feasible.

If you have JS-shell test cases that show allocation slowness, I would be
happy to look at them to see if there is anything that can be done.

Comment 3

[Justin Link]

Perhaps I should mention that I do have a patch that improves the packing of AvlTree nodes and that shows pretty significant improvements in many SP3 subtests. I'm just working on cleaning it up and getting it ready for review. (To get a good view of the impact of the change, go to the subtests for each platform and select "Hide uncertain results".)

Comment 4

[Justin Link]

Attachment: Bug 1847616: Made AvlTree::Node() smaller for better cache performance r=jseward,mgaudet

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/8afb0f64ad7a
Made AvlTree::Node() smaller for better cache performance r=jseward

Comment 6

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/8afb0f64ad7a