Abysmal performance for hash algorithms in dart:crypto

[DartBot]

This issue was originally filed by [email protected]

---

Test code:
new File('recordroyale.ogg').readAsBytes().then((buf) {
  var md5 = new MD5();
  md5.update(buf);
  print(md5.digest());
});

where 'recordroyale.ogg' is about six megabytes. This takes 22 seconds on my machine. Shelling out to md5sum(1) takes under 0.02 seconds. I understand that Dart won't ever be as fast as C, but with this disparity, the hash algorithms should be implemented in C[++] rather than Dart.

I had a vague suspicion that this was slow due to unnecessary allocations, but the allocations are mostly small and consumed quickly. Refactoring to eliminate unnecessary allocations resulted in no change.

My use case involved checksumming a byte array that existed only in memory at the relevant location; it is far less convenient to write data to a temporary file, shell out to md5sum(1), then delete that file.

[larsbak]

As a starting point we should add a benchmark to trace performance of MD5:

#import("dart:io");
#import("dart:crypto");

main() {
  new File('data').readAsBytes().then((buf) {
    var md5 = new MD5();
    md5.update(buf);
    print(md5.digest());
  });
}

---

Set owner to @madsager.
Added Area-Library label.

[madsager]

There is a lot that can be done to improve performance here. The data is being copied around way too much. Also, the code overflows smi range and (at least it used to be the case that) a lot of the medium-size integer operations ended up in runtime calls.

---

cc @iposva-google.
cc @sgmitrovic.

[madsager]

Added Triaged label.

[iposva-google]

Mads, let's work together at creating a repeatable test case. I don't think file reading is really needed here.

[lrhn]

Removed Area-Library label.
Added Area-Pkg, Library-Crypto labels.

[iposva-google]

I wrote a little test just now and it looks like we can close this bug. Abysmal is certainly not what we see anymore:

import "dart:io";
import "package:crypto/crypto.dart";

readFileFully(var path) {
  return new File(path).readAsBytesSync();
}

main() {
  var binary = new Options().executable;
  print("Using $binary");
  for (int i = 0; i < 3; i++) {
    var stopwatch = new Stopwatch()..start();
    var bytes = readFileFully(binary);
    stopwatch.stop();
    print("Read ${bytes.length} bytes in ${stopwatch.elapsedMilliseconds} ms.");

    // Now compute the MD5 hash on the read bytes.
    stopwatch = new Stopwatch()..start();
    var md5 = new MD5();
    md5.add(bytes);
    var hash = md5.close();
    stopwatch.stop();
    print("Hashed ${bytes.length} bytes into ${hash.length} bytes in "
          "${stopwatch.elapsedMilliseconds} ms.");
    var sb = new StringBuffer();
    for (int j = 0; j < hash.length; j++) {
      var val = hash[j].toRadixString(16);
      sb.write(val.length == 1 ? "0$val" : val);
    }
    print("Hash: $sb");
  }
}

Gives this set of results on my MacBook:

dalbe[runtime] ./xcodebuild/ReleaseX64/dart --package-root=./xcodebuild/ReleaseIA32/packages/ ~/dart/Bug4611.dart
Using ./xcodebuild/ReleaseX64/dart
Read 9875196 bytes in 66 ms.
Hashed 9875196 bytes into 16 bytes in 810 ms.
Hash: e5f175b851495b54b393327ac934583a
Read 9875196 bytes in 18 ms.
Hashed 9875196 bytes into 16 bytes in 802 ms.
Hash: e5f175b851495b54b393327ac934583a
Read 9875196 bytes in 33 ms.
Hashed 9875196 bytes into 16 bytes in 816 ms.
Hash: e5f175b851495b54b393327ac934583a

dalbe[runtime] time md5 ./xcodebuild/ReleaseX64/dart
MD5 (./xcodebuild/ReleaseX64/dart) = e5f175b851495b54b393327ac934583a
0.026u 0.007s 0:00.02 100.0% 0+0k 0+1io 0pf+0w

This means we calculate the MD5 hash for a 9.41MB file in 810ms, which is significantly better than the reported 6MB in 22 seconds.

---

Added AssumedStale label.

[kevmoo]

Removed Library-Crypto label.
Added Pkg-Crypto label.

[DartBot]

This issue has been moved to dart-lang/core#180.