Reassignment of multidimensional arrays in Swift is very slow

[factal (Joji)]

Hi there.

I found that Swift's multidimensional arrays are very slow on certain operations. I was aware of the performance issues with multidimensional arrays because I had read the Swift forum and Reddit (c.f. https://forums.swift.org/t/low-efficiency-multidimensional-array-problem/5717, https://www.reddit.com/r/swift/comments/2fqldf/slow_2d_array_multiply/), but the following is a more extreme example. Here is my code:

// 001.swift
let H = 10
let W = 100000

var arr = [[Int]](repeating: [Int](repeating: 0, count: W), count: H)

for i in 0..<H {
    for j in 0..<W {
        arr[i][j] = arr[i][j]
    }
}

I experimented with different H and W without changing H*W=1000000, and it seems that as W increases, the execution time increases rapidly.

The following code was used to measure execution time:

// logger.swift
import Foundation

let filePath = "./{executable}"

let task = Process()
task.launchPath = filePath

let startTime = Date()

try task.run()

task.waitUntilExit()

let elapsed = Date().timeIntervalSince(startTime)

print("Execution time: \(elapsed) s")

On the other hand, when assigning values other than the elements of arr, for example, 002.swift and 003.swift, the execution seems to be fast.

// 002.swift
let H = 10
let W = 100000

var arr = [[Int]](repeating: [Int](repeating: 0, count: W), count: H)

for i in 0..<H {
    for j in 0..<W {
        arr[i][j] = i + j
    }
}

// 003.swift
let H = 10
let W = 100000

var arr = [[Int]](repeating: [Int](repeating: 0, count: W), count: H)
var arr2 = [[Int]](repeating: [Int](repeating: 0, count: W), count: H)

for i in 0..<H {
    for j in 0..<W {
        arr[i][j] = arr2[i][j]
    }
}

More oddly, it runs just as fast when reassigned via the temporary variable.

// 004.swift
let H = 10
let W = 100000

var arr = [[Int]](repeating: [Int](repeating: 0, count: W), count: H)

for i unsunsin 0..<H {
    for j in 0..<W {
        let tmp = arr[i][j]
        arr[i][j] = tmp
    }
}

Here is a table of execution time (sec):

	H=1, W=10⁶	H=10, W=10⁵	H=10², W=10⁴	H=10³, W=10³	H=10⁴, W=10²	H=10⁵, W=10	H=10⁶, W=1
001.swift	464.240	21.267	4.732	0.936	0.932	1.000	1.264
002.swift	0.730	0.801	0.729	0.728	0.731	0.800	0.868
003.swift	0.535	0.399	0.464	0.464	0.797	1.202	1.200
004.swift	0.734	0.734	0.734	0.734	0.730	0.794	1.264

According to these results, almost the same process can be 400 to 500 times slower, depending on how it is written. And here is my environment:

• M1 MacBook Air (Early 2020)
• macOS Ventura 13.2.1
• Swift 5.7.2

Any good explanation?

[AlexanderM (Alexander Momchilov)]

By far the largest culprit here is that you have a CoW mutation happen on every single assignment. You can fix it by separating your read from the array and the write back into it:

for i in 0..<H {
    for j in 0..<W {
        arr[i][j] = arr[i][j]
    }
}

to:

for i in 0..<H {
    for j in 0..<W {
        let x = arr[i][j]
        arr[i][j] = x // Since the array is uniquely referenced here, there's no need for a copy.
    }
}

This alone reduces the time on my M1 Mac Mini from 17 seconds to 16 milliseconds

There's two other minor improvements you could make here:

1. You're causing 10 needeless CoW copies of your 100000 member array.
   • Your initial arr is one 10-element array, containing 10 arrays all backed by the same buffer. The first assignment within each is causing a CoW copy.
   • Fix: var arr = (0...H).map { _ in [Int](repeating: 0, count: W) }
   • This lowers the time down to 13 ms.
2. You're zeroing out your arrays to start. You can skip this if you can just initialize them with the correct values from the start.

[taylorswift]

@AlexanderM

By far the largest culprit here is that you have a CoW mutation happen on every single assignment. You can fix it by separating your read from the array and the write back into it:

for i in 0..<H {
    for j in 0..<W {
        arr[i][j] = arr[i][j]
    }
}

to:

for i in 0..<H {
    for j in 0..<W {
        let x = arr[i][j]
        arr[i][j] = x // Since the array is uniquely referenced here, there's no need for a copy.
    }
}

This alone reduces the time on my M1 Mac Mini from 17 seconds to 16 milliseconds

is this because Array.subscript(_:) uses a _modify?

i wonder if this CoW problem would still occur if you instead used a wrapper that exposes a traditional set.

[jrose (Jordan Rose)]

@AlexanderM

By far the largest culprit here is that you have a CoW mutation happen on every single assignment.

Can we change this behavior? a[i] = a[i] doesn’t have the same problem, because the evaluation of the inout access happens after the evaluation of the argument. It feels like that should be true of a[i][j] as well, even if there’s an observable difference when that’s implemented with get/set instead of modify.

[John_McCall]

This is surprising, yeah. I would expect us to not start any accesses involving the LHS here until after fully evaluating the RHS, essentially as if it were hoisted out as a let.

[ibex10]

I wonder what the execution times would look like using a linear array.

let H = 10
let W = 100000

var arr = [Int] (repeating: 0, count: H * W)

for i in 0..<H {
    let x = i * W
    for j in 0..<W {
       arr [x + j] = arr [x + j]
    }
}

[Bijan]

For anyone who would like to experiment without online: Compiler Explorer