lsils / mockturtle

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

Test results depend on the order of compare-equal elements in unstable sort #654

Closed rocallahan closed 2 weeks ago

rocallahan commented 4 weeks ago

Describe the bug Test results depend on compare-equal elements being treated in a specific way by std::sort (probably they depend on the order of compare-equal elements being preserved, but I haven't verified this)

To Reproduce Steps to reproduce the behavior:

  1. Use mockturtle master (50ffa108484ba65b44eee4a713832b7ee821d6d8 to be precise)
  2. Apply the following patch
    diff --git a/include/mockturtle/utils/tech_library.hpp b/include/mockturtle/utils/tech_library.hpp
    index cb3c83e..b40a57e 100644
    --- a/include/mockturtle/utils/tech_library.hpp
    +++ b/include/mockturtle/utils/tech_library.hpp
    @@ -1413,6 +1413,7 @@ private:
       }
       if ( _ps.np_classification && supergates_neg.size() > 0 )
       {
    +        std::random_shuffle( supergates_neg.begin(), supergates_neg.end() );
         std::sort( supergates_neg.begin(), supergates_neg.end(), [&]( auto const& a, auto const& b ) {
           return a.area < b.area;
         } );
  3. Run the tests multiple times.

You'll get failures like

/usr/local/google/home/rocallahan/mockturtle/test/algorithms/quality.cpp:190: FAILED:
  CHECK( v == std::vector<uint32_t>{ { 0, 34, 76, 39, 180, 78, 221, 159, 523, 1358, 258 } } )
with expansion:
  { 0, 34, 76, 39, 180, 78, 220, 158, 518 (0x206), 1135 (0x46f), 246 }
  ==
  { 0, 34, 76, 39, 180, 78, 221, 159, 523 (0x20b), 1358 (0x54e), 258 (0x102) }

The details of the failures will vary from run to run.

Environment This will reproduce in any environment.

Additional context The random shuffle should be a harmless no-op --- std::sort is allowed to put compare-equal elements in any order, and elements that don't compare equal will be sorted into that order.

Check list