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)
}

timeFilteredArrayConversion(0..<100_000_000, "100K Ints, keep all", iterations: 10) { $0 != -1 }
timeFilteredArrayConversion(0..<1_000_000_000, "1M Ints, keep all", iterations: 1) { $0 != -1 }

timeFilteredArrayConversion(0..<100_000_000, "100K Ints, keep half", iterations: 10) { $0 & 1 == 0 }
timeFilteredArrayConversion(0..<1_000_000_000, "1M Ints, keep half", iterations: 1) { $0 & 1 == 0 }

timeFilteredArrayConversion(0..<100_000_000, "100K Ints, keep none", iterations: 10) { $0 == -1 }
timeFilteredArrayConversion(0..<1_000_000_000, "1M Ints, keep none", iterations: 1) { $0 == -1 }

// TODO: do the same kinds of tests with collections of both eager and
// lazy things that contain one or two references (e.g.
//
//   [[Int]]
//   0..<N.lazy.map {[$0]}
//   [([Int],[Int])]
//   0..<N.lazy.map {([$0],[$0 + 1])}

So far this is looking like counting before allocation is very seldom a win:

swiftc x.swift -O -o /tmp/x && /tmp/x
-------
100K Ints, keep all: iterations: 10
no preallocation 11.8613370060921
count by reducing 14.1059579849243
count by counting 17.392293035984
-------
1M Ints, keep all: iterations: 1
no preallocation 17.075178027153
count by reducing 15.4278219938278
count by counting 18.7781310081482
-------
100K Ints, keep half: iterations: 10
no preallocation 7.82134997844696
count by reducing 11.3612000346184
count by counting 12.2089709639549
-------
1M Ints, keep half: iterations: 1
no preallocation 10.2271029949188
count by reducing 12.1018710136414
count by counting 13.9417160153389
-------
100K Ints, keep none: iterations: 10
no preallocation 3.12475001811981
count by reducing 3.12709802389145
count by counting 2.88343799114227
-------
1M Ints, keep none: iterations: 1
no preallocation 3.42199802398682
count by reducing 3.37954998016357
count by counting 3.2027440071106