1*4bdff4beSrobert================================== 2*4bdff4beSrobertUnspecified Behavior Randomization 3*4bdff4beSrobert================================== 4*4bdff4beSrobert 5*4bdff4beSrobertBackground 6*4bdff4beSrobert========== 7*4bdff4beSrobert 8*4bdff4beSrobertConsider the follow snippet which steadily happens in tests: 9*4bdff4beSrobert 10*4bdff4beSrobert 11*4bdff4beSrobert.. code-block:: cpp 12*4bdff4beSrobert 13*4bdff4beSrobert std::vector<std::pair<int, int>> v(SomeData()); 14*4bdff4beSrobert std::sort(v.begin(), v.end(), [](const auto& lhs, const auto& rhs) { 15*4bdff4beSrobert return lhs.first < rhs.first; 16*4bdff4beSrobert }); 17*4bdff4beSrobert 18*4bdff4beSrobertUnder this assumption all elements in the vector whose first elements are equal 19*4bdff4beSrobertdo not guarantee any order. Unfortunately, this prevents libcxx introducing 20*4bdff4beSrobertother implementatiosn because tests might silently fail and the users might 21*4bdff4beSrobertheavily depend on the stability of implementations. 22*4bdff4beSrobert 23*4bdff4beSrobertGoal 24*4bdff4beSrobert=================== 25*4bdff4beSrobert 26*4bdff4beSrobertProvide functionality for randomizing the unspecified behavior so that the users 27*4bdff4beSrobertcan test and migrate their components and libcxx can introduce new sorting 28*4bdff4beSrobertalgorithms and optimizations to the containers. 29*4bdff4beSrobert 30*4bdff4beSrobertFor example, as of LLVM version 13, libcxx sorting algorithm takes 31*4bdff4beSrobert`O(n^2) worst case <https://llvm.org/PR20837>`_ but according 32*4bdff4beSrobertto the standard its worst case should be `O(n log n)`. This effort helps users 33*4bdff4beSrobertto gradually fix their tests while updating to new faster algorithms. 34*4bdff4beSrobert 35*4bdff4beSrobertDesign 36*4bdff4beSrobert====== 37*4bdff4beSrobert 38*4bdff4beSrobert* Introduce new macro ``_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY`` which should 39*4bdff4beSrobert be a part of the libcxx config. 40*4bdff4beSrobert* This macro randomizes the unspecified behavior of algorithms and containers. 41*4bdff4beSrobert For example, for sorting algorithm the input range is shuffled and then 42*4bdff4beSrobert sorted. 43*4bdff4beSrobert* This macro is off by default because users should enable it only for testing 44*4bdff4beSrobert purposes and/or migrations if they happen to libcxx. 45*4bdff4beSrobert* This feature is only available for C++11 and further because of 46*4bdff4beSrobert ``std::shuffle`` availability. 47*4bdff4beSrobert* We may use `ASLR <https://en.wikipedia.org/wiki/Address_space_layout_randomization>`_ or 48*4bdff4beSrobert static ``std::random_device`` for seeding the random number generator. This 49*4bdff4beSrobert guarantees the same stability guarantee within a run but not through different 50*4bdff4beSrobert runs, for example, for tests become flaky and eventually be seen as broken. 51*4bdff4beSrobert For platforms which do not support ASLR, the seed is fixed during build. 52*4bdff4beSrobert* The users can fix the seed of the random number generator by providing 53*4bdff4beSrobert ``_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED=seed`` definition. 54*4bdff4beSrobert 55*4bdff4beSrobertThis comes with some side effects if any of the flags is on: 56*4bdff4beSrobert 57*4bdff4beSrobert* Computation penalty, we think users are OK with that if they use this feature. 58*4bdff4beSrobert* Non reproducible results if they don't use the fixed seed. 59*4bdff4beSrobert 60*4bdff4beSrobert 61*4bdff4beSrobertImpact 62*4bdff4beSrobert------------------ 63*4bdff4beSrobert 64*4bdff4beSrobertGoogle has measured couple of thousands of tests to be dependent on the 65*4bdff4beSrobertstability of sorting and selection algorithms. As we also plan on updating 66*4bdff4beSrobert(or least, providing under flag more) sorting algorithms, this effort helps 67*4bdff4beSrobertdoing it gradually and sustainably. This is also bad for users to depend on the 68*4bdff4beSrobertunspecified behavior in their tests, this effort helps to turn this flag in 69*4bdff4beSrobertdebug mode. 70*4bdff4beSrobert 71*4bdff4beSrobertPotential breakages 72*4bdff4beSrobert------------------- 73*4bdff4beSrobert 74*4bdff4beSrobertNone if the flag is off. If the flag is on, it may lead to some non-reproducible 75*4bdff4beSrobertresults, for example, for caching. 76*4bdff4beSrobert 77*4bdff4beSrobertCurrently supported randomization 78*4bdff4beSrobert--------------------------------- 79*4bdff4beSrobert 80*4bdff4beSrobert* ``std::sort``, there is no guarantee on the order of equal elements 81*4bdff4beSrobert* ``std::partial_sort``, there is no guarantee on the order of equal elements and 82*4bdff4beSrobert on the order of the remaining part 83*4bdff4beSrobert* ``std::nth_element``, there is no guarantee on the order from both sides of the 84*4bdff4beSrobert partition 85*4bdff4beSrobert 86*4bdff4beSrobertPatches welcome. 87