Most efficient way to access multi-dimensional arrays in Swift?

Chris Lattner himself responded on Apple dev forums about this and sounds like #2/#3 our best solutions until an imminent compiler fix is made .

"This is a known issue: 2D arrays ... can provoke extremely poor performance because the copy-on-write (COW) optimization they are based on is defeated in some cases...

The fix for it just narrowly missed the 6.1 release because it requires some internal infrastructure work. That said, it will go out in the next significant update of the swift compiler.

In the meantime, there are often (ugly but effective) workarounds you can use. For example, if your arrays are rectangular, you can use a single array sized to m*n elements, and manually index into it.

-Chris"

In a way, Apple have answered my question. I've not looked at this for a while now - and, indeed, haven't even been using Swift. But I've just installed XCode 9 and Swift 4, and thought I'd see if things have changed. I had to make some quick changes to get the test program to build, and I've tried it again.

Bottom line: All three options run in about the same time now, and that speed is not bad at all. I think that's a remarkable improvement, and it means that the standard Swift way of handling a 2D array - as an array of arrays - no longer has a performance penalty, and, at least on the basis of this test, is clearly the way to go now. Which is exactly what I think everyone would want. (I've built with -Ounchecked, which does make about a factor 2 difference.)

Compared to the equivalent code in C++, bearing in mind that you have to go through some hoops to pass multi-dimensional arrays to C++ routines, I think this is now much easier to code in Swift. Last time I said the fastest Swift option (the messy 'do the indexing yourself' option) ran only a factor 2 slower than the equivalent C++. Actually, I now see a factor 4 speed-up from using C++ and clang, but that's because clang now seems to have improved its already impressive optimisation (it throws vector instructions at the problem in a most ingenious way - it did that before, but now it seems to have gotten rid of some additional overheads). That's something I imagine may come to Swift with time; the important thing to my mind is that - again, on the basis of this one test - Swift no longer seems to be restricted by its array handling. Since I originally posted this question, clang/C++ has improved by a factor 2, but Swift has improved out of sight.

Here's the revised code:

//
//  main.swift
//
//  Tests 3 ways of handling 2D arrays in Swift. Test takes a 2D array and calls a routine
//  that takes each element of an input array and adds the X and Y index values to it and
//  returns an array with the result.
//
//  Command line arguments: Option Nrpt Nx Ny
//
//  Option is type of array used (1: Swift array of arrays,
//                                2: Array2D 1D array looking like a 2D array
//                                3: 1D array used like a 2D array with explicit index calculation)
//  Nrpt is number of repeats of subroutine call
//  Nx, Ny are array dimensions.
//

import Foundation

//  Array2D comes from http://blog.trolieb.com/trouble-multidimensional-arrays-swift/

class Array2D {
    var cols:Int, rows:Int
    var matrix: [Int]

    init(cols:Int, rows:Int) {
        self.cols = cols
        self.rows = rows
      matrix = Array(repeating:0, count:cols*rows)
    }
    subscript(col:Int, row:Int) -> Int {
        get { return matrix[cols * row + col] }
        set { matrix[cols*row+col] = newValue }
    }
    func colCount() -> Int { return self.cols }
    func rowCount() -> Int { return self.rows }
}

//  Using a 'proper' Swift '2D' array - ie an array of 1D arrays
func Subr (Input: Array<Array<Int>>, Nx: Int, Ny : Int, Output: inout Array<Array<Int>>) {
    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            Output[Iy][Ix] = Input[Iy][Ix] + (Ix + Iy)
        }
    }
}

//  Using an Array2D array - wrapping up a 1D array to act as a 2D one.
func Subr2d (Input: Array2D, Nx: Int, Ny : Int, Output: inout Array2D) {
    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            Output[Ix,Iy] = Input[Ix,Iy] + (Ix + Iy)
        }
    }
}

//  Using a 1D Swift array and doing the indexing explicitly
func Subr1d (Input: [Int], Nx: Int, Ny: Int, Output: inout [Int]) {
    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            Output[Iy * Nx + Ix] = Input[Iy * Nx + Ix] + (Ix + Iy)
        }
    }
}

var Option:Int = 1
if (CommandLine.argc > 1) {
    let argStr = CommandLine.arguments[1]
    if let argInt = Int(argStr) { Option = argInt }
}

var Nrpt:Int = 100
if (CommandLine.argc > 2) {
    let argStr = CommandLine.arguments[2]
    if let argInt = Int(argStr) { Nrpt = argInt }
}
var Nx:Int = 2000;
if (CommandLine.argc > 3) {
    let argStr = CommandLine.arguments[3]
    if let argInt = Int(argStr) { Nx = argInt }
}

var Ny:Int = 10;
if (CommandLine.argc > 4) {
    let argStr = CommandLine.arguments[4]
    if let argInt = Int(argStr) { Ny = argInt }
}

print("Repeats: \(Nrpt), Array \(Nx) by \(Ny)")

switch Option {
case 1:

    print ("Using an ordinary Swift '2D' array of arrays")

    var array = Array(repeating:Array(repeating:Int(), count:Nx), count:Ny)

    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            array[Iy][Ix] = (Ix + Iy)
        }
    }

    var output = Array(repeating:Array(repeating:Int(), count:Nx), count:Ny)

    let start : UInt64 = mach_absolute_time()

    for _ in 0...Nrpt-1 {
      Subr(Input: array,Nx: Nx,Ny: Ny,Output: &output)
    }

    let duration : UInt64 = mach_absolute_time() - start

    check:
    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            let Expected = array[Iy][Ix] + (Ix + Iy)
            if (output[Iy][Ix] != Expected) {
                print("Error at \(Ix),\(Iy) Got \(output[Iy][Ix]) expected \(Expected)")
                break check
            }
        }
    }

    var info : mach_timebase_info = mach_timebase_info(numer: 0, denom: 0)
    mach_timebase_info(&info)

    let total = (duration * UInt64(info.numer) / UInt64(info.denom)) / 1_000_000
    print("2D array took:\(total) ms.")

case 2:

    print ("Using the Array2D class")

    let array2 = Array2D(cols: Nx, rows: Ny)
    var output2 = Array2D(cols: Nx, rows: Ny)

    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            array2[Ix,Iy] = (Ix + Iy)
        }
    }

    print("Timing array2D version")

    let start2 : UInt64 = mach_absolute_time()

    for _ in 0...Nrpt-1 {
      Subr2d(Input: array2,Nx: Nx,Ny: Ny,Output: &output2)
    }

    let duration2 : UInt64 = mach_absolute_time() - start2

    check:
    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            let Expected = array2[Ix,Iy] + (Ix + Iy)
            if (output2[Ix,Iy] != Expected) {
                print("Error at \(Ix),\(Iy) Got \(output2[Ix,Iy]) expected \(Expected)")
                break check
            }
        }
    }


    var info2 : mach_timebase_info = mach_timebase_info(numer: 0, denom: 0)
    mach_timebase_info(&info2)

    let total2 = (duration2 * UInt64(info2.numer) / UInt64(info2.denom)) / 1_000_000
    print("Array2D version took:\(total2) ms.")

case 3:

    print ("Using an a 1D array and handling the indexing explicitly")

    var array3 = Array(repeating:Int(), count:Ny * Nx)

    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            array3[Iy * Nx + Ix] = (Ix + Iy)
        }
    }

    var output3 = Array(repeating:Int(), count:Ny * Nx)

    let start3 : UInt64 = mach_absolute_time()

    for _ in 0...Nrpt-1 {
      Subr1d(Input: array3,Nx: Nx,Ny: Ny,Output: &output3)
    }

    let duration3 : UInt64 = mach_absolute_time() - start3

    check:
    for Iy in 0...Ny-1 {
        for Ix in 0...Nx-1 {
            let Expected = array3[Iy * Nx + Ix] + (Ix + Iy)
            if (output3[Iy * Nx + Ix] != Expected) {
                print("Error at \(Ix),\(Iy) Got \(output3[Iy * Nx + Ix]) expected \(Expected)")
                break check
            }
        }
    }

    var info3 : mach_timebase_info = mach_timebase_info(numer: 0, denom: 0)
    mach_timebase_info(&info3)

    let total3 = (duration3 * UInt64(info3.numer) / UInt64(info3.denom)) / 1_000_000
    print("1D array took:\(total3) ms.")

default:
    print ("Invalid option code. Must be 1,2, or 3")
}