87 lines · plain
1==================================2Unspecified Behavior Randomization3==================================4 5Background6==========7 8Consider the follow snippet which steadily happens in tests:9 10 11.. code-block:: cpp12 13 std::vector<std::pair<int, int>> v(SomeData());14 std::sort(v.begin(), v.end(), [](const auto& lhs, const auto& rhs) {15 return lhs.first < rhs.first;16 });17 18Under this assumption all elements in the vector whose first elements are equal19do not guarantee any order. Unfortunately, this prevents libcxx introducing20other implementations because tests might silently fail and the users might21heavily depend on the stability of implementations.22 23Goal24===================25 26Provide functionality for randomizing the unspecified behavior so that the users27can test and migrate their components and libcxx can introduce new sorting28algorithms and optimizations to the containers.29 30For example, as of LLVM version 13, libcxx sorting algorithm takes31`O(n^2) worst case <https://llvm.org/PR20837>`_ but according32to the standard its worst case should be `O(n log n)`. This effort helps users33to gradually fix their tests while updating to new faster algorithms.34 35Design36======37 38* Introduce new macro ``_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY`` which should39 be a part of the libcxx config.40* This macro randomizes the unspecified behavior of algorithms and containers.41 For example, for sorting algorithm the input range is shuffled and then42 sorted.43* This macro is off by default because users should enable it only for testing44 purposes and/or migrations if they happen to libcxx.45* This feature is only available for C++11 and further because of46 ``std::shuffle`` availability.47* We may use `ASLR <https://en.wikipedia.org/wiki/Address_space_layout_randomization>`_ or48 static ``std::random_device`` for seeding the random number generator. This49 guarantees the same stability guarantee within a run but not through different50 runs, for example, for tests become flaky and eventually be seen as broken.51 For platforms which do not support ASLR, the seed is fixed during build.52* The users can fix the seed of the random number generator by providing53 ``_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED=seed`` definition.54 55This comes with some side effects if any of the flags is on:56 57* Computation penalty, we think users are OK with that if they use this feature.58* Non reproducible results if they don't use the fixed seed.59 60 61Impact62------------------63 64Google has measured couple of thousands of tests to be dependent on the65stability of sorting and selection algorithms. As we also plan on updating66(or least, providing under flag more) sorting algorithms, this effort helps67doing it gradually and sustainably. This is also bad for users to depend on the68unspecified behavior in their tests, this effort helps to turn this flag in69debug mode.70 71Potential breakages72-------------------73 74None if the flag is off. If the flag is on, it may lead to some non-reproducible75results, for example, for caching.76 77Currently supported randomization78---------------------------------79 80* ``std::sort``, there is no guarantee on the order of equal elements81* ``std::partial_sort``, there is no guarantee on the order of equal elements and82 on the order of the remaining part83* ``std::nth_element``, there is no guarantee on the order from both sides of the84 partition85 86Patches welcome.87