[swift-evolution] Reduce with inout

[Charles Srstka]

> On Jan 16, 2017, at 7:49 AM, Chris Eidhof via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Hi,
> 
> How does everyone feel about adding a second version of `reduce` to `Sequence`? Instead of a `combine` function that's of type `(A, Element) -> A`, it would be `(inout A, Element) -> ()`. This way, we can write nice functionals algorithms, but have the benefits of inout (mutation within the function, and hopefully some copy eliminations).
> 
> IIRC, Loïc Lecrenier first asked this on Twitter. I've been using it ever since, because it can really improve readability (the possible performance gain is nice, too).
> 
> Here's `reduce` with an `inout` parameter, including a sample: https://gist.github.com/chriseidhof/fd3e9aa621569752d1b04230f92969d7
> 
> -- 
> Chris Eidhof

I did this in my own private code a while ago. There is one drawback, which is that Swift’s type inference system isn’t quite up to handling it. For example, doing this results in an “ambiguous reference to member” warning:

range.reduce([Int]()) { $0.append($1) }

One would think that the type of this closure should be clear:

1) The closure calls append(), a mutating function, so $0 must be inout.

2) The closure doesn’t return anything, which should rule out the default implementations of reduce, all of which should require the closure to return [Int].

This means that the closure has to be explicitly typed, as you did in your example, which is kind of cumbersome.

However, the performance benefits are simply astonishing:

import Foundation

extension Sequence {
	func reduce<A>(_ initial: A, combine: (inout A, Iterator.Element) -> ()) -> A {
		var result = initial
		for element in self {
			combine(&result, element)
		}
		return result
	}
}

func timeIt<T>(closure: () -> T) -> T {
	let startDate = Date()
	defer { print("elapsed: \(Date().timeIntervalSince(startDate))") }
	return closure()
}

let range = 0..<1000000

let arr1: [Int] = timeIt {
	var arr: [Int] = []
	
	for i in range {
		arr.append(i)
	}
	
	return arr
}

// use the array, to prevent this from all getting optimized away
print("arr1 has \(arr1.count) elements")

let arr2 = timeIt { range.reduce([]) { (arr: inout [Int], elem) in arr.append(elem) } }
print("yours has \(arr2.count) elements")

let arr3 = timeIt { range.reduce([]) { $0 + [$1] } }
print("default reduce has \(arr3.count) elements”)

- - - - - - -

Compiling with optimizations on and running, the output of this is:

elapsed: 0.0109230279922485
arr1 has 1000000 elements
elapsed: 0.00743597745895386
yours has 1000000 elements

You may notice the lack of output for arr3. That’s because even though I started running this thing ten minutes ago, it still hasn’t finished. That’s right; the for loop and the inout reduce can both finish this in about 0.01 seconds, whereas the copy-based reduce() needs something greater than 10 minutes. I don’t even know how long it actually takes to finish this test, because the last time I did this I eventually got sick of waiting and killed the process. So, I don’t know quite how many orders of magnitude slower it is, but it’s a lot.

Charles