Uploaded image for project: 'WiredTiger'
  1. WiredTiger
  2. WT-11974

Take advantage of the fact that __wt_random is equivalent to flipping a coin 32 times

    • Type: Icon: Improvement Improvement
    • Resolution: Unresolved
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: None
    • StorEng - Refinement Pipeline

      I've noticed a few places calling __wt_random in a loop with repeated probabilites, to produce a logrithmic distribution. But that can be done more efficiently by taking the 32 bits returned and running them through count leading/trailing zeros/ones (doesn't matter which of the 4 combinations), which has an equivalent probability function to flipping a coin up to 32 times and counting the number of heads in a row (stopping at the first tails).

      For example, the code to choose a skiplist depth with probablity 1/4 of going deeper, could be just tmp = count_leading_zeros(_wt_random()); depth = min((tmp / 2) +1, 10);. And this code to pick a random sleep bucket could just be i = min(count_leading_zeros(_wt_random()), max);.

            Assignee:
            backlog-server-storage-engines [DO NOT USE] Backlog - Storage Engines Team
            Reporter:
            mathias@mongodb.com Mathias Stearn
            Votes:
            0 Vote for this issue
            Watchers:
            7 Start watching this issue

              Created:
              Updated: