Adding isPowerOf2 to BinaryInteger

(Ding Ye) #1

Hello everyone,

I would like to start a pitch about adding a property to stdlib for checking whether an integer is a power of two. Comments are welcome!

Introduction

Checking some mathematical properties of integers (e.g., parity, divisibility, etc.) is widely used in scientific and engineering applications. While Swift's standard library provides a convenient method isMultiple(of:) to test whether an integer is a multiple of another, there are other cases that are not yet supported. A frequently used one is to check if an integer is power of two. This pitch would like to address this problem by adding a computed property isPowerOf2 to the BinaryInteger protocol.

Motivation

It is commonly seen that programmers query if an integer is a power of two. Although the logic is conceptually simple, it would be substantially beneficial to have a standard implementation.

Commonality

There is a decade old question about How to check if a number is a power of 2 on Stack Overflow with ~200K views. There are public demands for such functionality, and it has been or will be officially supported by the libraries of many popular languages, such as C++20, D Programming Language, and .NET Framework.

Below are some uses in apple/swift.

// Example (1) - stdlib/public/core/HashTable.swift
internal struct _HashTable {
    internal init(words: UnsafeMutablePointer<Word>, bucketCount: Int) {
        _internalInvariant(bucketCount > 0 && bucketCount & (bucketCount - 1) == 0,
          "bucketCount must be a power of two")
        ...
    }
}
// Example (2) - stdlib/public/core/Integers.swift
extension BinaryInteger {
    internal func _description(radix: Int, uppercase: Bool) -> String {
        // Bit shifting can be faster than division when `radix` is a power of two
        let isRadixPowerOfTwo = radix.nonzeroBitCount == 1
        ...
    }
}
// Example (3) - stdlib/public/core/Misc.swift
func _isPowerOf2(_ x: UInt) -> Bool {
    // implementation
}
func _isPowerOf2(_ x: Int) -> Bool {
    // implementation very similar to above
}
// stdlib/public/core/Builtin.swift
internal func _roundUpImpl(_ offset: UInt, toAlignment alignment: Int) -> UInt {
    _internalInvariant(_isPowerOf2(alignment))
    ...
}

Readability

When programmers write code like n > 0 && n & (n - 1) == 0, they often need to leave some comments as well to indicate its underlying functionality, which is not intuitive to many people. As a result, n.isPowerOf2 is much more fluent.

Discoverability

This is very similar to the case of isMultiple. It can be suggested by IDE’s autocompletion. Notably, it works as a companion to isMultiple, and they can improve the discoverability of each other.

Performance

It can be more performant than user code, since the optimal implementation is a bit tricky and thus may not be obvious to some users (e.g., Example (2)).

Abstraction

Some users, especially those not familiar to the relevant type hierarchy, may have their own implementation targeting inappropriate types (e.g., the overloads for both Int and UInt in Example(3) causing duplicate code).

Proposed Solution

It could be a straightforward solution by adding a computed property to the BinaryInteger protocol.

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

Source Compatibility

Addictive change only.

Effect on ABI stability

Addictive change only.

Effect on API resilience

Addictive change only.

Alternative Considered

Given that we already have isMultiple(of:) in stdlib, a more generic form isPower(of:) instead of isPowerOf2 would be good for consistency considerations. This was discussed earlier when SE-0225 was being proposed.

In practice, however, querying for power of 2 is much more frequent than that of other numbers, for which there isn’t any known efficient implementation. If we’d go with such alternative, the solution would be something like:

extension BinaryInteger {
    @inlinable  
    public func isPower(of other: Self) -> Bool {
        if other == 2 {
           // short path
           return self > 0 && self & (self - 1) == 0
        }
        // long path
        ...
    }
}

8 Likes
(Jens Persson) #2

I wonder if the following might be more efficient (working also for binary floating point types):

extension FixedWidthInteger {
    var isPowerOfTwo: Bool { return nonzeroBitCount == 1 && self > 0 }
}
extension BinaryFloatingPoint {
    var isPowerOfTwo: Bool { return significandWidth == 0 && self > 0 } // Includes the negative powers of 2, ie 1/2, 1/4, 1/8, …
}

?

3 Likes
(Ding Ye) #3

Thank you and good point to put floating point types together, Jens! It is important to decide to what extend it covers, because it may affect the consistency of the big picture. I am thinking of extending isMultiple(of:) to support floating points as well. What do you think?

In terms of efficiency, nonzeroBitCount is a computed property. Its underlying implementation triggers ctpop, which actually counts the number of 1 bits. Although it takes advantages of SIMD when available, it still seems less performant than the proposed implementation.

1 Like
(Jens Persson) #4

I agree that it's important to consider the consistency of the big picture, but I'm not at all sure what the best API would be. For example, things like Float(1).isMultiple(of:0.1) are perhaps not as straight forward as one would like, but then again we already have eg:

print(Float(1).truncatingRemainder(dividingBy: 0.1)) // 0.09999999
print(Double(1).truncatingRemainder(dividingBy: 0.1)) // 0.09999999999999995
// Even though the "correct" (in R, not floating point) result would be 0.0,
// it only works as (naively) expected when using powers of two:
print(Float(1).truncatingRemainder(dividingBy: 0.125)) // 0.0
print(Double(1).truncatingRemainder(dividingBy: 0.125)) // 0.0

There might also be a bigger picture relation to the rounding methods. I've needed things like

x.roundedDownToClosestMultiple(of: 64)
x.roundedDownToClosestPowerOfTwo

for both floating point and integer types.

(Ding Ye) #5

Agree that when dealing with floating points, a focus on power of two rather than a general number makes more sense. If the community prefer isPowerOf2 to isPower(of:), we can apply it to floating points as you suggested. In fact, SE-0225 initially intended to introduce isOdd and isEven, but eventually got isMultiple(of:) instead... Let's see what other people in the community think.

As for the rounding methods, I prefer the signatures as you discussed earlier:
x.rounded(.up /*.down*/, toMultipleOf:)
x.rounded(.up /*.down*/, toPowerOf:)
Perhaps using .ceiling/.floor can be more precise. Because the terms .up/.down may be misunderstood by some users who want to get a strictly greater/less value.

1 Like
(Martin R) #6

A nice typo :slight_smile::

4 Likes
(Steve Canon) #7

There's some subtlety here (trading off optimality for small fixed-width integers, where x & x-1 is optimal, against bignums, where popcount looks better), but if this turns out to be important, this is an optimization that we would be able to do at the LLVM layer, anyway.

i.e. performance considerations shouldn't lead one to avoid popcount here.

1 Like
(Steve Canon) #8

Huh? The remainder operations are always exact, so they work "as expected" with any representable number, not only powers of two. The only issue here is that 0.1 isn't exactly representable.

(Steve Canon) #9

These are problematic for floating-point formats, because the value you will end up trying to round to will frequently not be exactly representable if the base value isn't the radix of the format:

let x: Float = 9999999980506447872
let y = x.rounded(.up, toMultipleOf: 10) // y = 9999999980506447872

What are you really trying to do with these operations?

2 Likes
(Jens Persson) #10

Sure, that's why I wrote

"correct" (in R, not floating point)

and

it only works as (naively) expected.


I understand how and why they would be problematic when designed/named like that, but (given a better name) one example use case might be a vector drawing app with a grid, where you want to snap a given point to the closest grid corner. This would work as (again, naively) expected for some but not all grid sizes, just like eg truncatingRemainder, simply because not all grid sizes are exactly representable.

(Steve Canon) #11

No, this is different from truncatingRemainder. The result of the remainder operation is always exact, so if the inputs are representable, no rounding occurs. The trouble with these is that even if the source value and the grid size that you're snapping to are exactly representable, the result may not be.

For simplicity, suppose we have a 1-digit decimal format:

20.rounded(.up, toMultipleOf: 9) // 30 (because 27 isn't representable)

Now, there's no more accurate result available, so this is OK for many purposes, but the API is quite misleading--most people would expect the result to actually be a multiple of 9. So my question is "how do you actually intend to use this, and can we design an API more narrowly focused on that task that isn't misleading like this?"

(Jens Persson) #12

That's my question too:

I understand how and why they would be problematic when designed/named like that, but (given a better name designed API) one example use case might be a vector drawing app with a grid, where you want to snap a given point to the closest grid corner.

(Steve Canon) #13

This use case doesn't make a lot of sense to me, because if you have a uniform grid, you implicitly are working with integer coordinates--simply using integers instead of floating-point seems like the simple escape valve here. There may be some scale+convert without intermediate rounding APIs that we're missing to enable that, but if so, let's add those!

(Jens Persson) #14

If I understand you correctly then adding something like the following rounding method for integers would make more sense then:

let result = myInteger.rounded(.down, toMultipleOf: 8)

?

Or do you mean that given my point's coordinate in floating point, I should scale it and round it to the closest integer using the existing rounding methods, then scale back?

(Steve Canon) #15

Yes, I think it makes considerably more sense for integers, because (barring overflow while rounding, which is rare), there's always a meaningful result that satisfies the implicit precondition.

I'm also saying that coordinates that are snapped to a grid usually work best if you store them as integer grid coordinates, and map them into floating-point display-space coordinates as late as possible.

1 Like
(Jens Persson) #16

The use case I envisioned would imply having vector shapes, probably paths/polybezier curves (consisting of control points that are probably represented as arrays of floating point coordinates). Not all of these control points are snapped, some might be, some not.

Snapping a control point would be like a mutating operation on a floating point coordinate, much like simply moving it to a new location (which happens to be that of the closest grid point in this case).

1 Like
(Steve Canon) #17

In that case, if I only had a single grid size, I would scale my coordinate system so the grid spacing was 1. If you have multiple incompatible grids, then you just need to eat the rounding (but if the space is small enough, or if you use Double, that's probably ok for almost all uses).

1 Like
#18

On the original topic, I agree that isPowerOf2 is far more commonly useful than checking for powers of other bases. However, from a mathematical perspective, it seems reasonable to include isPower(of:).

When SE–225 was reviewed, the core team chose to accept *only* isMultiple(of:), and not isEven, stating that the compiler should be able to optimize isMultiple(of: 2) as efficiently as it would isEven.

I would like to know if that is actually the case. Does the expression isMultiple(of: 2) compile down to the same instructions as (_lowWord & 1 == 0)?

My rudimentary investigations indicate it does not. Writing this code on Godbolt:

extension BinaryInteger {
    var isEven1: Bool {
        return _lowWord & 1 == 0
    }

    var isEven2: Bool {
        return isMultiple(of: 2)
    }
}

…yields vastly different results. Under -O optimization, the first version becomes 7 lines of assembly, while the second version apparently becomes 72.

So, if we can make isPower(of: 2) work as efficiently as isPowerOf2, then I’d be fine with just isPower(of:). But if the implementation ends up less efficient, then I think we should include the optimized power-of-2 version as well.

(Steve Canon) #19

It's important to keep in mind that "compiles down to X" is not a fixed thing. We can improve the optimizer. What matters from an API perspective is "does the compiler have all the information necessary to generate the optimal code" not "does it currently generate the optimal code". isMultiple(of: 2) has all the necessary information; to the extent that we don't get the desired codegen, that's a missed optimization, not a bad API design. Especially in a resilient, binary-stable world, we're designing API for the long-term, and current optimizer limitations should not be too worrisome, so long as we understand how to overcome them (on the other hand, magical thinking "the optimizer will save us" without knowing how is usually bad).

7 Likes
(Ding Ye) #20

Well, it is funny that way :slight_smile:

1 Like