xref: /openbsd-src/gnu/llvm/libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst (revision 4bdff4bed0e3d54e55670334c7d0077db4170f86)
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