ordered_map<cstring, ...> fiasko about p4c HOT 6 CLOSED

Switch to using an hvec_map instead? It has the same property of preserving the insertion order while allowing fast lookups (hash based), just needs a hash function.

from p4c.

Switch to using an hvec_map instead? It has the same property of preserving the insertion order while allowing fast lookups (hash based), just needs a hash function.

I am currently experimenting with different solutions, yes.

from p4c.

Another thing is that ordered_map is often used in places which don't actually need it (e.g. which don't do key-based lookup and don't rely of ordered_map to ensure deterministic iteration order). However, getting rid of it is a bit tricky as it risks easily introducing nondeterminism into the compiler later, if some iteration is added. One solution (although it has its downsides too) is to use non-iterable wrappers over (some) map/set types for these places so that attempt to iterate over them causes compiler error when building P4C. I had non-iterable wrappers over maps and sets in the Tofino P4C compiler, but they are lost there as I did not get to upstream them before leaving the team.

Having a higher-performing replacement would definitely help though.

from p4c.

However, getting rid of it is a bit tricky as it risks easily introducing nondeterminism into the compiler later, if some iteration is added.

Yeah. Another way (adopted by abseil, btw, if hash is not provided) is to randomize hashes, so the iteration order would be different in each invocation even on the same machine / same conditions. So, these issues would be exposed earlier. This is a bit aggressive though :)

from p4c.

However, getting rid of it is a bit tricky as it risks easily introducing nondeterminism into the compiler later, if some iteration is added.

Yeah. Another way (adopted by abseil, btw, if hash is not provided) is to randomize hashes, so the iteration order would be different in each invocation even on the same machine / same conditions. So, these issues would be exposed earlier. This is a bit aggressive though :)

The problem is, in my experience, that it is quite hard to find the nondeterminism by a test suite unless it specifically tests deterministic outputs. If all results are valid (which they absolutely should) and differ just in things like where something is allocated or how much resources are used, this can go unnoticed for a long time. Even when it is noticed, finding the culprit is very hard.

from p4c.

The problem is, in my experience, that it is quite hard to find the nondeterminism by a test suite unless it specifically tests deterministic outputs. If all results are valid (which they absolutely should) and differ just in things like where something is allocated or how much resources are used, this can go unnoticed for a long time. Even when it is noticed, finding the culprit is very hard.

Yes, I fully agree. Still it is a bit non-trivial to allow iterators and forbid iteration. But, anyway, care should be taken and it is review process designed to have spare pair of eyes to check for this.

from p4c.