FuncVsImperative

main.swift

//
//  main.swift
//  FuncVsImperative
//
//  Created by Pavol Vaskovic on 17.12.2014.
//  Copyright (c) 2014 Pavol Vaskovic. All rights reserved.
//

import Cocoa

/*

 The motivation for this excercise is to find best performing functional style (a la Haskell) implementation of core loop in  Mandelbrot set generator. In utopic ideal world this would have performance equivalent to the following imperative loop:

var iteration = 0
var z = ComplexNumber() // ℂ
do {
z = z * z + c
iteration++
} while (z.normal() < 2 && iteration < maxIter)


The functional implementation decomposes the computation into logical components (what), instead of describing the minutiae of the computation (how):

let quadrat: (ℂ, ℂ) -> ℂ = {c, z in z*z + c}
let orbit: ℂ -> GeneratorOf<ℂ> = {c in iterate(curry(quadrat)(c), ℂ(0))}
let iterations: GeneratorOf<ℂ> -> Int = {seq in
  length(takeWhile({z in z.normal() < 2}, take(maxIter, seq)))
}
iterations(orbit(ℂ(re, i:im)))

# Open questions for the Swift compiler team, Swift 1.1

* Combination of SequenceOf and GeneratorOf leads to poorer perf then GeneratorOf only. This seems to be importatnt for re-iterable sequences. Why the difference?
* What does -Ounchecked do? It results in 20_000x improvement in optimized code for the simplest tight loop, compared to the other forms, that have comparable performance when -O is used.

*/

public struct TakeSequence<S: Sequence>: Sequence {
    private let sequence: S
    private let n: Int
    
    public init(_ sequence: S, _ n: Int) {
        self.sequence = sequence
        self.n = n
    }
    
    public func makeIterator() -> AnyIterator<S.Iterator.Element> {
        var count = 0
        var generator = self.sequence.makeIterator()
        return AnyIterator<S.Iterator.Element> {
            count += 1
            if count > self.n {
                return nil
            } else {
                return generator.next()
            }
        }
    }
}

func take2 <S : Sequence>(_ count: Int, _ source: S) -> AnySequence<S.Iterator.Element> {
    return AnySequence(TakeSequence(source, count))
}

public struct TakeWhileSequence<S: Sequence>: Sequence {
    private let sequence: S
    private let condition: (S.Iterator.Element) -> Bool
    
    public init(_ sequence:S, _ condition:@escaping (S.Iterator.Element) -> Bool) {
        self.sequence = sequence
        self.condition = condition
    }
    
    public func makeIterator() -> AnyIterator<S.Iterator.Element> {
        var generator = self.sequence.makeIterator()
        var endConditionMet = false
        return AnyIterator<S.Iterator.Element> {
            let next: S.Iterator.Element? = generator.next()
            if !endConditionMet && next != nil {
                endConditionMet = !self.condition(next!)
            }
            if endConditionMet {
                return nil
            } else {
                return next
            }
        }
    }
}

func takeWhile2<S : Sequence>(_ includeElement: @escaping (S.Iterator.Element) -> Bool, _ source: S) -> AnySequence<S.Iterator.Element> {
        return AnySequence(TakeWhileSequence(source, includeElement))
}

public struct IterateSequence<A>: Sequence {
    typealias Element  = A
    
    private let x0: A
    private let f: (A) -> A
    
    public init(f: @escaping (A) -> A, x x0: A) {
        self.x0 = x0
        self.f = f
    }
    public func makeIterator() -> AnyIterator<A> {
        var x = x0
        return AnyIterator {
            let previous = x
            x = self.f(x)
            return previous
        }
    }
}

func iterate2<A>(_ f: @escaping (A) -> A, _ x0: A) -> AnySequence<A> {
    return AnySequence(IterateSequence(f: f, x: x0))
}

func iterate<A>(_ f: @escaping (A) -> A, _ x0: A) -> AnyIterator<A> {
    var x = x0
    return AnyIterator {
        let previous = x
        x = f(x)
        return previous
    }
}

func iterateAlt<A>(_ f: @escaping (A) -> A, _ x0: A) -> AnyIterator<A> {
    var x = x0
    return AnyIterator {
        defer { x = f(x) }
        return x
    }
}

struct RepeatedApplicationSequence: Sequence, IteratorProtocol {
    var x: Int
    let f: (Int) -> Int
    
    mutating func next() -> Int? {
        defer { x = f(x) }
        return x
    }
}



func takeWhile<S : Sequence>(_ includeElement: @escaping (S.Iterator.Element) -> Bool, _ source: S) -> AnyIterator<S.Iterator.Element> {
    var g = source.makeIterator()
    
    return AnyIterator {
        if let e = g.next() {
            return includeElement(e) ? e : .none
        } else {
            return .none
        }
    }
}

// TODO: Looks like AnySequence has a `prefix` method that seems equivalent to Haskell's take()

func take<S : Sequence>(_ count: Int, _ source: S) -> AnyIterator<S.Iterator.Element> {
    var i = 0
    var g = source.makeIterator()
    
    return AnyIterator {
        defer {i += 1}
        return (i < count) ? g.next() : .none
    }
}

func time<T>(_ fn: () -> T) -> (T, Double) {
    let start = CACurrentMediaTime();
    let result = fn();
    let stop = CACurrentMediaTime()
    return (result, stop - start)
}


func timeLoops(_ loops: [(String, () -> Int)]) {
    var timedLoops = [(String, Double)]()

    print("---Timing Loops...")
    for (name, loop) in loops {
        let (sum, timing) = time(loop)
        print(String(format:"\(name) \t %.2f \t \(sum)", timing))
        timedLoops.append((name, timing))
    }
    print("---Results:")
    
    timedLoops.sort { $0.1 < $1.1 }
    let best = timedLoops[0]
    
    for (name, time) in timedLoops {
        print(String(format:"\(name) is %.2fx of \(best.0)", time / best.1))
    }

}

let numIter = Int((CommandLine.arguments.last?.replacingOccurrences(of: "_", with: ""))!)
let iterations : Int = numIter ?? 100_000//_000

// TODO test replacing closure with functions: inc, inc2, Int.successor

func inc(_ i: Int) -> Int {
    return i + 1
}

func sum<S: Sequence>(_ s: S) -> Int where S.Iterator.Element == Int {
    var sum = 0
    for i in s {
        sum += i
    }
    return sum
}

// Imperative loops

let forImperative: () -> Int = {
    var sum = 0
    for i in 0 ..< iterations {
        sum += i
    }
    return sum
}

let forImperativeS3: () -> Int = {
    var sum = 0
    for i in 0 ..< iterations {
        sum += i
    }
    return sum
}

let whileLoop: () -> Int = {
    var sum = 0
    var i = 0
    while (i < iterations) {
        sum += i
        i += 1
    }
    return sum
}

let whileLoop2: () -> Int = {
    var sum = 0
    var i = 0
    while (i < iterations) {
        sum += i
        i += 1
    }
    return sum
}

let whileLet: () -> Int = {
    var sum = 0
    var i = (0..<iterations).makeIterator()
    while let b = i.next() {
        sum += b
    }
    return sum
}

// Loops with Range Generator

let forIn: () -> Int = {
    var sum = 0
    for i in 0..<iterations {
        sum += i
    }
    return sum
}

let sumRange: () -> Int = { return sum(0..<iterations) }

let reduced: () -> Int = {
//    return reduce(0..<iterations, 0, +)
    return (0..<iterations).reduce(0, +)
}

let whileManualIterator: () -> Int = {
    var sum = 0
    var i = (0..<iterations).makeIterator()
    var b: Int? = i.next()
    while (b != nil) {
        sum += b!
        b = i.next()
    }
    return sum
}

// Loops with Iterate Generator

let whileIterate: () -> Int = {
    var sum = 0
    var i = iterate({$0 + 1}, 0).makeIterator()
    var b: Int! = i.next()
    while (b < iterations) {
        sum += b
        b = i.next()
    }
    return sum
}

let whileLetIterate: () -> Int = {
    var sum = 0
    var i = iterate({$0 + 1}, 0).makeIterator()
    while let b = i.next(), b < iterations {
        sum += b
    }
    return sum
}

// TODO define func sum(s: SequenceType) that performs the sum; compare it to reduce - should be the same
// If so, then rewrite all multiline definitions to only define the sequence (the variable we are trully testing here)

let forInIterate: () -> Int = {
    var sum = 0
    for b in take(iterations, iterate({$0 + 1}, 0)) {
        sum += b
    }
    return sum
}

let sumIterate: () -> Int = { return sum(take(iterations, iterate({$0 + 1}, 0)))}

let forInIterateInc: () -> Int = {
    var sum = 0
    for b in take(iterations, iterate(inc, 0)) {
        sum += b
    }
    return sum
}

let reduceTakeIterate: () -> Int = {
    return take(iterations, iterate({$0 + 1}, 0)).reduce(0, +)
}

let reduceTake2Iterate2: () -> Int = {
    let iter = iterate2({$0 + 1}, 0)
    return take2(iterations, iter).reduce(0, +)
}

let reduceTakeRange: () -> Int = {take(iterations, 0..<iterations).reduce(0, +)}
let reduceTake2Range: () -> Int = {take2(iterations, 0..<iterations).reduce(0, +)}

// Why Slow? Optimization fails:
// 1) Generic specialization
// 2) Inlining
// 3) ???


let warmup: [(String, () -> Int)] = [
    "warmup1" : forImperative,
    "warmup2" : forImperative,
    ].map({name, loop in (name, loop)})

timeLoops(warmup)


let simpleLoops: [(String, () -> Int)] = [
    "for      " : forImperative,
    "for_in   " : forIn,
    "while    " : whileLoop,
    "whileLet " : whileLet,
    "whileManu" : whileManualIterator,
    "whileLetI" : whileLetIterate,
    "reduce   " : reduced,
    "sumRange " : sumRange,
    ].map({name, loop in (name, loop)})

timeLoops(simpleLoops)


let basicLoops: [(String, () -> Int)] = [
    "for      " : forImperative,
    "for Swif3" : forImperativeS3,
    "for_in   " : forIn,
    "while    " : whileLoop,
    "while2   " : whileLoop2,
    "reduce   " : reduced,
    "sumRange " : sumRange,
    "sumIterat" : sumIterate,
    "while_gen" : whileManualIterator,
    "while_ite" : whileIterate,
    "for_in_It" : forInIterate,
    "for_in_II" : forInIterateInc,
    "reduceTaI" : reduceTakeIterate,
    "reduceT2I2" : reduceTake2Iterate2,
    "reduceTaR" : reduceTakeRange,
    "reduceT2R" : reduceTake2Range,
    ].map({name, loop in (name, loop)})

//timeLoops(basicLoops)

let reduceTakeWhileIterate: () -> Int = {
    return takeWhile({$0 < iterations}, iterate({$0 + 1}, 0)).reduce(0, +)
}

let reduceTakeWhileTakeIterate: () -> Int = {
    return takeWhile({$0 < iterations}, take(iterations, iterate({$0 + 1}, 0))).reduce(0, +)
}

let reduceTakeWhile2Take2Iterate2: () -> Int = {
    return takeWhile2({$0 < iterations}, take2(iterations, iterate2({$0 + 1}, 0))).reduce(0, +)
}

let takeWhileRange: () -> Int = {
    var sum = 0
    let i = takeWhile({$0 < iterations}, (0..<iterations).makeIterator())
    for b in i {
        sum += b
    }
    return sum
}

let takeWhile2Range: () -> Int = {
    var sum = 0
    let i = takeWhile2({$0 < iterations}, (0..<iterations).makeIterator())
    for b in i {
        sum += b
    }
    return sum
}

let takeWhileIterate: () -> Int = {
    var sum = 0
    let i = takeWhile({$0 < iterations}, iterate({$0 + 1}, 0))
    for b in i {
        sum += b
    }
    return sum
}

let takeWhile2Iterate2: () -> Int = {
    var sum = 0
    let i = takeWhile2({$0 < iterations}, iterate2({$0 + 1}, 0))
    for b in i {
        sum += b
    }
    return sum
}

let takeWhileTakeIterate: () -> Int = {
    var sum = 0
    let i = takeWhile({$0 < iterations}, take(iterations, iterate({$0 + 1}, 0)))
    for b in i {
        sum += b
    }
    return sum
}

let takeWhile2Take2Iterate2: () -> Int = {
    var sum = 0
    let i = takeWhile2({$0 < iterations}, take2(iterations, iterate2({$0 + 1}, 0)))
    for b in i {
        sum += b
    }
    return sum
}

let loops =  basicLoops + [
//    "for_in   " : forIn,
    "takeWhile" : takeWhileRange,
    "takeWh_R2" : takeWhile2Range,
//    "reduce   " : reduced,
    "reduce_TI" : reduceTakeIterate,
    "reduce_TR" : reduceTakeRange,
    "reduce_T2" : reduceTake2Range,
    "reduceTWI" : reduceTakeWhileIterate,
    "redTWhTaI" : reduceTakeWhileTakeIterate,
    "redTW2T2I2" : reduceTakeWhile2Take2Iterate2,
    "takeW_Ite" : takeWhileIterate,
    "takeW2I2" : takeWhile2Iterate2,
    "takeWhTaI" : takeWhileTakeIterate,
    "takeW2T2I2" : takeWhile2Take2Iterate2,
    ].map({name, loop in (name, loop)})

//timeLoops(loops)

This is a 2016 Iterator based rewrite of the original version from 2014 that was build on top of Generators.