1821107 - WeakMap.get is 5x slower in SM than V8

Status: NEW

(Core :: JavaScript Engine, task, P2)

Description

[Jeff Muizelaar [:jrmuizel]]

Ember-todoMVC has:

 exports.peekMeta = function (obj) {
      var pointer = obj;
      var meta = void 0;
      while (pointer !== undefined && pointer !== null) {
        meta = metaStore.get(pointer);
        // jshint loopfunc:true
        if (meta !== undefined) {
          return meta;
        }

        pointer = getPrototypeOf(pointer);
      }

    };

peekMeta is called 684140 times during the shell version of ember-todoMVC and get returns an object only 2043 times.

SM: https://share.firefox.dev/3T7eZZ9, V8: https://share.firefox.dev/3ZPmaqX

Comment 1

[Jan de Mooij [:jandem]]

This is doing the unique id lookup thing. We probably should be moving away from that for these maps...

Comment 2

[Jeff Muizelaar [:jrmuizel]]

The original V8 profile had inlining enabled which made things seem worse than they actually are because peekMeta was getting inlined. I've updated the initial comment and the bug title.

Comment 3

[Steve Fink [:sfink] [:s:]]

I wrote a very basic microbenchmark. It creates a WeakMap, populates it with 50K keys mapping to 50K values (all distinct). Then it does 80M lookups, cycling through the keys.

• SM: 80ns / lookup
• V8: 20ns / lookup
• SM with PointerHasher: 50ns / lookup

It is about 80ns per lookup in SM, 20ns in V8, and 50ns in SM if I do the experiment of replacing MovableCellHasher<JSObject*> with PointerHasher<JSObject*>. The latter isn't actually correct because it doesn't do rekeying, so it fails to find objects once they've been moved. (5% of the lookups fail after this change. If I run with --no-ggc, they all succeed, and it drops to 47ns/lookup.)

before: https://share.firefox.dev/3T3xEVH
after: https://share.firefox.dev/3kRxkwQ

The main thing I see where this doesn't match is that all of my lookups are successful (modulo the PointerHasher correctness thing).

Comment 4

[Steve Fink [:sfink] [:s:]]

Attachment: weakmapBench.js

Comment 5

[Jeff Muizelaar [:jrmuizel]]

(In reply to Steve Fink [:sfink] [:s:] from comment #3)

The main thing I see where this doesn't match is that all of my lookups are successful (modulo the PointerHasher correctness thing).

Indeed. Most of the lookups in ember fail.

My quick reading here is that V8 early out's if the object doesn't have a hash and avoids the table lookup. Maybe that's the path that's being taken here?

Comment 6

[Jeff Muizelaar [:jrmuizel]]

Maybe my theory is wrong. Here's the generated code for V8's Builtin:WeakMapLookupHashIndex:

test bl, 0x1
jz $+0xe9
mov rdx, qword [rbx - 0x1]
movzx edx, word [rdx + 0xb]
cmp dx, 0x114
jnb $+0x27
mov rcx, qword [r13 + 0x1a78]
test byte [rcx], -0x1
jz $+0xca
cmp dx, 0x80
jnz $+0xbf
test byte [rbx + 0xb], 0x4
jnz $+0xb5
jmp $+0xf
lea ecx, dword [rdx - 0x831]
cmp ecx, 0x3
jna $+0xa4
cmp dx, 0x114
jnb $+0xb
mov edx, dword [rbx + 0x7]
shr edx, 0x2
movsxd rdx, edx
jmp $+0x4c
mov rdx, qword [rbx + 0x7]
test dl, 0x1
jnz $+0x6
sar rdx, 0x20
jmp $+0x38
mov rcx, qword [rdx - 0x1]
movzx ecx, word [rcx + 0xb]
cmp cx, 0x103
jz $+0x1b
cmp cx, 0xb3
jz $+0x4
xor edx, edx
jmp $+0x1e
movsxd rcx, dword [rdx + 0xb]
cmp rcx, 0x4
jna $+0x6a
movsxd rdx, dword [rdx + 0x33]
jmp $+0xe
movsxd rdx, dword [rdx + 0xb]
shr rdx, 0xa
and edx, 0x1fffff
test rdx, rdx
jz $+0x46
movsxd rcx, dword [rax + 0x23]
sub rcx, 0x1
and rdx, rcx
xor esi, esi
jmp $+0x10
add rsi, 0x1
add rdx, rsi
mov rdi, rcx
and rdi, rdx
mov rdx, rdi
lea rdi, qword [rdx * 2 + 0x3]
mov r8, qword [rax + rdi * 8 + 0xf] # This is the hottest part of the function
cmp qword [r13 + 0x98], r8
jz $+0x11
cmp rbx, r8
jnz $-0x2b
lea rbx, qword [rdi + 0x1]
shl rbx, 0x20
mov rax, rbx
ret
mov rax, -0x100000000
ret
int 0x3
nop
nop

The hot part looks sort of like this loop:
https://source.chromium.org/chromium/chromium/src/+/main:v8/src/builtins/builtins-collections-gen.cc;l=2429;drc=bec0ef46974cd9a6bc0f1f1ae34baa11913f77af

Comment 7

[Jan de Mooij [:jandem]]

(In reply to Jeff Muizelaar [:jrmuizel] from comment #5)

Indeed. Most of the lookups in ember fail.

Are you sure? Yesterday I added some logging to WeakMapObject::get_impl and when we do the lookup, we found an item in the table in ~185k cases and miss in ~1300. That was EmberJS from Speedometer 2.1 and includes browser startup though.

Comment 8

[Jeff Muizelaar [:jrmuizel]]

(In reply to Jan de Mooij [:jandem] from comment #7)

(In reply to Jeff Muizelaar [:jrmuizel] from comment #5)

Indeed. Most of the lookups in ember fail.

Are you sure? Yesterday I added some logging to WeakMapObject::get_impl and when we do the lookup, we found an item in the table in ~185k cases and miss in ~1300. That was EmberJS from Speedometer 2.1 and includes browser startup though.

You're right, my instrumentation was backwards. It's mostly getting hits with a small number of misses.

Comment 9

[Jeff Muizelaar [:jrmuizel]]

If we can get this to match V8 it looks like it would improve the Ember score by ~3.5%

Comment 10

[Jeff Muizelaar [:jrmuizel]]

FWIW, it sounds like we might be removing Ember from Speedometer so it may make sense to pause work on this until we know if that's happening or not.

Comment 11

[Jeff Muizelaar [:jrmuizel]]

However, it also shows up in the updated Vue benchmark so it's probably still worth while.

Comment 12

[Jon Coppeard (:jonco) (PTO until 27th Jan)]

I've done all the work on this that I plan to at the moment. The current score is now down to 2.7 times worse than V8. There may be other areas to investigate beyond improving unique ID lookup that are benefical to the use case.

Comment 13

[Jan de Mooij [:jandem]]

This still shows up on Speedometer 3, but much less without Ember, as expected.

I see about 430,000 calls to WeakMapObject::get_impl on a full Speedometer 3 run, so ~43k for a single iteration. On Speedometer 2.1 it's more than 1.8 million calls for the full run.

On Speedometer 2 the lookup finds an item in > 99% of cases. On Speedometer 3 this is ~84%.