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

Hash code computation for tear-offs is very inefficient #31875

Open
mraleph opened this Issue Jan 12, 2018 · 3 comments

Comments

Projects
None yet
3 participants
@mraleph
Contributor

mraleph commented Jan 12, 2018

This code:

class Foo {
  int tearOff() => 10;
}

void main() {
  final s = new Set();
  final foo = new Foo();
  for (var i = 0; i < 1000000; i++) s.add(foo.tearOff);
}

is roughly 2x slower than this code:

class Foo {
  int tearOff() => 10;
}

void main() {
  final s = new Set();
  final foo = new Foo();
  for (var i = 0; i < 1000000; i++) s.add(() => foo.tearOff());
}

This might be rather suprising for Dart developers. The reason for the slowness is the fact that Closure hash-code for tear-offs is a combination of identity hashcode for the receiver and function itself and neither of those is computed efficiently (see Closure::ComputeHash code)

  • To compute receiver hash we call back into Dart code via DartLibraryCalls::IdentityHashCode, even though on 64-bit platforms there is fast path for accessing identity hash code from object header itself.
  • To compute function hash we call Function::ComputeClosureHash which does this:
intptr_t Function::ComputeClosureHash() const {
  ASSERT(IsClosureFunction());
  const Class& cls = Class::Handle(Owner());
  intptr_t result = String::Handle(name()).Hash();
  result += String::Handle(Signature()).Hash();  // (!!!)
  result += String::Handle(cls.Name()).Hash();
  return result;
}

The line marked with (!!!) is extremely expensive - it formats function signature as a string - and it does no caching - so formatting of signature is done every time you invoke f.hashCode on a new tear-off.

It seems that Function::ComputeClosureHash can benefit from some memoization and Instance::IdentityHashCode() can benefit from fast-pathing on 64-bit platforms.

@mraleph

This comment has been minimized.

Show comment
Hide comment
@mraleph

mraleph Jan 12, 2018

Contributor

Tentatively assigning to @ErikCorryGoogle because of the work previously done on hash codes.

Contributor

mraleph commented Jan 12, 2018

Tentatively assigning to @ErikCorryGoogle because of the work previously done on hash codes.

@lrhn

This comment has been minimized.

Show comment
Hide comment
@lrhn

lrhn Jan 14, 2018

Member

Drive-by comment: Your two examples look quite different since I'd expect the size of the sets to be one vs 1000000.
A closure like () => foo.tearOff() can/should create instances that are not equal to any other function instance. A tear-off creates a new instance that's equal to other tear-offs of the same method from the same object.

(I'm guessing you might be optimizing and recognizing that foo doesn't differ even if the scope of the function expression changes between evaluations, and you've done loop-invariant code movement on it. In either case, I'd thing a more comparable example would be:

class Foo {
  int tearOff() => 10;
}

void main() {
  final s = new Set();
  final foo = new Foo();
  tearOff() => foo.tearOff();
  for (var i = 0; i < 1000000; i++) s.add(tearOff);
}

... just to be certain).

Member

lrhn commented Jan 14, 2018

Drive-by comment: Your two examples look quite different since I'd expect the size of the sets to be one vs 1000000.
A closure like () => foo.tearOff() can/should create instances that are not equal to any other function instance. A tear-off creates a new instance that's equal to other tear-offs of the same method from the same object.

(I'm guessing you might be optimizing and recognizing that foo doesn't differ even if the scope of the function expression changes between evaluations, and you've done loop-invariant code movement on it. In either case, I'd thing a more comparable example would be:

class Foo {
  int tearOff() => 10;
}

void main() {
  final s = new Set();
  final foo = new Foo();
  tearOff() => foo.tearOff();
  for (var i = 0; i < 1000000; i++) s.add(tearOff);
}

... just to be certain).

@mraleph

This comment has been minimized.

Show comment
Hide comment
@mraleph

mraleph Jan 14, 2018

Contributor

@lrhn good catch. it's much slower than 2x then.

Contributor

mraleph commented Jan 14, 2018

@lrhn good catch. it's much slower than 2x then.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment