Most efficient way to access multidimensional arrays in Swift?

I have a fixed size multidimensional array of numbers (usually floats, but ints in my example code so as not to get distracted by the conversion overhead) and I want to manage it efficiently. Swift does not provide multidimensional arrays per se, but you can get the effect through an array of 1D arrays. However, they seem to be very, very slow. Is there a better way?

I have a test problem (which I used to compare other languages) where I pass two 2D arrays to a subroutine that sets each element from one to the corresponding element of the other, plus the sum of the two index values. (This means what happens to each element depends on its coordinates, which happens in most cases in the real world.)

I compiled using the -Ounchecked flag.

Option 1. Using an array of 1D arrays, I get very slow performance. 10 passes took 1.5 seconds.

Option 2: using a pretty neat idea at http://blog.trolieb.com/trouble-multidimensional-arrays-swift where the Array2D class uses a base 1D array and implements index () to make it look like a 2D array, everything accelerates (by 2 orders of magnitude): 1000 passes took 1.0 seconds

Option 3: Going back to the very awkward type of code that used to be used in C where you use a 1D array and explicitly make index = (row * columns) + columns, things speed up once again (not just 2 orders of magnitude) 100000 passes took 3.6 seconds.

Option 3 is within the 2 nd factor of what I get from the equivalent C code compiled with -O3 in clang, so great for an early days compiler. The problem is that this is really ugly, inconvenient and error prone. There are tricks that can be used in C, like allocating arrays of pointers to the beginning of each line (Numerical Recipes in C does this) so that you can use two-dimensional syntax for arrays, and with object-oriented C you can do it quite elegantly, and also effective. My question is, is there a way in Swift to get code like array [Iy] [Ix] (or array [Iy, Ix] or whatever, as opposed to array [Iy * Ny + Ix]) for quick launch?

I have to say that I am very new to Swift and I like what I have seen so far and I appreciate that compilers will only be faster. I am doing a lot of coding in scientific applications using fixed size multidimensional arrays and I am interested in the possibility of using Swift in the future. Or should I ask Apple to add real multidimensional array support to Swift?

Here's the test code I used:

//
//  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 Darwin

//  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(count:cols*rows, repeatedValue:0)
    }
    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, inout Output: 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, inout Output: 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, inout Output: [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 let argStr = String.fromCString(C_ARGV[1]) {
    if let argInt = argStr.toInt() { Option = argInt }
}

var Nrpt:Int = 100
if let argStr = String.fromCString(C_ARGV[2]) {
    if let argInt = argStr.toInt() { Nrpt = argInt }
}

var Nx:Int = 2000;
if let argStr = String.fromCString(C_ARGV[3]) {
    if let argInt = argStr.toInt() { Nx = argInt }
}

var Ny:Int = 10;
if let argStr = String.fromCString(C_ARGV[4]) {
    if let argInt = argStr.toInt() { Ny = argInt }
}


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

switch Option {
case 1:

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

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

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

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

    let start : UInt64 = mach_absolute_time()

    for Irpt in 0...Nrpt-1 {
       Subr(array,Nx,Ny,&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) {
                println("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
    println("2D array took:\(total) ms.")

case 2:

    println ("Using the Array2D class")

    var 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)
        }
    }

    println("Timing array2D version")

    let start2 : UInt64 = mach_absolute_time()

    for Irpt in 0...Nrpt-1 {
        Subr2d(array2,Nx,Ny,&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) {
                println("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
    println("Array2D version took:\(total2) ms.")

case 3:

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

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

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

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

    let start3 : UInt64 = mach_absolute_time()

    for Irpt in 0...Nrpt-1 {
        Subr1d(array3,Nx,Ny,&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) {
                println("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
    println("1D array took:\(total3) ms.")

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

      

+3


source to share


2 answers


Chris Lattner himself answered the Apple dev forums about this himself and apparently found better solutions for 2 / # 3 until the inevitable compiler fix is ​​generated.

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

The fix for it just skipped the 6.1 release because it requires some internal infrastructure. However, it will be released in the next major update to the fast compiler.



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

-Chris "

+1


source


In a way, Apple has answered my question. I haven't looked at this for a while - and haven't even used Swift. But I just installed XCode 9 and Swift 4 and thought I'd see if everything changed. I had to make some quick changes to get a test program to build and I tried again.

Bottom line: All three options start at about the same time, and this speed is not bad at all. I think this is a great improvement, which means that Swift's standard method of handling a 2D array - as an array of arrays - no longer has a performance penalty and, at least based on this test, is clearly the way to go now. This is exactly what I think everyone will want. (I plotted with -Ounchecked, which makes a difference in factor of 2.)

Compared to the equivalent C ++ code, bearing in mind that you have to go through several hoops to pass multidimensional arrays to C ++ routines, I think this is now much easier to code in Swift. I said last time that Swift's fastest option (the useless "do indexing yourself" option) only ran factor 2 slower than the C ++ equivalent. In fact, I now see factor 4 speeding up from using C ++ and clang, but that's because now clang has improved an already impressive optimization (it throws vector instructions in the problem in the most ingenious way - it has been done before, but now it looks like it got rid of some extra overhead). What I imagine may eventually come to Swift; I believe that, again,based on this test - Swift is no longer limited to array processing. Since I originally posted this question clang / C ++ has improved 2x, but Swift has improved out of sight.



Here's the code given:

//
//  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")
}

      

+1


source







All Articles