lsils / mockturtle

C++ logic network library
MIT License
191 stars 133 forks source link

Use `std::stable_sort` instead of `std::sort` everywhere #655

Closed rocallahan closed 2 weeks ago

rocallahan commented 4 weeks ago

Test results currently depend on how compare-equal elements are sorted by std::sort's unstable sort. Defaulting to std::stable_sort avoids that problem and generally increases the determinism of the code, which is good.

If there are specific cases where the (fairly small) performance overhead of stable sorting is a concern, those can be switched back to unstable sorting as an optimization, but first one would need to verify that that doesn't break the tests (e.g., by running the tests with a shuffle before each call to unstable sort).

Resolves #654

costamag commented 2 weeks ago

Verified no significant performance degradation in the experiments when doing the suggested replacement. Thank you for identifying this source of non-determinism!