Investigate using SIMD to improve performance of common Matrix operations #60538

Background

SIMD (Single Instruction Multiple Data) works by providing specialized instructions for large 128 bit (or more) registers that provide the potential for greater parallelism. For example, the current matrix equality code in Flutter is roughly:

    return a.storage[0] == b.storage[0]
        && a.storage[1] == b.storage[1]
        && a.storage[2] == b.storage[2]
        && a.storage[3] == b.storage[3]
        && a.storage[4] == b.storage[4]
        && a.storage[5] == b.storage[5]
        && a.storage[6] == b.storage[6]
        && a.storage[7] == b.storage[7]
        && a.storage[8] == b.storage[8]
        && a.storage[9] == b.storage[9]
        && a.storage[10] == b.storage[10]
        && a.storage[11] == b.storage[11]
        && a.storage[12] == b.storage[12]
        && a.storage[13] == b.storage[13]
        && a.storage[14] == b.storage[14]
        && a.storage[15] == b.storage[15];

Simplifying a bit, with a 4x4 matrix we need to perform 16 comparisons. With SIMD, many of these comparisons can be run at the same time. Given a matrix where the columns are represented by the Float32x4 type, it can instead be written like:

Int32x4 col0Equals = column0.equal(other.column0);
Int32x4 col1Equals = column1.equal(other.column1);
Int32x4 col2Equals = column2.equal(other.column2);
Int32x4 col3Equals = column3.equal(other.column3);
Int32x4 temp = col0Equals & col1Equals & col2Equals & col3Equals;
return temp.signMask == 15;

While 16 comparisons are still performed, these are now done 4 at a time. Generally, performing a SIMD operation in Dart should be about 3x faster than the equivalent scalar code.

While SIMD was never adopted in JavaScript*, Flutter applications on mobile/desktop could take advantage of it. The most obvious cases in Flutter are the matrix operations required during layout, transforms, semantics, and hit testing. Beyond matrix operations, SIMD has been applied to a number of other domains such as parsing/deserialization, like simdjson.

• Though WASM might: https://v8.dev/features/simd

Overview

I implemented several of the most common operations in flutter using SIMD types and compared them to their vector_math equivalents: matrix multiplication, inversion, matrix equality, and point transformation. I then measured the performance using the benchmark scripts in jonahwilliams@77475d6

Pixel 4 (arm64) Results

Inversion: SIMD 47% faster than vector math.
Multiplication: SIMD 350% faster than vector math.
Equality: SIMD 2600 % slower than vector math.
Transform Point: SIMD 13% faster than vector math

macOS (x86_64) Results

Inversion: SIMD 21% slower than vector math (250% faster than vector math - implementation 2).
Multiplication: SIMD 350% faster than vector math.
Equality: SIMD 74 % faster than vector math.
Transform Point: SIMD identical to vector math

The slower inversion code on x86_64 is due to using an ARM focused implementation. A separate investigation which ported the inversion code from the TC39 SIMD benchmark found it was 2.5X faster than vector_math. The extreme slowdown in equality checks on ARM devices is due to an inefficient emulation of signMask in Dart.

Next Steps

A larger investigation would be required to determine how significant any performance improvements would be at a macro level, or whether the existing use of Matrix4 types could be changed with a breaking change process. Converting Matrix4 types to SIMD on the fly might have overhead that outweighs any performance gained. The loss of precision might also impact rendering in unknown ways. This investigation would be constrained to desktop devices unless dart-lang/sdk#41950 was also fixed.

Resources

The diff master...jonahwilliams:simd_integration contains implementations of the matrix operations above as well as the benchmark. NN: There are separate Intel and ARM matrix inversion algorithms that must be used for performance reasons.

Originally investigated via go/simd-in-flutter, this document is not available widely so the full text has been transported here.