BinaryInteger.isMultiple(of: 2) optimization

Development Standard Library
1

It is not uncommon to want to determine whether a number is even or odd. For integers backed by a binary representation (BinaryInteger), this can be done very quickly by checking the trailing bit.

I think the standard library should use this trick when checking for multiples of 2, rather than doing a remainder operation and comparing that to 0.

I’ve had some trouble building the Swift standard library on my machine and profiling this change, so I’m reluctant to submit a pull request directly. It seems considerably faster to use trailingZeroBitCount != 0 than isMultiple(of: 2) when measured using XCTest, for what that’s worth.

It also seems to compile much more compactly, though I doubt that benefit could be borne out in the same method.

1 Like
2

You must compile with optimizations and look at what's produced after specialization for concrete types. In the case of isMultiple(of: 2), it's already the most optimal possible result.

4 Likes
3

The optimal way to write this generically is with the _lowWord property:

func isMultipleOfTwo<T: BinaryInteger>(_ x: T) -> Bool {
  x._lowWord & 1 == 0
}

And there is indeed a substantial difference in the generated code, as seen in this godbolt link.

4

Only if the type is not know at compile time or the compiler can't specialise. In the specialised case, they produce the same assembly: Compiler Explorer

3 Likes
5

In other words, it is impossible for someBinaryInteger.isMultiple(of: 2) to be unoptimized. Unless the compiler has optimizations disabled, of course.

It’s always good to hear that the best-case scenario already exists.