package:crypto Hmac code is around 5-7x slower in AOT

[mraleph]

I looked at the code and I think there are two main reasons for this:

• Small helpers are not inlined (e.g. _rotr32(int n, int x) => (x >> n) | ((x << (32 - n)) & mask32); is not inlined) - our AOT compiler is much less eager to inline static methods (basically almost never inlines them for the code size reasons).
• The code produced for the integer operations is pretty bad even on x64, e.g _rotr32 produces this graph:

  2: B1[target]:0 ParallelMove rbx <- S+2, rdx <- C
  4:     CheckStackOverflow:8()
  6:     CheckNull:12(v4)
  8:     ParallelMove rsi <- S+3
  8:     v25 <- UnboxInt64(v3) [-9223372036854775808, 9223372036854775807] T{_int64}
 10:     ParallelMove rdi <- rbx
 10:     v27 <- UnboxInt64(v4 T{int}) [-9223372036854775808, 9223372036854775807] T{_int64}
 11:     ParallelMove rcx <- rsi
 12:     ParallelMove rdi <- rdi
 12:     v5 <- ShiftInt64Op(>> [tr], v27, v25) [-9223372036854775808, 9223372036854775807] T{_int64}
 14:     v43 <- UnboxedConstant(#32) [32, 32] T{_Smi}
 16:     ParallelMove r8 <- C
 16:     v8 <- BinaryInt64Op(- [tr], v43, v25) [-9223372036854775808, 9223372036854775807] T{_int64}
 18:     ParallelMove rbx <- rbx
 18:     v31 <- UnboxInt64(v4 T{int}) [-9223372036854775808, 9223372036854775807] T{_int64}
 19:     ParallelMove rcx <- r8
 20:     ParallelMove rbx <- rbx
 20:     v10 <- ShiftInt64Op(<< [tr], v31, v8) [-9223372036854775808, 9223372036854775807] T{_int64}
 22:     v37 <- BoxInt64(v10) [-9223372036854775808, 9223372036854775807] T{_int64}
 24:     ParallelMove rcx <- rcx
 24:     v13 <- CheckedSmiOp:22(&, v37 T{_int64}, v12) T{int?}
 26:     CheckNull:26(v13)
 28:     ParallelMove rcx <- rcx
 28:     v39 <- UnboxInt64(v13 T{int}) [-9223372036854775808, 9223372036854775807] T{_int64}
 30:     ParallelMove rdi <- rdi
 30:     v15 <- BinaryInt64Op(| [tr], v5, v39) [-9223372036854775808, 9223372036854775807] T{_int64}
 32:     v41 <- BoxInt64(v15) [-9223372036854775808, 9223372036854775807] T{_int64}
 33:     ParallelMove rax <- rax
 34:     Return:30(v41 T{_int64})

The code below provided by @MariaMelnik

import 'package:crypto/crypto.dart';

int convert(){
  List<int> U_i = [121, -8, 43, -70, 22, -31, -22, -60, -32, 44, 74, -81, 22, -19, 25, 47, -40, 88, 22, -64, -64, -41, 45, 73, -46, 19, 13, 87, -53, 57, -75, -116, 0, 0, 0, 1];
  int c = 10000;
  List<int> password = [66, 97, 115, 115, 103, 64, 49, 57, 49, 57];
  Hmac hmac = Hmac(sha256, password);

  int l = 32;
  for (int i = 1; i <= l; i++) {
    for (int i = 0; i < c; i++) {
      U_i = hmac.convert(U_i).bytes;
    }
  }

  return U_i[0];
}

void main() {
  final sw = new Stopwatch()..start();
  convert();
  print('--> ${sw.elapsedMilliseconds}');
}

╭─vegorov@volhv ~/src/dart/sdk ‹fix-34462›
╰─$ out/ReleaseX64/dart --packages=.packages /tmp/aot.dart                                                              254 ↵
--> 2739
╭─vegorov@volhv ~/src/dart/sdk ‹fix-34462›
╰─$ pkg/vm/tool/precompiler2 --packages=.packages /tmp/aot.dart /tmp/aot.snapshot
╭─vegorov@volhv ~/src/dart/sdk ‹fix-34462›
╰─$ pkg/vm/tool/dart_precompiled_runtime2 /tmp/aot.snapshot
--> 19654

Similar number when running on my Nexus 5X:

╭─vegorov@volhv ~/src/flutter/flutter/examples/hello_world ‹master*›                                                    [1/23]
╰─$ flutter run --release
...
I/flutter (28577): --> 39948
╭─vegorov@volhv ~/src/flutter/flutter/examples/hello_world ‹master*›
╰─$ flutter run --debug
Launching lib/main.dart on Nexus 5X in debug mode...
...
I/flutter (28869): --> 8202

/cc @aartbik might be a good example for the "better integer math" project.

[aartbik]

Runtimes on my desktop

JIT: --> 2323
AOT: --> 13938

The profiles below strongly support mraleph's observations above.
This will be fun to work on!

JIT hot method profile:

  27.55%  dart     jitted-129012-9366.so  [.] *_Sha256Sink@24160809_updateHash                                                
   3.39%  dart     jitted-129012-35.so    [.] _stub_OneArgCheckInlineCache                                                    
   3.21%  dart     jitted-129012-9374.so  [.] *HashSink__iterate@28385876  

AOT hot method profile:

  23.29%  dart_precompile  libb.so                   [.] Precompiled__Sha256Sink_21160809__rotr32_21160809_3885               
  16.40%  dart_precompile  libb.so                   [.] Precompiled____add32_3889                                            
  15.50%  dart_precompile  libb.so                   [.] Precompiled__Sha256Sink_21160809_updateHash_3882                    
   4.25%  dart_precompile  libb.so                   [.] Precompiled__Sha256Sink_21160809__bsig0_21160809_3884               
   3.69%  dart_precompile  libb.so                   [.] Precompiled__Sha256Sink_21160809__bsig1_21160809_3887               
   2.57%  dart_precompile  dart_precompiled_runtime  [.] dart::BootstrapNatives::DN_TypedData_GetUint32                      
   2.57%  dart_precompile  libb.so                   [.] Precompiled__Sha256Sink_21160809__ch_21160809_3886                 
   2.45%  dart_precompile  libb.so                   [.] Precompiled__Sha256Sink_21160809__ssig1_21160809_3890               
   2.14%  dart_precompile  libb.so                   [.] Precompiled__Sha256Sink_21160809__maj_21160809_3883  

[aartbik]

I wrote some internal microbenchmarks (we already have a few related, but none with Hmac).

JIT
HmacBenchMD5(RunTime): 454.3218873495344 us.
HmacBenchSHA1(RunTime): 508.16337372967484 us.
HmacBenchSHA256(RunTime): 790.9870865954922 us.
AOT
HmacBenchMD5(RunTime): 1759.7643403693933 us.
HmacBenchSHA1(RunTime): 2421.769700968523 us.
HmacBenchSHA256(RunTime): 4732.826756501182 us.

[aartbik]

With some quick and dirty prototype around inlining and speculation, the performance of AOT improves as follows. Still not JIT, but in some cases already about 2x better than where it was....

JIT --> 2364
AOT --> 7988

JIT
HmacBenchMD5(RunTime): 449.65652045863317 us.
HmacBenchSHA1(RunTime): 490.29337279411754 us.
HmacBenchSHA256(RunTime): 772.3630050193051 us.

AOT
HmacBenchMD5(RunTime): 1117.0341328866555 us.
HmacBenchSHA1(RunTime): 1448.5659869659667 us.
HmacBenchSHA256(RunTime): 2050.995091188525 us.

[aartbik]

Bit more prototyping brings this down more, over 3x. Of course we will need to balance the heuristics on what work wells overall.

AOT --> 3921

AOT
HmacBenchMD5(RunTime): 1176.1603691945913 us.
HmacBenchSHA1(RunTime): 921.3746089359743 us.
HmacBenchSHA256(RunTime): 1617.9368827809215 us.

[aartbik]

A loop-based heuristic gives an immediate 2.5x speedup, without resorting to the code size hungry "inline always" heuristic (although we still need to double check that code size increase is acceptable).

JIT --> 2119
AOT --> 5447

Some preliminary experiments on our internal benchmark also look extremely promising!

[aartbik]

#34969

[a-siva]

@aartbik you have made significant improvements to the Hmac code, are we still considerably slower? Can the issue be closed?

[aartbik]

@a-siva let's keep this open; there is still much more we can do (better inlining without codesize increase for one, but even after that better instruction selection); this bug is a nice way to track progress in that area.

[aartbik]

This is the current status, with some plans on how to go forward:

JIT
--> 2089
AOT
--> 6437

[aartbik]

Pending CL yields the following results (more than an other 1.8x), which only 3.4% codesize increase on e.g. FlutterGallery. Many other benchmarks speedup substantially as well.

JIT
--> 2062
AOT
--> 3433

[aartbik]

Closing this issue since the huge gap has been bridged (fine tuning the arithmetic operations is expected to continue of course).