Remove Type ordering#3793
Conversation
As found in WebAssembly#3682, the current implementation of type ordering is not correct, and although the immediate issue would be easy to fix, I don't think the current intended comparison algorithm is correct in the first place. Rather than try to switch to using a correct algorithm (which I am not sure I know how to implement, although I have an idea) this PR removes Type ordering entirely. In places that used Type ordering with std::set or std::map because they require deterministic iteration order, this PR uses new set and map wrappers to provide deterministic insertion-order iteration.
kripken
left a comment
There was a problem hiding this comment.
Nice!
For fuzzing this, I'd up the frequency of the CheckDeterminism tool from 0.1 to 1.
| iterator begin() { return vec.cbegin(); } | ||
| iterator end() { return vec.cend(); } | ||
|
|
||
| bool empty() const { return vec.size() == 0; } |
There was a problem hiding this comment.
| bool empty() const { return vec.size() == 0; } | |
| bool empty() const { return vec.empty(); } |
| iterator begin() { return vec.begin(); } | ||
| iterator end() { return vec.end(); } | ||
|
|
||
| bool empty() const { return vec.size() == 0; } |
There was a problem hiding this comment.
| bool empty() const { return vec.size() == 0; } | |
| bool empty() const { return vec.empty(); } |
| // Keeps track of the binary index of the scratch locals used to lower | ||
| // tuple.extract. | ||
| std::map<Type, Index> scratchLocals; | ||
| std::unordered_map<Type, Index> scratchLocals; |
There was a problem hiding this comment.
this must be sorted, we iterate on it and it affects the order of localTypes which is reflected in the binary IIANM
|
Good idea with the fuzzing. I quickly found that there was indeed a determinism issue. The parallel function analysis used a map that was deterministically ordered by non-deterministic function addresses, which ultimately caused the insertion order in |
| std::map<Type, Name> map; | ||
| std::map<Name, Type> rev; | ||
| std::unordered_map<Type, Name> map; | ||
| std::unordered_map<Name, Type> rev; |
There was a problem hiding this comment.
How about for changes like this, we create a new uniterable_map (or better name), which is unordered_map without the ability to iterate? That would avoid the possibility of nondeterminism, which otherwise can be very annoying to find later if we miss anything in this PR.
In other words, the PR could change a map into either uniterable_map (if we never iterate on it) or ordered_map (if we do). Then we should have 0 risk.
There was a problem hiding this comment.
If we had an uniterable_map available in a header, I have a hard time imagining that I would use it beyond this single PR. The tough part about getting the determinism correct here is that now getting deterministic iteration depends on having deterministic insertions, whereas previously the insertions could be non-deterministic and the iteration would still be deterministic due to sorting. An uniterable_map would not help solve that problem, unfortunately.
There was a problem hiding this comment.
I see, very good point...
Yes, maybe not that generally useful then. Still I think it's worthwhile, but can discuss separately if it doesn't help you here.
| }; | ||
|
|
||
| typedef std::map<Function*, T> Map; | ||
| typedef ordered_map<Function*, T> Map; |
There was a problem hiding this comment.
CallGraphPropertyAnalysis is used widely so the extra overhead here worries me a little. Worth measuring the memory and speed impact of this PR.
|
I plan to update this so that not all parallel analyses are affected; only the ones that matter. |
|
Btw, I noticed that we already have code for insert-ordered data structures, |
|
Oh, good to know. I'll take a look at that refactoring. |
kripken
left a comment
There was a problem hiding this comment.
Nice!
lgtm, but I'd recommend fuzzing heavily before landing (and with CheckDeterminism as before)
| return *this; | ||
| } | ||
| InsertOrderedMap(InsertOrderedMap&& other) | ||
| : Map(std::move(other.Map)), List(std::move(other.List)) {} |
There was a problem hiding this comment.
Are move semantics guaranteed to get this right? I feel like I've read that they have, but I've never depended on that as much as this line seems to...
There was a problem hiding this comment.
Good question. I couldn't find any specific spec guarantees, so I removed this new constructor and assignment operator. They were left over from shots in the dark trying to fix a bug that turned out to be unrelated.
| (block | ||
| (local.set $0 | ||
| (i32.const -1048577) | ||
| (i32.const 8192) |
There was a problem hiding this comment.
This does not look right, but reading more carefully, it actually is...
As found in #3682, the current implementation of type ordering is not correct,
and although the immediate issue would be easy to fix, I don't think the current
intended comparison algorithm is correct in the first place. Rather than try to
switch to using a correct algorithm (which I am not sure I know how to
implement, although I have an idea) this PR removes Type ordering entirely. In
places that used Type ordering with std::set or std::map because they require
deterministic iteration order, this PR uses new set and map wrappers to provide
deterministic insertion-order iteration.