Qiskit / qiskit / 6036244196

88%

push

github

Fix non-determinism in SabreSwap rust code (#10740)

In the SabreSwap rust module there were 2 potential sources of
non-determinism that could cause variation in results even with a fixed
seed, the ExtendedSet struct's nodes attribute and the decremented
tracking when populating the extended set. Both were caused by the same
root cause iterating over a HashMap object. Iteration order on a HashMap
(or a HashSet) is dependent on the internal hash seed of the hasher and
iteration order is explicitly not guaranteed. In the case of the
decrementer it's unlikely to have any effect even if the iteration order
is not guaranteed but it is switched to using an indexmap regarldess
just out of best practice. But for the nodes attribute in the
ExtendedSet struct there is a potential issue there because when the
total_score() method is called the nodes are iterated over, the distance
is looked up for each swap and then summed. As the distances are all
floating point values the iteration order could result in different
values being output. In both cases the `hashbrown::HashMap<K, V>` is
changed to be an `indexmap::IndexMap<K, V, ahash::RandomState>` which
will have deterministic iteration order (it uses insertion order).

5 of 5 new or added lines in 2 files covered. (100.0%)

74404 of 85235 relevant lines covered (87.29%)

60584.16 hits per line