SE-0368: StaticBigInt

Oh gosh, you’re absolutely right. This is the example that got stuck in my memory as .values:

let value: StaticBigInt = -0x8000000000000000_0000000000000000
  ///     value.bitWidth        //-> 128
  ///     value[0] as UInt64    //-> 0x0000000000000000
  ///     value[1] as UInt64    //-> 0x8000000000000000
  ///     value[2] as UInt64    

Can it be modeled as an infinite multi-pass sequence that also happens to have a subscript operator? It feels strange to index into a StaticBigInt as if it were itself a collection.

1 Like

I’m actually thinking we should require the as: parameter. The closest analogies to this API that I can think of are pointer APIs like UnsafeRawPointer.load(fromByteOffset:as:); these require a type-pinning parameter not for any technical reason, but purely for clarity.

An alternative might be to make StaticBigInt generic on some underlying unsigned integer type, and then make it a Collection with that element type:

extension UInt256: ExpressibleByIntegerLiteral {

  public init(integerLiteral value: StaticBigInt<UInt64>) {
    precondition(
      value.signum() >= 0 && value.bitWidth <= Self.bitWidth + 1,
      "integer literal '\(value)' overflows when stored into '\(Self.self)'"
    )
    self.words = Words()
    for index in value.indices {
      self.words[index] = value[index]
    }
  }
}

This would make the type and indexing a little less squishy, but I’m not sure the added complexity of a generic type is worth it.

While the subscript typing could be improved, I don’t think it’s a deal-breaker, and the proposal otherwise looks pretty solid to me.

3 Likes

Also, it would be nice to be able to pass an existential directly as an argument, rather than having to create a local function that just unwraps it into a type parameter so it can be used with value[n] as T.

  • SIMD types have subscripts, but they're not collections (or sequences).

  • BigInt wouldn't want an infinite sequence, and other types may not want the sign bit, so indexing depends on the use case.

  • Collection operations may produce subsequences or lazy wrappers, whereas Sequence operations may unexpectedly produce arrays.

  • https://belkadan.com/blog/2021/08/Swift-Regret-Sequence/


In which case, should both arguments be labeled? Would a method be preferred?

The problem with making it a collection is that we can't subscript past endIndex, in order to copy the sign extension. So we'd have to pre- or post-initialize the rest of the elements (if your example was a signed Int256 type).

1 Like

Would BigInt need additional compiler support to be able to be initialized with a pointer to immortal data in const section? Or StaticBigInt provides enough compiler/runtime support to implement BigInt in pure Swift code?

Is StaticBigInt binary compatible with immortal array buffer of words that BigInt could use? Would construction of BigInt from StaticBigInt require heap allocation and deep copy?

BTW, do array literals already use immortal buffers?

1 Like

Or, we make this subscript non-generic, returning UInt only, that being the preferred type anyway. The performance pitfall that can occur with using types of narrower bit width, and the lack of performance benefit (as I understand it) for this more complicated API for types of wider bit width, along with trivial composability, argue against the generic subscript bearing its own weight particularly if it requires these gymnastics to design.

2 Likes

The intention is for StaticBigInt to support the implementation of BigInt in a package. The comparison with StaticString exists because BigInt could then be moved into the standard library.


No, StaticBigInt uses the following ABI-neutral abstraction, to avoid the requirement of contiguously stored words on every platform.

Builtin.wordAtIndex_IntLiteral(
  _ value: Builtin.IntLiteral,
  _ index: Builtin.Word
) -> Builtin.Word

No, a simple implementation could store both a StaticBigInt and an array of words (which may be empty if unused).

public struct BigInt: SignedInteger {
  internal let _constant: StaticBigInt
  internal var _variable: [UInt]
}

It's a trade-off between branching on every storage access, and heap allocation on every construction.

Alternatively, apple/swift-numerics#84 stores a cache of digits for better performance.

private static let _digits: [BigInt] = (0 ... 36).map {

Yes, this is very tempting, as long as we don't give up on the infinite sign extension.

I can rewrite the examples and tests for 64-bit architectures only.

(32-bit testing isn't available on CI bots now, and on my computer the watchsimulator-i386 target displays an empty alert for every executable test.)

I don’t get it. What’s the downside to not including it in the first place?

Swift supports explicitly writing out a positive sign in front of an integer literal. This support is provided in the form of prefix + defined in the standard library for all types expressible by an integer literal. Excluding the function in question for StaticBigInt would drop that support, but only for integer literals that are used to express large integers. This would be a mystifying inconsistency that's bad for the end user experience.

7 Likes

I've created a pull request that uses only a "non-generic" subscript, in case the Language Workgroup decides to amend the proposal.

/// Returns a 32-bit or 64-bit word of this value's binary representation.
///
/// The words are ordered from least significant to most significant, with
/// an infinite sign extension. Negative values are in two's complement.
///
///     let negative: StaticBigInt = -0x0011223344556677_8899AABBCCDDEEFF
///     negative.signum()  //-> -1
///     negative.bitWidth  //-> 118
///     negative[0]        //-> 0x7766554433221101
///     negative[1]        //-> 0xFFEEDDCCBBAA9988
///     negative[2]        //-> 0xFFFFFFFFFFFFFFFF
///
///     let positive: StaticBigInt = +0x0011223344556677_8899AABBCCDDEEFF
///     positive.signum()  //-> +1
///     positive.bitWidth  //-> 118
///     positive[0]        //-> 0x8899AABBCCDDEEFF
///     positive[1]        //-> 0x0011223344556677
///     positive[2]        //-> 0x0000000000000000
///
/// - Parameter wordIndex: A nonnegative zero-based offset.
public subscript(_ wordIndex: Int) -> UInt { get }

For expressions like StaticBigInt(+42) and UInt64(+0xFFFF_FFFF_FFFF_FFFF), another alternative to waiting for a "plus sign" in the language is:

extension ExpressibleByIntegerLiteral {

  /// Creates a new instance from the given integer.
  ///
  /// If the value passed as `source` is not representable in this type, a
  /// runtime error may occur.
  ///
  /// - Parameter source: An immutable arbitrary-precision signed integer.
  public init(_ source: StaticBigInt) {
    let target = IntegerLiteralType(_builtinIntegerLiteral: source._value)
    self.init(integerLiteral: target)
  }
}

It was originally suggested as init(dynamicIntegerLiteral:) by @John_McCall. However, it's blocked by an issue where overflow can result in a zero-initialized value (without a compile-time or run-time error). I don't know how to fix that issue, and I didn't want to delay this proposal. I'm also unsure of the effect on source compatibility, if it's implemented without an argument label.

As I understand it, there is a general bug where we don't emit runtime diagnostics during generic initialization of integer literals. That is something we need to fix, but I don't think it's reasonable to block this on that.

3 Likes

This is a very useful addition which will add great flexibility. I like the idea of unblocking literals for external big int implementations without otherwise committing the language.

The latest version with a non-generic subscript is a good improvement. Simplicity wins.

1 Like

Hello Everyone,

The discussion of the generic subscript in this thread led to a proposed change to make that subscript non-generic. The author has amended the proposal with that change. The Language Workgroup is extending the review until next Tuesday to provide more time to discuss the amended proposal.

Thanks everyone,
Doug

6 Likes

Why are we proposing a StaticBigInt if we think an eventual BigInt will just "deprecate" it much like StaticString & String, if we could instead just jump to the BigInt addition?

1 Like

BigInt would not deprecate StaticBigInt. StaticBigInt is a tool for expressing arbitrary-precision integer literals, which can be useful for negotiating the boundary between the language syntax and the static/dynamic semantics of a specific type, which needn't be arbitrary-precision to benefit from the existence of StaticBigInt.

6 Likes

In addition, an eventual BigInt might not be in the standard library, but StaticBigInt has to be in order to provide this function for literals.

7 Likes

I almost forgot to review this. This has a +1 for me. Arbitrary length integer literals is a definite improvement over the status quo.

I realize it's not really up for discussion yet, but I absolutely support the future direction of moving the prefix + for positive numbers to the grammar instead of having it be an operator. I have never once used the prefix + operator on anything other than a literal.

3 Likes

This proposal has been accepted, thank you everyone!

Doug

2 Likes