Is there any advantage with Int.quotientAndRemainder(dividingBy:) vs. using `/` and `%`?

Using Swift
1

I assume .quotientAndRemainder(dividingBy:) calculate both quotient and remainder values with fewer instructions then doing it separately with / and %?

For my use case, the code look a little less clear with .quotientAndRemainder(dividingBy:):

extension Int {
    // collect digits in reverse order, ignoring negative sign
    var digitsInReverse: [Int] {
        if self == 0 {
            return [0]
        }
        var result = [Int]()
        var n = abs(self)
        while (n > 0) {
            let (q, r) = n.quotientAndRemainder(dividingBy: 10) // is there anyway to assign quotient to `n` directly here?
            result.append(r)
            n = q
        }
        return result
    }
}

vs.

extension Int {
    // collect digits in reverse order, ignoring negative sign
    var digitsInReverse: [Int] {
        if self == 0 {
            return [0]
        }
        var result = [Int]()
        var n = abs(self)
        while (n > 0) {
            result.append(n % 10)
            n = n / 10
        }
        return result
    }
}
2

For "normal" types like Int, no, the two are equivalent, because the optimizer knows that division and remainder forma a pair. For integer types implemented in a library, there could be a difference.

(It's worth noting that neither of these will actually result in a divide instruction, because the compiler also knows that instead of dividing by 10 you can do a fixed-point multiplication by 1/10 and fixup rounding for negative inputs.)

4 Likes
3

If you use sequence and need to copy the variable you're mutating, into a constant, then quotientAndRemainder gets around the problem of already having something named quotient. But defer saves a line of code. I have no preference between the two if the performance is in fact identical.

public extension UnsignedInteger {
  /// The digits that make up this number.
  /// - Parameter radix: The base the result will use.
  func digits(radix: Self = 10) -> [Self] {
    sequence(state: self) { quotient in
      guard quotient > 0
      else { return nil }

      defer { quotient /= radix }
      return quotient % radix
    }
    .reversed()
  }
}

public extension UnsignedInteger {
  /// The digits that make up this number.
  /// - Parameter radix: The base the result will use.
  func digits(radix: Self = 10) -> [Self] {
    sequence(state: self) { quotient in
      guard quotient > 0
      else { return nil }

      let division = quotient.quotientAndRemainder(dividingBy: radix)
      quotient = division.quotient
      return division.remainder
    }
    .reversed()
  }
}
4

Worth noting that if one cares about performance (which is presumably why one is fussing with this at all), all of these digit-serial implementations are somewhat problematic, because there's a loop-carried dependency on the division that prevents an out-of-order CPU from extracting much/any ILP. What you would really like to do is split the input into groups of a few digits using division by 100, 1000, or 10000, and then extract individual digits from those (if you use groups of two or even three digits, a table lookup instead of division/remainder is pretty attractive).

You can also use a binary-tree approach for maximum ILP, but that only really matters if you have a distribution of inputs that's somewhat uniform, which is unusual.

4 Likes
5

Is this optimization only when the divisor 10 is a compile time constant? There is no such optimization if the divisor is a variable as @anon9791410 does with radix?

6

I actually want the digits in reverse order, but I have question, please see comment in code:

extension UnsignedInteger {
    func digitsR(radix: Self = 10) -> UnfoldSequence<Self, Self> {    // Q: since UnfoldSequence conform to Sequence
//    func digitsR<S>(radix: Self = 10) -> S where S: Sequence, S.Element == Self {    // How to return Sequence instead?
        sequence(state: self) { (quotient) -> Self? in
            guard quotient > 0
            else { return nil }

            defer { quotient /= radix }
            return quotient % radix
        }
    }
}
7

Such an optimization is possible, but most compilers, including swiftc, do not perform it today. The usual thing you see for formatting like this is to have a couple codepaths for the most common cases.