swift - 在 Swift 中访问多维数组的最有效方法？

Question

我有一个固定大小的多维数字数组(通常是 float ，但在我的示例代码中是整数以避免被转换开销分散注意力)，我想有效地操作它。 Swift 本身不提供多维数组，但您可以通过一维数组的数组来获得效果。但是，这些似乎非常非常慢。有没有更好的办法？

我有一个测试问题(我曾用它来对其他语言进行基准测试)，我将两个二维数组传递给一个子例程，该子例程将一个数组的每个元素设置为另一个数组的相应元素加上两个索引值的总和。 (这意味着每个元素会发生什么取决于它的坐标，这在大多数现实世界的情况下都会发生。)

我使用 -Ounchecked 标志进行编译。

选项 1:使用一维数组的数组，我的性能非常慢。 10 次传球用时 1.5 秒。

选项 2:使用 http://blog.trolieb.com/trouble-multidimensional-arrays-swift 中相当简洁的想法Array2D 类使用底层一维数组并实现 subscript() 以使其看起来像二维数组的地方，事情会加快很多(2 个数量级): 1000 次传球用时 1.0 秒

选项 3:回到以前在 C 中使用的那种非常笨拙的代码，您使用一维数组并显式地执行索引 = (行 * 列) + 列计算，速度再次加快(不是相当 2 个数量级) 100000 次传球用时 3.6 秒。

选项 3 是我从 clang 中使用 -O3 编译的等效 C 代码中得到的结果的 2 倍之内，因此对于早期的编译器来说很好。问题是它真的很丑陋、笨拙而且容易出错。在 C 中可以使用一些技巧，例如将指针数组分配到每一行的开头(C 中的数字食谱就是这样做的)以允许您对数组使用二维语法，并且使用面向对象的 C 可以做到这一点相当优雅和高效。我的问题是，在 Swift 中真的有一种方法可以让像 array[Iy][Ix](或 array[Iy,Ix] 或其他任何东西，而不是 array[Iy*Ny + Ix])这样的代码快速运行吗？

我应该说我是 Swift 的新手，我喜欢我目前看到的一切，我很欣赏编译器只会变得更快。我使用固定大小的多维数组对科学应用程序进行了大量编码，并且我对将来使用 Swift 的可能性很感兴趣。或者我应该要求 Apple 为 Swift 添加真正的多维数组支持？

这是我一直在使用的测试代码:

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

Answer 1

Chris Lattner 本人在 Apple 开发者论坛上对此做出了回应，听起来像是 #2/#3 我们最好的解决方案，直到做出迫在眉睫的编译器修复。

“这是一个已知问题:二维数组……可能会导致性能极差，因为它们所基于的写时复制 (COW) 优化在某些情况下会失效……

它的修复只是勉强错过了 6.1 版本，因为它需要一些内部基础架构工作。也就是说，它将在 swift 编译器的下一次重大更新中推出。

与此同时，您通常可以使用(丑陋但有效的)解决方法。例如，如果您的数组是矩形的，您可以使用大小为 m*n 个元素的单个数组，并手动对其进行索引。

-克里斯“