Issue 2983823002: Improve hashCode for closures

Issue 2983823002: Improve hashCode for closures (Closed)

Created:
3 years, 5 months ago by alexmarkov

Modified:
3 years, 5 months ago

Reviewers:
zra, rmacnak, siva

CC:
reviews_dartlang.org, vm-dev_dartlang.org

Target Ref:
refs/heads/master

Visibility:
Public.

More Reviews

Description

Improve hashCode for closure objects This performance improvement is inspired by Flutter listeners stored in the HashSet (see ObserverList) and frequently checked using HashSet.contains(). If there are many such listeners and they are implicit instance closures (for example, created by 'new Listenable.merge(...)'), HashSet.contains() becomes very slow. It spends a lot of time in Closure_equals native method due to hash collisions between closure objects with same function but different receivers. This CL improves hashCode() calculation for implicit instance closures by mixing function hashcode with identity hashcode of the receiver. For explicit closures and static implicit closures hashCode() is improved by using identityHashCode() of a closure object. Also, hashcode is calculated once and cached in each closure instance. The size of a closure instance doesn't grow up because there was unused word-size padding both on 32-bit and 64-bit architectures. The execution time of the following micro-benchmark is reduced from 47665ms to 135ms on my Linux/x64 box. ------------------------------------- import "dart:collection"; class Foo { int _a; Foo(this._a); void bar() {} } main() { HashSet hs = new HashSet(); for (int i = 0; i < 1000; ++i) { hs.add(new Foo(i).bar); } var watch = new Stopwatch()..start(); for (int i = 0; i < 1000; ++i) { for (var c in hs) { hs.contains(c); } } int time = watch.elapsedMilliseconds; print("Time: ${time}ms\n"); } ------------------------------------- R=rmacnak@google.com, zra@google.com Committed: https://github.com/dart-lang/sdk/commit/b1197eb7141762fe42d7c738fa3395f3dc8c2b9d

Patch Set 1 #

Total comments: 14

Patch Set 2 : Review fixes #

Total comments: 2

Patch Set 3 : HashCode is also improved for explicit and static implicit closures #

Patch Set 4 : Error handling #

Total comments: 2

Created: 3 years, 5 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+89 lines, -35 lines)			Patch
M	runtime/lib/function.cc	View	1	1 chunk	+2 lines, -3 lines	0 comments	Download
M	runtime/lib/function.dart	View	1	2 chunks	+10 lines, -2 lines	0 comments	Download
M	runtime/vm/bootstrap.cc	View	1	2 chunks	+3 lines, -1 line	0 comments	Download
M	runtime/vm/bootstrap_natives.h	View	1	1 chunk	+1 line, -1 line	0 comments	Download
M	runtime/vm/clustered_snapshot.cc	View		1 chunk	+0 lines, -1 line	0 comments	Download
M	runtime/vm/dart_entry.h	View		1 chunk	+3 lines, -0 lines	0 comments	Download
M	runtime/vm/dart_entry.cc	View	1	1 chunk	+18 lines, -0 lines	0 comments	Download
M	runtime/vm/object.h	View	1	5 chunks	+9 lines, -4 lines	0 comments	Download
M	runtime/vm/object.cc	View	1 2 3	4 chunks	+36 lines, -18 lines	2 comments	Download
M	runtime/vm/raw_object.h	View	1	2 chunks	+6 lines, -5 lines	0 comments	Download
M	runtime/vm/symbols.h	View		1 chunk	+1 line, -0 lines	0 comments	Download

Messages

Total messages: 14 (4 generated)

Expand Messages | Collapse Messages | Show Generated Messages | Hide Generated Messages

rmacnak

https://codereview.chromium.org/2983823002/diff/1/runtime/lib/function.cc File runtime/lib/function.cc (right): https://codereview.chromium.org/2983823002/diff/1/runtime/lib/function.cc#newcode71 runtime/lib/function.cc:71: DEFINE_NATIVE_ENTRY(Closure_calculateHashCode, 1) { computeHash (Compare String and Type) https://codereview.chromium.org/2983823002/diff/1/runtime/lib/function.cc#newcode85 ...

3 years, 5 months ago (2017-07-19 01:00:24 UTC) #3

alexmarkov

3 years, 5 months ago (2017-07-19 17:54:20 UTC) #4

zra

https://codereview.chromium.org/2983823002/diff/20001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/2983823002/diff/20001/runtime/vm/object.cc#newcode21655 runtime/vm/object.cc:21655: if (receiverHash.IsInteger()) { I think if this isn't an ...

3 years, 5 months ago (2017-07-19 20:10:58 UTC) #6

alexmarkov

Description was changed from ========== Improve hashCode for implicit instance closures This performance improvement is ...

3 years, 5 months ago (2017-07-19 20:15:19 UTC) #7

Description was changed from

==========
Improve hashCode for implicit instance closures

This performance improvement is inspired by Flutter listeners stored in
the HashSet (see ObserverList) and frequently checked using
HashSet.contains(). If there are many such listeners and they are
implicit instance closures (for example, created by
'new Listenable.merge(...)'), HashSet.contains() becomes very slow.
It spends a lot of time in Closure_equals native method due to hash
collisions between implicit instance closure objects with same function
but different receivers.

This CL improves hashCode() calculation for implicit instance closures
by mixing function hashcode with identity hashcode of the receiver.
Also, hashcode is calculated once and cached in each closure instance.
The size of a closure instance doesn't grow up because there was unused
word-size padding both on 32-bit and 64-bit architectures.

The execution time of the following micro-benchmark is reduced from
47665ms to 135ms on my Linux/x64 box.

-------------------------------------

import "dart:collection";

class Foo {
  int _a;
  Foo(this._a);
  void bar() {}
}

main() {
  HashSet hs = new HashSet();
  for (int i = 0; i < 1000; ++i) {
    hs.add(new Foo(i).bar);
  }

  var watch = new Stopwatch()..start();

  for (int i = 0; i < 1000; ++i) {
    for (var c in hs) {
      hs.contains(c);
    }
  }

  int time = watch.elapsedMilliseconds;
  print("Time: ${time}ms\n");
}

-------------------------------------
==========

to

==========
Improve hashCode for closure objects

This performance improvement is inspired by Flutter listeners stored in
the HashSet (see ObserverList) and frequently checked using
HashSet.contains(). If there are many such listeners and they are
implicit instance closures (for example, created by
'new Listenable.merge(...)'), HashSet.contains() becomes very slow.
It spends a lot of time in Closure_equals native method due to hash
collisions between closure objects with same function
but different receivers.

This CL improves hashCode() calculation for implicit instance closures
by mixing function hashcode with identity hashcode of the receiver.
For explicit closures and static implicit closures hashCode() is improved by
using identityHashCode() of a closure object.

Also, hashcode is calculated once and cached in each closure instance.
The size of a closure instance doesn't grow up because there was unused
word-size padding both on 32-bit and 64-bit architectures.

The execution time of the following micro-benchmark is reduced from
47665ms to 135ms on my Linux/x64 box.

-------------------------------------

import "dart:collection";

class Foo {
  int _a;
  Foo(this._a);
  void bar() {}
}

main() {
  HashSet hs = new HashSet();
  for (int i = 0; i < 1000; ++i) {
    hs.add(new Foo(i).bar);
  }

  var watch = new Stopwatch()..start();

  for (int i = 0; i < 1000; ++i) {
    for (var c in hs) {
      hs.contains(c);
    }
  }

  int time = watch.elapsedMilliseconds;
  print("Time: ${time}ms\n");
}

-------------------------------------
==========

alexmarkov

Description was changed from ========== Improve hashCode for closure objects This performance improvement is inspired ...

3 years, 5 months ago (2017-07-19 20:17:33 UTC) #8

Description was changed from

==========
Improve hashCode for closure objects

This performance improvement is inspired by Flutter listeners stored in
the HashSet (see ObserverList) and frequently checked using
HashSet.contains(). If there are many such listeners and they are
implicit instance closures (for example, created by
'new Listenable.merge(...)'), HashSet.contains() becomes very slow.
It spends a lot of time in Closure_equals native method due to hash
collisions between closure objects with same function
but different receivers.

This CL improves hashCode() calculation for implicit instance closures
by mixing function hashcode with identity hashcode of the receiver.
For explicit closures and static implicit closures hashCode() is improved by
using identityHashCode() of a closure object.

Also, hashcode is calculated once and cached in each closure instance.
The size of a closure instance doesn't grow up because there was unused
word-size padding both on 32-bit and 64-bit architectures.

The execution time of the following micro-benchmark is reduced from
47665ms to 135ms on my Linux/x64 box.

-------------------------------------

import "dart:collection";

class Foo {
  int _a;
  Foo(this._a);
  void bar() {}
}

main() {
  HashSet hs = new HashSet();
  for (int i = 0; i < 1000; ++i) {
    hs.add(new Foo(i).bar);
  }

  var watch = new Stopwatch()..start();

  for (int i = 0; i < 1000; ++i) {
    for (var c in hs) {
      hs.contains(c);
    }
  }

  int time = watch.elapsedMilliseconds;
  print("Time: ${time}ms\n");
}

-------------------------------------
==========

to

==========
Improve hashCode for closure objects

This performance improvement is inspired by Flutter listeners stored in
the HashSet (see ObserverList) and frequently checked using
HashSet.contains(). If there are many such listeners and they are
implicit instance closures (for example, created by
'new Listenable.merge(...)'), HashSet.contains() becomes very slow.
It spends a lot of time in Closure_equals native method due to hash
collisions between closure objects with same function
but different receivers.

This CL improves hashCode() calculation for implicit instance closures
by mixing function hashcode with identity hashcode of the receiver.
For explicit closures and static implicit closures hashCode() is
improved by using identityHashCode() of a closure object.

Also, hashcode is calculated once and cached in each closure instance.
The size of a closure instance doesn't grow up because there was unused
word-size padding both on 32-bit and 64-bit architectures.

The execution time of the following micro-benchmark is reduced from
47665ms to 135ms on my Linux/x64 box.

-------------------------------------

import "dart:collection";

class Foo {
  int _a;
  Foo(this._a);
  void bar() {}
}

main() {
  HashSet hs = new HashSet();
  for (int i = 0; i < 1000; ++i) {
    hs.add(new Foo(i).bar);
  }

  var watch = new Stopwatch()..start();

  for (int i = 0; i < 1000; ++i) {
    for (var c in hs) {
      hs.contains(c);
    }
  }

  int time = watch.elapsedMilliseconds;
  print("Time: ${time}ms\n");
}

-------------------------------------
==========

alexmarkov

3 years, 5 months ago (2017-07-19 20:57:50 UTC) #9

alexmarkov

Description was changed from ========== Improve hashCode for closure objects This performance improvement is inspired ...

3 years, 5 months ago (2017-07-19 21:36:48 UTC) #11

Description was changed from

==========
Improve hashCode for closure objects

This performance improvement is inspired by Flutter listeners stored in
the HashSet (see ObserverList) and frequently checked using
HashSet.contains(). If there are many such listeners and they are
implicit instance closures (for example, created by
'new Listenable.merge(...)'), HashSet.contains() becomes very slow.
It spends a lot of time in Closure_equals native method due to hash
collisions between closure objects with same function
but different receivers.

This CL improves hashCode() calculation for implicit instance closures
by mixing function hashcode with identity hashcode of the receiver.
For explicit closures and static implicit closures hashCode() is
improved by using identityHashCode() of a closure object.

Also, hashcode is calculated once and cached in each closure instance.
The size of a closure instance doesn't grow up because there was unused
word-size padding both on 32-bit and 64-bit architectures.

The execution time of the following micro-benchmark is reduced from
47665ms to 135ms on my Linux/x64 box.

-------------------------------------

import "dart:collection";

class Foo {
  int _a;
  Foo(this._a);
  void bar() {}
}

main() {
  HashSet hs = new HashSet();
  for (int i = 0; i < 1000; ++i) {
    hs.add(new Foo(i).bar);
  }

  var watch = new Stopwatch()..start();

  for (int i = 0; i < 1000; ++i) {
    for (var c in hs) {
      hs.contains(c);
    }
  }

  int time = watch.elapsedMilliseconds;
  print("Time: ${time}ms\n");
}

-------------------------------------
==========

to

==========
Improve hashCode for closure objects

This performance improvement is inspired by Flutter listeners stored in
the HashSet (see ObserverList) and frequently checked using
HashSet.contains(). If there are many such listeners and they are
implicit instance closures (for example, created by
'new Listenable.merge(...)'), HashSet.contains() becomes very slow.
It spends a lot of time in Closure_equals native method due to hash
collisions between closure objects with same function
but different receivers.

This CL improves hashCode() calculation for implicit instance closures
by mixing function hashcode with identity hashcode of the receiver.
For explicit closures and static implicit closures hashCode() is
improved by using identityHashCode() of a closure object.

Also, hashcode is calculated once and cached in each closure instance.
The size of a closure instance doesn't grow up because there was unused
word-size padding both on 32-bit and 64-bit architectures.

The execution time of the following micro-benchmark is reduced from
47665ms to 135ms on my Linux/x64 box.

-------------------------------------

import "dart:collection";

class Foo {
  int _a;
  Foo(this._a);
  void bar() {}
}

main() {
  HashSet hs = new HashSet();
  for (int i = 0; i < 1000; ++i) {
    hs.add(new Foo(i).bar);
  }

  var watch = new Stopwatch()..start();

  for (int i = 0; i < 1000; ++i) {
    for (var c in hs) {
      hs.contains(c);
    }
  }

  int time = watch.elapsedMilliseconds;
  print("Time: ${time}ms\n");
}

-------------------------------------

R=rmacnak@google.com, zra@google.com

Committed:
https://github.com/dart-lang/sdk/commit/b1197eb7141762fe42d7c738fa3395f3dc8c2b9d
==========

alexmarkov

Committed patchset #4 (id:60001) manually as b1197eb7141762fe42d7c738fa3395f3dc8c2b9d (presubmit successful).

3 years, 5 months ago (2017-07-19 21:36:49 UTC) #12

siva

DBC https://codereview.chromium.org/2983823002/diff/60001/runtime/vm/object.cc File runtime/vm/object.cc (right): https://codereview.chromium.org/2983823002/diff/60001/runtime/vm/object.cc#newcode21645 runtime/vm/object.cc:21645: int64_t Closure::ComputeHash() const { Maybe declare zone here ...

3 years, 5 months ago (2017-07-19 21:59:47 UTC) #13

alexmarkov

3 years, 5 months ago (2017-07-20 21:47:18 UTC) #14

Message was sent while issue was closed.

https://codereview.chromium.org/2983823002/diff/60001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/2983823002/diff/60001/runtime/vm/object.cc#ne...
runtime/vm/object.cc:21645: int64_t Closure::ComputeHash() const {
On 2017/07/19 21:59:47, siva wrote:
> Maybe declare zone here
> 
> Zone* zone = Thread::Current()->zone();
> 
> and use it in the handle creation below.

Done (see the new review).

Expand Messages | Collapse Messages | Show Generated Messages | Hide Generated Messages