Implement String.hashCode.

Implement String.hashCode.

Committed: https://code.google.com/p/dart/source/detail?r=4714

[ahe, 2012-02-28 09:33:10]

Micro benchmark used:

main() {
  Expect.equals(0,
foo('fiskfiskfiskfiskfiskfiskfiskfiskfiskfiskfiskfiskfiskfiskfiskfisk'));
}

foo(x) {
  int j = 0;
  for (int i = 0; i < 1000; i++) {
    var sw = new Stopwatch.start();
    j ^= bar(x);
    sw.stop();
    print(sw.elapsedInMs());
  }
  return j;
}

bar(x) {
  int j = 0;
  for (int i = 0; i < 1000000; i++) {
    j ^= x.hashCode();
  }
  return j;
}

To see the raw performance, modify builtin$hashCode$0 in js_helper.dart to:

builtin$hashCode$0(receiver) => stringHashCodeUnchecked(receiver);

[kasperl, 2012-02-28 09:37:08]

LGTM.

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
dart/frog/leg/lib/js_helper.dart:1202: var hash = 0;
int hash?

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
dart/frog/leg/lib/js_helper.dart:1204: for (var i = 0; i < length; i++) {
int i?

[ahe, 2012-02-28 10:09:35]

Hi Kasper,

Thank you for taking a look. I have uploaded a new version that is 36% faster
than Frog by avoiding bailout code in builtin$hashCode$0 for the number case.

I think we need to think about if we can limit type guards to the first basic
block that requires it instead of always pushing them to the beginning of a
method.

Cheers,
Peter

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
dart/frog/leg/lib/js_helper.dart:1202: var hash = 0;
On 2012/02/28 09:37:08, kasperl wrote:
> int hash?

Done.

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
dart/frog/leg/lib/js_helper.dart:1204: for (var i = 0; i < length; i++) {
On 2012/02/28 09:37:08, kasperl wrote:
> int i?

Done.

[ngeoffray, 2012-02-28 10:13:24]

LGTM

Why are the tests not failing anymore?

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
dart/frog/leg/lib/js_helper.dart:1206: hash ^= JS("int", @"$0 << $1", hash, 10);
Cobnsistency -> use ' instead of "

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
dart/frog/leg/lib/js_helper.dart:1209: hash ^= JS("int", @"$0 << $1", hash, 3);
ditto

https://chromiumcodereview.appspot.com/9490003/diff/3001/dart/frog/leg/lib/js...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/3001/dart/frog/leg/lib/js...
dart/frog/leg/lib/js_helper.dart:1192: if (receiver is num) return JS('int',
@'$0 & 0x1FFFFFFF', receiver);
Please add a TODO to make sure we change the code to the original once our
optimizations are smarter.

[ahe, 2012-02-28 11:58:15]

I don't know what I was thinking. There is something with + and XOR both being
useful for shuffling bits, but they are not equivalent. So I think I have to
scrap my 40% improvement.

[ahe, 2012-02-28 13:51:38]

Uploaded new version without XOR.

[ngeoffray, 2012-02-28 13:57:12]

Still LGTM

[kasperl, 2012-02-28 13:58:42]

LGTM.

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
dart/frog/leg/lib/js_helper.dart:1184: * This is the [Jenkins hash function][1],
but always using XOR
Update comment to match reality.

[Lasse Reichstein Nielsen, 2012-02-28 14:12:16]

DBC.

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
dart/frog/leg/lib/js_helper.dart:1191: if (receiver is num) return JS('int',
@'$0 & 0x1FFFFFFF', receiver);
That's a somewhat bad hash for doubles (specifically fractions are all the
same).

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
dart/frog/leg/lib/js_helper.dart:1192: if (receiver is !String) return
UNINTERCEPTED(receiver.hashCode());
What about arrays and booleans?

[floitsch, 2012-02-28 14:13:36]

On 2012/02/28 14:12:16, Lasse Reichstein Nielsen wrote:
> DBC.
> 
>
https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
> File dart/frog/leg/lib/js_helper.dart (right):
> 
>
https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
> dart/frog/leg/lib/js_helper.dart:1191: if (receiver is num) return JS('int',
> @'$0 & 0x1FFFFFFF', receiver);
> That's a somewhat bad hash for doubles (specifically fractions are all the
> same).
> 
>
https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
> dart/frog/leg/lib/js_helper.dart:1192: if (receiver is !String) return
> UNINTERCEPTED(receiver.hashCode());
> What about arrays and booleans?

booleans currently don't implement the hashable interface...
I imagine that's the same for arrays.

[ahe, 2012-02-28 17:26:10]

Team,

Thank you so much for all your comments and suggestions.

@lrn: do you have a better suggestion for double?

Cheers,
Peter

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
dart/frog/leg/lib/js_helper.dart:1206: hash ^= JS("int", @"$0 << $1", hash, 10);
On 2012/02/28 10:13:25, ngeoffray wrote:
> Cobnsistency -> use ' instead of "

Done.

https://chromiumcodereview.appspot.com/9490003/diff/1/dart/frog/leg/lib/js_he...
dart/frog/leg/lib/js_helper.dart:1209: hash ^= JS("int", @"$0 << $1", hash, 3);
On 2012/02/28 10:13:25, ngeoffray wrote:
> ditto

Done.

https://chromiumcodereview.appspot.com/9490003/diff/3001/dart/frog/leg/lib/js...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/3001/dart/frog/leg/lib/js...
dart/frog/leg/lib/js_helper.dart:1192: if (receiver is num) return JS('int',
@'$0 & 0x1FFFFFFF', receiver);
On 2012/02/28 10:13:25, ngeoffray wrote:
> Please add a TODO to make sure we change the code to the original once our
> optimizations are smarter.

Done.

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
File dart/frog/leg/lib/js_helper.dart (right):

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
dart/frog/leg/lib/js_helper.dart:1184: * This is the [Jenkins hash function][1],
but always using XOR
On 2012/02/28 13:58:42, kasperl wrote:
> Update comment to match reality.

Done.

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
dart/frog/leg/lib/js_helper.dart:1191: if (receiver is num) return JS('int',
@'$0 & 0x1FFFFFFF', receiver);
On 2012/02/28 14:12:16, Lasse Reichstein Nielsen wrote:
> That's a somewhat bad hash for doubles (specifically fractions are all the
> same).

What do you suggest I use instead?

https://chromiumcodereview.appspot.com/9490003/diff/1005/dart/frog/leg/lib/js...
dart/frog/leg/lib/js_helper.dart:1192: if (receiver is !String) return
UNINTERCEPTED(receiver.hashCode());
On 2012/02/28 14:12:16, Lasse Reichstein Nielsen wrote:
> What about arrays and booleans?

I checked, neither List nor bool are hashable.