Integer succeed and precede?

Evolution Discussion
1

I know older versions of Swift had successor() and predecessor() methods that went one unit forward or backward. They were kind of like C's ++ and -- operators, and so were retired when we moved away from C for-looping. Now I wonder if BinaryInteger should add similar operations in case it can model a single increment faster than the full addition routine with a second operand of 1. (Of course, an alternative is to check for 1 in the addition routine then special-case optimize.)

  • succeed: += 1
  • precede: -= 1

we could go further:

  • double: <<= 1
  • halve: >>= 1
  • reset: %= 1

(Can you figure out why I didn't add multiplication or division versions?)

2

Is there a reason LLVM wouldn’t already generate increment instructions whenever it would be beneficial?

3

I forgot:

  • makeOdd: |= 1
  • flipParity: ^= 1

(and there wouldn't be a bitwise-AND version.)

4

That could help with the default integer types, which map to the processor's integer primitives, but that wouldn't help with user-defined integer types, especially those that don't shadow processor primitives.

5

So you’re adding customization point (both protocol requirements and default implementation). Wouldn’t that be ABI breaking?

6 
func f(x : inout Int) {
    x += 1
}

generates this assembly with -O

output.f(x: inout Swift.Int) -> ():
        push    rbp
        mov     rbp, rsp
        mov     rax, qword ptr [rdi]
        inc     rax
        jo      .LBB1_2
        mov     qword ptr [rdi], rax
        pop     rbp
        ret
.LBB1_2:
        ud2

There's an inc instead of an add with a 1 immediate. Does this reflect the desired behavior or did you mean something else?

1 Like
7

Yes, but that wouldn't help with user-defined integer types.

8

As I understand it from threads here with posts from Swift big-wigs, adding a customization point with a corresponding default implementation is not ABI breaking. There have been several similar suggestions before. It is ABI-breaking to remove customization points (obviously) or to add new base or intermediate protocols (even if you maintain source compatibility).

1 Like
9

Could you give an example of a user-defined integer type that would benefit from this but does not compile to sufficiently optimized code today?

1 Like
10

There's nothing magical about adding or subtracting 1 that you can do significantly more efficiently than adding or subtracting, say, 2. Even if there were, the compiler should be able to see through what you're doing and optimize accordingly. I don't see any need for these operations on the protocol.

3 Likes
11

What's the concern here, that some custom type will have a fast-path for increment/decrement and without a customization point the compiler won't generate the best code?

If such a fast-path exists and is implemented by that type in the regular addition method, the optimizer will handle it fine. Here's an example—the conditional gets optimized away and the caller didn't have to do anything special, which is what we want:

struct SillyInt: BinaryInteger {
  private let value: Int

  // ...

  static func += (lhs: inout SillyInt, rhs: SillyInt) {
    if rhs.value == 1 {  // FAST PATH
      lhs.makeOneBigger()
    } else {
      lhs = SillyInt(lhs.value + rhs.value)
    }
  }

  @inline(never)  // so we see it in the output
  mutating func makeOneBigger() { self = .init(self.value + 1) }

  // ...
}

func myFunc() -> SillyInt {
  var mySillyInt: SillyInt = 5
  mySillyInt += 1
  return mySillyInt
}

Generated assembly:

output.myFunc() -> output.SillyInt:
        push    rbp
        mov     rbp, rsp
        push    r13
        push    rax
        // var mySillyInt: SillyInt = 5
        mov     qword ptr [rbp - 16], 5
        // mySillyInt += 1
        lea     r13, [rbp - 16]
        call    (output.SillyInt.makeOneBigger() -> ())
        mov     rax, qword ptr [rbp - 16]
        //
        add     rsp, 8
        pop     r13
        pop     rbp
        ret

Full godbolt output:

4 Likes