Typed data array operations are slow, read/write one byte at a time

[osa1]

Optimized code for `_Float64List.[]`

 (func $_Float64List.\5b\5d (type $type$63) (param $0 (ref $type$17)) (param $1 i64) (result (ref null $type$56))
  (local $2 (ref $type$4))
  (local $3 (ref $type$66))
  (local $4 (ref $type$65))
  (local $5 i32)
  (local.set $3
   (ref.cast $type$66
    (local.get $0)))
  (block $label$1
   (if
    (i64.ge_s
     (local.get $1)
     (i64.const 0))
    (br_if $label$1
     (i64.gt_s
      (call $_TypedListBase.length
       (local.get $3))
      (local.get $1))))
   (struct.set $type$65 0
    (local.tee $4
     (struct.new_default $type$65))
    (i32.const 271))
   (call $IndexError.withLength
    (local.get $4)
    (local.get $1)
    (call $_TypedListBase.length
     (local.get $3))
    (global.get $global$54))
   (call $Error._throw
    (local.get $4)
    (call $StackTrace.current))
   (unreachable))
  (struct.new $type$9
   (i32.const 11)
   (f64.reinterpret_i64
    (i64.or
     (i64.or
      (i64.or
       (i64.or
        (i64.or
         (i64.or
          (i64.or
           (i64.extend_i32_u
            (array.get_u $type$4
             (local.tee $2
              (struct.get $type$66 3
               (local.get $3)))
             (local.tee $5
              (i32.wrap_i64
               (i64.shl
                (local.get $1)
                (i64.const 3))))))
           (i64.shl
            (i64.extend_i32_u
             (array.get_u $type$4
              (local.get $2)
              (i32.add
               (local.get $5)
               (i32.const 1))))
            (i64.const 8)))
          (i64.shl
           (i64.extend_i32_u
            (array.get_u $type$4
             (local.get $2)
             (i32.add
              (local.get $5)
              (i32.const 2))))
           (i64.const 16)))
         (i64.shl
          (i64.extend_i32_u
           (array.get_u $type$4
            (local.get $2)
            (i32.add
             (local.get $5)
             (i32.const 3))))
          (i64.const 24)))
        (i64.shl
         (i64.extend_i32_u
          (array.get_u $type$4
           (local.get $2)
           (i32.add
            (local.get $5)
            (i32.const 4))))
         (i64.const 32)))
       (i64.shl
        (i64.extend_i32_u
         (array.get_u $type$4
          (local.get $2)
          (i32.add
           (local.get $5)
           (i32.const 5))))
        (i64.const 40)))
      (i64.shl
       (i64.extend_i32_u
        (array.get_u $type$4
         (local.get $2)
         (i32.add
          (local.get $5)
          (i32.const 6))))
       (i64.const 48)))
     (i64.shl
      (i64.extend_i32_u
       (array.get_u $type$4
        (local.get $2)
        (i32.add
         (local.get $5)
         (i32.const 7))))
      (i64.const 56))))))

Currently typed data lists use a i8 array as the buffer and read/write one byte at a time. I can't tell from the code why we use a byte array in typed data lists, but I suspect it has to do with JS interop or getting different views of a lists without copying (which would break sharing).

Opening this issue to document the requirements and alternatives.

It's a bit difficult to find where the typed list constructors and accessors are generated, so here are a few links:

• Allocating typed data lists:

  sdk/pkg/dart2wasm/lib/intrinsics.dart

  Line 1375 in 82b7891

  // (Int|Uint|Float)(8|16|32|64)(Clamped)?(List|ArrayView) constructors

• [] and []=:

  sdk/pkg/dart2wasm/lib/intrinsics.dart

  Line 216 in 82b7891

  // _TypedList._(get|set)(Int|Uint|Float)(8|16|32|64)

• For the class definitions we mostly use VM's patch: https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/typed_data_patch.dart
  • We override _TypedList._getFloat32, _TypedList._setInt64 etc.

[osa1]

We discussed this with @askeksa-google. The main issue here is the views. Example:

import 'dart:typed_data';

void main() {
  Float64List f64s = Float64List.fromList([1.2, 3.4, 5.6]);
  print(f64s);

  // Uses the same storage with f64s
  Float32List f32View = Float32List.sublistView(f64s);
  print(f32View);
  
  // Updates f64s
  f32View[2] = 7.8;
  print(f64s);
}

When creating a view we can't copy the original list's array as an update to one of the original list or views need to update all the others.

The solution is to use a byte array as the backing storage which is shared with all of the views. Each view class can then do reads and writes according to their element types.

The problem is, unlike linear memory, Wasm GC arrays don't support reading elements other than the array's declared element type. So when we use an i8 array as the storage type we have to read and write one byte at a time.

It seems to me like this can potentially be considered as an omission in the MVP GC spec, and maybe we can consider adding a "byte array" type that allows reading/writing different sizes in single read/write, similar to linear memory instructions i32.load, i64.load etc. (I think @eyebrowsoffire has some ideas on this)

However this will have to be turned into a proposal and in the best case it will take months before we can use this new array type.

An alternative that doesn't rely on any new platform features is: we optimize the case when a typed array is used directly (or with a view with the same element type) by allocating an array with the right type. The views will have to do the conversions if necessary. For this we also have two options:

• We create a view for every conversion. E.g. a view type that reads F64 from I32 array, a view for reading F32 from I32 array and so on.

  This will have smaller overhead in views when reading elements of different types, but there will be N^2 view classes. (where N is the number of typed array element types)

• We create a single view class for each element type, and add a "read one byte" method to typed arrays. So if I have a F64 array and a F32 view, the view will use the byte read/write methods of the original array.

[osa1]

Fix in https://dart-review.googlesource.com/c/sdk/+/312907.