Measure the cost of pre-counting lazy filtered collections when converting to Array, WIP

LazyFilteredCollectionToArrayBenchmark.swift

import Darwin
import CoreFoundation

// A variable we can use with exit() to ensure that the optimizer
// doesn't remove code we want to time
var undead = 0 

// A filtered collection that can be more efficiently counted than the stock one.
struct LazyFilterBidirectionalCollection2<Base : BidirectionalCollection> : Collection {
  typealias Impl = LazyFilterBidirectionalCollection<Base>
  let impl: Impl
  
  var startIndex: Impl.Index { return impl.startIndex }
  var endIndex: Impl.Index { return impl.endIndex }
  
  func makeIterator() -> Impl.Iterator {
    return impl.makeIterator()
  }

  subscript(i: Impl.Index) -> Impl.Iterator.Element {
    return impl[i]
  }

  func index(after i: Impl.Index) -> Impl.Index {
    return impl.index(after: i)
  }
  
  func index(before i: Impl.Index) -> Impl.Index {
    return impl.index(before: i)
  }
  
  init(_ impl: Impl) {
    self.impl = impl
  }

  typealias IndexDistance = Impl.IndexDistance
  var count: IndexDistance {
    var total: IndexDistance = 0
    for _ in impl { total += 1 as IndexDistance }
    return total
  }
}

func timeFilteredArrayConversion<C: BidirectionalCollection>(
  _ c: C, _ label: String, iterations: Int,  _ predicate: @escaping (C.Iterator.Element)->Bool
) {
  print("-------\n\(label): iterations: \(iterations)")
  let sc = c.lazy.filter(predicate)
  let ss = c.lazy.filter(predicate) as LazyFilterSequence

  let sc2 = LazyFilterBidirectionalCollection2(sc)

  let t0 = CFAbsoluteTimeGetCurrent()
  for _ in 0..<iterations {
    undead = undead &+ Array(ss).count
  }
  let t1 = CFAbsoluteTimeGetCurrent()
  for _ in 0..<iterations {
    undead = undead &+ Array(sc2).count
  }
  let t2 = CFAbsoluteTimeGetCurrent()
  for _ in 0..<iterations {
    undead = undead &+ Array(sc).count
  }
  let t3 = CFAbsoluteTimeGetCurrent()

  print("no preallocation", t1 - t0)
  print("count by reducing", t2 - t1)
  print("count by counting", t3 - t2)
}

func runBenchmark<C: BidirectionalCollection>(
  _ label: String, 
  smallSize: Int = 10_000_000,
  _ makeCollection: (CountableRange<Int>) -> C, 
  keepAll: @escaping (C.Iterator.Element) -> Bool,
  keepHalf: @escaping (C.Iterator.Element) -> Bool,
  keepNone: @escaping (C.Iterator.Element) -> Bool
) {
  print("=======\n\(label)")

  let largeSize = smallSize * 10
  let small = makeCollection(0..<smallSize)
  let large = makeCollection(0..<largeSize)
  
  timeFilteredArrayConversion(small, "\(smallSize) \(label), keep all", iterations: 10, keepAll)
  timeFilteredArrayConversion(large, "\(largeSize) \(label), keep all", iterations: 1, keepAll)
  
  timeFilteredArrayConversion(small, "\(smallSize) \(label), keep half", iterations: 10, keepHalf)
  timeFilteredArrayConversion(large, "\(largeSize) \(label), keep half", iterations: 1, keepHalf)
  
  timeFilteredArrayConversion(small, "\(smallSize) \(label), keep none", iterations: 10, keepNone)
  timeFilteredArrayConversion(large, "\(largeSize) \(label), keep none", iterations: 1, keepNone)
}

runBenchmark("Ints", { $0.map {[$0]} }, 
             keepAll: {$0.first! != -1}, keepHalf: {$0.first! & 1 == 0}, keepNone: {$0.first! == -1})
runBenchmark("[Int]s", { $0.map {[$0]} }, 
             keepAll: {$0.first! != -1}, keepHalf: {$0.first! & 1 == 0}, keepNone: {$0.first! == -1})
runBenchmark("lazy mapped [Int]s", smallSize: 1_000_000, { r -> LazyMapRandomAccessCollection<CountableRange<Int>, [Int]> in r.lazy.map {[$0]} }, 
             keepAll: {$0.first! != -1}, keepHalf: {$0.first! & 1 == 0}, keepNone: {$0.first! == -1})
runBenchmark("[([Int], [Int])]s", { $0.map {([$0], [$0 + 1])} }, 
             keepAll: {$0.0.first! != -1}, keepHalf: {$0.0.first! & 1 == 0}, keepNone: {$0.0.first! == -1})
runBenchmark("lazy mapped [([Int], [Int])]s", smallSize: 1_000_000, { r -> LazyMapRandomAccessCollection<CountableRange<Int>, ([Int], [Int])> in r.lazy.map {([$0], [$0 + 1])} }, 
             keepAll: {$0.0.first! != -1}, keepHalf: {$0.0.first! & 1 == 0}, keepNone: {$0.0.first! == -1})

exit(undead & 1 == 0 ? 0 : 1)

Results on my slowpoke computer:

=======
Ints
-------
10000000 Ints, keep all: iterations: 10
no preallocation 4.43979805707932
count by reducing 9.69161397218704
count by counting 10.6043819785118
-------
100000000 Ints, keep all: iterations: 1
no preallocation 21.3222540020943
count by reducing 36.3235419988632
count by counting 35.707288980484
-------
10000000 Ints, keep half: iterations: 10
no preallocation 5.9913130402565
count by reducing 7.4403629899025
count by counting 7.58815002441406
-------
100000000 Ints, keep half: iterations: 1
no preallocation 20.3896369934082
count by reducing 17.9947239756584
count by counting 24.4387440085411
-------
10000000 Ints, keep none: iterations: 10
no preallocation 5.01989901065826
count by reducing 2.95706695318222
count by counting 3.58450800180435
-------
100000000 Ints, keep none: iterations: 1
no preallocation 11.9381369948387
count by reducing 12.633309006691
count by counting 32.3676760196686
=======
[Int]s
-------
10000000 [Int]s, keep all: iterations: 10
no preallocation 4.10637098550797
count by reducing 10.9087879657745
count by counting 12.6934820413589
-------
100000000 [Int]s, keep all: iterations: 1
no preallocation 22.3533889651299
count by reducing 40.3681710362434
count by counting 41.3448309898376
-------
10000000 [Int]s, keep half: iterations: 10
no preallocation 6.21703100204468
count by reducing 8.93813198804855
count by counting 9.00026202201843
-------
100000000 [Int]s, keep half: iterations: 1
no preallocation 21.7443950176239
count by reducing 26.68372797966
count by counting 35.1635410189629
-------
10000000 [Int]s, keep none: iterations: 10
no preallocation 5.60520899295807
count by reducing 3.39811301231384
count by counting 4.40284895896912
-------
100000000 [Int]s, keep none: iterations: 1
no preallocation 13.7264239788055
count by reducing 13.1998640298843
count by counting 34.2767069935799
=======
lazy mapped [Int]s
-------
1000000 lazy mapped [Int]s, keep all: iterations: 10
no preallocation 2.97119998931885
count by reducing 6.60435199737549
count by counting 6.65158402919769
-------
10000000 lazy mapped [Int]s, keep all: iterations: 1
no preallocation 3.1414960026741
count by reducing 6.5491150021553
count by counting 6.2759929895401
-------
1000000 lazy mapped [Int]s, keep half: iterations: 10
no preallocation 2.4695879817009
count by reducing 5.38691699504852
count by counting 5.27106499671936
-------
10000000 lazy mapped [Int]s, keep half: iterations: 1
no preallocation 2.64799898862839
count by reducing 5.57331103086472
count by counting 5.56495100259781
-------
1000000 lazy mapped [Int]s, keep none: iterations: 10
no preallocation 2.2107470035553
count by reducing 2.12528699636459
count by counting 2.01414400339127
-------
10000000 lazy mapped [Int]s, keep none: iterations: 1
no preallocation 2.37625998258591
count by reducing 2.20341604948044
count by counting 1.96827894449234
=======
[([Int], [Int])]s
-------
10000000 [([Int], [Int])]s, keep all: iterations: 10
no preallocation 11.5341950058937
count by reducing 27.7522740364075
count by counting 21.6997439861298
-------
100000000 [([Int], [Int])]s, keep all: iterations: 1
no preallocation 67.5512109994888
count by reducing 105.794189989567
count by counting 97.2051550149918
-------
10000000 [([Int], [Int])]s, keep half: iterations: 10
no preallocation 14.4360269904137
count by reducing 18.4714570045471
count by counting 16.664214015007
-------
100000000 [([Int], [Int])]s, keep half: iterations: 1
no preallocation 57.9028039574623
count by reducing 104.645868003368
count by counting 93.2313390374184
-------
10000000 [([Int], [Int])]s, keep none: iterations: 10
no preallocation 13.4023489952087
count by reducing 12.4180989861488
count by counting 15.3729599714279
-------
100000000 [([Int], [Int])]s, keep none: iterations: 1
no preallocation 30.2365120053291
count by reducing 30.1292479634285
count by counting 97.5843870043755
=======
lazy mapped [([Int], [Int])]s
-------
1000000 lazy mapped [([Int], [Int])]s, keep all: iterations: 10
no preallocation 6.2127600312233
count by reducing 14.8382480144501
count by counting 13.7598659992218
-------
10000000 lazy mapped [([Int], [Int])]s, keep all: iterations: 1
no preallocation 5.65660601854324
count by reducing 13.7244889736176
count by counting 13.5696310400963
-------
1000000 lazy mapped [([Int], [Int])]s, keep half: iterations: 10
no preallocation 5.1170009970665
count by reducing 10.9582349658012
count by counting 10.2799320220947
-------
10000000 lazy mapped [([Int], [Int])]s, keep half: iterations: 1
no preallocation 5.09667199850082
count by reducing 11.3804849982262
count by counting 10.6742680072784
-------
1000000 lazy mapped [([Int], [Int])]s, keep none: iterations: 10
no preallocation 4.71599102020264
count by reducing 4.61118400096893
count by counting 3.93769496679306
-------
10000000 lazy mapped [([Int], [Int])]s, keep none: iterations: 1
no preallocation 4.47975999116898
count by reducing 4.31283700466156
count by counting 3.90426999330521