sdk icon indicating copy to clipboard operation
sdk copied to clipboard

[vm/core] `_GrowableList.add` has unnecessary bounds check

Open rakudrama opened this issue 1 year ago • 0 comments

The []= call in _GrowableList.add here generates an index bounds check:

  @pragma("vm:entry-point", "call")
  @pragma("vm:prefer-inline")
  void add(T value) {
    var len = length;
    if (len == _capacity) {
      _growToNextCapacity();
    }
    _setLength(len + 1);
    this[len] = value;          // HERE
  }

I can estimate the static number of range checks in the dart2js compiler as follows:

$ dart compile aot-snapshot pkg/compiler/lib/src/dart2js.dart --output=z1
$ objdump -d --visualize-jumps --no-addresses --no-show-raw-insn z1 > z1.x
$ cat z1.x | grep 'call.*_stub_RangeError' | wc -l
10838

If I change the pragma on _GrowableList.add to @pragma('vm:never-inline') the result drops to

8607

So 2231 of 10838, or 20% of the static range checks are due to inlining _GrowableList.add.

The calls account for ~0.1% of the lines in the disassembly, but since each stub call is likely paired with a compare and branch, total size saving might be closer to 0.25%

I see two ways of fixing this

  1. Improve range analysis so that the check can be optimized away using the length from the previous line. Why it is not working I can't guess, but len >= 0 is true and len + 1 can't overflow, both because len is an array length.
  2. Add a variant of []= / _setIndexed that unsafely omits the range check.

rakudrama avatar Jun 27 '24 21:06 rakudrama