Add `--omit-concurrent-modification-errors` flag to dart2wasm

[mkustermann]

We have various optimization levels -O1/-O2 that respect semantics and soundness and -O3 that omits implicit type checks and -O4 that omits extra checks (e.g. bounds checks).

Now I would argue that the concurrent modification error checks we have in list / map iterators and elsewhere are much less important to perform than e.g. implicit type checks. Those cost code size and performance for many collection iterations and are very unlikely to reveal custom issues in production (compared with omitting type checks required for soundness).

Even more so these concurrent modification checks aren't actually identifying all concurrent modifications (e.g. replacing list values with new values while iterating a list) - they only catch some concurrent modifications (e.g. changing size of containers)

So I'd suggest we add a --omit-concurrent-modification-errors and enable it in -O3 and -O4.

/cc @osa1 /cc @sigmundch for dart2js perspective - maybe it should do this as well - or already does?

[sigmundch]

I agree in principle. I am however wondering if we should still enable it it globally by default under the O3/O4 flags.

You may recall that if we could do everything oveer again, we'd not have done -O3/4 as global options, but instead added scoped pragmas that allowed you to toggle the behavior on a fine-grain manner. Then we could enable these options in performance critical framework code, but leave them disabled in user's code.

@rakudrama - WDYT?

[kevmoo]

Keep in mind, the default for Flutter is -O4.

[rakudrama]

To me, the most unsatisfactory aspect of concurrent modification checks is that they have a cost even when there is no iteration. For complex collections (almost anything other than the system List), checking for CME requires supporting fields, for example, a modification clock on the collection and a snapshot of the clock on the iterator. I don't know, though, that this really matters.

A fine-grained, or local, pragma works well when there a single place of action that can be annotated (each function entry, each as expression, each recognized indexer). It is not clear how a fine-grained pragma for CME checks would work. A CME check connects an iteration in one place, mediated by a moveNext method in a second (usually inaccessible) place, with a modification from third place. How would you implement set1.addAll(set2) having different behaviour for two call sites to the same method?

We could experiment with a global conditional flag for each moveNext by having a guard environment variable. The check

  x != y

becomes something like

  !bool.fromEnviroment('dart.compiler.omit-hash-set-concurrent-modification-check') && x != y

If the guard condition is simplified sufficiently early in the compilation, the moveNext methods will become simpler, potentially becoming better inlining candidates.

The model is that a global flag like --omit-concurrent-modification-checks sets a number of these environment variables, so that each collection can be maintained independently.

To get the full benefit from --omit-concurrent-modification-checks, we would also want an optimization to remove the supporting fields. A modification clock is incremented in many places, so it would require an elaborate analysis to remove it automatically. After the CME check has been removed, there is a residual cycle of values through fields, parameters, local variables, expression values, and pure operations, that does not reach an effect or control flow. This would have to be removed as an atomic edit. It is possible this could be done in Kernel and benefit all compilers. Maybe this is unnecessary if all the modification clock updates are guarded by the same condition (so the fields can be removed by current 'unused' optimizations).

It is not clear that removing CME checks will be worthwhile. We could assess by editing the core/collection libraries to remove them by hand. There are two levels, level 1 is just removing the checks, level 2 is removing the supporting fields. I remember trying something like this for dart2js and it was unimpressive, but I don' recall exactly what I did.

---

We don't omit concurrent modification error checks in dart2js.

dart2js does optimize away CME checks in one circumstance: for-in on lists.

For for-in on an Iterable that is known (from global inference, similar to TFA) to be a system list, dart2js lowers for-in to different code to what you would get from direct inlining. The custom lowering overcomes some of the CFG-level weaknesses of the dart2js SSA optimizer and some quirks of some JavaScript implementations. The substitute code is an indexing loop which also compares the original 'snapshot' length to the current length. The length check is optimized away if the length is determined to be a region constant (several tricks here, trivial for known fixed-length lists, the most powerful trick is load elimination which has some primitive awareness of side-effects and aliasing).

dart2js removes CME checks from about 25% of for-in loops. You can find the lowered loops by looking for the variable _i in generated code (get readable optimized via -O4 --no-minify).

The custom lowering provides a single place of action that could be annotated with a fine-grained pragma. It would be relatively simple to add to dart2js a pragma that could be placed on a library, class, or method that caused the CME check to be omitted from the custom code for lowered for-in loops within the annotated element.

[rakudrama]

I am going to experiment with a global environment variable (on dart2js initially).

[mkustermann]

One of the conceptual things I don't like about the CME checks is that it's not what a developer would expect. I think normal developers expect the following two loops to behave semantically the same:

for (final value in list) { // <- would throw if adding to `list` while iterating
  foo(value)
}

for (int i = 0; i < list.length; ++i) { // <- would allow adding to `list` while iterating
  final value = list[i];
  foo(value);
}

Maybe some programmers will think the first one is nicer to write but less efficient due to usage of iterators, but very very few users would expect there to be a difference in semantics.

Turns out our tools aren't even consistent with this CME behavior: DDC(I assume DartPad uses DDC) doesn't actually throw a CME error, see dartpad.dev/cme-example

/cc @lrhn Maybe we can consider removing the CME check (at least on lists) entirely?

[rakudrama]

DDC has a known bug: https://github.com/dart-lang/sdk/issues/44082

I ran the experiment for dart2js. There were some nice wins. It is not clear yet if these would translate to native or wasm.

The best wins were for List.from and List.unmodifiable with per-element checks disabled (via -O3). Here the for-in loop was polymorphic in the collection type, so an iterator was needed, but dynamically, the iterator was mostly the system List iterator. The version of iterator without the check was faster. Some series were 40% faster. I am very suspicious of this gain. Perhaps V8 polymorphic inlining thresholds had an impact there.

Other gains were more modest. There were some JsonEncode benchmark with ~3-4% improvements, and some simple polymorphic iteration benchmarks with a similar gain, but these had quite a lot of noise.

After a bit of fiddling, I was able to get dart2js to remove the modification clock fields from the Maps too.

I don't think the code size wins for dart2js are interesting. Most moveNext methods are not inlined, so the code size improvement does not scale. This will be different for native.

If we add a global flag to omit concurrent modification error checks, it looks like it would have to be a Dart-wide option. Code with CME checks is shared between all platforms. For example, this check in ListBase.forEach (link into my experiment).

[lrhn]

The CME tests are for your own protection. If we remove them, then we have to specify what happens (or at least specified as unspecified behavior).

Our breaking change policy says that it's not breaking to change behavior of code that throws an Error. It would also say that changing unspecified behavior is not considered breaking. And I'm not sure that actually works. The interleaving of asynchronous events and microtasks is unspecified, and woe on us if we try to change it.

You say that a for/in loop is equivalent to one for loop with an index. But why that particular loop, and not

for (int i = 0, n = list.length; i < n; ++i) { // <- would allow adding to `list` while iterating
  final value = list[i];
  foo(value);
}

? That's also a loop that allows changing the list length while iterating, but it behaves differently than the other loop if the list length actually changes. If foo adds to the list, this one doesn't loop forever. Iffoo removes from the list, this one throws where the other one didn't.

That's the kind of implementation details that concurrent modification errors exist to hide. It doesn't matter how we implement the iteration if we throw the moment the difference begins to matter.

That said, we have generally defined concurrent modifications as unspecified behavior, so we are allowed to remove the checks, or only do them in development mode. I'd been very sorry to not do them in development mode, because they are reporting a very likely bug. That's why it's a problem that DDC omits the check.

[lrhn]

global environment variable (on dart2js initially)

Please call it something starting with dart.tool.dart2js..

The example

  !bool.fromEnviroment('dart.compiler.omit-hash-set-concurrent-modification-check')

shouldn't be used. Adding flags to the top-level dart. scope should be avoided. If we want a top-level container for compilation/mode flags, we should consider adding one, but I wouldn't call it compiler.

[rakudrama]

@lrhn What would you call the environment variable when it is consumed by dart2js, dart2wasm, native, and is used in code that is compiled by DDC? (i.e., what to you call the variable that is used in ListBase)?

[lrhn]

@rakudrama According to https://github.com/dart-lang/sdk/issues/54785, I'd call it dart.mode.something.

We could just use asserts, and only do concurrent modification checks when asserts are enabled. That would be easy to explain, but doesn't give the same granularity.

So maybe dart.mode.concurrentModificationChecks, and set it to true when they are enabled.

[osa1]

I suggest we sort #56949 out first before adding more discrepancies between dart2js and dart2wasm.

I would think that CME should never be caught and handled explicitly, but there may be cases where that's done with a catch without an on, or by cathing Error or Object.

I'm mainly worried about the PR aspect of this, when things work with dart2js but not with dart2wasm, people will at some point conclude that dart2wasm is too broken to be used, regardless of whether dart2wasm semantics is standard compliant or not.