<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/123855>123855</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [libc++] Question about __libcpp_timed_backoff_policy implementation
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          bobsayshilol
      </td>
    </tr>
</table>

<pre>
    I'm not sure if this is the right place to ask this, but I tried using `std::barrier` and observed large sleep calls that I wasn't expecting when calling `wait()`. The issue seems to occur because of the interaction of the 2 largest checks in `__libcpp_timed_backoff_policy`:

https://github.com/llvm/llvm-project/blob/635e154bbc94342080ccba583ff6fb16ea364f4b/libcxx/include/__thread/timed_backoff_policy.h#L28-L31

Once `__elapsed` goes over 64 *micro*seconds we then backoff at increasing intervals until it reaches 128 *milli*seconds, at which point we then cap it to only 8ms. This means that it can sleep for up to 64ms before dropping down to 8ms.

As an example repro case:

```c++
int main() {
  // In practice this doesn't get close to 1M entries, but play it safe.
 std::vector<chrono::nanoseconds> timings(1'000'000);
  std::size_t counter = 0;
  chrono::nanoseconds last_elapsed = chrono::nanoseconds::zero();

 auto capture_backoff_timings = [&](chrono::nanoseconds elapsed) {
    // Save elapsed time to avoid an additional now() call in __poll().
 last_elapsed = elapsed;
    // Add the elapsed time of this call to the timings.
    timings[counter] = elapsed;
    ++counter;
    return __libcpp_timed_backoff_policy{}(elapsed);
  };

  auto poll_for_200ms = [&] {
    // As cheap as we can make it - this is just an atomic load in std::barrier::wait().
    return last_elapsed > chrono::milliseconds(250);
 };

  __libcpp_thread_poll_with_backoff(poll_for_200ms, capture_backoff_timings);

  // Sanity check.
  assert(counter < timings.size());
  timings.resize(counter);

  // Convert timings to how long the sleeps are.
  std::vector<chrono::nanoseconds> sleeps(counter);
 std::adjacent_difference(timings.begin(), timings.end(), sleeps.begin());

 // Print largest sleep call.
  auto max_sleep = std::max_element(sleeps.begin(), sleeps.end());
  auto &os = std::cout;
 os << "max sleep: "
     << chrono::duration_cast<chrono::milliseconds>(*max_sleep).count()
     << "ms\n";

#if 0 // Print timings too for graphing.
  os << "timings = [";
  for (auto &t : timings) {
    os << t.count() << ',';
  }
  os << "]\nsleeps = [";
  for (auto &s : sleeps) {
    os << s.count() << ',';
  }
  os << "]\n";
#endif
}
```

Running this locally prints `max sleep: 59ms` (it's consistently in the 40-60ms range) and plotting out the timings (with 0 markers) gives this:


I don't know if `chrono::milliseconds(128)` is meant to be in `microseconds` or if it should be `chrono::milliseconds(8)` to match the final backoff value, or if this is intentionally a large wait? I couldn't see anything on the PR that introduced this code https://reviews.llvm.org/D68480, though the "Show Older Changes" button doesn't seem to work so it might be hidden in there.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJykV11v6zgO_TXKC9HAkT-SPOQht70BCsxiZmf2PZBlOtatLBmSnDTz6xeUP5LctncxWCBoE1kmD8nDI0p4r04Gccfybyx_WYg-NNbtSlt6cfWN0lYvSltdd6-Mr1swNoDvHYKqITTKg_IQGgSnTk2ATguJECwI_xYfM_4MZR_gFYJTWEHvlTkBKxIfKpbuWbovhXMKHSsSEKYCW3p0Z6xAC3dC8BqxAym0JjeCDF2EN4yvA-B7hzKQvUuDJm4ajV-ECoxvGN-yIlnCfxoE5X2P4BFbT_islL2DEqXoPYKtYwzKBHRCBmXNtMQHHD6AbFC-eVCGHByPWpWy645BtVgdSyHfbF0fO6uVvLIiodAS-jQhdJ5-8QPjh5MKTV8upW0ZP2h9nv49dc7-QBkYP5TalowfijTHVZ6VpdxmacaTTSJlKfJNWtdFXa4KFGmR1RltJSTv74wflJG6r5Dxw_EYGoeiYvzwGcBlw3j6G988_ZauBpi_G4lDXKhF57GicpwserBndFBkwPi-VdJZxvcepTWVhwtSigyMxkEEUEY6FLHGMZlnoT30JigNKoBDIRv0sOKbwZ7W6maPqCICXBolG-isMmH2IEVH71PdjL7CpvVUVOWhRWFGYqgAUpiRMLV10Hf0QpG1HkqsrUOonO06wlbZi6GHZGhIwN6DMIDvou00gsPOWZDC41xIKmr8SMa_0SfZE8JWKDMwDdiaFgGGUsOrgS6SiRqCsFYWR-KeMIDU1sdOWf0L0FBzzL3SaXGlcLyokeDB3CtnlME6lj7Lxlljh0UjjJ1SmH6HoFplTp7xzYrxdZIk098tSweAszmv_sZjAGl7qhWw9AWSadMXHkALHyaSxDe-hEILfyMxZjM7J9OiD5TbLvQOZ2KOqKNFEiJesPyF8c1XMCaa3uV9zvxf4ozTBkrHIEhnqyqqsagqRR0uNBh7GWtH2kGtfaQO0cNiTP2HcCfH6U9O91UVBePBrx01MpoPNm4YI12Or0_lyr-NZWD5y1eOiHfTrnnZYegdIf-VIq2_sTWl85a2yQCtz6UZakMpONbWHXmStD-V5GO2956kUXQgoiJQD7biDYnAT_MJ8aP3ISY_2FZJ0FZUlO4Ph0D8cVPv5WOMPxXj-wP3oprMUrLh-R3lH4O8pSqKZCz58aJCM2WN8c1jDqgzv2DsA7VvDDQqXIcjY4hBeI-Ooro12_NMBerDsUtuhZkeOhwfT5X_zOGzNWd0YXqJuNbYC2hrTpF0URU9CDcIyj9TlOHlTxDczIjqh5BowrFSdY0OjSTEUwglniaVpExOy2iq2-Lg5HHrXaBjnH84Et3pSL4NB8sbe1vxfhweEHFnhLSMGls0VIXPvM0Y7nDN1YimGS-sfzQrbR_GPfHRM9WVcd6K98EcSwk8H4k87bjPdtU7QYJ0lMKHnyrxQOr0e4S1nyOkDok1GeE--iAUnuXPhtxPiWQ8VTUkj_m8scbGk_PkRNcocxqy-hDXB53mU4boRcY3U6ICUOS3JrkTjpvBcA__5mXN-DP9vZOoD0DoeMifzUjs_wnHRzgTkz9H4_9vNLdM8xRNpWr6GvfP48NQhj97Y1TsTeVBW6LwFToqhqcx7IE9-bb1NI4xviFdXHuQ1njlA5qgrySj1OFZ8lSQWjthTkj4aZjutA1xQLZ9uD98yBYJHiTQCveGLubkpM7oh6l9nnr4iuXfXltxwuE8_sU823t0TyIEIRvqMs_4gVQvfilXWSKSvHySaSGfsq3kT6Lm5VORJHWZrLgocT0wmCX7V6jsMCi9GXuhiwaNXV9L_Wqa9GGcCOOkWOI4q8exddpdJGAdmaT5qrG9rmjjr-1P1qO4BNnETNaKJohp9D0L3SNJyGB8OvZoBjbDsKGvIMY7TTzf0gO80uSlqyFUjwjCXEMTyzXU9I8_x9HWBGerXtJYEccJWyE8VsLhWeHFL-k2sbTuxPjhpdhkmyQKbmP70wCbcf4XnQy_6wodPDfEFs84p8EzWHM3pNJViUK-WPcG3lLC2njHKxEaVVVoRuo5XC6qXVpt061Y4G61Ttd5kmV5tmh2myRbrbNsXa242KyTFZbFtq6Kdb1NZV5s04Xa8YTnyYrzJEnWabbMq2JbpNW6qldyleKWZQm2Quk5skW8ye1WPN3k-UKLErXfDb1Px_o4nceWXLhdvF2V_cmzLNHKh1uGFkEFHW-9d6_lL_DvHn28AYqSuuaXcxUoui4Q26OCL3qnd__4xhfjoSYZQzrv-H8DAAD__7Sz3Ls">