PartitioningIndex Index Benchmarks

main.swift

import Algorithms
import CollectionsBenchmark

// Adaptation of original solution at
// https://github.com/objcio/OptimizingCollections/blob/master/Sources/SortedArray.swift
extension Collection {
  @inlinable
  func partitioningIndex2(
    where belongsInSecondPartition: (Element) throws -> Bool
  ) rethrows -> Index where Index == Int {
    var start = 0
    var end = self.count
    while start < end {
      let diff = end - start
      if diff < 1024 {
        let middle = start + diff >> 1
        if try !belongsInSecondPartition(self[middle]) {
          start = middle + 1
        }
        else {
          end = middle
        }
      }
      else {
        let third = diff / 3
        let m1 = start + third
        let m2 = end - third
        let v1 = self[m1]
        let v2 = self[m2]
        if try belongsInSecondPartition(v1) {
          end = m1
        }
        else if try !belongsInSecondPartition(v2) {
          start = m2 + 1
        }
        else {
          start = m1
          end = m2 + 1
        }
      }
    }
    return start
  }
}

var benchmark = Benchmark(title: "Demo Benchmark")

benchmark.add(
  title: "PartitioningIndex (Vanilla)",
  input: ([Int], [Int]).self
) { input, pivots in
  let sortedInput = input.sorted()
  return { timer in
    for pivot in pivots {
      blackHole(sortedInput.partitioningIndex{ $0 > pivot })
    }
  }
}

benchmark.add(
  title: "PartitioningIndex (objc.io)",
  input: ([Int], [Int]).self
) { input, pivots in
  let sortedInput = input.sorted()
  return { timer in
    for pivot in pivots {
      blackHole(sortedInput.partitioningIndex2{ $0 > pivot })
    }
  }
}

benchmark.main()