Dart VM does not preserve identities for SIMD objects

[sgrekhov]

The following test fail on dartkp-strong-linux-release-simarm64 configuration

import "dart:typed_data";
import "../../../Utils/expect.dart";

main() {
  var obj1 = new Float32x4(1.0, 2.0, 3.0, 4.0);
  var obj2 = new Float32x4(1.0, 2.0, 3.0, 4.0);
  var obj3 = obj1;
  var obj4 = new Float32x4(1.0, 2.0, 3.0, 4.0);

  Expect.isTrue(obj1 == obj3);
  Expect.isTrue(obj1 == obj1);
  Expect.isFalse(obj2 == obj3); // Fail here
  Expect.isFalse(obj1 == obj2);
  Expect.isFalse(obj1 == obj4);
}

Output is

/==================================================================================================================================================\
| dartkp-strong-linux-release-simarm64:co19/LibTest/typed_data/Float32x4/operator_equality_A01_t01 is new and failed (RuntimeError, expected Pass) |
\==================================================================================================================================================/

--- Command "vm_compile_to_kernel" (took 03.000137s):
DART_CONFIGURATION=ReleaseSIMARM64 /b/s/w/ir/pkg/vm/tool/gen_kernel --enable-experiment=non-nullable --aot --platform=out/ReleaseSIMARM64/vm_platform_strong.dill -o /b/s/w/ir/out/ReleaseSIMARM64/generated_compilations/dartkp/tests_co19_src_LibTest_typed_data_Float32x4_operator_equality_A01_t01/out.dill /b/s/w/ir/tests/co19/src/LibTest/typed_data/Float32x4/operator_equality_A01_t01.dart --enable-experiment=non-nullable --packages=/b/s/w/ir/.packages -Ddart.vm.product=false -Ddart.developer.causal_async_stacks=true --sound-null-safety

exit code:
0

--- Command "precompiler" (took 05.000422s):
DART_CONFIGURATION=ReleaseSIMARM64 out/ReleaseSIMARM64/gen_snapshot --enable-experiment=non-nullable --snapshot-kind=app-aot-elf --elf=/b/s/w/ir/out/ReleaseSIMARM64/generated_compilations/dartkp/tests_co19_src_LibTest_typed_data_Float32x4_operator_equality_A01_t01/out.aotsnapshot --loading-unit-manifest=/b/s/w/ir/out/ReleaseSIMARM64/generated_compilations/dartkp/tests_co19_src_LibTest_typed_data_Float32x4_operator_equality_A01_t01/ignored.json --sound-null-safety --enable-experiment=non-nullable --ignore-unrecognized-flags --packages=/b/s/w/ir/.packages /b/s/w/ir/out/ReleaseSIMARM64/generated_compilations/dartkp/tests_co19_src_LibTest_typed_data_Float32x4_operator_equality_A01_t01/out.dill

exit code:
0

--- Command "remove_kernel_file" (took 15ms):
DART_CONFIGURATION=ReleaseSIMARM64 rm /b/s/w/ir/out/ReleaseSIMARM64/generated_compilations/dartkp/tests_co19_src_LibTest_typed_data_Float32x4_operator_equality_A01_t01/out.dill

exit code:
0

--- Command "vm" (took 31ms):
DART_CONFIGURATION=ReleaseSIMARM64 out/ReleaseSIMARM64/dart_precompiled_runtime --sound-null-safety --enable-experiment=non-nullable --ignore-unrecognized-flags --packages=/b/s/w/ir/.packages /b/s/w/ir/out/ReleaseSIMARM64/generated_compilations/dartkp/tests_co19_src_LibTest_typed_data_Float32x4_operator_equality_A01_t01/out.aotsnapshot

exit code:
255

stderr:
Unhandled exception:
Expect.isFalse(true) fails.
#0      _fail (file:///b/s/w/ir/tests/co19/src/Utils/expect.dart:20)
#1      Expect.isFalse (file:///b/s/w/ir/tests/co19/src/Utils/expect_common.dart:48)
#2      main (file:///b/s/w/ir/tests/co19/src/LibTest/typed_data/Float32x4/operator_equality_A01_t01.dart:26)
#3      _startIsolate.<anonymous closure> (dart:isolate-patch/isolate_patch.dart:301)
#4      _RawReceivePortImpl._handleMessage (dart:isolate-patch/isolate_patch.dart:168)

--- Re-run this test:
python tools/test.py -n dartkp-strong-linux-release-simarm64 co19/LibTest/typed_data/Float32x4/operator_equality_A01_t01

[mraleph]

/cc @mkustermann for triage

[mkustermann]

@cskau-g Could you take a look at this?

[ghost]

This test appears to fail for all variants: dartkp-strong-linux-{debug,release}-{simarm64,simarm,x64}.

Dumping the kernel (Looks OK):

  static method main() → dynamic {
    typ::Float32x4 obj1 = [@vm.inferred-type.metadata=dart.typed_data::_Float32x4] typ::Float32x4::•();
    typ::Float32x4 obj2 = [@vm.inferred-type.metadata=dart.typed_data::_Float32x4] typ::Float32x4::•();
    typ::Float32x4 obj3 = obj1;
    typ::Float32x4 obj4 = [@vm.inferred-type.metadata=dart.typed_data::_Float32x4] typ::Float32x4::•();
    Exp::Expect::isTrue([@vm.direct-call.metadata=dart.core::Object.==] [@vm.inferred-type.metadata=dart.core::bool (skip check) (receiver not int)] obj1.{core::Object::==}(obj3));
    Exp::Expect::isTrue([@vm.direct-call.metadata=dart.core::Object.==] [@vm.inferred-type.metadata=dart.core::bool (skip check) (receiver not int)] obj1.{core::Object::==}(obj1));
    Exp::Expect::isFalse([@vm.direct-call.metadata=dart.core::Object.==] [@vm.inferred-type.metadata=dart.core::bool (skip check) (receiver not int)] obj1.{core::Object::==}(obj2));
    Exp::Expect::isFalse([@vm.direct-call.metadata=dart.core::Object.==] [@vm.inferred-type.metadata=dart.core::bool (skip check) (receiver not int)] obj2.{core::Object::==}(obj3));
    Exp::Expect::isFalse([@vm.direct-call.metadata=dart.core::Object.==] [@vm.inferred-type.metadata=dart.core::bool (skip check) (receiver not int)] obj1.{core::Object::==}(obj4));
  }

Printing the CFG from the .dart file (Looks OK):

==== file:///usr/local/google/home/cskau/src/dart_wd4/sdk/tests/co19/src/LibTest/typed_data/Float32x4/operator_equality_A01_t01.dart_::_main (RegularFunction)
B0[graph]:0
B1[function entry]:2
    CheckStackOverflow:8(stack=0, loop=0)
    DebugStepCheck:10()
    t0 <- Constant(#TypeArguments: null)
    t1 <- Constant(#1.0)
    t2 <- Constant(#2.0)
    t3 <- Constant(#3.0)
    t4 <- Constant(#4.0)
    t0 <- StaticCall:12( Float32x4.<0> t0, t1, t2, t3, t4)
    StoreLocal(obj1 @-1, t0)
    t0 <- Constant(#TypeArguments: null)
    t1 <- Constant(#1.0)
    t2 <- Constant(#2.0)
    t3 <- Constant(#3.0)
    t4 <- Constant(#4.0)
    t0 <- StaticCall:14( Float32x4.<0> t0, t1, t2, t3, t4)
    StoreLocal(obj2 @-2, t0)
    DebugStepCheck:16()
    t0 <- LoadLocal(obj1 @-1)
    StoreLocal(obj3 @-3, t0)
    t0 <- Constant(#TypeArguments: null)
    t1 <- Constant(#1.0)
    t2 <- Constant(#2.0)
    t3 <- Constant(#3.0)
    t4 <- Constant(#4.0)
    t0 <- StaticCall:18( Float32x4.<0> t0, t1, t2, t3, t4)
    StoreLocal(obj4 @-4, t0)
    t0 <- LoadLocal(obj1 @-1)
    t1 <- LoadLocal(obj3 @-3)
    t0 <- InstanceCall:20( ==<0>, t0, t1)
  [...]

Disassembling (Not OK):

Code for optimized function 'file:///.../tests/co19/src/LibTest/typed_data/Float32x4/operator_equality_A01_t01.dart_::_main' (RegularFunction) {
        ;; B0
        ;; B1
        ;; Enter frame
        ;; PrologueOffset = 0
0x0    55                     push rbp
0x1    4889e5                 movq rbp,rsp
        ;; CheckStackOverflow:8(stack=0, loop=0)
0x4    493b6640               cmpq rsp,[thr+0x40]
0x8    0f865b000000           jna +97
        ;; PushArgument(v235)
0xe    41ffb6c8000000         push [thr+0xc8]
        ;; StaticCall:22( isTrue<0> v235)
0x15    e8fbffffff             call +0
0x1a    59                     pop rcx
        ;; PushArgument(v235)
0x1b    41ffb6c8000000         push [thr+0xc8]
        ;; StaticCall:26( isTrue<0> v235)
0x22    e8fbffffff             call +0
  [...]

From what I can tell, something is broken in the ASM generation/optimisation.

@mkustermann, perhaps you have some ideas where we might go looking for bug on this?

(Note: I swapped two of the test cases in the above code, but the issue remains the same.)

[mraleph]

I suggest that we maybe change the expected semantics here and maybe the test itself.

Float32x4 is a factory constructor so there is nothing in the language preventing it from returning the same object again.

@lrhn @leafpetersen I would be helpful for us if SIMD types got the same treatment as records in terms of identity (e.g. VM would not need to preserve their identity). Currently there is nothing in their documentation which allows for such treatment, and we in fact violate it in few places (like this test shows for example).

[lrhn]

@mraleph So you're suggestion changing the == and identical on Float32x4 to be pointwise equality/identity (only difference is that nan != nan, but identical(nan, nan) can be true), and then claim that the constructor canonicalizes.
That would be valid with the current semantics. It will add a cost to identical unless when we can statically ensure that
at least one operand is not a Float32x4. (Do be careful with Expando, though.)

The only reason the SIMD type cannot be a record/tuple type itself is that its elements don't have a Dart type, and we can't use ffi native types in the browser, so we can't declare (float, float, float, float) as a record. Which sucks because "four unmodifiable floats" screams tuple to me!

So, do we want a way to declare a class as a "record class" (struct) where identity is not necessarily preserved by assignment, only contents (and the state must then be unmodifiable)? It'll have all the usual record problems with deciding when identity is preserved, or adding extra cost to the identical operation to reject structs entirely. It'll otherwise be a normal class with all the same affordances (just no non-final instance variables, and Expando doesn't work with it).

[mraleph]

So you're suggestion changing the == and identical on Float32x4 to be pointwise equality/identity (only difference is that nan != nan, but identical(nan, nan) can be true), and then claim that the constructor canonicalizes.

Yes, except that constructor is not obliged to canonicalize because identity is not observable. So it might be canonicalizing might be not.

Essentially I propose to treat simd types the same way we treat double.

So, do we want a way to declare a class as a "record class" (struct) where identity is not necessarily preserved by assignment, only contents (and the state must then be unmodifiable)?

That might be helpful, I have already considered experimenting with this because there are some use cases when this can be helpful, e.g. Int64 type from fixnum package when running on VM.

identical already has to discern double and _Mint objects and treat them in a special way so adding special treatment for structs / simd types is probably not going that big of an impact.

Hard to say about JS though (though I think that most of the compile-to-JS code does not actually use SIMD types because they don't come with any performance benefits) - any opinions on the subject @rakudrama?

[rakudrama]

There were some efforts to add SIMD types to JavaScript, but they have been abandoned (the action is in WebAssembly).
The Dart SIMD types like Float32x4 and their lists are worth avoiding when compiling to JavaScript. If performance is any concern you would do much better to write Fortranesque code that mucks around in a Float32List.

It would be interesting to allow GVN optimizations for allocations of some 'record' types. I don't want to add code to identity to handle these cases though, since we can currently compile identity to ===* and anything else will be considerably slower, and there is not a lot that can be done about when the arguments have a generic static type.
*Yes, we break identity(double.nan, double.nan).

Where I want loose identity in my everyday life is with unmodifiable collections. List.unmodifiable should be able to return its argument if it already is unmodifiable. I could trim a lot of memory from dart2js very simply with that (ditto Set, Map, and I'd prefer a better typed interface like List.of rather than List.from).

[mkustermann]

Marking this as blocked - since we're waiting for language team to decide whether those SIMD types can be treated differently regarding to identical, ...

[lrhn]

The quick answer is that they can't be treated differently. Nothing in the current language allows that.

The question is whether we want to add an exception, and if so, how would we phrase that?
It's not something the language team are actively looking at, other than our occasionally on-going experiments with "date types".

[gmpassos]

There's nothing saying or indicating that a default equality operator should be always treated as an identical operation, since the correct way to check for identical instances is calling identical.

What's happening here is that Float32x4 is not overwriting the == operator., and any factory constructor can return the same instance (this is the pattern for any class with a factory constructor and a default == operator).

I think that Float32x4 should have implemented the == operator likeString does, checking if the internal value is equals, and not the default,identical. Also anyone that really wants to check if 2 objects are the same instance, should use identical and never the == operator, since == can always be overwritten in future versions (an advise that should be documented).

It's also not intuitive to have operations with Float32x4 or Float64x2 that won't behave in the same way as double.

[mraleph]

@lrhn @leafpetersen is it possible to bump this into language team agenda? What we would like here is to permit implementations to loose the identity of SIMD objects, either as a language change targeting specifically these types or something slightly wider (e.g. @pragma('value-type') applied to a class with non-late final fields only) which would permit creation of types that can loose their identity (be automatically unboxed and reboxed by the implementation at will). The missing piece here is a decision of how to handle identical(): either make it unpredictable or make it recursive (similar to how we discussed this for records).

Currently VM already partially looses identity of SIMD types, however this obviously violates the spec. The choice we have now is either to fix implementation to conform or amend the specification. We did these optimisations back in the day without realising that spec did not expand its treatment of numeric types to SIMD types (which seems natural to do).

Note that current specification essentially limits us to local unboxing (or rather allocation sinking - which unlike unboxing preserves identity), and does not allow us to unbox fields, parameters and return values.

[gmpassos]

The only real purpose of 'Float32x4' is the SIMD optimization. Anything that reduces the SIMD performance or reduces the global performance of a Dart code that will be "adapted" in VM/AOT to use SIMD instructions is against the actual existence of 'Float32x4'.

The use of 'identity' in a type that depends on factory constructors is already odd. Also perform an 'identity' check in 'Float32x4' should be strange like perform that in a double.

[mraleph]

@gmpassos

The use of 'identity' in a type that depends on factory constructors is already odd.

The issue is a bit more subtle that this - it's not really about whether the same (factory) constructor invocation returns two different instances or the same instance. It is about whether an identity of an instance can be lost as it travels through the program:

Float32x4 foo(Float32x4 o) => o;

Object bar(Object o) => foo(o as Float32x4);

void main() {
  final o = Float32x4(...);
  print(identical(o, bar(o)));
}

If you replace Float32x4 with double in the code above then o and bar(o) might be two different objects (though you would not be able to observe that using identical because identical is defined to compare double payload rather than look at object identity). Float32x4 and other SIMD types are not treated in the same way by the specification, meaning that if we were to adhere to the specification we have to preserve the identity of o, which inhibits some optimizations.

[gmpassos]

I strongly suggest to forget about 'identical' for 'Float32x4', since the overhead to keep it reduces a lot the usage of 'Float32x4' and destroys GC for intensive SIMD tasks. It's something that goes against the existence of SIMD support in Dart. Also there's no real usage of 'identical' for types like that.

[mraleph]

@gmpassos yes, that what I suggest as well, but the decision needs to be made by the language team in the end, so we just wait for the them to discuss this issue and respond. All the necessary arguments were made.

[gmpassos]

I think that the code that need to be changed is small and easy to test. The point is much more about a team decision and to get the right people to discuss, specially about real case scenarios.

Remember that with the current language definition, a small immutable object (Float32x4) is destroying the GC for an intensive computation task that uses SIMD, and this is the real use case for this kind of type. A loop of multiplications should not generate new heap allocations.

[mraleph]

I am trying to move this forward in dart-lang/language#2246