Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance regression in v8.10 and v9.0 for Maps with object keys #19769

Closed
themaarten opened this issue Apr 3, 2018 · 15 comments

Comments

@themaarten
Copy link

commented Apr 3, 2018

  • Version: >= v8.10.0, >= v9.0.0
  • Platform: multiple (tested on Ubuntu 14.04.5 LTS (GNU/Linux 3.13.0-129-generic x86_64) and macOS 10.13.3 (17D102) Darwin 17.4.0)
  • Subsystem: V8

Compared to v8.9.4 there's a major performance regression in v8.10.0 and v9.0.0 for Map instances that use objects as keys. The issue is making our application unacceptably slow, forcing us to downgrade.

To be more specific, the get, set, and has methods of Map instances with several hundred (or more) keys have become very slow when those keys are objects (and exist in the map). The performance for string and number keys (the two primitive types that I've tested) seems to be fine.

Comparing run time of the script below between Node.js v8.9.4 and v8.10.0 demonstrates the problem.

'use strict';

const runCount = 100;
const keyCount = 10000;

let map = new Map();

// Create an array of unique objects used as keys below
let keys = new Array(keyCount);
for (let i = 0; i < keyCount; i++) keys[i] = {};

// Create a map entry for each key
for (let key of keys) map.set(key, true);


let startTime = process.hrtime();

// Perform runCount rounds in which each key is looked up
for (let i = 0; i < runCount; i++) {
    for (let key of keys) {

        // This call below is the one we're benchmarking. We're using
        // `map.get` here, but `map.set` and `map.has` show a similar
        // performance regression.

        let value = map.get(key);

        // Do something with the value to make sure that 
        // the get call isn't being optimized away
        if (value !== true) throw new Error();
    }
}

// Print the Node.js version and elapsed time in milliseconds
let elapsed = process.hrtime(startTime);
let [seconds, nanoseconds] = elapsed;
let milliseconds = Math.round(seconds * 1e3 + nanoseconds / 1e6);
console.log(`${process.version} ${milliseconds} ms`);

The performance difference becomes more pronounced as the size of the map (keyCount) increases. My system produced these figures for the supplied parameters:

v8.9.4     88 ms
v8.10.0  3980 ms

This issue could perhaps be the cause of #19444.

@targos targos added the V8 Engine label Apr 3, 2018

@vsemozhetbyt

This comment has been minimized.

Copy link
Contributor

commented Apr 3, 2018

Node.js v8.9.4 has V8 6.1, while Node.js v8.10.0 and v9.0.0 have V8 6.2, so it may be V8 regression.

@vsemozhetbyt

This comment has been minimized.

Copy link
Contributor

commented Apr 3, 2018

cc @nodejs/v8

@targos

This comment has been minimized.

Copy link
Member

commented Apr 3, 2018

This is fixed in current V8. Using our canary builds, I can say the fix is between V8 versions 6.3.292 and 6.3.296

@vsemozhetbyt

This comment has been minimized.

Copy link
Contributor

commented Apr 3, 2018

Are we planning to upgrade Node.js v8.x LTS to V8 6.3?

@targos

This comment has been minimized.

Copy link
Member

commented Apr 3, 2018

@vsemozhetbyt There is no plan to do it. v9.x was never upgraded to this version.

This is very likely fixed by this commit: v8/v8@a803fad

@vsemozhetbyt

This comment has been minimized.

Copy link
Contributor

commented Apr 3, 2018

So we can only advise upgrading to Node.js v10 after the release in a month in this situation, right?

@vsemozhetbyt

This comment has been minimized.

Copy link
Contributor

commented Apr 3, 2018

In my machine:

v8.9.4 153 ms
v8.11.0 4282 ms
v10.0.0-nightly20180402a9a1f12b42 52 ms

So after upgrading to Node.js v10, there may be a 3x performance gain comparing to v8.9.4.

@targos

This comment has been minimized.

Copy link
Member

commented Apr 3, 2018

So we can only advise upgrading to Node.js v10 after the release in a month in this situation, right?

We can try to backport the fix. I'm doing that right now.

@targos

This comment has been minimized.

Copy link
Member

commented Apr 3, 2018

targos added a commit that referenced this issue Apr 5, 2018

deps: cherry-pick a4bddba from upstream V8
Original commit message:

    [Runtime] Use platform specific value for JSReceiver::HashMask

    This allows us to remove the loop while calculating the hash value and
    just use the HashMask as the mask for ComputeIntegerHash. This
    previously overflowed on 32-bit systems failing the Smi::IsValid
    check.

    Bug: v8:6404
    Change-Id: I84610a7592fa9d7ce4fa5cef7903bd50b8e8a4df
    Reviewed-on: https://chromium-review.googlesource.com/702675
    Reviewed-by: Adam Klein <adamk@chromium.org>
    Commit-Queue: Sathya Gunasekaran <gsathya@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#48319}

Refs: v8/v8@a4bddba

PR-URL: #19770
Fixes: #19769
Reviewed-By: Ali Ijaz Sheikh <ofrobots@google.com>

targos added a commit that referenced this issue Apr 5, 2018

deps: cherry-pick 7abdadc from upstream V8
Original commit message:

    Sprinkle some DisallowHeapAllocation

    Cq-Include-Trybots: master.tryserver.chromium.linux:linux_chromium_rel_ng
    Change-Id: I7d34ccddeea08f5935e360e8c36791365f27f89e
    Reviewed-on: https://chromium-review.googlesource.com/647706
    Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
    Commit-Queue: Camillo Bruni <cbruni@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#47804}

Refs: v8/v8@7abdadc

PR-URL: #19770
Fixes: #19769
Reviewed-By: Ali Ijaz Sheikh <ofrobots@google.com>

targos added a commit that referenced this issue Apr 5, 2018

deps: cherry-pick a803fad from upstream V8
Original commit message:

    Make sure the identity hash is uniform (at least in the lower bits).

    In the current implementation of hash code for objects (identity hash),
    we do not bother to shift the hash when we retrieve it from the
    hash-length bitfield in a property array. (Even worse, we store shifted
    value even if we do not have property array or inside dictionaries.)
    That means that the hash-code for objects is always divisible by 1024.
    Since our hash table uses a simple masking with (2^logsize - 1) to
    obtain the bucket, we get terrible hash collisions - essentially, our
    hash table degenerates to a linked list for fewer than 1024 elements.

    This CL always shifts the hash code so that the value in the lowest
    21 bits is uniformly distributed.

    This results in big improvements on medium to large hash tables.
    A program storing 1M elements into a WeakMap gets roughly
    17x faster.  A program retrieving 1M elements from a Map
    improves even more dramatically (>100x).

    const a = [];
    for (let i = 0; i < 1e6; i++) a[i] = {};

    const m = new Map();
    console.time("Map.set");
    for (let i = 0; i < 1e6; i++) {
      m.set(a[i], i);
    }
    console.timeEnd("Map.set");

    console.time("Map.get");
    let s = 0;
    for (let i = 0; i < 1e6; i++) {
      s += m.get(a[i]);
    }
    console.timeEnd("Map.get");

    const w = new WeakMap();
    console.time("WeakMap.set");
    for (let i = 0; i < 1e6; i++) {
      w.set(a[i], i);
    }
    console.timeEnd("WeakMap.set");

    Before the fix:

    Map.set: 157.575000
    Map.get: 28333.182000
    WeakMap.set: 6923.826000

    After the fix:

    Map.set: 178.382000
    Map.get: 185.930000
    WeakMap.set: 409.529000

    Note that Map does not suffer from the hash collision on insertion because
    it uses chaining (insertion into linked list is fast regardless of size!), and
    we cleverly avoid lookup in the hash table on update if the key does not have
    identity hash yet. This is in contrast to the WeakMap, which uses
    open-addressing, and deals with collisions on insertion.

    Bug: v8:6916
    Change-Id: Ic5497bd4501e3b767b3f4acb7efb4784cbb3a2e4
    Reviewed-on: https://chromium-review.googlesource.com/713616
    Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
    Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#48480}

Refs: v8/v8@a803fad

PR-URL: #19770
Fixes: #19769
Reviewed-By: Ali Ijaz Sheikh <ofrobots@google.com>
@targos

This comment has been minimized.

Copy link
Member

commented Apr 5, 2018

Fix landed on v9.x-staging. PR to v8.x-staging: #19824

gibfahn added a commit that referenced this issue Apr 12, 2018

deps: cherry-pick a4bddba from upstream V8
Original commit message:

    [Runtime] Use platform specific value for JSReceiver::HashMask

    This allows us to remove the loop while calculating the hash value and
    just use the HashMask as the mask for ComputeIntegerHash. This
    previously overflowed on 32-bit systems failing the Smi::IsValid
    check.

    Bug: v8:6404
    Change-Id: I84610a7592fa9d7ce4fa5cef7903bd50b8e8a4df
    Reviewed-on: https://chromium-review.googlesource.com/702675
    Reviewed-by: Adam Klein <adamk@chromium.org>
    Commit-Queue: Sathya Gunasekaran <gsathya@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#48319}

PR-URL: #19824
Refs: v8/v8@a4bddba
Fixes: #19769
Reviewed-By: Yang Guo <yangguo@chromium.org>
Reviewed-By: Gibson Fahnestock <gibfahn@gmail.com>

gibfahn added a commit that referenced this issue Apr 12, 2018

deps: cherry-pick 7abdadc from upstream V8
Original commit message:

    Sprinkle some DisallowHeapAllocation

    Cq-Include-Trybots: master.tryserver.chromium.linux:linux_chromium_rel_ng
    Change-Id: I7d34ccddeea08f5935e360e8c36791365f27f89e
    Reviewed-on: https://chromium-review.googlesource.com/647706
    Reviewed-by: Michael Lippautz <mlippautz@chromium.org>
    Commit-Queue: Camillo Bruni <cbruni@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#47804}

PR-URL: #19824
Refs: v8/v8@7abdadc
Fixes: #19769
Reviewed-By: Yang Guo <yangguo@chromium.org>
Reviewed-By: Gibson Fahnestock <gibfahn@gmail.com>

gibfahn added a commit that referenced this issue Apr 12, 2018

deps: cherry-pick a803fad from upstream V8
Original commit message:

    Make sure the identity hash is uniform (at least in the lower bits).

    In the current implementation of hash code for objects (identity hash),
    we do not bother to shift the hash when we retrieve it from the
    hash-length bitfield in a property array. (Even worse, we store shifted
    value even if we do not have property array or inside dictionaries.)
    That means that the hash-code for objects is always divisible by 1024.
    Since our hash table uses a simple masking with (2^logsize - 1) to
    obtain the bucket, we get terrible hash collisions - essentially, our
    hash table degenerates to a linked list for fewer than 1024 elements.

    This CL always shifts the hash code so that the value in the lowest
    21 bits is uniformly distributed.

    This results in big improvements on medium to large hash tables.
    A program storing 1M elements into a WeakMap gets roughly
    17x faster.  A program retrieving 1M elements from a Map
    improves even more dramatically (>100x).

    const a = [];
    for (let i = 0; i < 1e6; i++) a[i] = {};

    const m = new Map();
    console.time("Map.set");
    for (let i = 0; i < 1e6; i++) {
      m.set(a[i], i);
    }
    console.timeEnd("Map.set");

    console.time("Map.get");
    let s = 0;
    for (let i = 0; i < 1e6; i++) {
      s += m.get(a[i]);
    }
    console.timeEnd("Map.get");

    const w = new WeakMap();
    console.time("WeakMap.set");
    for (let i = 0; i < 1e6; i++) {
      w.set(a[i], i);
    }
    console.timeEnd("WeakMap.set");

    Before the fix:

    Map.set: 157.575000
    Map.get: 28333.182000
    WeakMap.set: 6923.826000

    After the fix:

    Map.set: 178.382000
    Map.get: 185.930000
    WeakMap.set: 409.529000

    Note that Map does not suffer from the hash collision on insertion because
    it uses chaining (insertion into linked list is fast regardless of size!), and
    we cleverly avoid lookup in the hash table on update if the key does not have
    identity hash yet. This is in contrast to the WeakMap, which uses
    open-addressing, and deals with collisions on insertion.

    Bug: v8:6916
    Change-Id: Ic5497bd4501e3b767b3f4acb7efb4784cbb3a2e4
    Reviewed-on: https://chromium-review.googlesource.com/713616
    Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
    Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#48480}

PR-URL: #19824
Refs: v8/v8@a803fad
Fixes: #19769
Reviewed-By: Yang Guo <yangguo@chromium.org>
Reviewed-By: Gibson Fahnestock <gibfahn@gmail.com>
@targos

This comment has been minimized.

Copy link
Member

commented Apr 27, 2018

Fix landed and will be available in the next release

@targos targos closed this Apr 27, 2018

@nkreeger

This comment has been minimized.

Copy link

commented Apr 29, 2018

Hi @targos thank you for the update - do you have an ETA on the next release? Is there a place I can track this? I work on TensorFlow.js and our platform uses WeakMap for internal references to tensor data. We have a node.js binding that we plan on shipping soon, but we'd like to have the node release handy (long training loops are affected w/ this bug):

https://github.com/tensorflow/tfjs-node
https://github.com/tensorflow/tfjs-core

@Koslun

This comment has been minimized.

Copy link

commented Apr 30, 2018

Thanks for the great work @targos !

Going from the the past half year or so I presume a new release is coming between now and the coming two months or so but if anyone has a better guess I'd greatly welcome it. Good to know it'll be any 8.x release higher than 8.11.1.

As described in this medium article it also affects Webpack 4 users as Webpack 4 relies on SortableSet internally. In that example switching back to Node.js 8.9.4 improved build times from 6s to 4.5s. I would imagine this changing wildly depending on your configuration but should affect all Webpack 4 users noticeably.

@targos

This comment has been minimized.

Copy link
Member

commented May 10, 2018

According to #20478, the release will be on 2018-05-18.

@Koslun

This comment has been minimized.

Copy link

commented May 10, 2018

@targos Thanks, not too far off then.

billyvg added a commit to getsentry/sentry that referenced this issue Mar 14, 2019

billyvg added a commit to getsentry/sentry-plugins that referenced this issue Mar 14, 2019

build(webpack): Fix incremental webpack builds (upgrade to node@8.15.1)
Upgrades to node@8.15.1 and yarn@1.13.0 to be consistent with rest of sentry

Perf regression in node 8.10.0 - see nodejs/node#19769
See getsentry/sentry#12408

billyvg added a commit to getsentry/sentry that referenced this issue Mar 15, 2019

billyvg added a commit to getsentry/sentry-plugins that referenced this issue Mar 15, 2019

build(webpack): Fix incremental webpack builds (upgrade to node@8.15.…
…1) (#453)

Upgrades to node@8.15.1 and yarn@1.13.0 to be consistent with rest of sentry

Perf regression in node 8.10.0 - see nodejs/node#19769
See getsentry/sentry#12408
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.