Closed Bug 1341265 Opened 7 years ago Closed 3 years ago

Inline Map/Set operations

Categories

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

enhancement

Tracking

()

RESOLVED FIXED
93 Branch
Tracking Status
firefox93 --- fixed

People

(Reporter: evilpie, Assigned: anba)

References

(Blocks 3 open bugs)

Details

(Keywords: perf, perf-alert)

Attachments

(23 files)

15.58 KB, patch
Details | Diff | Splinter Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
Developers should be able to use Map/Set instead of normal JS objects, but still get predictable performance. We should inline the lookup and hash calculate for Map#get, Map#has and Set#has. Optimizing Map#set and Set#add wouldn't hurt.
Blocks: sm-js-perf
Priority: -- → P3
Keywords: perf
I was curious how much it would help to optimize those functions to a direct call. Even on six-speed's map-set-lookup this doesn't really seem to make a difference at all.

I guess we could use the AliasSet to hoist this, but that is just cheating, we aren't actually faster. 

We probably have to write custom inlining code for this. Best case even with compile time hashing for constants, even though this probably doesn't help much in the real world.

We should definitely look into optimizing Map and Set soon. Both the new facebook page and Google Docs use them quite a bit nowadays.

Bug 775896 has been fixed, so we can remove the fixme comment.

Assignee: nobody → andrebargull
Status: NEW → ASSIGNED

Move BigInt comparison to the MacroAssembler, so we can reuse it in a later
patch of this series.

Depends on D118967

Add mul32 with an immediate in preparation for a later patch of this series.

Depends on D118968

ARM64 and MIPS64 already support this mode. And ARM32 and MIPS32 can simply take
the same approach as x86.

The next part will add another branch64 method and that method supports
Condition::Equal. And instead of adjusting the comment for branch64 when
Equal is or is not supported, it was easier to just support it everywhere.

Depends on D118969

Add branch64 with (Address, Register64) operands in preparation for a
later patch of this series.

Depends on D118970

Use a simple VM-call in CacheIR for now. This approach won't be enough to
close the distance to the competition, because JSC/V8 can inline the complete
hash operation, but already inlining everything in CacheIR seems a bit extreme.

The next parts will inline the hash operation when called with specific types,
because there we can guarantee we won't generate a big blob of assembly in
CacheIR.

Depends on D118971

Inline Set.prototype.has in CacheIR when called with non-GC things.

We have to inline the following steps:

  1. Guard the input is a non-GC thing.
  2. Normalise the input, i.e. transform doubles to int32 when possible and
    canonicalise NaN values.
  3. Hash the input through mozilla::HashGeneric().
  4. Perform the hash lookup.

The hash lookup already uses templates and handles BigInts in preparation for
the next parts.

Depends on D118972

Inline Set.prototype.has in CacheIR when called with strings.

Normalising a string input is a bit annoying, because we have to atomise the
string, which means performing a VM-call. And in contrast to other VM-calls,
we have to continue the CacheIR operation after the call, which means we can't
implement this as a shared method in CacheIRCompiler, but instead need to
implement it in BaselineCacheIRCompiler. And furthermore we require that
atomising a string won't GC, because we spill the SetObject on the stack.

Depends on D118973

Inline Set.prototype.has in CacheIR when called with symbols.

Depends on D118974

Inline Set.prototype.has in CacheIR when called with BigInts.

Depends on D118975

Inline Set.prototype.has in CacheIR when called with objects.

Implementing MacroAssembler::hashObject() on 32-bit platforms is difficult,
because it uses 64-bit operations, so we either have to allocate twice as much
registers for Register64 or alternatively spill the values on the stack. For
now just punt and only support this optimisation on 64-bit platforms.

Depends on D118976

Similar to part 7, optimise the hash lookup for non-GC things.

Depends on D118977

Similar to part 8, optimise the hash lookup for strings.

Depends on D118978

Similar to part 9, optimise the hash lookup for symbols.

Depends on D118979

Similar to part 10, optimise the hash lookup for BigInts.

Depends on D118980

Similar to part 11, optimise the hash lookup for objects.

MHashObject can't be moved, because the hash value depends on the object's
address, which can change when the object is moved by the GC.

Depends on D118981

Inline the complete hash operation even for value types when the code is hot
enough to be Warp-compiled. (Except on 32-bit platforms, because we can't
compute the hash of objects inline, cf. the previous part.)

Depends on D118982

Similar to the optimisations for Set.prototype.has, also inline
Map.prototype.has in CacheIR.

Depends on D118983

And inline Map.prototype.has in Warp.

Depends on D118984

Similar to the optimisations for Map.prototype.has, also inline
Map.prototype.get in CacheIR.

Depends on D118985

And inline Map.prototype.get in Warp.

Depends on D118986

Type: defect → enhancement
Pushed by andre.bargull@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/33a140c71ff0
Part 1: Remove stale fixme comment. r=iain
https://hg.mozilla.org/integration/autoland/rev/e9272f7d1823
Part 2: Add MacroAssembler::equalBigInts(). r=iain
https://hg.mozilla.org/integration/autoland/rev/88e497d213fe
Part 3: Add MacroAssembler::mul32(Imm32, Register). r=iain
https://hg.mozilla.org/integration/autoland/rev/820e01c32bcd
Part 4: Remove unnecessary restriction for branch64 with Address operand. r=iain
https://hg.mozilla.org/integration/autoland/rev/b861bb6771c7
Part 5: Add branch64 for (Address, Register64). r=iain
https://hg.mozilla.org/integration/autoland/rev/09f04c26176c
Part 6: Optimise Set.prototype.has in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/56ec3626f0ba
Part 7: Optimise Set.prototype.has for non-GC things in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/3fa14377770a
Part 8: Optimise Set.prototype.has for strings in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/bd5e0950f9d9
Part 9: Optimise Set.prototype.has for symbols in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/21199bd4965d
Part 10: Optimise Set.prototype.has for BigInts in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/26787054e0db
Part 11: Optimise Set.prototype.has for objects in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/6716962a06ed
Part 12: Optimise Set.prototype.has for non-GC things in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/13da03ae88a8
Part 13: Optimise Set.prototype.has for strings in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/85f8b1c24e9d
Part 14: Optimise Set.prototype.has for symbols in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/720032f06c94
Part 15: Optimise Set.prototype.has for BigInts in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/5d9d8af2f4ac
Part 16: Optimise Set.prototype.has for objects in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/bf631916de9b
Part 17: Optimise Set.prototype.has for values in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/991572f50cf9
Part 18: Optimise Map.prototype.has in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/199d9708682d
Part 19: Optimise Map.prototype.has in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/c3094bf07295
Part 20: Optimise Map.prototype.get in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/ad0987b840c1
Part 21: Optimise Map.prototype.get in Warp. r=iain

== Change summary for alert #30774 (as of Wed, 04 Aug 2021 10:37:19 GMT) ==

Improvements:

Ratio Suite Test Platform Options Absolute values (old vs new)
5% ares6-sm linux64-shippable 45.95 -> 43.45
5% ares6-sm linux64-shippable 46.12 -> 43.89

For up to date results, see: https://treeherder.mozilla.org/perfherder/alerts?id=30774

== Change summary for alert #30770 (as of Wed, 04 Aug 2021 09:03:27 GMT) ==

Improvements:

Ratio Suite Test Platform Options Absolute values (old vs new)
5% ares6 macosx1014-64-shippable-qr webrender 57.14 -> 54.29
5% ares6 macosx1015-64-shippable-qr webrender 55.95 -> 53.21
5% ares6 windows10-64-shippable-qr webrender 52.98 -> 50.52
4% ares6 linux1804-64-shippable-qr webrender 60.40 -> 57.71

For up to date results, see: https://treeherder.mozilla.org/perfherder/alerts?id=30770

Regressions: 1724298

Backed out for causing Bug 1724298.

Flags: needinfo?(agi)

Thanks.

Flags: needinfo?(agi) → needinfo?(andrebargull)
Backout by abutkovits@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/a1d9ddb4fb79
Backed out 21 changesets for causing Bug 1724298. CLOSED TREE
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Target Milestone: 92 Branch → ---

Assert the inline hash computation is correct.

Flags: needinfo?(andrebargull)
Pushed by andre.bargull@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/602b65bfb721
Part 1: Remove stale fixme comment. r=iain
https://hg.mozilla.org/integration/autoland/rev/2b174465dea5
Part 2: Add MacroAssembler::equalBigInts(). r=iain
https://hg.mozilla.org/integration/autoland/rev/f1c40722a50e
Part 3: Add MacroAssembler::mul32(Imm32, Register). r=iain
https://hg.mozilla.org/integration/autoland/rev/df7c4fac5dc8
Part 4: Remove unnecessary restriction for branch64 with Address operand. r=iain
https://hg.mozilla.org/integration/autoland/rev/08768e69a817
Part 5: Add branch64 for (Address, Register64). r=iain
https://hg.mozilla.org/integration/autoland/rev/cab9608e9d98
Part 6: Optimise Set.prototype.has in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/3c94f61e57ca
Part 7: Optimise Set.prototype.has for non-GC things in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/77735582aefb
Part 8: Optimise Set.prototype.has for strings in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/46f05b533e75
Part 9: Optimise Set.prototype.has for symbols in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/e5f6eb92c12c
Part 10: Optimise Set.prototype.has for BigInts in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/186a7d8db816
Part 11: Optimise Set.prototype.has for objects in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/6f1d162738b4
Part 12: Optimise Set.prototype.has for non-GC things in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/d24cb3906dda
Part 13: Optimise Set.prototype.has for strings in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/77d1207af1c0
Part 14: Optimise Set.prototype.has for symbols in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/63d0d4dc2972
Part 15: Optimise Set.prototype.has for BigInts in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/b1db78c1508a
Part 16: Optimise Set.prototype.has for objects in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/ed9ca5806dbc
Part 17: Optimise Set.prototype.has for values in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/1f7646c44496
Part 18: Optimise Map.prototype.has in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/7b187e896bef
Part 19: Optimise Map.prototype.has in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/684915d2fc1c
Part 20: Optimise Map.prototype.get in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/182be3b078d9
Part 21: Optimise Map.prototype.get in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/d21b307ccfaf
Part 22: Assert the hash is correctly computed. r=iain

Thanks, I'll look into it.

Flags: needinfo?(andrebargull)
Pushed by andre.bargull@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/4ff4b998d1e0
Part 1: Remove stale fixme comment. r=iain
https://hg.mozilla.org/integration/autoland/rev/1a6a218606f0
Part 2: Add MacroAssembler::equalBigInts(). r=iain
https://hg.mozilla.org/integration/autoland/rev/a66c12cfcc6c
Part 3: Add MacroAssembler::mul32(Imm32, Register). r=iain
https://hg.mozilla.org/integration/autoland/rev/e5112a66b77f
Part 4: Remove unnecessary restriction for branch64 with Address operand. r=iain
https://hg.mozilla.org/integration/autoland/rev/3ff8b21506fa
Part 5: Add branch64 for (Address, Register64). r=iain
https://hg.mozilla.org/integration/autoland/rev/9fb7fdf7cfda
Part 6: Optimise Set.prototype.has in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/e2eaede65aff
Part 7: Optimise Set.prototype.has for non-GC things in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/2852f51c1ba4
Part 8: Optimise Set.prototype.has for strings in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/5a2e28ae1a71
Part 9: Optimise Set.prototype.has for symbols in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/96deae80424b
Part 10: Optimise Set.prototype.has for BigInts in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/facc90d124f6
Part 11: Optimise Set.prototype.has for objects in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/f7193a68e410
Part 12: Optimise Set.prototype.has for non-GC things in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/742dccdce71b
Part 13: Optimise Set.prototype.has for strings in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/0fc54c597c6f
Part 14: Optimise Set.prototype.has for symbols in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/39c9b3ccc224
Part 15: Optimise Set.prototype.has for BigInts in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/189d496a0b0d
Part 16: Optimise Set.prototype.has for objects in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/2f70a3c1a32b
Part 17: Optimise Set.prototype.has for values in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/939d0d0c77d1
Part 18: Optimise Map.prototype.has in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/d4ea49a182f4
Part 19: Optimise Map.prototype.has in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/cfc430046c54
Part 20: Optimise Map.prototype.get in CacheIR. r=iain
https://hg.mozilla.org/integration/autoland/rev/9bdc0a480190
Part 21: Optimise Map.prototype.get in Warp. r=iain
https://hg.mozilla.org/integration/autoland/rev/cbcbf9b36569
Part 22: Assert the hash is correctly computed. r=iain

(In reply to Pulsebot from comment #30)

Backout by abutkovits@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/a1d9ddb4fb79
Backed out 21 changesets for causing Bug 1724298. CLOSED TREE

== Change summary for alert #30853 (as of Tue, 10 Aug 2021 03:22:25 GMT) ==

Regressions:

Ratio Suite Test Platform Options Absolute values (old vs new)
6% ares6-sm linux64-shippable 43.76 -> 46.37

For up to date results, see: https://treeherder.mozilla.org/perfherder/alerts?id=30853

Old alert summary before the backout:

== Change summary for alert #30782 (as of Thu, 05 Aug 2021 01:35:57 GMT) ==

Regressions:

Ratio Suite Test Platform Options Absolute values (old vs new)
10% imdb loadtime android-hw-g5-7-0-arm7-shippable-qr warm webrender 5,898.17 -> 6,467.79
6% imdb loadtime android-hw-g5-7-0-arm7-shippable-qr cold webrender 7,078.08 -> 7,473.67
4% imdb ContentfulSpeedIndex android-hw-g5-7-0-arm7-shippable-qr cold webrender 4,707.71 -> 4,907.75

Improvements:

Ratio Suite Test Platform Options Absolute values (old vs new)
47% facebook-cristiano LastVisualChange android-hw-g5-7-0-arm7-shippable-qr warm webrender 1,615.92 -> 853.00
45% facebook-cristiano loadtime android-hw-g5-7-0-arm7-shippable-qr warm webrender 1,542.58 -> 846.29
45% facebook-cristiano SpeedIndex android-hw-g5-7-0-arm7-shippable-qr warm webrender 1,232.42 -> 683.00
44% facebook LastVisualChange android-hw-g5-7-0-arm7-shippable-qr warm webrender 1,132.50 -> 637.25
44% facebook loadtime android-hw-g5-7-0-arm7-shippable-qr cold webrender 2,815.38 -> 1,590.21
... ... ... ... ... ...
4% facebook fnbpaint android-hw-g5-7-0-arm7-shippable-qr warm webrender 649.96 -> 622.42

For up to date results, see: https://treeherder.mozilla.org/perfherder/alerts?id=30782

(In reply to Pulsebot from comment #30)

Backout by abutkovits@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/a1d9ddb4fb79
Backed out 21 changesets for causing Bug 1724298. CLOSED TREE

This is a new alert summary as a result of the backout:
== Change summary for alert #30857 (as of Tue, 10 Aug 2021 11:55:25 GMT) ==

Regressions:

Ratio Suite Test Platform Options Absolute values (old vs new)
90% facebook-cristiano LastVisualChange android-hw-g5-7-0-arm7-shippable-qr warm webrender 857.50 -> 1,626.67
83% facebook-cristiano loadtime android-hw-g5-7-0-arm7-shippable-qr warm webrender 846.79 -> 1,553.38
82% facebook-cristiano SpeedIndex android-hw-g5-7-0-arm7-shippable-qr warm webrender 680.92 -> 1,238.92
78% facebook LastVisualChange android-hw-g5-7-0-arm7-shippable-qr warm webrender 642.50 -> 1,146.17
78% facebook-cristiano PerceptualSpeedIndex android-hw-g5-7-0-arm7-shippable-qr warm webrender 702.08 -> 1,248.42
77% facebook loadtime android-hw-g5-7-0-arm7-shippable-qr warm webrender 837.96 -> 1,484.33
74% facebook loadtime android-hw-g5-7-0-arm7-shippable-qr cold webrender 1,617.08 -> 2,813.25
67% dailymail loadtime android-hw-g5-7-0-arm7-shippable-qr warm webrender 1,467.54 -> 2,455.42
62% dailymail loadtime android-hw-g5-7-0-arm7-shippable-qr cold webrender 2,256.96 -> 3,651.00
55% facebook-cristiano LastVisualChange android-hw-g5-7-0-arm7-shippable-qr cold webrender 1,748.58 -> 2,710.92
... ... ... ... ... ...
6% facebook FirstVisualChange android-hw-g5-7-0-arm7-shippable-qr warm webrender 640.00 -> 677.67
6% facebook dcf android-hw-g5-7-0-arm7-shippable-qr warm webrender 600.48 -> 635.00
6% facebook fcp android-hw-g5-7-0-arm7-shippable-qr warm webrender 619.79 -> 654.71
6% facebook fnbpaint android-hw-g5-7-0-arm7-shippable-qr warm webrender 624.08 -> 658.92
4% ares6 macosx1015-64-shippable-qr webrender 53.28 -> 55.55

Improvements:

Ratio Suite Test Platform Options Absolute values (old vs new)
9% imdb loadtime android-hw-g5-7-0-arm7-shippable-qr warm webrender 6,485.75 -> 5,884.92
5% imdb loadtime android-hw-g5-7-0-arm7-shippable-qr cold webrender 7,474.33 -> 7,110.67
4% imdb ContentfulSpeedIndex android-hw-g5-7-0-arm7-shippable-qr cold webrender 4,892.96 -> 4,680.83
2% imdb LastVisualChange android-hw-g5-7-0-arm7-shippable-qr cold webrender 10,356.33 -> 10,138.25

For up to date results, see: https://treeherder.mozilla.org/perfherder/alerts?id=30857

== Change summary for alert #30900 (as of Thu, 12 Aug 2021 09:01:48 GMT) ==

Improvements:

Ratio Test Platform Options Absolute values (old vs new)
5% ares6-sm linux64-shippable 46.38 -> 44.06
5% ares6-sm linux64-shippable 46.00 -> 43.79

For up to date results, see: https://treeherder.mozilla.org/perfherder/alerts?id=30900

Regressions: 1729269
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: