libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst

   1 ==================================
   2 Unspecified Behavior Randomization
   3 ==================================
   4
   5 Background
   6 ==========
   7
   8 Consider the follow snippet which steadily happens in tests:
   9
  10
  11 .. code-block:: cpp
  12
  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
  18 Under this assumption all elements in the vector whose first elements are equal
  19 do not guarantee any order. Unfortunately, this prevents libcxx introducing
  20 other implementations because tests might silently fail and the users might
  21 heavily depend on the stability of implementations.
  22
  23 Goal
  24 ===================
  25
  26 Provide functionality for randomizing the unspecified behavior so that the users
  27 can test and migrate their components and libcxx can introduce new sorting
  28 algorithms and optimizations to the containers.
  29
  30 For example, as of LLVM version 13, libcxx sorting algorithm takes
  31 `O(n^2) worst case <https://llvm.org/PR20837>`_ but according
  32 to the standard its worst case should be `O(n log n)`. This effort helps users
  33 to gradually fix their tests while updating to new faster algorithms.
  34
  35 Design
  36 ======
  37
  38 * Introduce new macro ``_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY`` which should
  39   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 then
  42   sorted.
  43 * This macro is off by default because users should enable it only for testing
  44   purposes and/or migrations if they happen to libcxx.
  45 * This feature is only available for C++11 and further because of
  46   ``std::shuffle`` availability.
  47 * We may use `ASLR <https://en.wikipedia.org/wiki/Address_space_layout_randomization>`_ or
  48   static ``std::random_device`` for seeding the random number generator. This
  49   guarantees the same stability guarantee within a run but not through different
  50   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 providing
  53   ``_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED=seed`` definition.
  54
  55 This 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
  61 Impact
  62 ------------------
  63
  64 Google has measured couple of thousands of tests to be dependent on the
  65 stability of sorting and selection algorithms. As we also plan on updating
  66 (or least, providing under flag more) sorting algorithms, this effort helps
  67 doing it gradually and sustainably. This is also bad for users to depend on the
  68 unspecified behavior in their tests, this effort helps to turn this flag in
  69 debug mode.
  70
  71 Potential breakages
  72 -------------------
  73
  74 None if the flag is off. If the flag is on, it may lead to some non-reproducible
  75 results, for example, for caching.
  76
  77 Currently supported randomization
  78 ---------------------------------
  79
  80 * ``std::sort``, there is no guarantee on the order of equal elements
  81 * ``std::partial_sort``, there is no guarantee on the order of equal elements and
  82    on the order of the remaining part
  83 * ``std::nth_element``, there is no guarantee on the order from both sides of the
  84    partition
  85
  86 Patches welcome.