[swift-evolution] Reduce with inout

[Dave Abrahams]

on Mon Jan 16 2017, Charles Srstka <swift-evolution at swift.org> wrote:

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

The diagnostic could be better, but the compiler shouldn't let you do
that, because it requires passing an unnamed temporary value ([Int]())
as inout.

> 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,

The closure *does* return something: (), the empty tuple

> 
> 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. 

Well, no surprise: the non-mutating version is an O(N^2) algorithm.

> 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
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
-Dave