Why does Swift use signed integers for unsigned indices?

Evolution Discussion
,
21

Right, but it's infinite "enough" that most real world code wouldn't notice, since most quantities programs deal with are not larger than the number of atoms in the universe. In Pascal, where there are arbitrary integer types with user-specifiable lower and upper bounds, mixed-type arithmetic formally uses the AIR model but most real implementations got away with using a machine word or 32-bit LONGINT as the practical limit. For Int128 itself in this implementation, overflow would still be a hard error.

Right shifts don't really change the math, since they can be modeled as just floor(x / 2**shift).

IMO, a quality implementation would have compiler support so that expression evaluation is optimized not to need larger-than-necessary intermediates, yeah.

2 Likes
22

Yet we use 2^128 attosecond intervals to be able representing billions ages of the universe :face_with_monocle:

I compared these three functions that check array index validity:

func isIndexValid1(index: Int, count: Int) -> Bool {
    precondition(count >= 0)
    return index >= 0 && index < count
}
func isIndexValid2(index: Int, count: Int) -> Bool {
    precondition(count >= 0)
    return UInt(bitPattern: index) < UInt(bitPattern: count)
}
func isIndexValid3(index: Int, count: Int) -> Bool {
    precondition(count >= 0)
    return ((index &- count) & ~index) < 0
}

The first is the naive one, the second uses @TellowKrinkle suggestion above and the third is the one I cooked. The second one is the shortest but in the third there are no logical cmp instructions (presumably fewer pipeline stalls?), which version is the fastest? Godbolt link.

Edit: this is the asm for ARM (with preconditions commented out):

func isIndexValid1(index: Int, count: Int) -> Bool {
//    precondition(count >= 0)
    return index >= 0 && index < count
//    0x100001e38 <+0>:  cmp    x0, #0x0
//    0x100001e3c <+4>:  ccmp   x0, x1, #0x0, ge
//    0x100001e40 <+8>:  cset   w0, lt
//    0x100001e44 <+12>: ret
}
func isIndexValid2(index: Int, count: Int) -> Bool {
//    precondition(count >= 0)
    return UInt(bitPattern: index) < UInt(bitPattern: count)
//    0x100001e3c <+0>: cmp    x0, x1
//    0x100001e40 <+4>: cset   w0, lo
//    0x100001e44 <+8>: ret
}
func isIndexValid3(index: Int, count: Int) -> Bool {
//    precondition(count >= 0)
    return ((index &- count) & ~index) < 0
//    0x100001e38 <+0>:  sub    x8, x0, x1
//    0x100001e3c <+4>:  bic    x8, x8, x0
//    0x100001e40 <+8>:  lsr    x0, x8, #63
//    0x100001e44 <+12>: ret
}
23

A cmp instruction wouldn't introduce pipeline stalls anymore than any other flags-setting instruction; it doesn't branch by itself if that's what you're thinking. So I would expect the shorter implementation to be better. But then again, I would also expect LLVM to be able to optimize all of these into the same single-instruction comparison.

3 Likes
24

Is this because it would limit the penalty of a misprediction to less than the cost of decoding those extra instructions?

25

There is no branch in the emitted assembly code (other than the precondition). It's just a number of instructions to evaluate linearly. So there is nothing to mis-predict.

1 Like
26

Oh, those js instructions are for the precondition()… and they’re present in all 3.

27

I measured the timing on ARM & Intel:

The code 
func isIndexValid1(index: Int, count: Int) -> Bool {
    index >= 0 && index < count
}

func isIndexValid2(index: Int, count: Int) -> Bool {
    UInt(bitPattern: index) < UInt(bitPattern: count)
}

func isIndexValid3(index: Int, count: Int) -> Bool {
    ((index &- count) & ~index) < 0
}

extension Array where Element == Int {
    subscript(subscript1 index: Int) -> Element {
        precondition(isIndexValid1(index: index, count: count))
        return index // fake it
    }
    subscript(subscript2 index: Int) -> Element {
        precondition(isIndexValid2(index: index, count: count))
        return index // fake it
    }
    subscript(subscript3 index: Int) -> Element {
        precondition(isIndexValid3(index: index, count: count))
        return index // fake it
    }
}

let items = (0 ... 10_000_000).map { $0 }
let n = 100
var total1 = 0
var start = Date()
for _ in 0 ..< n {
    for i in 0 ..< items.count {
        let item = items[subscript1: I]
        total1 &+= item
    }
}
let elapsed1 = Date().timeIntervalSince(start)

var total2 = 0
start = Date()
for _ in 0 ..< n {
    for i in 0 ..< items.count {
        let item = items[subscript2: I]
        total2 &+= item
    }
}
let elapsed2 = Date().timeIntervalSince(start)

var total3 = 0
start = Date()
for _ in 0 ..< n {
    for i in 0 ..< items.count {
        let item = items[subscript3: I]
        total3 &+= item
    }
}
let elapsed3 = Date().timeIntervalSince(start)
precondition(total1 == total2 && total1 == total3)
print(elapsed1, elapsed2, elapsed3)

Resulting timings (the smaller the better):

ARM:
    0.31936 (101%)
    0.31562 (100%) the fastest by a small margin
    0.32189 (102%) the slowest by a small margin
Intel:
    1: 0.89381 (112%)
    2: 1.06488 (133%) the slowest
    3: 0.79868 (100%) the fastest

Interestingly the trick version I managed to find makes a difference on Intel, but not on ARM. Surprisingly the naïve (1) version is faster than the clever (2) version on Intel.

2 Likes
28

For what it’s worth, it would not be useful to extrapolate from that data to performance in a real array, because it doesn’t do a load from memory that depends on the index. That data dependency can massively impact pipelining.

2 Likes
29

Unlike indices, time is a continuous value, and the value range is not the only thing to consider for continuous value. The resolution/precision is also an important metric.

1 Like
30

Not so surprising. You have to check the generated assembly, as the compiler are often better at understanding and optimizing naïve implementations than complex ones.

1 Like