Adding isPowerOf2 to BinaryInteger

Evolution Pitches
24

I have done some experiments to compare the performance of different strategies, including isPowerOf2 (the straight forward solution), isPowerOf2_ctpop (the popcount implementation), and isPower(of:) (the more general interface). The table below shows the execution time (in sec) for type Int under the -O optimization level across a range of devices.

. iMac (3.8G Core i5) Macbook Pro (2.9G Core i7) iPhone X Max iPhone X iPhone 6S iPad Air (A1474)
isPowerOf2 0.083 0.098 0.121 0.148 0.194 0.305
isPowerOf2_ctpop 0.135 0.154 0.121 0.148 0.222 0.343
isPower(of: 2) 0.082 0.097 0.121 0.148 0.193 0.305
isPower(of: 3) 1.330 1.472 1.442 1.603 3.102 3.775

It can be seen that:

  • The popcount implementation can be as efficient as isPowerOf2 on some latest devices (e.g., iPhone X and iPhone X Max), but overall is less performant.
  • In addition, isPower(of: 2) (i.e., the slow path of the general interface isPower(of:)) is as efficient as isPowerOf2.
  • Moreover, the complexity of isPower(of: non2) is O(log(self) with base non2), and it can be an order of magnitude slower than the other three O(1) scenarios. I think it is acceptable because checking for powers of non-2 bases is much less commonly used, and there isn't any known efficient algorithm.

The results for other built-in integer types have a similar pattern to this one, so they are not given in this table. The code of such experiment is shown below:

import Foundation
extension BinaryInteger {
    // Proposed solution
    @inlinable public var isPowerOf2: Bool {
        return self > 0 && self & (self - 1) == 0
    }

    // Alternative solution #1
    //@{
    @inlinable public func isPower(of other: Self) -> Bool {
        if other == 2 { return self.isPowerOf2 } // fast path
        return self._isPower(of: other)          // slow path
    }
    @usableFromInline internal func _isPower(of other: Self) -> Bool {
       // If self is 1, then it is always true.
       if self == 1 { return true }
       // Now self cannot be 1, so it is false when other is 1.
       if other == 1 { return false }
       // If other is 0, then self must be 0; if other is -1, then self must be -1.
       if (other == 0) || (other < 0 && other + 1 == 0) { return self == other }

       // At this point, we have abs(other) > 1.
       guard self % other == 0 else { return false }
       let bound = self / other
       var x: Self = 1
       while (x > 0 ? x : 0 - x) < (bound > 0 ? bound : 0 - bound) { x *= other }
       return x == bound
    }
    //@}
}


extension FixedWidthInteger {
    // Alternative solution #2
    @inlinable public var isPowerOf2_ctpop: Bool {
        return self > 0 && self.nonzeroBitCount == 1
    }
}


func timing(title: String, op: ()->()) {
    let t1 = CFAbsoluteTimeGetCurrent() // <------ Start timing
    op()
    let t2 = CFAbsoluteTimeGetCurrent() // <------ End timing
    let d = String(format: "%.3f", t2 - t1)
    print("\(title):  execution time is \(d) s.")
}


func measure<T: FixedWidthInteger>(_ :T.Type, _ repeating: Int = 100_000_000) {
    timing(title: "\(T.self).isPowerOf2      ", op: {
        var n: T = T(1) << (T.bitWidth - 2)
        for _ in 0..<repeating {
            if n.isPowerOf2 {
                n += 1
            } else {
                n -= 1
            }
        }
        guard n != 0 else { exit(-1) }
    })
    timing(title: "\(T.self).isPowerOf2_ctpop", op: {
        var n: T = T(1) << (T.bitWidth - 2)
        for _ in 0..<repeating {
            if n.isPowerOf2_ctpop {
                n += 1
            } else {
                n -= 1
            }
        }
        guard n != 0 else { exit(-1) }
    })
    timing(title: "\(T.self).isPower(of: 2)  ", op: {
        var n: T = T(1) << (T.bitWidth - 2)
        for _ in 0..<repeating {
            if n.isPower(of: 2) {
                n += 1
            } else {
                n -= 1
            }
        }
        guard n != 0 else { exit(-1) }
    })
    timing(title: "\(T.self).isPower(of: 3)  ", op: {
        var n: T = T(1) << (T.bitWidth - 2)
        for _ in 0..<repeating {
            if n.isPower(of: 3) {
                n += 1
            } else {
                n -= 1
            }
        }
        guard n != 0 else { exit(-1) }
    })
}


measure(UInt8.self)
measure(UInt16.self)
measure(UInt32.self)
measure(UInt64.self)
measure(Int8.self)
measure(Int16.self)
measure(Int32.self)
measure(Int64.self)
3 Likes