Truncating division operator (a ~/ b) is slower than (a / b).toInt()

[untp]

Run this code in dart vm.

import 'dart:math';

final random = Random();

void main() {
  equals((a, b) => (a / b).toInt(), (a, b) => a ~/ b);
  equals((a, b) => (a / b).truncate().toInt(), (a, b) => a ~/ b);
  measure('           (a / b).toInt()', (a, b) => (a / b).toInt());
  measure('(a / b).truncate().toInt()', (a, b) => (a / b).truncate().toInt());
  measure('                    a ~/ b', (a, b) => a ~/ b);
}

void measure(String name, int Function(double a, double b) function) {
  final watch = Stopwatch()..start();
  // warm-up
  for (var i = 0; i < 10000000; i++) {
    final a = random.nextDouble();
    final b = random.nextDouble();
    function(a, b);
  }
  watch.reset();
  // measure
  for (var i = 0; i < 10000000; i++) {
    final a = random.nextDouble();
    final b = random.nextDouble();
    function(a, b);
  }
  print('$name ${watch.elapsed}');
}

void equals(int Function(double a, double b) function0, int Function(double a, double b) function1) {
  for (var i = 0; i < 10000000; i++) {
    final a = random.nextDouble();
    final b = random.nextDouble();
    if (function0(a, b) != function1(a, b)) {
      throw Error();
    }
  }
}

It outputs these durations on my environment.

           (a / b).toInt() 0:00:00.497658
(a / b).truncate().toInt() 0:00:00.679565
                    a ~/ b 0:00:02.305170

I also compiled to exe with dart compile exe, and run:

           (a / b).toInt() 0:00:00.407087
(a / b).truncate().toInt() 0:00:00.618090
                    a ~/ b 0:00:02.135045

It is very slow.

Also analyzer says The operator x ~/ y is more efficient than (x / y).toInt(). but it is wrong. x ~/ y is actually more slower than (x / y).toInt().

Problem is the this line:

sdk/runtime/lib/double.cc

Line 111 in bf2691c

return DoubleToInteger(trunc(left / right),

It first calls trunc then DoubleToInteger. trunc returns a double with given a double. DoubleToInteger checks nan and finite, then casts double to int. Casting double to int, already truncates the value. So why slow trunc is used? It could be DoubleToInteger(left / right,. Relevant SO question

Dart SDK Version (dart --version)

Dart SDK version: 2.13.4 (stable) (Wed Jun 23 13:08:41 2021 +0200) on "windows_x64"

[vsmenon]

Labeling as an analyzer issue as perhaps we should just remove this performance hint. The ~/ in the sample above appears faster in dart2js but slower on the vm when I run locally.

Not sure what the source of that hint is - @mraleph @rakudrama ?

[mraleph]

Slowness here comes from the fact that Double.~/ is implemented as a runtime call, rather than in pure Dart or via instrinsics. trunc itself is not slow - it is just compiled to a single instruction on model Intel processors. (trunc is used because semantics requires it, see documentation https://api.dart.dev/dev/2.14.0-388.0.dev/dart-core/double/operator_truncate_divide.html).

We should just replace Double.~/ with a pure Dart implementation.

[vsmenon]

@mraleph - thanks! Shall we keep the analyzer hint and reassign this to the VM then?

[mraleph]

I think we should remove the hint, it is not going to be faster than (a/b).toInt() on the VM if we just implement it as (a/b).truncate().toInt() cause it has one more operation - so the hint does not make sense.

[untp]

I edited sample, added (a / b).truncate().toInt(). It is slightly slower than (a / b).toInt(). If ~/ will be implemented as pure dart, can we just implement as:

int operator ~/(num other) => (this / other).toInt();

It would be faster than (this / other).truncate().toInt().

For analysis, I think, this rule shouldn't be removed.
If ~/ implemented as (this / other).toInt(), it should triggered by (this / other).toInt().
If ~/ implemented as (this / other).truncate().toInt(), it should triggered by (this / other).truncate().toInt().
Also instead saying ~/ is more efficient than (x / y).toInt(), it should say ~/ is more shorter.

[rakudrama]

I propose the following action items:

• The VM makes this case faster via a pure Dart implementation, as suggested above. This should address the reported performance difference.

• The analyzer amends the hint to fire only when a and b have static type int.

An int-only hint was probably the original intention - when porting code from Java or C++ the user might expect / on int values to return an int but it returns a double which is then 'fixed' by adding .toInt() rather than using the corresponding operator ~/.

The two forms are not exact replacements on the VM due edge cases:

  print(((-9223372036854775808) / (-1)).toInt()); // 9223372036854775808.0 .toInt() -> 9223372036854775807 (clipped)
  print((-9223372036854775808) ~/ (-1)); // -9223372036854775808 (overflow into sign)

@untp .truncate().toInt() is redundant as .truncate() returns an int. It is essentially .truncateToDouble().toInt().

---

Tips on benchmarking:

When I run the dart2js code, the first one is always fastest, even when I swap the calls to measure.

The following version avoids some problems with the benchmark code

1. The warmup code is a separate loop. The second loop is part of the measured code, so it should be warmed up too.
2. The first benchmark is completed before the second one is warmed up. On dart2js + Chrome, the first benchmark is always 2x faster because the JavaScript VM inlines the function into the loop. When it sees a second function, it realizes its 'mistake' and recompiles the code without inlining the function.

To compensate for these effects, the benchmarks should be all warmed before any measurements are taken.
One quick trick to do this is to run all the benchmarks several times in a loop and use the last set of results.

import 'dart:math';

final random = Random();

void main() {
  equals((a, b) => (a / b).toInt(), (a, b) => a ~/ b);
  equals((a, b) => (a / b).truncate().toInt(), (a, b) => a ~/ b);
  for (int i = 0; i < 3; i++) {
    print('');
    measure('           (a / b).toInt()', (a, b) => (a / b).toInt());
    measure('(a / b).truncate().toInt()', (a, b) => (a / b).truncate().toInt());
    measure('                    a ~/ b', (a, b) => a ~/ b);
  }
}

void measure(String name, int Function(double a, double b) function) {
  final watch = Stopwatch()..start();
  for (var i = 0; i < 10000000; i++) {
    final a = random.nextDouble();
    final b = random.nextDouble();
    function(a, b);
  }
  print('$name ${watch.elapsed}');
}

void equals(int Function(double a, double b) function0, int Function(double a, double b) function1) {
  for (var i = 0; i < 10000000; i++) {
    final a = random.nextDouble();
    final b = random.nextDouble();
    if (function0(a, b) != function1(a, b)) {
      throw Error();
    }
  }
}

With dart2js I get:

           (a / b).toInt() 0:00:00.210000
(a / b).truncate().toInt() 0:00:00.359000
                    a ~/ b 0:00:00.426000

           (a / b).toInt() 0:00:00.340000
(a / b).truncate().toInt() 0:00:00.337000
                    a ~/ b 0:00:00.351000

           (a / b).toInt() 0:00:00.332000
(a / b).truncate().toInt() 0:00:00.361000
                    a ~/ b 0:00:00.332000

You can see that the results settle down to being very similar.

[untp]

@rakudrama Thanks for comment. I didn't know there would be an edge case. I created another benchmark code for all possibilities with your benchmark tips. It also measures a no-op function, subtracts that from all durations.

import 'dart:math';

final random = Random();

const functionNames = [
  'a / b',
  '(a / b).toInt()',
  '(a / b).truncate()',
  '(a / b).truncate().toInt()',
  '(a / b).truncateToDouble().toInt()',
  'a ~/ b',
];

final functions = <num Function(num, num)>[
  (a, b) => a / b,
  (a, b) => (a / b).toInt(),
  (a, b) => (a / b).truncate(),
  (a, b) => (a / b).truncate().toInt(),
  (a, b) => (a / b).truncateToDouble().toInt(),
  (a, b) => a ~/ b,
];

void main() {
  final maximumNameLength =
      functionNames.map((e) => e.length).reduce((a, b) => a > b ? a : b);

  for (var _ = 0; _ < 3; _++) {
    final c = measure((a, b) => 0);
    for (var i = 0; i < functions.length; i++) {
      print('${functionNames[i].padLeft(maximumNameLength)} '
          '${measure(functions[i]) - c}');
    }
    print('');
  }

  print('Edge case');
  final a = -9223372036854775808;
  final b = -1;
  for (var i = 0; i < functions.length; i++) {
    print('${functionNames[i].padLeft(maximumNameLength)} '
        '${functions[i](a, b)}');
  }
}

Duration measure(num Function(num, num) function) {
  final watch = Stopwatch()..start();
  for (var i = 0; i < 10000000; i++) {
    final a = random.nextDouble();
    final b = random.nextDouble();
    function(a, b);
  }
  return watch.elapsed;
}

vm output

                             a / b 0:00:00.034661
                   (a / b).toInt() 0:00:00.041837
                (a / b).truncate() 0:00:00.221561
        (a / b).truncate().toInt() 0:00:00.213379
(a / b).truncateToDouble().toInt() 0:00:00.218563
                            a ~/ b 0:00:01.911966

                             a / b 0:00:00.047506
                   (a / b).toInt() 0:00:00.042563
                (a / b).truncate() 0:00:00.232746
        (a / b).truncate().toInt() 0:00:00.229212
(a / b).truncateToDouble().toInt() 0:00:00.226901
                            a ~/ b 0:00:01.915268

                             a / b 0:00:00.042161
                   (a / b).toInt() 0:00:00.037700
                (a / b).truncate() 0:00:00.232059
        (a / b).truncate().toInt() 0:00:00.240242
(a / b).truncateToDouble().toInt() 0:00:00.223749
                            a ~/ b 0:00:01.905076

Edge case
                             a / b 9223372036854776000.0
                   (a / b).toInt() 9223372036854775807
                (a / b).truncate() 9223372036854775807
        (a / b).truncate().toInt() 9223372036854775807
(a / b).truncateToDouble().toInt() 9223372036854775807
                            a ~/ b -9223372036854775808

In dart2js, functions duration's are similar.

I don't understand why truncate is ~6 times slower than toInt.

For your proposed items:

• The VM makes this case faster via a pure Dart implementation, as suggested above. This should address the reported performance difference.

Yes, this would be better. But which implementation should we use? (a / b).toInt() or (a / b).truncate()? I would choose toInt which is faster. Also isn't this would be breaking change for a = -9223372036854775808 b = -1 as you stated?

• The analyzer amends the hint to fire only when a and b have static type int.

I am against this, because a ~/ b should be preferred over (a / b).toInt() for int or double. It is short and simple. Also it aligns well with other lints that prefers simple (prefer_is_empty, use_is_even_rather_than_modulo, prefer_iterable_whereType, prefer_inlined_adds...).

[srawlins]

Since the timings are very close now, I don't think this has a lot of benefit as a performance-centered item. Now I think it is a stylistic report, and should be moved to linter.

CC @pq