on Mon Jan 16 2017, Charles Srstka <[email protected]> wrote:
>> On Jan 16, 2017, at 7:49 AM, Chris Eidhof via swift-evolution >> <[email protected]> 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 > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution -- -Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
