I missed posting about the last couple of releases of Swift before it was open sourced, but now that I have some time to write a couple of posts over the holidays, here’s a one about this sentence in the release notes for 2.0 beta 5:

For consistency and better composition of generic code, ArraySlice indices are no longer always zero-based but map directly onto the indices of the collection they are slicing and maintain that mapping even after mutations.

Why is this interesting enough to write a whole post over? It has to do with this bit of code that you see written from time to time:

// iterate over the indices in a collection:
for idx in 0..<someCollection.count {
  // use someCollection[idx] in some way
  // that can't be done via for x in someCollection
}

What’s wrong with that? Well, if someCollection is an Array, nothing. Hmm, maybe readability. All collections have an indices property that does the same thing. If you think

for idx in 0..<someCollection.count

is just as readable as

for idx in someCollection.indices

then I put it to you that all these C derivatives have addled your brain. If you remain unconvinced, the rest of this article is probably going to be a bit like this cartoon.

(if you find yourself wanting all but the last index, or all but the first, remember Range is a collection, so you can write things like someCollection.indices.dropLast())

Anyway, readability aside, the problems come when you try and make your loop generic. For example, take everyone’s favorite way to start an algorithms text book, a binary search. Here’s a version for arrays:

extension Array
  // this seems to be the indentation style
  // found in the open-sourced the Swift code...
  where  
  Generator.Element: Comparable {
    /// Returns an index of an element in `self` which 
    /// is equal to `element`, or `nil` if such value
    /// is not found.
    ///
    /// - Requires: elements of `self` are ordered by <
    ///
    /// - Complexity: O(log(`self.count`)).
    public func binarySearch(
      element: Generator.Element
    ) -> Int? {
        var left = 0
        var right = count - 1

        while left <= right {
            let mid = (left + right) / 2
            let candidate = self[mid]

            if candidate < element {
                left = mid + 1
            }
            else if element < candidate {
                right = mid - 1
            }
            else {
                return mid
            }
        }
        // Not found
        return nil
    }
}

(you'd probably want to implement a version that takes an isOrderedBefore predicate, then implement this one in terms of that one, but let's ignore that for now)

Binary searches are notoriously hard to get right, and this one contains at least one bug – that I've left in deliberately to talk about later – as well as the ones I added accidentally that you can let me know about.

A first trainer-wheels attempt to make this generic might be to switch the extension to be of CollectionType, and constrain the index to be of type Int:

extension CollectionType 
  where 
  Index == Int, 
  Generator.Element: Comparable {
    // same as before
}

This seems like it's working at first. You can now use it on ContiguousArray, UnsafeBufferPointer and, up until it changed, ArraySlice. It won't work with random-access-indexed collections that don't use integer indices, but there aren't many of those around. But it makes a big assumption that the collection is zero based. As I mentioned in a previous changes post when collections all became sliceable, this became a very shakey assumption, and now it doesn't even apply to array slices. It's also not something the type system will help you find – you'd discover it at runtime when your out-of-bounds error traps.

You could fix it while keeping the constraint to integer indices, but at this point you may as well rip the band-aid off and just make it fully generic. This also helps you spot all the places where you need to fix your zero-based assumption. It starts easy enough…

extension CollectionType 
  where
  Index: RandomAccessIndexType, 
  Generator.Element: Comparable {
    public func binarySearch(
      element: Generator.Element
    ) -> Index? {
        // instead of 0 for the start:
        var left: Index = startIndex
        // and instead of count - 1 for the end:
        var right: Index = endIndex.predecessor()

but then we hit trouble:

// error: binary operator '+' cannot be
// applied to two 'Self.Index' operands
let mid = (left + right) / 2

You can't just add two indices together. Think about non-contiguous storage like a node-based container like a linked list or a tree. You can't just add together two node pointers. Or for a random-access example, what about ReverseRandomAccessCollection, which is a wrapper around a random-access collection, and has an opaque index type. How could you add two of those together?

Really there are two concepts here – indices, and distances between indices. You can always count, as an integer, the number of times you need to call successor() on an index to get to a later index. This is the distance between them. You can do mathematical operations on distances – you can go twice as far from an index, or advance as far from one index as another is from the start. All indices have this ability, but bi-directional indices can have negative distances (the number of times you'd need to call predecessor()), and random-access indices can move by a distance in constant time.

When we had an integer index on a zero-based collection, a handy trick we were relying on is that any index is also the distance of that index from the start. So when we wrote let mid = (left + right) / 2, really this was saying that the mid-point was the average of the distance from the start of the two indices. But now we want our algorithm to work not just on zero-based integer indices but kind of random-access index (random-access because if you can't move around in constant time, you may as well do a linear search).

You could rewrite that generically as:

let mid = startIndex.advancedBy(
           (  startIndex.distanceTo(left) 
            + startIndex.distanceTo(right)
          ) / 2)

but this would be a bit silly. Instead, you can just take the distance from the left to the right, halve that, and add it to the start. We can add this ability to Range, to give us a mid-point property (and which also fixes a bug, if you followed the earlier link):

extension Range {
    var mid: Element {
        return startIndex.advancedBy(
          startIndex.distanceTo(endIndex) / 2
        )
    }
}

which we can use in a fully generic binary search:

extension CollectionType 
  where 
  Index: RandomAccessIndexType {
    public func binarySearch(
      element: Generator.Element, 
      isOrderedBefore: (Generator.Element,Generator.Element)->Bool
    ) -> Index? {
        var searchRegion = self.indices

        while !searchRegion.isEmpty {
            let mid = searchRegion.mid
            let candidate = self[mid]

            if isOrderedBefore(candidate,element) {
                searchRegion.startIndex = mid + 1
            }
            else if isOrderedBefore(element,candidate) {
                searchRegion.endIndex = mid
            }
            else {
                return mid
            }
        }
        return nil
    }
}

extension CollectionType 
where Index: RandomAccessIndexType, 
      Generator.Element: Comparable 
{
    public func binarySearch(
      element: Generator.Element
    ) -> Index? {
        return binarySearch(element, isOrderedBefore: <)
    }
}

Note, we can still write searchRegion.startIndex = mid + 1 because RandomAccessIndexType conforms to Strideable, which has this definition of +

public func +<T : Strideable>(lhs: T, rhs: T.Stride) -> T

that allows you to add a distance (which is an indices' stride) to an index. There's a matching definition with the lhs and rhs flipped so you can write it the other way around.

This version makes a couple of other changes. It combines the left and right indices into a Range, searchRegion. I think this helps readability a bit – !searchRegion.isEmpty is a bit nicer than left<=right – and also allows us to use our mid extension. But more importantly, this rewrite ditches the other trick we were relying on when the index was an integer – you can go one past the end or ahead of the start without any consequences. When your index is an integer, who cares if you decrement it from 0 to -1. But some indices don't take kindly to going past their limit (try calling "hello".endIndex.successor()). So to make the algorithm properly generic, it needed a rewrite to avoid this being a possibility.

Talking of readability, 2.1b5 added some additional slicing methods, so instead of:

a[a.startIndex...idx]
a[a.startIndex..<idx]
a[idx..<a.endIndex]

you can now write:

a.prefixThrough(idx)
a.prefixUpTo(idx)
a.suffixFrom(idx)

It's kinda fun, though probably a bit cute to be used in production code, to write Python-style one-sided subscript operations for these as well:

postfix operator ..< { }
prefix operator ..< { }
prefix operator ... { }

struct RangeStart<I: ForwardIndexType> { let start: I }
struct RangeToEnd<I: ForwardIndexType> { let end: I }
struct RangeThroughEnd<I: ForwardIndexType> { let end: I }

postfix func ..< <I: ForwardIndexType>(lhs: I) -> RangeStart<I>
{ return RangeStart(start: lhs) }

prefix func ..< <I: ForwardIndexType>(rhs: I) -> RangeToEnd<I>
{ return RangeToEnd(end: rhs) }

prefix func ... <I: ForwardIndexType>(rhs: I) -> RangeThroughEnd<I>
{ return RangeThroughEnd(end: rhs) }

extension CollectionType {
    subscript(r: RangeStart<Self.Index>) -> SubSequence {
        return self.suffixFrom(r.start)
    }
    subscript(r: RangeToEnd<Self.Index>) -> SubSequence {
        return self.prefixUpTo(r.end)
    }
    subscript(r: RangeThroughEnd<Self.Index>) -> SubSequence {
        return self.prefixThrough(r.end)
    }
}

which then means you can write:

let a = [1,2,3,4]
a[1..<] // [2,3,4]
a[..<2] // [1,2]
a[...2] // [1,2,3]

You could even define pattern-matching versions, for use in a switch statement:

infix operator ~= {
    associativity none
    precedence 130
}

func ~=<I: ForwardIndexType where I : Comparable>(pattern: RangeStart<I>, value: I) -> Bool {
    return value > pattern.start
}

func ~=<I: ForwardIndexType where I : Comparable>(pattern: RangeToEnd<I>, value: I) -> Bool {
    return value < pattern.end
}

func ~=<I: ForwardIndexType where I : Comparable>(pattern: RangeThroughEnd<I>, value: I) -> Bool {
    return value <= pattern.end
}

so you can write:

for i in [9, 10, 11] {
    switch i {
    case ..<10: print("below 10")
    case ...10: print("10 or below")
    case 2..<: print("2 or more")
    default: fatalError()
    }
}

If you're not familiar with ~=, check out Ole's series of posts about pattern matching, it's pretty powerful.

Patient: Doctor doctor, it hurts when I do this.
Doctor: Well, don’t do that.

On twitter, I wrote:

Your reminder that building arrays with reduce, while fun, is accidentally quadratic.

I was surprised at how surprising some found this. Quite a few people suggested the reduce version could be changed to not do the array copy (I don’t think it can). Some suggested maybe + could be optimized so it doesn’t perform a copy (I don’t think that it could easily, as we’ll see shortly).¹

In other feedback, a few commented on the previous post about linked lists. Why implement an outdated data structure? What’s the point when we have arrays?

So, you know how sometimes I mention this isn’t a blog about Mac and iOS programming? It’s not a blog about Mac and iOS programming! Don’t put a enum-based linked list into your app just because I happen to find it interesting. I’ll probably find your ensuing performance problems interesting too. You won’t. That said, I think the linked list example is very interesting, and worth implementing and playing with, and might help shed some light on the Array reduce performance. And it might even be useful in real code in certain (infrequent) circumstances.²

So, to recap – sometimes, you’ll see reduce used to build an array (or dictionary or set), for example, in this implementation of map:

extension SequenceType {
   func mapUsingReduce<T>(transform: Generator.Element->T) -> [T] {
        return reduce([]) { $0 + [transform($1)] }
    }
}

as opposed to creating a mutable array then adding to it from a for loop:

extension SequenceType {
   func mapUsingFor<T>(transform: Generator.Element->T) -> [T] {
        var result: [T] = []
        for x in self { result.append(transform(x)) }
        return result
    }
}

The difference being, + creates a copy of the accumulating array every time. And copying the array takes linear time, inside a loop over the full array, so the overall time taken increases quadratically with the length of the array being mapped:

Of course, people aren’t normally going around re-implementing map though: you more often see this technique with, say, filtering duplicates or building dictionaries of word frequencies. But the problem remains the same.

Why is this relevant to a list? Well, because you could implement a version of map using reduce on the list code from last time, like so:

extension SequenceType {
    func mapToList<T>(transform: Generator.Element->T) -> List<T> {
        return reduce(List()) { $0.cons(transform($1)) }.reverse()
    }
}

The performance results you get are so perfectly half the array performance (because of the reverse step) that your teacher may accuse you of faking the results instead of doing the experiment:

This works because the list is persistent – it shares nodes between previous lists and newly consed lists, forever. So no copying needed. But this comes at the cost of only being able to grow from the head (hence the need for a reverse), and the list has to be fully immutable, so you have to make a copy to modify it even when it’s uniquely referenced. This is unlike Array, which can detect unique use of its buffer and just change it in-place, no copying required. Lists have other costs as well – to sum a list of numbers takes twice as long as to sum an array of numbers, as the indirection needed to traverse the list takes time.

So is the full copy on + with arrays fixable? To think about that, let’s first look at how a copy-on-write array might work. Mike Ash already has a great blog post on implementing a copy-on-write Array, so let’s do something a little different, which is to use the ManagedBuffer class from the standard library to build it.

ManagedBuffer

ManagedBuffer is a class you can inherit from, which simplifies the process of allocating/deallocating and managing storage on the heap. It is generic, and has two separate placeholders, Value and Element. Element is the type of the block of storage of n elements, allocated dynamically on creation. Value is the type of an extra single variable on the side for storing other information – for example, to implement an array, you would need to store the element count, as the elements need to be destroyed before the memory is deallocated. Access to the elements is via withUnsafeMutablePointerToElements, whereas the value can be accessed either through a similar unsafe method, or directly via a .value property.

Here’s a very simple self-destroying ArrayBuffer:

private class MyArrayBuffer<Element>: ManagedBuffer<Int,Element> {
    deinit {
        self.withUnsafeMutablePointerToElements { elems->Void in
            elems.destroy(self.value)
        }
    }
}

So, MyArrayBuffer is still generic on what elements it stores, but it fixes the Value of ManagedBuffer to just be an Int, which will store the number of elements in the buffer (bear in mind, we will allocate more storage than we have elements in the array, to avoid constantly reallocating).

When the buffer deinitializes, MyArrayBuffer.deinit will be called prior to ManagedBuffer.deinit, which deallocates the memory. This gives MyArrayBuffer a chance to destroy all its objects. Destroying is necessary if Element is something more than just a passive struct – for example, if the array contained other copy-on-write types, destroying them will trigger them freeing their memory if necessary.

Now, we can create an array type of a struct, with a private buffer as its storage:

public struct MyArray<Element> {
    private var _buf: MyArrayBuffer<Element>

    public init() {
        _buf = MyArrayBuffer<Element>.create(8) { _ in 0 } as! MyArrayBuffer<Element>
    }
}

We don’t use MyArrayBuffer’s init directly – instead we use the class method from ManagedBuffer. Because this method returns the superclass, we force-downcast it to the right type.

Then, we turn MyArray into a collection type:

extension MyArray: CollectionType {
    public var startIndex: Int { return 0 }
    public var endIndex: Int { return _buf.value }

    public subscript(idx: Int) -> Element {
        guard idx < self.endIndex else { fatalError("Array index out of range") }
        return _buf.withUnsafeMutablePointerToElements { $0[idx] }
    }
}

Next, we need two fairly similar methods on the buffer, one to clone the storage and one to resize the storage. Cloning will be used when shared storage is detected, resizing when non-shared storage needs to get bigger:

extension MyArrayBuffer {
    func clone() -> MyArrayBuffer<Element> {
        return self.withUnsafeMutablePointerToElements { oldElems->MyArrayBuffer<Element> in
            return MyArrayBuffer<Element>.create(self.allocatedElementCount) { newBuf in
                newBuf.withUnsafeMutablePointerToElements { newElems->Void in
                    newElems.initializeFrom(oldElems, count: self.value)
                }
                return self.value
            } as! MyArrayBuffer<Element>
        }
    }

    func resize(newSize: Int) -> MyArrayBuffer<Element> {
        return self.withUnsafeMutablePointerToElements { oldElems->MyArrayBuffer<Element> in
            let elementCount = self.value
            return MyArrayBuffer<Element>.create(newSize) { newBuf in
                newBuf.withUnsafeMutablePointerToElements { newElems->Void in
                    newElems.moveInitializeFrom(oldElems, count: elementCount)
                }
                self.value = 0
                return elementCount
            } as! MyArrayBuffer<Element>
        }
    }
}

Creating and populating the buffers in one shot is a little finicky – first we need to get the unsafe pointer to the existing elements, then call create, which takes a closure that receives the partially-created object (i.e. allocated but not initialized memory), which we then need to call newBuf.withUnsafeMutablePointerToElements on to copy the memory from the old buffer to the new.

The main difference between the two is clone doesn’t change the elements in the old buffer, just loads new copies into a new buffer. resize moves the elements from the old to the new storage (via UnsafeMutablePointer’s moveInitializeFrom method), then updates the old buffer to tell it that it no longer has any elements to manage – otherwise, it would try to destroy them during its deinit.

Finally, we give MyArray an append and extend method:

extension MyArray {
    public mutating func append(x: Element) {
        if !isUniquelyReferencedNonObjC(&_buf) {
            _buf = _buf.clone()
        }

        if _buf.allocatedElementCount == count {
            _buf = _buf.resize(count*2)
        }

        _buf.withUnsafeMutablePointers { (val, elems)->Void in
            (elems + val.memory++).initialize(x)
        }
    }

    public mutating func extend<S: SequenceType where S.Generator.Element == Element>(seq: S) {
        for x in seq { self.append(x) }
    }
}

This is just sample code. In practice, you would break out the uniqueness and resizing code, so you could re-use it in subscript set or other mutating methods, but I’ve crammed it all in the append method to keep it brief. Also you’d want to reserve enough space for the extend up-front if possible, and avoid double-copying the buffer when it’s both shared and too small. But none of these things have a major impact on the bigger picture for our purposes.

OK now for the operators. First, +=, which being an assignment operator takes an inout left-hand side and just extends it with the right-hand side:

func +=<Element, S: SequenceType where S.Generator.Element == Element>
  (inout lhs: MyArray<Element>, rhs: S) {
    lhs.extend(rhs)
}

And finally, +. We can implement this in terms of +=. The operator takes two immutable arrays, and adds them together to produce a new array. It does this by relying on the copy-on-write behaviour to create a mutable copy of the left-hand side, then extend it with the right-hand side:

func +<Element, S: SequenceType where S.Generator.Element == Element>
  (lhs: MyArray<Element>, rhs: S) -> MyArray<Element> {
    var result = lhs
    result += rhs
    return result
}

In fact you could shorten this further by using the var modifier in front of the lhs argument:

func +<Element, S: SequenceType where S.Generator.Element == Element>
  (var lhs: MyArray<Element>, rhs: S) -> MyArray<Element> {
    lhs += rhs
    return lhs
}

I mention this second version because some suggested a better reduce solution might involve using var on the accumulating argument. But this would be similar to what is happening here with lhs: all var does is declare your passed-by-value variable to be mutable. It is still a copy – it is not the original variable somehow passed through by reference.

Can + be optimized?

We now have a fully working toy implementation of a copy-on-write array you can append to, and which has a + operator. Which means we can rewrite our reduce version of map with it:

func mapUsingMyReduce<T>(transform: Generator.Element->T) -> MyArray<T> {
    return reduce([]) { $0 + [transform($1)] }
}

func mapUsingMyFor<T>(transform: Generator.Element->T) -> MyArray<T> {
    var result = MyArray<T>()
    for x in self { result.append(transform(x)) }
    return result
}

and if you chart the performance, you’ll see both exhibiting the similar behaviour as with array.

So, given we now have an implementation we have complete control over, can we change + so it doesn’t make a copy? I don’t think so.

In a simpler case, could we change this:

var a = MyArray<Int>()
a.extend(0..<3)
let b = a + [6,7,8]

so that it didn’t make a copy? It seems pretty obvious we can’t. b has to be a new copy of the array, in order to not affect a. Even if we don’t make any further changes to a after the creation of b, there’s no way the implementation of + could know this. Maybe the compiler could know this, and optimize accordingly, but the + func can’t.

Checking for unique references wouldn’t help here. a is still in existence, so the lhs variable will not be the only owner of the buffer.

reduce is no different. Here’s a possible implementation:

extension SequenceType {
    func myReduce<T>(initial: T, combine: (T,Generator.Element)->T) -> T {
        var result = initial
        for x in self {
            result = combine(result,x)
        }
        return result
    }
}

Assuming combine here is { $0 + [transform($1)] }, you can see that + similarly has no knowledge of the fact that we’re actually going to assign the outcome directly to the result variable. We know, on inspecting the code, that it’ll just be fine to add the right-hand side onto the left-hand side, if that were even possible (in theory it is, since even though the array is passed immutably by value, the buffer is a class and so could be mutated since it has reference semantics). But + can’t know that from where it sits. It definitely knows it’s copy of the left-hand side isn’t the only owner of the buffer. There is another owner too: reduce holds a copy of result – and is about to throw it away and replace it with a new result, but that’s coming after + has run.

One ray of hope is if arrays were also their own slices (which they aren’t – there is ArraySlice instead, which has extra overhead to track the start and end slice into the parent array). If they were, then perhaps they could be modified to allow one, but only one, array to have an append happen to it which the others could ignore. But this would probably add overhead to arrays in general, and the whole point of arrays is to be fast – you don’t want to slow them down just to cater to this use case.

Perhaps there is a very clever way of figuring all this out, with or without the compiler’s help. But such gymnastics don’t seem like a good idea even then. The semantics are that + creates a new array. Wanting it to secretly modify an existing one under very specific circumstances doesn’t seem like the right solution – mutating the array is. If you prefer, you can wrap that var up in a nice little generic method and then pretend it’s not there. But it’ll make your code faster.