[demo][hook-callback][Chrome Canary 63.0.3239.0] Map.get() is very slow

[t2ym]

[demo][hook-callback][Chrome Canary 63.0.3239.0] Map.get() is very slow

More than 100 times slower than that on Chrome 61.

Observe until the release.

[t2ym]

Suspected Root Cause - this is not the root cause

• The slow Map object _globalObjects has their objects registered in the order of Object.keys(Object.getOwnPropertyDescriptors(window)).sort(), which may generate the index of the Map object in a very inefficient way. Randomization of the registration order may solve the issue.
  • Another Map object _globalMethods does not have the issue maybe because of the order of the registration.

[t2ym]

Observation (Chrome Canary 63 only)

• The costs of searching (Map.get()) differ in various keys.
  • _globalObject.get(Object) is very slow while _globalObject.get(firebase) is fast.
    • More than 100 times of difference in the throughputs.
    • Is the Map object performing linear search? The last object registered is retrieved fastest.
  • _globalObject.get(PrivateAPI) is relatively fast. It seems that native APIs with smaller hash ids are causing the bottleneck in searching.

Verification Code

Object.getOwnPropertyNames(window).filter(name => name.indexOf('_pp_') < 0).forEach((name) => {
    let start = Date.now(); let o = _global[name];
    for (let i = 0; i < 100000; i++) { _globalObjects.get(o) === name; }
    let end = Date.now();
    console.log('name: ' + (name + ' '.repeat(48)).substr(0, 48) + ' ' + (' '.repeat(16) + (new Intl.NumberFormat()).format(parseInt(100000 * 1000 / (end - start)))).substr(-16) + ' op/s');
})

function _globalObjectsGet(o) { let name = o instanceof Object ? o.name : undefined; if (o === _global[name]) { return name; } else { return _globalObjects.get(o); } }
Object.getOwnPropertyNames(window).filter(name => name.indexOf('_pp_') < 0).forEach((name) => {
    let start = Date.now(); let o = _global[name];
    for (let i = 0; i < 100000; i++) { _globalObjectsGet(o) === name; }
    let end = Date.now();
    console.log('name: ' + (name + ' '.repeat(48)).substr(0, 48) + ' ' + (' '.repeat(16) + (new Intl.NumberFormat()).format(parseInt(100000 * 1000 / (end - start)))).substr(-16) + ' op/s');
})

[t2ym]

Chromium Source Code Analysis

• In JSMap, CollectionsBuiltinsAssembler::FindOrderedHashTableEntry linearly walk the bucket chain of the looked-up hash for the key, which can cause many iterations in searching (Map.prototype.get), depending on the key and the hash table.
  • The code has not been checked against Chrome 61, which has no such issue.
• This can cause slow lookup of the key and the value in Map.prorotype.get due to the inappropriately long chain of the hash table.

https://codereview.chromium.org/2958063002 https://github.com/v8/v8/commit/aba708a1464043c73e7267a2baef500c2c6c0cc9 https://github.com/v8/v8/commit/4e9e81454049b59b256a71a604a9c36a341f923e https://github.com/v8/v8/blame/31cde16eeeccad72239c3036c8547a44a33f75d8/src/builtins/builtins-collections-gen.cc#L683

https://bugs.chromium.org/p/v8/issues/detail?id=6571 https://docs.google.com/document/d/13z1fvRVpe_oEroplXEEX0a3WK94fhXorHjcOMsDmR-8/edit#

[t2ym]

Potential Workaround

• Get constructor.name and compare constructor with _global[constructor.name]
• Overheads for Chrome 61
• Map would be practically meaningless if this inefficiency should not be fixed in Turbofan engine for future release versions of Chrome browsers

This solution is useless since the workaround is slower...

  const isSlowMap = (() => {
    const __globalObjectsGet = (o) => { let name = o instanceof Object ? o.name : undefined; if (o === _global[name]) { return name; } else { return _globalObjects.get(o); } };
    let startMap = Date.now();
    for (let i = 0; i < 100000; i++) {
      _globalObjects.get(Object)
    }
    let endMap = Date.now();
    let startProperty = Date.now();
    for (let i = 0; i < 100000; i++) {
      __globalObjectsGet(Object)
    }
    let endProperty = Date.now();
    return (endMap - startMap) > (endProperty - startProperty);
  })();
  let isInGlobalObjectsGet = false; // guard for recursive infinite calls
  const _globalObjectsGet = function _globalObjectsGet(o) {
    let name;
    if (!isInGlobalObjectsGet && typeof o === 'function') {
      isInGlobalObjectsGet = true;
      name = o.name;
      if (name && _globalObjects.values()[name] && _global[name] === o && _global.hasOwnProperty(name)) {
        isInGlobalObjectsGet = false;
        return name;
      }
      isInGlobalObjectsGet = false;
    }
    return _globalObjects.get(o);
  }
  // Usage:
  name = isSlowMap ? _globalObjectsGet(ctor) : _globalObjects.get(ctor);

[t2ym]

More practical approach: This is practically effective.

  // Note: Expecting JIT compiler to expand this function inline
  // Note: _globalObjectsGet() is faster for these case-labeled objects than Map.get() for them
  const _globalObjectsGet = typeof window === 'object'
    ? function _globalObjectsGet(o) {
        switch (o) {
        case undefined: return 'undefined';
        case Object: return 'Object';
        case Array: return 'Array';
        case Function: return 'Function';
        case Math: return 'Math';
        case window: return 'window';
        case RegExp: return 'RegExp';
        default:
          return _globalObjects.get(o);
        }
      }
    : function _globalObjectsGet(o) {
        switch (o) {
        case undefined: return 'undefined';
        case Object: return 'Object';
        case Array: return 'Array';
        case Function: return 'Function';
        case Math: return 'Math';
        case RegExp: return 'RegExp';
        default:
          return _globalObjects.get(o);
        }
      };

[t2ym]

Benchmarks with hookBenchmark('__hook__acl')

Chrome version	hookacl	. (op/s)	= (op/s)	() (op/s)	f (op/s)
61.0.3163.100	0.0.159	1,824,817	2,110,595	954,380	5,824,111
63.0.3239.0	0.0.159	642,756	644,870	315,547	11,494,252
61.0.3163.100	0.0.160	2,236,636	2,283,626	1,034,768	6,172,839
63.0.3239.100	0.0.160	2,123,593	2,382,086	1,034,447	10,695,187

[t2ym]

The root cause is not fixed. So Chrome status should be tracked.

[t2ym]

The root cause is fixed in Chrome Canary 64.0.3240.0

Note

• It seems the difference is in === operations, not in Map.get()

Chrome 64.0.3240.0

console.time(); for (let i = 0; i < 1000000000; i++) { _globalObjects.get(Object) === 'Object'; } console.timeEnd()
default: 8611.14501953125ms
console.time(); for (let i = 0; i < 1000000000; i++) { _globalObjects.get(Object); } console.timeEnd()
default: 620.914794921875ms

Chrome 61.0.3163.100

console.time(); for (let i = 0; i < 1000000000; i++) { _globalObjects.get(Object) === 'Object'; } console.timeEnd()
default: 1392.01904296875ms
console.time(); for (let i = 0; i < 1000000000; i++) { _globalObjects.get(Object); } console.timeEnd()
default: 619.695068359375ms```

[t2ym]

If the root cause is fixed in the Chrome 62 release (not beta), the changes for the issue will be removed.