BinaryInteger.isMultiple(of: 2) optimization

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

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

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.

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

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.

Terms of Service

Privacy Policy

Cookie Policy