Самый эффективный способ доступа к многомерным массивам в Swift?

Question

У меня есть многомерный массив чисел с фиксированным размером (обычно это float, но ints в моем примере кода, чтобы не отвлекаться на накладные расходы преобразования), и я хочу эффективно его обрабатывать. Swift не предоставляет многомерные массивы как таковые, но вы можете получить эффект через массив из 1D массивов. Однако они кажутся очень и очень медленными. Есть ли способ лучше?

У меня есть тестовая проблема (которую я использовал для сравнения других языков), где я передаю два 2D-массива подпрограмме, которая устанавливает каждый элемент из одного в соответствующий элемент другого, плюс сумму двух значений индекса , (Это означает, что каждый элемент зависит от его координат, что происходит в большинстве случаев в реальном мире.)

Я скомпилировал с использованием флага -Ounchecked.

Вариант 1: Используя массив из 1D массивов, я получаю очень медленную производительность. 10 проходов заняли 1,5 секунды.

Вариант 2: Используя довольно аккуратную идею в http://blog.trolieb.com/trouble-multidimensional-arrays-swift где класс Array2D использует базовый 1D массив и реализует индекс(), чтобы сделать его похожим на 2D массив, то ускорить много (на 2 порядка): 1000 проходов заняло 1,0 секунды

Вариант 3: Падение назад на очень неудобный вид кода, который использовался для использования на C, где вы используете 1D-массив, и делаете столбцы index = (row *) + столбцы явно, вещи (не совсем на 2 порядка) 100000 проходов заняли 3,6 секунды.

Вариант 3 находится в пределах коэффициента 2 из того, что я получаю из эквивалентного кода С, скомпилированного с -O3 в clang, так что отлично подходит для компилятора ранних дней. Проблема в том, что это действительно уродливое, неудобное и склонное к ошибкам. Есть трюки, которые можно использовать в C, например, выделение массивов указателей в начало каждой строки (Numerical Recipes in C делает это), чтобы вы могли использовать двумерный синтаксис для массивов, а с объектно-ориентированным C вы можете сделать это довольно элегантный, а также эффективный. Мой вопрос в том, есть ли способ в Swift получить код, такой как array [Iy] [Ix] (или массив [Iy, Ix] или что-то еще, в отличие от массива [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

Крис Латтнер сам ответил на Apple, Дев форумах об этом и звучит как # 2/# 3 наши лучшие решения до неминуемой затруднительное компилятор не сделал.

«Это известная проблема: 2D массивы ... может спровоцировать крайне низкую производительность, поскольку оптимизация копирования при записи (КПС) они основаны на побежден в некоторых случаях ...

затруднительного положения поскольку он просто пропустил выпуск 6.1, потому что он требует некоторой внутренней работы в области инфраструктуры. Это говорит о том, что он выйдет в следующем значительном обновлении быстродействующего компилятора.

Тем временем часто используются (уродливые, но эффективные) обходные пути вы можете использовать. Например, если ваши массивы прямоугольные, вы можете использовать один массив размером до m * n элементов и вручную индексировать его.

-Крис»

Answer 2

В некотором смысле, Apple ответили на мой вопрос, который я не смотрел на это на некоторое время теперь. - и, по сути, даже не используя Swift Но я бы просто. установил XCode 9 и Swift 4, и подумал, что посмотрю, изменились ли какие-либо изменения. Мне пришлось сделать некоторые быстрые изменения, чтобы подготовить тестовую программу, и я попробовал ее снова.

Итог: все три параметры запускаются примерно в то же время, и эта скорость неплохая. Я думаю, это замечательное улучшение, а это означает, что стандартный метод Swift для обработки 2D-массива - как массива массивов - больше не имеет производительности штраф и, по крайней мере, на основании этого теста, явно теперь можно идти. Это именно то, что я думаю, что все захотят. (Я построил с -Ounchecked, что делает разницу в коэффициенте 2.)

По сравнению с эквивалентным кодом на C++, имея в виду, что вам нужно пройти несколько обручей, чтобы передать многомерные массивы в C++ подпрограмм, я думаю, теперь это намного проще закодировать в Swift. В прошлый раз я сказал, что самая быстрая опция Swift (бесполезная опция «сделать индексирование самостоятельно») запустила только фактор 2 медленнее, чем эквивалент C++. Фактически, теперь я вижу фактор 4, ускоряющий использование C++ и clang, но это потому, что теперь clang улучшил уже впечатляющую оптимизацию (он бросает векторные инструкции на проблему самым изобретательным образом - это делалось раньше, но теперь, похоже, он избавился от некоторых дополнительных накладных расходов). Это то, о чем я думаю, может со временем прийти в Свифт; я считаю, что, опять же, на основе этого теста - Swift больше не ограничивается обработкой массива. Поскольку я изначально разместил этот вопрос, clang/C++ улучшился в 2 раза, но 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 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") 
}