cc @stephentyrone

My recollection is that _precondition does not imply an assume, but we should also be able to deduce this from the fact that the type is unsigned and earlier we have upperBound > something, IIRC.

Yes, the whole modulo operation, where this optimization would come in is inside

if m.low < upperBound {
  … 
} 

Would such optimization be in the realm of Swift, or is this already some LLVM stuff?

It's up to Swift to make sure that the necessary information reaches the LLVM layer. It's up to LLVM to take advantage of it to do the optimization. So, both.

Could you please ping me on a PR that fixes this? I'd love to learn how that's done.

Is there a self-contained example that can go in this bug? Neither the precondition nor the `>` check are present in the linked assembly generation.

The relevant method is in extension of RandomNumberGenerator in this commit here. I'm not sure how to replicate _precondition outside of stdlib internals. The subtraction on line 102 should probably be overflowing for better performance. For completeness, here it is again with that fix:

@inlinable
  public mutating func next<T: FixedWidthInteger & UnsignedInteger>(
    upperBound: T
  ) -> T {
    _precondition(upperBound != 0, "upperBound cannot be zero.")
    var random: T = next()
    var m = random.multipliedFullWidth(by: upperBound)
    if m.low < upperBound {
      var t = 0 &- upperBound
      if t >= upperBound {
        t &-= upperBound
        if t >= upperBound {
          t %= upperBound
        }
      }
      while m.low < t {
        random = next()
        m = random.multipliedFullWidth(by: upperBound)
      }
    }
    return m.high
  }
}

Regular precondition is probably close enough. Or does that change the results significantly?

I suspect I have misinterpreted the situation. The Swift vs. C assembly comparison wasn't fair as I took a too narrow code snippet I suspected to be problematic and took out code that included important hints for the Swift compiler to perform optimization. Further, the original code was C++!

I re-did the Godbolt Compiler Explorer comparison again:

• Swift

• C++

I believe the generated instructions are largely equivalent.

Looking again at the original article by O'Neill, the modulo optimization provides a slight improvement on Large-Shuffle Benchmark, but on Small-Shuffle Benchmark the version with modulo optimization performs the same as Lemire's original version "Debiased Int Mult (t-opt)" in chart. Our benchmarks in SBS most closely correspond to small shuffle, which would explain why I saw no improvement from modulo optimization on our benchmarks.

@stephentyrone I guess I should come up with a synthetic benchmark to mimic O'Neill's Large-Shuffle and we could re-introduce the modulo optimization together with your rejection sampling. Could you please review my analysis and close this bug as invalid, if you agree?

I think the reason it's not optimized is because of the overflow checks. If you dump the llvm-ir, you can see that clang doesn't do this optimization itself, it just produces IR that LLVM can optimize.

If you change the example a bit and remove the `>=` checks: https://swift.godbolt.org/z/Psgou5 you get the optimization.