Bitwise operations slow in VM

[DartBot]

This issue was originally filed by lry@google.com

---

Bitwise operations run slow, discovered with an implementation of the Jenkins hash function (http://en.wikipedia.org/wiki/Jenkins_hash_function).

To avoid big numbers we applied bit masks, for example

  const int _mask31 = 0x7fffffff;
  hash = (hash + ((hash & 0x1fffff) << 10)) & _mask31;

Attached a dart version, which takes 300 ms for hashing a string of length 8'000'000. The JVM version (scala file attached) runs in 23ms.

---

Attachments:
bench.scala (864 Bytes)
bitBench.dart (862 Bytes)

[iposva-google]

Set owner to @iposva-google.
Removed Performance label.
Added Accepted label.

[iposva-google]

The operations in the loop ...

  for (int i = 0; i < s.length; i++) {
    hash = (hash + s.codeUnitAt(i)) & _mask31;
    hash = (hash + ((hash & 0x1fffff) << 10)) & _mask31;
    hash = hash ^ (hash >> 6);
  }

... do keep overflowing the Smi range when executed on 32-bit architectures causing significant allocation of Mint objects. This can be verified by running the same program on a 64-bit build and observing a 8.5x speed improvement on the same hardware.

For example: _mask31 should be 0x3fffffff to stay in signed 31-bit range.

We'll keep this open to investigate why we are allocating so many Mint objects during the loop.

---

Set owner to @sgmitrovic.

[DartBot]

This comment was originally written by lry@google.com

---

Thank you for taking a look and sorry for the confusion.

[DartBot]

This comment was originally written by lry@google.com

---

a version that doesn't overflow runs in 50ms, as noted by ivan:

const int _mask29 = 0x1fffffff;

int substringHash29(String s) {
  int hash = 0;
  for (int i = 0; i < s.length; i++) {
    hash = (hash + s.codeUnitAt(i)) & _mask29;
    hash = (hash + ((hash & 0x7ffff) << 10)) & _mask29;
    hash = hash ^ (hash >> 6);
  }
  hash = (hash + ((hash & 0x3ffffff) << 3)) & _mask29;
  hash = hash ^ (hash >> 11);
  hash = (hash + ((hash & 0x3fff) << 15)) & _mask29;
  return hash;
}

[iposva-google]

The only thing that came out of the investigation in comment #­2 I believe was issue #5.

---

Added Duplicate label.
Marked as being merged into #13875.

[rakudrama]

FYI the DOM libraries use a version of the code in #­4 under the name JenkinsSmiHash.
Even if the VM held the loop variables in a register representation, the DOM libraries would continue to use the masking-to-29bits code because the same issue occurs when the code is compiled to JavaScript. Not all JavaScript implementations enregister 'hash' for the loop either.

[iposva-google]

I am not exactly sure what different JavaScript implementations have to do with a reported performance bug in the VM, but this issue was resolved as a misunderstanding of Smi values and an overly aggressive boxing/unboxing of Mint values.

[fsc8000]

cc @mraleph.

[mraleph]

Unmerging.

Building on top of my latest fix that enables range inference across non-smi phis, I added logic to infer ranges for xor operation plus logic to unbox int32 phis that appear after we narrow mint operations - this brings us down to 45ms on my machine for original bitBench.dart removing all boxing in the loop. I am underging from the 13875 because there are no true Mint phis in the code - there are only int32 ones which we support.

The code looks almost ok, but still has some redundancies that can be cleared away.

---

cc @fsc8000.
cc @sgmitrovic.
Set owner to @mraleph.
Added Started label.
Marked as being merged into #.