Benchmarking improvements to the ArrayElementValuePropagation pass

mergesort.swift

import Cocoa

func mergeSort(_ array: [Int]) -> [Int] {
  guard array.count > 1 else { return array }
  let middleIndex = array.count / 2
  let leftArray = mergeSort(Array(array[0..<middleIndex]))
  let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
  return merge(leftPile: leftArray, rightPile: rightArray)
}

func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
  var leftIndex = 0
  var rightIndex = 0
  var orderedPile = [Int]()

  while leftIndex < leftPile.count && rightIndex < rightPile.count {
    if leftPile[leftIndex] < rightPile[rightIndex] {
      orderedPile += [leftPile[leftIndex]]
      leftIndex += 1
    } else if leftPile[leftIndex] > rightPile[rightIndex] {
      orderedPile += [rightPile[rightIndex]]
      rightIndex += 1
    } else {
      orderedPile += [leftPile[leftIndex]]
      leftIndex += 1
      orderedPile += [rightPile[rightIndex]]
      rightIndex += 1
    }
  }

  while leftIndex < leftPile.count {
    orderedPile += [leftPile[leftIndex]]
    leftIndex += 1
  }

  while rightIndex < rightPile.count {
    orderedPile += [rightPile[rightIndex]]
    rightIndex += 1
  }

  return orderedPile
}

func makeList(_ n:UInt32) -> [Int] {
    var result:[Int] = []
    for _ in 0..<n {
        result += [Int(arc4random_uniform(n) + 1)]
    }
    return result.sorted()
}

let cnt:UInt32 = 1000000;
let generateStart = CFAbsoluteTimeGetCurrent()
let list = makeList(cnt)
print("Generated \(cnt) random integers in \(CFAbsoluteTimeGetCurrent() - generateStart) s")

let sortStart = CFAbsoluteTimeGetCurrent()
let _ = mergeSort(list)
print("Sorted \(cnt) integers in \(CFAbsoluteTimeGetCurrent() - sortStart) s")

// swiftc foo.swift:
// Generated 1000000 random integers in 0.310413002967834 s
// Sorted 1000000 integers in 4.01484096050262 s
// 
// real  0m4.349s
// user  0m4.175s
// sys 0m0.089s
// 
// 
// Improved swiftc foo.swift:
// Array append contentsOf calls replaced in _TF4elsa8makeListFVs6UInt32GSaSi_ (1)
// Array append contentsOf calls replaced in _TF4elsa5mergeFT8leftPileGSaSi_9rightPileGSaSi__GSaSi_ (6)
// Generated 1000000 random integers in 0.173403024673462 s
// Sorted 1000000 integers in 1.35956203937531 s
// 
// real  0m1.559s
// user  0m1.482s
// sys 0m0.061s
//
// Sorted ~3x quicker