Bug 280938 – `mnemonist/lru-cache` .set is 28x slower in jsc/bun compared to v8/node

• Status: NEW
• Component: JavaScriptCore

[Jarred Sumner]

Created attachment 472822 [details]
reproduction

jsc shell (system installed version on macOS 14.4.1)
```
clk: ~2.74 GHz
cpu: null
runtime: jsc (javascript-browser)

benchmark              avg (min … max) p75   p99    (min … top 1%)
-------------------------------------- -------------------------------
mnemonist/lru-cache       4.40 ms/iter   4.50 ms   4.96 ms ▂██▅▄▄▃▂▁▁▁
```

Bun v1.1.30 (https://commits.webkit.org/284721@main)

```js
clk: ~2.74 GHz
cpu: null
runtime: bun 1.1.30 (javascript-browser)

benchmark              avg (min … max) p75   p99    (min … top 1%)
-------------------------------------- -------------------------------
mnemonist/lru-cache       5.70 ms/iter   6.03 ms   6.68 ms ▃▅▄█▆▆▇▆▃▂▂
```

Node.js:
```
clk: ~2.62 GHz
cpu: Apple M3 Max
runtime: node 22.9.0 (arm64-darwin)

benchmark              avg (min … max) p75   p99    (min … top 1%)
-------------------------------------- -------------------------------
mnemonist/lru-cache     161.77 µs/iter 158.17 µs 215.46 µs █▅▂▁▂▁▁▁▁▁▁
```

Sampling profiler output from jsc shell:
```

Sampling rate: 1000.000000 microseconds. Total samples: 35619
Top functions as <numSamples  'functionName#hash:sourceID'>
 35582    '#<nil>:3'
    35    '(module)#<nil>:3'
     1    'newPromiseCapabilitySlow#<nil>:2'
     1    'isArray#<nil>:2'


Sampling rate: 1000.000000 microseconds. Total samples: 35619

Tier breakdown:
-----------------------------------
LLInt:                     0  (0.000000%)
Baseline:                  3  (0.008422%)
DFG:                      74  (0.207754%)
FTL:                   35540  (99.778208%)
js builtin:                2  (0.005615%)
IPInt:                     0  (0.000000%)
WasmLLInt:                 0  (0.000000%)
BBQ:                       0  (0.000000%)
OMG:                       0  (0.000000%)
Wasm:                      0  (0.000000%)
Host:                      0  (0.000000%)
RegExp:                    0  (0.000000%)
C/C++:                     0  (0.000000%)
Unknown Executable:        2  (0.005615%)


Hottest bytecodes as <numSamples   'functionName#hash:JITType:bytecodeIndex'>
 31918    '#<nil>:FTL:bc#143'
  2482    '#<nil>:FTL:bc#154'
   815    '#<nil>:FTL:bc#12'
   198    '#<nil>:FTL:bc#0'
    57    '#<nil>:DFG:bc#143'
    21    '#<nil>:FTL:bc#166'
    20    '(module)#<nil>:FTL:bc#709'
    13    '#<nil>:FTL:bc#229'
     9    '#<nil>:FTL:bc#199'
     8    '#<nil>:DFG:bc#154'
     6    '#<nil>:FTL:bc#125'
     6    '#<nil>:FTL:bc#72'
     6    '(module)#<nil>:FTL:bc#675'
     6    '#<nil>:FTL:bc#217'
     5    '#<nil>:FTL:bc#137'
     5    '#<nil>:FTL:bc#184'
     5    '#<nil>:FTL:bc#178'
     5    '#<nil>:FTL:bc#98'
     4    '#<nil>:FTL:bc#96'
     4    '#<nil>:FTL:bc#67'
     4    '#<nil>:DFG:bc#12'
     3    '#<nil>:FTL:bc#113'
     3    '(module)#<nil>:FTL:bc#688'
     2    '(module)#<nil>:DFG:bc#703'
     2    '#<nil>:FTL:bc#55'
     2    '#<nil>:FTL:bc#148'
     1    '(module)#<nil>:Baseline:bc#593'
     1    '#<nil>:FTL:bc#160'
     1    '#<nil>:Baseline:bc#143'
     1    '(module)#<nil>:DFG:bc#731'
     1    '#<nil>:DFG:bc#98'
     1    '(module)#<nil>:Baseline:bc#543'
     1    '#<nil>:None:<nil>'
     1    '(module)#<nil>:FTL:bc#670'
     1    'newPromiseCapabilitySlow#<nil>:None:<nil>'
     1    'isArray#<nil>:DFG:bc#4'
```

Sampling profiler output from Bun v1.1.30:
```

Sampling rate: 1000.000000 microseconds. Total samples: 40705
Top functions as <numSamples  'functionName#hash:sourceID'>
 40703    '#<nil>:2'
     2    'profile#<nil>:4294967295'



Sampling rate: 1000.000000 microseconds. Total samples: 40706

Tier breakdown:
-----------------------------------
LLInt:                     0  (0.000000%)
Baseline:                362  (0.889304%)
DFG:                      25  (0.061416%)
FTL:                   40316  (99.041910%)
js builtin:                0  (0.000000%)
IPInt:                     0  (0.000000%)
WasmLLInt:                 0  (0.000000%)
BBQ:                       0  (0.000000%)
OMG:                       0  (0.000000%)
Wasm:                      0  (0.000000%)
Host:                      0  (0.000000%)
RegExp:                    0  (0.000000%)
C/C++:                     0  (0.000000%)
Unknown Executable:        3  (0.007370%)


Hottest bytecodes as <numSamples   'functionName#hash:JITType:bytecodeIndex'>
 36281    '#<nil>:FTL:bc#143'
  3041    '#<nil>:FTL:bc#154'
   994    '#<nil>:FTL:bc#12'
   157    '#<nil>:Baseline:bc#146'
    98    '#<nil>:Baseline:bc#107'
    93    '#<nil>:Baseline:bc#113'
    21    '#<nil>:DFG:bc#143'
    14    '#<nil>:Baseline:bc#39'
     4    '#<nil>:DFG:bc#154'
     3    'profile#<nil>:None:<nil>'
```

The version with the benchmarking library: https://gist.github.com/Jarred-Sumner/bba8b350a1db561fb8f487928285b7b7

A reproduction without the benchmarking library is attached. Both can be run from JSC shell.

Note that this is a different issue than https://bugs.webkit.org/show_bug.cgi?id=280600, this library isn't using a Set or a Map in this code path, and this is occurring after that commit landed. Maybe it's something related to iterators in FTL?

[Jarred Sumner]

Created attachment 472823 [details]
repro for jsc shell

[Dylan Conway]

Minimized repro:

```
const CAPACITY = 1000;

class LRUCache {
    constructor() {
        this.backward = [];
        this.keys = [];
        this.size = 0;
        this.head = 0;
        this.tail = 0;
        this.items = {};
    }
    set(key) {
        var pointer = this.items[key];
        if (this.size < CAPACITY) {
            pointer = this.size++;
        } else {
            pointer = this.tail;
            this.tail = this.backward[pointer];
            delete this.items[this.keys[pointer]];
        }
        this.items[key] = pointer;
        this.keys[pointer] = key;
        this.backward[this.head] = pointer;
        this.head = pointer;
    }
}

var lru = new LRUCache();

for (let i = 0; i < CAPACITY; i++) {
    for (let j = 0; j < CAPACITY * 2; j++) {
        lru.set("hi" + j);
    }
}
```

[Radar WebKit Bug Importer]

<rdar://problem/137802068>