Object vs Int array subscript (get and set) is 250 times too slow

(Title is serious. 0.06sec vs 16sec. See performance numbers below.)

I first discovered this problem when implementing a min heap backed by an array in order to solve a Leetcode problem. The Heap was 30x slower than the Heap. All other functionality was equivalent.

I continued to debug the problem and created the following test code to illustrate the core issue so as to ignore any implementation details of a min heap.

The following code has a class, which contains an array, and a method that swaps elements of the array. Performing these simple array subscript (get and set) operations directly on the encapsulated member variable array, and if that array type is of some class, performance is 30 times worse than swapping elements using an inout reference or using an int array. Needing to use an inout reference is unexpected. This class implements both the fast and slow methods for the following performance tests.

This problem seems to only happen if this array and functionality are encapsulated in a class. If the array is global, this doesn't happen. Using ContiguousArray<> doesn't help. Using a UnsafeMutablePointer<> does also solve the problem. (The sample code below doesn't include these tests, but one can easily modify it.)

The following is the output from the below sample code:

Running test 'Int array swaps fast':
  Completed in 0.06475687026977539 seconds
Running test 'Obj array swaps fast':
  Completed in 0.06326985359191895 seconds
Running test 'Int array swaps slow (but still fast)':
  Completed in 0.25764894485473633 seconds
Running test 'Int array swaps slow (and is SLOW!)':
  Completed in 16.006703853607178 seconds

The difference is even more extreme (5000x - .003 vs 16) when run with swift -O or -Ounchecked.

Below is this sample code:

// A class holding an array that does subscript operations on it
class ArrayHolder<T> {
  var arr: [T]
   
  init(_ arr: [T]) {
    self.arr = arr
  }

  // This is the same function as swapsTestOuter(),
  // but using the local arr.
  // And is very very slow!
  func swapsTestInnerSlow(_ repeats: Int) {
    let size = arr.count
    for i in 0..<repeats {
      let index1 = i % size
      let index2 = (i + 1) % size
      (arr[index1], arr[index2]) = (arr[index2], arr[index1])
    }
  }

  func swapsTestInnerFast(_ repeats: Int) {
    swapsTestUsingReference(&arr, repeats)
  }

  // Seemingly identical to the above, but perf is much better.
  func swapsTestUsingReference(_ arr: inout [T], _ repeats: Int) {
    let size = arr.count
    for i in 0..<repeats {
      let index1 = i % size
      let index2 = (i + 1) % size
      (arr[index1], arr[index2]) = (arr[index2], arr[index1])
    }
  }
}


// A simple wrapper to time the tests
func tester(_ msg: String, _ toTest: () -> ()) {
  print("Running test '\(msg)':")
  let start = Date().timeIntervalSince1970
  toTest()
  let end = Date().timeIntervalSince1970
   
  print("  Completed in \(end-start) seconds")
}

// Just a simple object
class Obj {
  var data: Int

  init(_ data: Int = 0) {
    self.data = data
  }
}

let arraySize = 10000
let repeats = 100000

// Create the objects to test.
var wrappedIntArray = ArrayHolder(
  Array(repeating: 0, count: arraySize))
var wrappedObjArray = ArrayHolder(
  Array(repeating: Obj(), count: arraySize))


// The tests and timing them.

tester("Int array swaps fast") {
  wrappedIntArray.swapsTestInnerFast(repeats)
}

tester("Obj array swaps fast") {
  wrappedObjArray.swapsTestInnerFast(repeats)
}

tester("Int array swaps slow (but still fast)") {
  wrappedIntArray.swapsTestInnerSlow(repeats)
}

tester("Int array swaps slow (and is SLOW!)") {
  wrappedObjArray.swapsTestInnerSlow(repeats)
}


tester("Simple tests of correctness, to make sure I'm actually mutating the array") {
  let t1 = ArrayHolder([1, 2, 3, 4, 5])
  t1.swapsTestInnerFast(17)
  print(t1.arr)
   
  let t2 = ArrayHolder([1, 2, 3, 4, 5].map{Obj($0)})
  t2.swapsTestInnerFast(17)
  print(t2.arr.map{$0.data})
   
  let t3 = ArrayHolder([1, 2, 3, 4, 5])
  t3.swapsTestInnerSlow(17)
  print(t3.arr)
   
  let t4 = ArrayHolder([1, 2, 3, 4, 5].map{Obj($0)})
  t4.swapsTestInnerSlow(17)
  print(t4.arr.map{$0.data})
}

Lastly, my env:

Xcode - Version 14.2 (14C18)

swift-driver version: 1.62.15 Apple Swift version 5.7.2 (swiftlang-5.7.2.135.5 clang-1400.0.29.51)
Target: x86_64-apple-macosx12.0

MacOS Monterey 12.6.2 (21G320)
2.4 GHz 8-Core Intel Core i9
64 GB 2667 MHz DDR4