For a range like "A...B", will the compiler use the most efficient way to test the range? I was thinking of bit-twiddling to check faster, and want to make sure the compiler isn't already doing that.
The Swift frontend emits the check into LLVM IR in a fairly literal way and trusts LLVM to optimize it appropriately. Range-checking with an arbitrary range generally requires two comparisons or (essentially equivalently) a subtraction and a comparison, but some ranges can be done more efficiently, and LLVM knows a lot of those tricks. If there's one it's missing, our general approach would be to teach LLVM about it, not to handle it specifically in Swift.
LLVM does try to minimize branches. You should see that, under optimization, something like if (M...N).contains(x) is done by merging flags and doing a single branch. This is usually slightly better for performance, although, of course, this may vary by workload, architecture, and microarchitecture.
LLVM also knows the trick of checking whether a signed value is in the range 0...N or 0..<N using a single unsigned comparison. Doing that in a single comparison requires knowledge that N is non-negative, but LLVM will at least turn a sge 0 && a slt b into b sge 0 && a ult b. Again, this is usually slightly more efficient, but YMMV.
5 Likes
godbolt.org is an easy way to check your intuition here, especially if you understand assembly.
func check(_ value: Int) -> Bool {
(1...100).contains(value)
}
compiles into
output.check(Swift.Int) -> Swift.Bool: # @"output.check(Swift.Int) -> Swift.Bool"
dec rdi
cmp rdi, 100
setb al
ret
which aligns with John's explanation.
6 Likes
If the bounds are not known at compile time, like this:
func check1(_ value: Int, range: ClosedRange<Int>) -> Bool {
range.contains(value)
}
Then we get this output on Godbolt:
output.check1(_: Swift.Int, range: Swift.ClosedRange<Swift.Int>) -> Swift.Bool: # @"output.check1(_: Swift.Int, range: Swift.ClosedRange<Swift.Int>) -> Swift.Bool"
cmp rdi, rsi
setge cl
cmp rdx, rdi
setge al
and al, cl
ret
Note the presence of two cmp instructions.
However if our numbers are UInt and we use bit-twiddling code like this:
func check2(_ value: UInt, range: ClosedRange<UInt>) -> Bool {
(value &- range.lowerBound) <= (range.upperBound &- range.lowerBound)
}
Then we can get that down to just one cmp instruction:
output.check2(_: Swift.UInt, range: Swift.ClosedRange<Swift.UInt>) -> Swift.Bool: # @"output.check2(_: Swift.UInt, range: Swift.ClosedRange<Swift.UInt>) -> Swift.Bool"
sub rdi, rsi
sub rdx, rsi
cmp rdx, rdi
setae al
ret
I have not benchmarked to see if this is actually faster in practice. Maybe speculative execution is really good at predicting these branches or something.
Regardless, we can get the same single-cmp assembly from Int by bit-casting:
func check3(_ value: Int, range: ClosedRange<Int>) -> Bool {
let x = UInt(truncatingIfNeeded: value)
let a = UInt(truncatingIfNeeded: range.lowerBound)
let b = UInt(truncatingIfNeeded: range.upperBound)
return (x &- a) <= (b &- a)
}
Also worth noting that without the bit-twiddling, just changing the original code to use UInt, we get the original assembly with two cmp instructions:
func check4(_ value: UInt, range: ClosedRange<UInt>) -> Bool {
range.contains(value)
}
check2 is very slightly better, but not for reasons that have anything to do with speculative execution (there are no branches in either).
If you look at the actual dependency graphs, for check1 we get:
cmp rdi, rsi cmp rdx, rdi
| |
setge cl setge al
\ /
and al, cl
These are all single-cycle operations, and EFLAGS is renamed on anything recent, so there are no false dependencies. 3 cycles latency, and whatever throughput 5 basic integer ops gets you.
For check2:
sub rdi, rsi sub rdx, rsi
\ /
cmp rdx, rdi
|
setae
Also 3 cycles latency, but only 4 basic integer ops and the dependency chain is no more complex. So check2 is effectively never slower, and up to 20% faster in contexts that are bound by integer execute resources (those are somewhat rare, however; usually this is roughly break-even). When there are actual branches, then check2 can be more of a win.
Also note that the compiler can do this optimization for you if the right invariants are communicated to the LLVM layer. As a concrete example of this, I did exactly this unsigned transform late in 6.2 as a stopgap for Span bounds-checking performance, but in 6.3 we added _assumeNonNegative where needed and were able to remove the use of unsigned and still get a single comparison.
5 Likes
Switching to aarch64 I get these results on Godbolt:
output.check1(_: Swift.Int, range: Swift.ClosedRange<Swift.Int>) -> Swift.Bool: // @"output.check1(_: Swift.Int, range: Swift.ClosedRange<Swift.Int>) -> Swift.Bool"
cmp x0, x1
ccmp x2, x0, #8, ge
cset w0, ge
ret
output.check2(_: Swift.UInt, range: Swift.ClosedRange<Swift.UInt>) -> Swift.Bool: // @"output.check2(_: Swift.UInt, range: Swift.ClosedRange<Swift.UInt>) -> Swift.Bool"
sub x8, x0, x1
sub x9, x2, x1
cmp x9, x8
cset w0, hs
ret
Again I don’t know if one is better than the other in practice.
Tradeoff is more subtle on arm64. Best thing for most users is to communicate the correct invariants to LLVM and let the backend work it out.
Note that an integer comparison is basically the same operation as an integer subtraction, it just sets flags (which subtraction also does on many ISAs, or at least can) and throws away the result. Turning comparisons into subtractions is not itself an optimization unless the hardware is very weird. The latency improvement Steve is talking about arises because the x86 ISA makes it awkward to merge flags after successive comparisons, not because comparisons should be thought of as expensive in and of themselves. But still, maybe LLVM could be better here.
Also, there is very little code in the world that needs to care about performance at the level of single-cycle latencies like this. Even code that does this operation in a tight loop with many iterations is likely doing it to values loaded from memory, and so the memory latency is ultimately what will dominate performance.
6 Likes
I was looking at this issue and could not find a way to convince LLVM to output the other containment-check code that in cases can be more performant.
Looked to me LLVM just doesn't know or refuses to do the supposed optimization. Which is weird considering I know LLVM knows lots of these optimizations.
However it wasn't all for nothing, still put up this PR for teaching LLVM that range.lowerBound<=range.upperBound which helps it shave some instructions and small (likely well-predicted) branches.
Open to suggestions if there are better ways to implement this.
The change is pretty small in terms of having an effect but in some micro-benchmarks I have personally felt the impact of that small branch that for-in loops can create for the range check, versus just a while-loop.
2 Likes