relates to:

• SR-5048 Tuples of homogenous contents should adopt a common protocol

Issue Description:

Swift needs a fixed-size array.

Motivation: I’ve been porting code for Monte Carlo Tree Search in my Go-playing program from C++ to Swift. Performance is crucial for this code, as more simulations lead to better play. After the initial port, the Swift code was more than 10x slower than C++. After several weeks of optimizing, profiling, and digging through disassembly, I’ve gotten to within a factor of 2.

The main issues I had to overcome:

• avoid heap allocation

• avoid reference counting

• avoid indirection

• avoid initialization checks

For my application, these issues would all be addressed by having a fixed-size array data structure in Swift. My app is designed for a 19x19 (or smaller) Go board, not an arbitrary N x N board, so I don’t want to pay the high cost of variable-size data structures in the lowest levels of my app.

(Arrays in Swift are implemented as a header pointing to an object on the heap. Thus every array involves a heap allocation, and accessing an element in the array requires an extra indirection. Same for ContiguousArray.)

Workaround: Import C array

You can define a fixed-size array in C, then import that to Swift. For example, define the following in a C header file:

const int NumWords = 6;
struct Bitset {
uint64_t bits[NumWords];
};

Then in Swift:

struct PointSet {
var bits = Bitset()
}

The problem is that Bitset is imported into Swift as a tuple (Int, Int, Int, Int, Int, Int), and there is no direct way to use an index to access these members. You can hack it by going through UnsafeRawPointer:

struct FixedSizeArray<T> {

var array = SomeArrayImportedFromC()
let count = ...

private func setElement(_ pointer: UnsafeMutableRawPointer, at index: Int, to value: T) {
let a = pointer.bindMemory(to: T.self, capacity: count)
a[index] = value
}

private func getElement(_ pointer: UnsafeRawPointer, at index: Int) -> T {
let a = pointer.bindMemory(to: T.self, capacity: count)
return a[index]
}

subscript(_ index: Int) -> T {
// This 'mutating' is necessary due to bug SR-4542.
mutating get { return getElement(&array, at: index) }
set { setElement(&array, at: index, to: newValue) }
}
}

This is really ugly, and the SR-4542 bug that forces the getter to be mutable impacts client code. It does, however, address the performance issue.

Array initialization

I have some arrays that are statically initialized, e.g. the following one to map a set of directions into a sequence of offsets, used for efficient iteration through neighbor points (goN, goW, goE, goS are constants):

let nbOffsetForSet: [Int8] = [
/* 0*/ 0, 0, 0, 0,
/* 1*/ goN, 0, 0, 0,
/* 2*/ goW, 0, 0, 0,
/* 3*/ goN, goW, 0, 0,
/* 4*/ goE, 0, 0, 0,
/* 5*/ goN, goE, 0, 0,
/* 6*/ goW, goE, 0, 0,
/* 7*/ goN, goW, goE, 0,
/* 8*/ goS, 0, 0, 0,
/* 9*/ goN, goS, 0, 0,
/10/ goW, goS, 0, 0,
/11/ goN, goW, goS, 0,
/12/ goE, goS, 0, 0,
/13/ goN, goE, goS, 0,
/14/ goW, goE, goS, 0,
/15/ goN, goW, goE, goS, 0, 0, 0, 0 ]

When declaring this constant array, Swift will initialize it once. However, before accessing it, the code needs to check whether it’s initialized. I get a significant performance boost by declaring the same array in C and using the following function:

func getNbOffsetForSet(_ index: Int) -> Int8 {

func getElement(_ pointer: UnsafeRawPointer, at index: Int) -> Int8 {
let a = pointer.bindMemory(to: Int8.self, capacity: 17*4)
return a[index]
}
return getElement(&nbOffsetForSetImportedFromC, at: index)
}

This kind of hack should just not be necessary to make Swift code perform well.

Proposal

Adding support for a fixed-size array in Swift would make it possible to write performant code without resorting to C and ugly hacks.

var a = FixedArray(repeating: 0, count: 10)

There are many possibilities for how to include this in Swift, e.g. a separate FixedArray class that behaves mostly like Array, except that the compiler knows that count and capacity are constant. But whichever way it’s done, I feel like this is the most important feature currently missing from Swift.