benchmark/single-source/Queue.swift

//===--- RangeAssignment.swift --------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

import TestsUtils

public let QueueGeneric = BenchmarkInfo(
  name: "QueueGeneric",
  runFunction: run_QueueGeneric,
  tags: [.validation, .api],
  setUpFunction: { buildWorkload() },
  tearDownFunction: nil)

public let QueueConcrete = BenchmarkInfo(
  name: "QueueConcrete",
  runFunction: run_QueueConcrete,
  tags: [.validation, .api],
  setUpFunction: { buildWorkload() },
  tearDownFunction: nil)
 
// TODO: remove when there is a native equivalent in the std lib
extension RangeReplaceableCollection where Self: BidirectionalCollection {
  public mutating func popLast() -> Element? {
    if isEmpty { return nil}
    else { return removeLast() }
  }
}

public struct Queue<Storage: RangeReplaceableCollection>
where Storage: BidirectionalCollection {
  public typealias Element = Storage.Element

  internal var _in: Storage
  internal var _out: Storage
  
  public init() {
    _in = Storage()
    _out = Storage()
  }
}

extension Queue {  
  public mutating func enqueue(_ newElement: Element) {
    _in.append(newElement)
  }

  public mutating func dequeue() -> Element? {
    if _out.isEmpty {
      _out.append(contentsOf: _in.reversed())
      _in.removeAll()
    }
    return _out.popLast()
  }
}

func testQueue<Elements: Collection>(elements: Elements)
where Elements.Element: Equatable {
  var q = Queue<[Elements.Element]>()
  for x in elements { q.enqueue(x) }
  let results = sequence(state: q) { $0.dequeue() }
  let i = results.reduce(0, { i,_ in i &+ 1 })
  for x in elements { q.enqueue(x) }
  let j = results.reduce(i, { i,_ in i &+ 1 })
  CheckResults(j == elements.count*2)
}

let n = 10_000
let workload = (0..<n).map { "\($0): A long enough string to defeat the SSO, or so I hope." }

public func buildWorkload() {
  let contents = workload
  _ = contents.reduce(0) { $0 + $1.count }
}

@inline(never)
func run_QueueGeneric(_ scale: Int) {
  for _ in 0..<scale {
    testQueue(elements: workload)
  }
}

public struct ConcreteQueue {
  internal var _in: [String]
  internal var _out: [String]
  
  public init() {
    _in = Array()
    _out = Array()
  }
}

extension ConcreteQueue {  
  public mutating func enqueue(_ newElement: String) {
    _in.append(newElement)
  }

  public mutating func dequeue() -> String? {
    if _out.isEmpty {
      _out.append(contentsOf: _in.reversed())
      _in.removeAll()
    }
    return _out.popLast()
  }
}

func testConcreteQueue(elements: [String]) {
  var q = ConcreteQueue()
  for x in elements { q.enqueue(x) }
  let results = sequence(state: q) { $0.dequeue() }
  let i = results.reduce(0, { i,_ in i &+ 1 })
  for x in elements { q.enqueue(x) }
  let j = results.reduce(i, { i,_ in i &+ 1 })
  CheckResults(j == elements.count*2)
}


@inline(never)
func run_QueueConcrete(_ scale: Int) {
  for _ in 0..<scale {
    testConcreteQueue(elements: workload)
  }
}