Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Notes on the user experience of new integer protocols

Notes on the user experience of new integer protocols

Xiaodi Wu
June 17, 2017

Introduction

The design, re-design, and implementation of SE-0104, a proposal to revise integer protocols in Swift, is now largely complete in shipping previews of Swift 4. As an exercise, I have used the new APIs to develop a set of additional numeric facilities. Here are some insights gained from that experience--and from two unpublished exercises to implement a BigInt type (one from scratch, one wrapping GMP)--as well as suggestions for improvement.

Topics

  1. Performing heterogeneous comparison with integer literals
  2. Conforming to _ExpressibleByBuiltinIntegerLiteral
  3. Overriding implementations of heterogeneous comparison and bit shift operators
  4. Defining the semantics of masking shifts for arbitrary-precision integers
  5. Using ArithmeticOverflow
  6. Initializing integers from a floating-point source

Heterogeneous comparison with integer literals

SE-0104 added heterogeneous comparison and bit shift operators to the language to improve the user experience (for example, you can now check if an Int value is equal to a UInt value).1

1 Similar enhancements for operations such as addition are not yet possible because a design is lacking for how to express promotion. When (if) Swift allows integer constants in generic constraints, this may become a more realistic prospect as promotion would then be expressible using generic constraints (e.g. func + <T, U>(lhs: T, rhs: U) -> U where T : FixedWidthInteger, U : FixedWidthInteger, T.BitWidth < U.BitWidth). This is meant to be an aside and is certainly outside the scope of correcting or incrementally improving upon SE-0104.

These operators behave as intended with concrete types, but comparisons in generic algorithms behave differently. This was encountered during review of the standard library's implementation of DoubleWidth, which in fact had a bug as a consequence of the following behavior:

func f() -> Bool {
  return UInt.max == ~0
}

func g() -> Bool {
  return UInt.max == .max
}

func h<T : FixedWidthInteger>(_: T.Type) -> Bool {
  return T.max == ~0
}

func i<T : FixedWidthInteger>(_: T.Type) -> Bool {
  return T.max == .max
}

f()          // Returns `true`.
g()          // Returns `true`.
h(UInt.self) // Returns `false`.
i(UInt.self) // Returns `true`.

The reason that h(_:) gives a surprising result is explained as follows:

  • Each concrete integer type implements its own overload of the homogeneous comparison operator, whereas protocol extension methods implement heterogeneous comparison operators. When an integer literal is used on the right-hand side of the comparison, the compiler looks first to the concrete type for an suitable implementation of the operator and finds the homogeneous overload. Therefore, it does not traverse the protocol hierarchy and instead infers the literal to be of the same type as the left-hand side.

  • In generic code, even if the most refined protocol implements its own overload of the homogeneous comparison operator, the compiler will look for all overloads of the operator by traversing the entire protocol hierarchy. Since heterogeneous comparison operators are defined somewhere along the hierarchy, the compiler will always find an overload that accepts the "preferred" integer literal type (Swift.IntegerLiteralType, aka Int) and infers the literal to be of type Int.

Therefore, in the invocation h(UInt.self), we are actually comparing UInt.max to ~(0 as Int). This is a surprising result, as evidenced by the fact that a bug nearly slipped into the standard library itself.

Suggestion for improvement

Based on the demonstration that the expression T.max == .max infers the correct type in both concrete and generic code, I would suggest that type inference for integer literals be changed based on the following (notional) rule:

  • Any use of an integer literal x should be equivalent to the use of an implicit member expression .init(integerLiteral: x).

This generally preserves the current behavior that an integer literal will preferentially be inferred to be of type IntegerLiteralType:

func j(_ x: Int) {
  print("Int", x)
}

func j(_ x: UInt) {
  print("UInt", x)
}

j(42)                        // Prints "Int 42".
j(.init(integerLiteral: 42)) // Prints "Int 42".

Intriguingly, T.init(integerLiteral: 0) is currently ambiguous where T : FixedWidthInteger:

func k<T : FixedWidthInteger>(_: T.Type) -> Bool {
  return (0 as T) == T.init(integerLiteral: 0)
  // error: ambiguous reference to member 'init(integerLiteral:)'
}

A minor re-design of related protocols appears to be necessary for implementation of this rule give the appropriate behavior. Namely:

  • In the protocol ExpressibleByIntegerLiteral, associatedtype IntegerLiteralType should be constrained to _ExpressibleByBuiltinIntegerLiteral & BinaryInteger (instead of _ExpressibleByBuiltinIntegerLiteral alone). This may give rise to a recursive constraint and require a workaround to implement at the present moment. Namely:
public protocol _ExpressibleByIntegerLiteral : ExpressibleByIntegerLiteral
where IntegerLiteralType : BinaryInteger { }
/* ... */
public protocol BinaryInteger : /* ... */, _ExpressibleByIntegerLiteral { }
  • In the protocol BinaryInteger, a default implementation is required as follows:
public init(integerLiteral value: IntegerLiteralType) {
  self.init(value)
}

_ExpressibleByBuiltinIntegerLiteral

For a numeric type modeling rational numbers, it is natural to conform that type to ExpressibleByIntegerLiteral. For instance, let x = 42 as Rational would create an instance of Rational<Int> with numerator 42 and denominator 1. A similar line of reasoning applies to a numeric type modeling complex numbers (and likely other types as well).

To conform to the protocol ExpressibleByIntegerLiteral, the type must implement an initializer of the form init(integerLiteral: U). However, U must conform to an underscored protocol _ExpressibleByBuiltinIntegerLiteral.

For a type such as Rational<T>, where the numerator and denominator are of type T, it is natural to have this initializer take an integer literal of type T. Currently, therefore, this requires that T be constrained to an underscored protocol. This is suboptimal for two reasons: (1) _ExpressibleByBuiltinIntegerLiteral is an underscored protocol not meant for public use; (2) it prevents an implementation of Rational<T> where T : _ExpressibleByBuiltinIntegerLiteral from having, say, arbitrary-precision integers as numerator and denominator (i.e., Rational<BigInt>) unless the arbitrary-precision integer type itself conforms to _ExpressibleByBuiltinIntegerLiteral.

Suggestion for improvement

From a user perspective, the semantics of ExpressibleByIntegerLiteral suggest that a generic type that has exclusively stored properties of type T where T : ExpressibleByIntegerLiteral should be conformable to ExpressibleByIntegerLiteral by implementing an initializer that accepts a literal value of type T--without being constrained to any underscored protocol. I suspect, however, that this is not a trivial detail to implement, especially without recursive protocol constraints.

Implementations of heterogeneous comparison and bit shift operators

In Swift, there is a distinction between default implementations of protocol requirements and protocol extension methods which are not requirements. Both are defined in extensions to protocols, but default implementations are dynamically dispatched and can be overridden by conforming types, while extension methods can be shadowed but never overridden. (For example, homogeneous == is a protocol requirement of Equatable, but homogeneous != is a protocol extension method that cannot be overridden.)

The paragraph above is meant to provide some background on existing features of the language, but it is meant neither to question their existence in the language nor to question the design of Equatable and Comparable, which are far outside the scope of improving the revised integer protocols.

The heterogeneous comparison and bit shift operators introduced in Swift 4 by SE-0104 are protocol extension methods.

Consider a custom BigInt type and the comparison (42 as BigInt) == (21 as UInt). There is an efficient way to perform that comparison which does not involve first converting the UInt value to a BigInt value. However, even if BigInt manually implements this specialized comparison operator, a generic algorithm implemented for all binary integers (say, for integer exponentiation) will use the less efficient standard library implementation of heterogeneous ==. By contrast, the same algorithm will use the most specialized implementation of homogeneous ==, because that function is a protocol requirement that is dynamically dispatched.

Suggestion for improvement

Heterogeneous <, <=, ==, >, >= should be requirements of the protocol on which they are now extension methods, as should heterogeneous masking shifts. That would permit conforming types to provide more specialized implementations. This may, however, increase the work of the type checker at compile time.

Semantics of masking shifts for arbitrary-precision integers

SE-0104 introduced two different types of bit shift operations for integers, called masking shifts and smart shifts.

Smart shifts, spelled << and >>, are protocol extension methods that always behave in a well-defined way when overshifting or undershifting. For example, x << -2 is now equivalent to x >> 2 in Swift 4, where previously the behavior was undefined.

However, because there is sometimes a performance cost for branches that handle overshifting and undershifting that cannot be optimized away, Swift now offers masking shifts, spelled &<< and &>>. As explained in SE-0104, "[a] masking shift logically preprocesses the right[-]hand operand by masking its bits to produce a value in the range 0...(x-1) where x is the number of bits in the left[-]hand operand." These semantics for masking shifts make sense when the number of bits in the left-hand operand is fixed, as is the case for all fixed-width integers.

However, all binary integers must implement &<< and &>>. For an arbitrary-width integer type (which, for various reasons, are best represented as sign-and-magnitude rather than two's-complement), the literal interpretation of those semantics is problematic. For example, most users might think that (1 as BigInt) << 1000 should not result in overshift. However, the number of bits in the left-hand operand is 2, and therefore a plausible interpretation of the semantics of &<< would have (1 as BigInt) &<< 1000 == 1. By extension, therefore, (1 as BigInt) << 1000 == 0; this is a counterintuitive result.

Suggestion for improvement

The semantics of smart shift should be clarified to state that the right-hand operand is preprocessed by masking its bits to produce a value in the range 0..<x where x is the maximum number of bits in a value of the same type as the left-hand operand. This is equivalent to viewing arbitrary-width integers for the purposes of bitwise operations as notionally infinite sequences of bits sign-extended from the two's-complement representation of the integral value.

For the purposes of implementation, BinaryInteger may require a new static property maxBitWidth, which would be equal to bitWidth for fixed-width integers and could be defined as Int.max for arbitrary-precision integers. Alternatively, add a new static property isFixedWidth to serve a purpose analogous to isSigned. The implementation of << and >> would then make use of the added properties to give the expected behavior.

ArithmeticOverflow

With SE-0104, the addWithOverflow family of arithmetic operations are not longer static. They have been renamed addingReportingOverflow and the like, and their return type has been changed from (T, Bool) to (partialValue: T, overflow: ArithmeticOverflow). ArithmeticOverflow is an enum with two cases, overflow and none. Initially, this may appear to be an improvement in terms of readability.

However, in actual use, ArithmeticOverflow is extremely lacking in ergonomics. Where previously it was possible to destructure the tuple and evaluate overflow by writing if overflow { ... }, it is now required to use a much more verbose incantation: if overflow == .overflow { ... }. There is little else one can do with an ArithmeticOverflow result besides converting it into a value of type Bool. When working with these operations repeatedly--and, chances are that if you need such an operation, you don't need it just once--this quickly becomes very cumbersome.

Inside the standard library, the ArithmeticOverflow values returned from *ReportingOverflow functions are created by calling an initializer that takes a Bool argument. Therefore, with every call to a *ReportingOverflow function, a Bool is converted to an ArithmeticOverflow, returned, then converted by the user back into a Bool. Worse, based on comments in the standard library, it appears that the compiler cannot currently elide these operations.

Suggestions for improvement

  1. Change the return type of *ReportingOverflow functions to (partialValue: T, overflow: Bool) (or, didOverflow) and eliminate the ArithmeticOverflow type. In practice, this would require deprecating the current functions and providing new overloads.

  2. Since the presence of type inference may cause (1) to be source-breaking even with proper deprecations, avoid creating a source-breaking change by naming the revised functions something else. Specifically, take the opportunity to improve the name of these functions, changing addingReportingOverflow to addingWithOverflowReporting (mutatis mutandis for the remaining functions). This avoids the "-ing -ing" clash and eliminates the nonsensical interpretation of the phrase "adding, reporting overflow by 42."

Integers from a floating-point source

The new BinaryInteger protocol has the following requirements:

  • init?<T : FloatingPoint>(exactly source: T)
  • init<T : FloatingPoint>(_ source: T)

However, in my experience, it does not appear possible (or at least, it is not apparent even after some careful thought) how to implement these requirements solely with the properties and methods required by FloatingPoint. There do, however, exist straightforward ways to convert BinaryFloatingPoint values to BinaryInteger values.

In the standard library, concrete integer types implement conversions to and from concrete built-in floating-point types. However, whether coincidentally or not, the standard library itself has not yet implemented these protocol requirements. At last check, the entire implementation of the first requirement was:

  public init?<T : FloatingPoint>(exactly source: T) {
    // FIXME(integers): implement
    fatalError()
  }

Suggestion for improvement

Consider changing the protocol requirement so that T is constrained as follows: T : BinaryFloatingPoint.

@dabrahams

This comment has been minimized.

Show comment Hide comment
@dabrahams

dabrahams Jul 18, 2017

@xwu what are the “various reasons” you think arbitrary precision integers are best represented as sign-magnitude? As far as I can tell, two's complement has only advantages and no drawbacks in this application.

@xwu what are the “various reasons” you think arbitrary precision integers are best represented as sign-magnitude? As far as I can tell, two's complement has only advantages and no drawbacks in this application.

@dabrahams

This comment has been minimized.

Show comment Hide comment
@dabrahams

dabrahams Jul 19, 2017

@xwu regarding making heterogeneous comparison a protocol requirement, I'm a little uncertain. It seems to me that any really good implementation of BigInt will have an inline representation for small integers that doesn't require a dynamic allocation, and so presumably the optimizer should be able to do a pretty good job with x < 42. Have you got some measurements that demonstrate a need for this? That would help justify a change.

@xwu regarding making heterogeneous comparison a protocol requirement, I'm a little uncertain. It seems to me that any really good implementation of BigInt will have an inline representation for small integers that doesn't require a dynamic allocation, and so presumably the optimizer should be able to do a pretty good job with x < 42. Have you got some measurements that demonstrate a need for this? That would help justify a change.

@xwu

This comment has been minimized.

Show comment Hide comment
@xwu

xwu Jul 19, 2017

@dabrahams You're right that I don't get notifications on gists. It's been a while since I've thought about these issues, but let's see if I can still answer intelligently:

On the "various reasons" for sign-and-magnitude representation

  • Efficient algorithms for multiplication of arbitrary-precision integers (Karatsuba, Toom-Cook, etc.) have been developed for unsigned values only; unless I'm mistaken, they cannot be applied to two's-complement representations of negative values. Therefore, any multiplication or division with large two's-complement BigInt operands may require complementing one or both operands and/or the result on-the-fly. (By contrast, bitwise operators that treat a BigInt as if it's in two's-complement notation are easy to implement and not computationally inefficient regardless of actual underlying representation.)

  • The sign bit in sign-and-magnitude representation requires one byte (or less, if Swift can be smart about packing the struct); in two's-complement representation, if the bits required to represent the magnitude take up an exact multiple of the "digit" bit width--typically, a "digit" would be a machine word--then the sign bit necessitates an entire extra word.

  • Negating a large BigInt is cheap in sign-and-magnitude representation when the underlying "digits" are copy-on-write; negating a large BigInt is not so much (although this is not, in and of itself, a hugely persuasive argument).

On protocol requirements for heterogeneous comparison

The gold standard, as far as I'm aware, for arbitrary-precision integer libraries is GMP. Julia, Python, R, Ruby all provide arbitrary-precision types by a wrapper to GMP. Although some languages (Ruby, for one, I believe) themselves provide an inline representation for small integers to avoid calling GMP, I'm not aware that GMP itself yet uses an inline representation for small integers other than zero. GMP does provide functions, though, for binary operations with one mpn_t (i.e. big integer) operand and one word-sized operand.

It should be possible to provide a high-quality Swift BigInt type that simply wraps GMP. One aim of these protocols should be to make it easier and not harder for end users to write their own efficient libraries. True, a sufficiently sophisticated wrapper could take the Ruby approach. However, given that the standard library itself has not yet fully solved the issue of efficient conversion in generic code between integer types, I would suggest that this is a heavy task to fall on a third-party author.

Owner

xwu commented Jul 19, 2017

@dabrahams You're right that I don't get notifications on gists. It's been a while since I've thought about these issues, but let's see if I can still answer intelligently:

On the "various reasons" for sign-and-magnitude representation

  • Efficient algorithms for multiplication of arbitrary-precision integers (Karatsuba, Toom-Cook, etc.) have been developed for unsigned values only; unless I'm mistaken, they cannot be applied to two's-complement representations of negative values. Therefore, any multiplication or division with large two's-complement BigInt operands may require complementing one or both operands and/or the result on-the-fly. (By contrast, bitwise operators that treat a BigInt as if it's in two's-complement notation are easy to implement and not computationally inefficient regardless of actual underlying representation.)

  • The sign bit in sign-and-magnitude representation requires one byte (or less, if Swift can be smart about packing the struct); in two's-complement representation, if the bits required to represent the magnitude take up an exact multiple of the "digit" bit width--typically, a "digit" would be a machine word--then the sign bit necessitates an entire extra word.

  • Negating a large BigInt is cheap in sign-and-magnitude representation when the underlying "digits" are copy-on-write; negating a large BigInt is not so much (although this is not, in and of itself, a hugely persuasive argument).

On protocol requirements for heterogeneous comparison

The gold standard, as far as I'm aware, for arbitrary-precision integer libraries is GMP. Julia, Python, R, Ruby all provide arbitrary-precision types by a wrapper to GMP. Although some languages (Ruby, for one, I believe) themselves provide an inline representation for small integers to avoid calling GMP, I'm not aware that GMP itself yet uses an inline representation for small integers other than zero. GMP does provide functions, though, for binary operations with one mpn_t (i.e. big integer) operand and one word-sized operand.

It should be possible to provide a high-quality Swift BigInt type that simply wraps GMP. One aim of these protocols should be to make it easier and not harder for end users to write their own efficient libraries. True, a sufficiently sophisticated wrapper could take the Ruby approach. However, given that the standard library itself has not yet fully solved the issue of efficient conversion in generic code between integer types, I would suggest that this is a heavy task to fall on a third-party author.

@stephentyrone

This comment has been minimized.

Show comment Hide comment
@stephentyrone

stephentyrone Jul 19, 2017

Hi Xiaodi! A couple quick notes:

Asymptotically, conversion between sign-magnitude and twos-complement is O(n), so it disappears into the O(n^(3/2)) or O(n lg* n) of even fast multiplication and division for sufficiently large integers. Also, you can definitely do all of these algorithms directly on twos-complement representations--I'll be happy to help you fill in the details. There is a range between ~128 bits and ~2K bits where conversion is a non-trivial factor, but as a tradeoff you get a simpler add and subtract in that range, as well as the possibility to make fixed-width operations (weakly) constant time without extra inefficiency, which isn't easy with sign-magnitude (this has less value than it sounds like at first, since perf-sensitive bignum computation tends to be done on fixed-width unsigned integer types, where this is a total non-issue).

I think(?) that it should also be possible to use sign-magnitude "under the covers", though this makes naive use of word(at: ) inefficient (I know this last point is something that Dave and I have discussed a little bit in the past).

GMP is superb asymptotically, but pretty bad for smallish fixed-size numbers, due to (a) function call overhead (b) the optimizer can't see through the function calls and (c) there are no fast-paths for small values, even if the optimizer could see through (these are precisely the issues that Dave is hinting at). This is roughly analogous to the distinction between BLAS and Eigen; short of teaching the compiler about BLAS calls as first-class objects for the optimizer, it'll never be competitive with templated optimizations for 3x3 matrices where the compiler can see exactly what it's doing. Not everything is present in Swift to make the later approach viable for bignums (yet?), but the protocols should definitely have that possibility in mind.

Hi Xiaodi! A couple quick notes:

Asymptotically, conversion between sign-magnitude and twos-complement is O(n), so it disappears into the O(n^(3/2)) or O(n lg* n) of even fast multiplication and division for sufficiently large integers. Also, you can definitely do all of these algorithms directly on twos-complement representations--I'll be happy to help you fill in the details. There is a range between ~128 bits and ~2K bits where conversion is a non-trivial factor, but as a tradeoff you get a simpler add and subtract in that range, as well as the possibility to make fixed-width operations (weakly) constant time without extra inefficiency, which isn't easy with sign-magnitude (this has less value than it sounds like at first, since perf-sensitive bignum computation tends to be done on fixed-width unsigned integer types, where this is a total non-issue).

I think(?) that it should also be possible to use sign-magnitude "under the covers", though this makes naive use of word(at: ) inefficient (I know this last point is something that Dave and I have discussed a little bit in the past).

GMP is superb asymptotically, but pretty bad for smallish fixed-size numbers, due to (a) function call overhead (b) the optimizer can't see through the function calls and (c) there are no fast-paths for small values, even if the optimizer could see through (these are precisely the issues that Dave is hinting at). This is roughly analogous to the distinction between BLAS and Eigen; short of teaching the compiler about BLAS calls as first-class objects for the optimizer, it'll never be competitive with templated optimizations for 3x3 matrices where the compiler can see exactly what it's doing. Not everything is present in Swift to make the later approach viable for bignums (yet?), but the protocols should definitely have that possibility in mind.

@xwu

This comment has been minimized.

Show comment Hide comment
@xwu

xwu Jul 20, 2017

@stephentyrone I stand corrected about direct use of fast multiplication algorithms with two's-complement representations. That is very interesting--one day, I will take you up on the offer of filling in the details (other real-life things are taking up my attention at the moment). Agree that Swift protocols should make it possible to implement bignums that have special representations for small numbers; however, at the moment, I still think it's important that it also doesn't stand in the way of wrapping GMP facilities such as heterogeneous comparison, which in that specific use case mitigates some of the problems you've outlined.

Owner

xwu commented Jul 20, 2017

@stephentyrone I stand corrected about direct use of fast multiplication algorithms with two's-complement representations. That is very interesting--one day, I will take you up on the offer of filling in the details (other real-life things are taking up my attention at the moment). Agree that Swift protocols should make it possible to implement bignums that have special representations for small numbers; however, at the moment, I still think it's important that it also doesn't stand in the way of wrapping GMP facilities such as heterogeneous comparison, which in that specific use case mitigates some of the problems you've outlined.

@lorentey

This comment has been minimized.

Show comment Hide comment
@lorentey

lorentey Jul 21, 2017

(Popping in as an author of a big integer package): it seems to me there is demand for both signed and unsigned big integers, so I want to/need to provide both variants. The sign-magnitude representation allows me to formulate the signed BigInt type in terms of BigUInt, instead of having to maintain two separate, slightly different implementations of all integer operations. It isn't clear to me yet if a two's complement representation for signed integers would allow for code reuse like that -- perhaps with gyb it would.

@stephentyrone: The revised words API allows reasonably efficient on-the fly conversion from sign-magnitude to two's-complement:

https://github.com/lorentey/BigInt/blob/swift4/sources/BigInt.swift#L141-L194

(Popping in as an author of a big integer package): it seems to me there is demand for both signed and unsigned big integers, so I want to/need to provide both variants. The sign-magnitude representation allows me to formulate the signed BigInt type in terms of BigUInt, instead of having to maintain two separate, slightly different implementations of all integer operations. It isn't clear to me yet if a two's complement representation for signed integers would allow for code reuse like that -- perhaps with gyb it would.

@stephentyrone: The revised words API allows reasonably efficient on-the fly conversion from sign-magnitude to two's-complement:

https://github.com/lorentey/BigInt/blob/swift4/sources/BigInt.swift#L141-L194

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment