Reduce with inout


(Chris Eidhof) #1

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


(Dave Abrahams) #2

+1

···

on Mon Jan 16 2017, Chris Eidhof <swift-evolution@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

--
-Dave


(Charles Srstka) #3

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

···

On Jan 16, 2017, at 7:49 AM, Chris Eidhof via swift-evolution <swift-evolution@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


(Dave Abrahams) #4

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.

···

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

On Jan 16, 2017, at 7:49 AM, Chris Eidhof via swift-evolution <swift-evolution@swift.org> wrote:

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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
-Dave


(Ben Cohen) #5

+1

Instead of a filter reimplementation for the proposal, might be good to do something that doesn’t exist this would be useful for, like a version of Unix uniq that filters adjacent equal entries.

···

On Jan 16, 2017, at 5:49 AM, Chris Eidhof via swift-evolution <swift-evolution@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Karl) #6

+1

I would even argue for it to be the default.

···

On 16 Jan 2017, at 14:49, Chris Eidhof via swift-evolution <swift-evolution@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Russ Bishop) #7

That’s all the endorsement I need. +1 from me.

I do wonder if there is any way to get this sort of optimization out of the compiler. I suppose it would be difficult because the compiler doesn’t know what the mutable vs immutable pairs are or if such a pair even exists (array doesn’t have appending()).

If we assume + for Array had a mutating variant ala func + (lhs: inout Array, rhs: Array) { … }, would the compiler be able to prefer the inout version? What if a type wanted to offer a specialized version of a function for the compiler to call when the compiler can prove only temporaries are involved? I don’t want to go too far down the road of move constructors and whatnot for that way lies madness.

(Not a compiler expert, just wondering if there is a way to make situations like this into a “pit of success”).

Russ

···

On Jan 16, 2017, at 9:43 AM, Charles Srstka via swift-evolution <swift-evolution@swift.org> wrote:

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.


(Step C) #8

I like it.

Inicio del mensaje reenviado:

···

De: Dave Abrahams via swift-evolution <swift-evolution@swift.org>
Fecha: 16 de enero de 2017, 5:15:23 PM GMT+1
Para: swift-evolution@swift.org
Asunto: Re: [swift-evolution] Reduce with inout
Responder a: Dave Abrahams <dabrahams@apple.com>

on Mon Jan 16 2017, Chris Eidhof <swift-evolution@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

+1

--
-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Charles Srstka) #9

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.

No it doesn’t. The signature of the method is:

func reduce<A>(_ initial: A, combine: (inout A, Iterator.Element) -> ()) -> A

The unnamed temporary value is “initial” here, which is not passed as inout; the inout parameter is the first argument to the “combine” closure. The value represented by the ‘initial’ parameter is passed to the closure, true, but only after being stored in a not-unnamed ‘var’ variable, as you can see from the source of the proposed method:

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

Therefore, I don’t understand this objection.

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

But it’s not what it’s supposed to return. Sequence’s implementation of reduce, which the compiler thinks matches the above, is declared like this:

public func reduce<Result>(_ initialResult: Result, _ nextPartialResult: (Result, Self.Iterator.Element) throws -> Result) rethrows -> Result

The closure is supposed to return Result, which in this case would be [Int]. It doesn’t, so I’m not sure why the compiler is thinking this is a match.

Charles

···

On Jan 16, 2017, at 6:42 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

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

On Jan 16, 2017, at 7:49 AM, Chris Eidhof via swift-evolution <swift-evolution@swift.org> wrote:


(Karl) #10

I mean, assuming having two “reduce”s would stress the typechecker, as Joe suggested it might, I would say “inout” makes sense to be the default and the other one can find itself a new name.

···

On 17 Jan 2017, at 23:09, Karl Wagner <karl.swift@springsup.com> wrote:

On 16 Jan 2017, at 14:49, Chris Eidhof via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

+1

I would even argue for it to be the default.


(Charles Srstka) #11

The (somewhat naïve) assumption that some optimization of this sort might be going on is what led me to do the speed test in the first place. However, when you think about it, it’d be really quite hard to do. A reduce that builds an array consists of the closure that adds something to an array, and the reduce function itself. With the code to both of these, it’s not inconceivable that the compiler could figure out what you’re doing, but unfortunately the two components live in different modules / compilation units. The closure doesn’t know that its return value is just going to be replacing the passed-in value, and the reduce function doesn’t know that the closure isn’t going to store the original array somewhere, so neither can really know that it’s safe to modify the array in place.

Charles

···

On Jan 21, 2017, at 12:37 AM, Russ Bishop <xenadu@gmail.com> wrote:

On Jan 16, 2017, at 9:43 AM, Charles Srstka via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

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.

That’s all the endorsement I need. +1 from me.

I do wonder if there is any way to get this sort of optimization out of the compiler. I suppose it would be difficult because the compiler doesn’t know what the mutable vs immutable pairs are or if such a pair even exists (array doesn’t have appending()).


(Dave Abrahams) #12

Okay, sounds like I'm totally wrong! Has to happen at least once in a
lifetime, doesn't it? :wink:

So please file bug reports for these issues.

···

on Mon Jan 16 2017, Charles Srstka <cocoadev-AT-charlessoft.com> wrote:

On Jan 16, 2017, at 6:42 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

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

On Jan 16, 2017, at 7:49 AM, Chris Eidhof via swift-evolution <swift-evolution@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.

No it doesn’t. The signature of the method is:

func reduce<A>(_ initial: A, combine: (inout A, Iterator.Element) -> ()) -> A

The unnamed temporary value is “initial” here, which is not passed as inout; the inout parameter is
the first argument to the “combine” closure. The value represented by the ‘initial’ parameter is
passed to the closure, true, but only after being stored in a not-unnamed ‘var’ variable, as you can
see from the source of the proposed method:

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

Therefore, I don’t understand this objection.

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

But it’s not what it’s supposed to return. Sequence’s implementation
of reduce, which the compiler thinks matches the above, is declared
like this:

public func reduce<Result>(_ initialResult: Result, _
nextPartialResult: (Result, Self.Iterator.Element) throws -> Result)
rethrows -> Result

The closure is supposed to return Result, which in this case would be
[Int]. It doesn’t, so I’m not sure why the compiler is thinking this
is a match.

--
-Dave


(Joe Groff) #13

This one should already be fixed in master. If it isn't, definitely file a new one!

-Joe

···

On Jan 16, 2017, at 8:10 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Mon Jan 16 2017, Charles Srstka <cocoadev-AT-charlessoft.com> wrote:

On Jan 16, 2017, at 6:42 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

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

On Jan 16, 2017, at 7:49 AM, Chris Eidhof via swift-evolution <swift-evolution@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.

No it doesn’t. The signature of the method is:

func reduce<A>(_ initial: A, combine: (inout A, Iterator.Element) -> ()) -> A

The unnamed temporary value is “initial” here, which is not passed as inout; the inout parameter is
the first argument to the “combine” closure. The value represented by the ‘initial’ parameter is
passed to the closure, true, but only after being stored in a not-unnamed ‘var’ variable, as you can
see from the source of the proposed method:

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

Therefore, I don’t understand this objection.

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

But it’s not what it’s supposed to return. Sequence’s implementation
of reduce, which the compiler thinks matches the above, is declared
like this:

public func reduce<Result>(_ initialResult: Result, _
nextPartialResult: (Result, Self.Iterator.Element) throws -> Result)
rethrows -> Result

The closure is supposed to return Result, which in this case would be
[Int]. It doesn’t, so I’m not sure why the compiler is thinking this
is a match.

Okay, sounds like I'm totally wrong! Has to happen at least once in a
lifetime, doesn't it? :wink:

So please file bug reports for these issues.


(David Sweeris) #14

IIRC, the "reduce" name comes from functional programming... should the functional style keep the functional name?

- Dave Sweeris

···

On Jan 17, 2017, at 16:11, Karl Wagner via swift-evolution <swift-evolution@swift.org> wrote:

On 17 Jan 2017, at 23:09, Karl Wagner <karl.swift@springsup.com> wrote:

On 16 Jan 2017, at 14:49, Chris Eidhof via swift-evolution <swift-evolution@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

+1

I would even argue for it to be the default.

I mean, assuming having two “reduce”s would stress the typechecker, as Joe suggested it might, I would say “inout” makes sense to be the default and the other one can find itself a new name.


(Xiaodi Wu) #15

Agree. The functional style should keep the functional name.

···

On Tue, Jan 17, 2017 at 16:18 David Sweeris via swift-evolution < swift-evolution@swift.org> wrote:

On Jan 17, 2017, at 16:11, Karl Wagner via swift-evolution < > swift-evolution@swift.org> wrote:

On 17 Jan 2017, at 23:09, Karl Wagner <karl.swift@springsup.com> wrote:

On 16 Jan 2017, at 14:49, Chris Eidhof via swift-evolution < > swift-evolution@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

+1

I would even argue for it to be the default.

I mean, assuming having two “reduce”s would stress the typechecker, as Joe
suggested it might, I would say “inout” makes sense to be the default and
the other one can find itself a new name.

IIRC, the "reduce" name comes from functional programming... should the
functional style keep the functional name?

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(TJ Usiyan) #16

Is there any chance that the forthcoming memory annotations could help
here? If we had some way to signify that the item returned from each call
to the closure should be connected to the incoming argument…

···

On Sat, Jan 21, 2017 at 2:27 AM, Charles Srstka via swift-evolution < swift-evolution@swift.org> wrote:

On Jan 21, 2017, at 12:37 AM, Russ Bishop <xenadu@gmail.com> wrote:

On Jan 16, 2017, at 9:43 AM, Charles Srstka via swift-evolution < > swift-evolution@swift.org> wrote:

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

That’s all the endorsement I need. +1 from me.

I do wonder if there is any way to get this sort of optimization out of
the compiler. I suppose it would be difficult because the compiler doesn’t
know what the mutable vs immutable pairs are or if such a pair even exists
(array doesn’t have appending()).

The (somewhat naïve) assumption that some optimization of this sort might
be going on is what led me to do the speed test in the first place.
However, when you think about it, it’d be really quite hard to do. A reduce
that builds an array consists of the closure that adds something to an
array, and the reduce function itself. With the code to both of these, it’s
not inconceivable that the compiler could figure out what you’re doing, but
unfortunately the two components live in different modules / compilation
units. The closure doesn’t know that its return value is just going to be
replacing the passed-in value, and the reduce function doesn’t know that
the closure isn’t going to store the original array somewhere, so neither
can really know that it’s safe to modify the array in place.

Charles

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Russ Bishop) #17

I was thinking of an optimization like this:

1. The closure or function doesn’t capture anything (and thus by definition nothing can escape the closure)
2. ???
3. Therefore input returns true for isUniquelyReferenced and no copying of the underlying storage is required (Profit!)

The problem is obviously in step 2. We don’t have any way to express the necessary contract other than inout, which requires a separate definition. If it worked like throws/rethrows where a non-mutating closure promoted to an inout closure then we could just change the definition of reduce (though you’d still have to return the value). The compiler would need to understand that ownership of the underlying array storage moves from the input parameter to the constructed array inside the closure (and ultimately the return value). That’s a bit of a tall order.

That leads me to think about why inout is required (because isKnownUniquelyReferenced returns false otherwise). Why can’t the compiler determine that the intermediate array is unique? Take this program:
func doSomething(_ x: MyStruct) -> MyStruct {
    var mutX = x
    let isUnique = isKnownUniquelyReferenced(&mutX.refTypeInstance)
    print("isUnique = \(isUnique)") //prints false
    return mutX
}
doSomething(MyStruct())

The fact that storage is uniquely owned is trivially provable to a human but not to the compiler. Why?

These are just idle musings. My suspicion is you need ownership annotations (aka borrow checker) to make this tractable but I don’t have any proof of that.

Russ

···

On Jan 20, 2017, at 11:27 PM, Charles Srstka <cocoadev@charlessoft.com> wrote:

On Jan 21, 2017, at 12:37 AM, Russ Bishop <xenadu@gmail.com <mailto:xenadu@gmail.com>> wrote:

On Jan 16, 2017, at 9:43 AM, Charles Srstka via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

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.

That’s all the endorsement I need. +1 from me.

I do wonder if there is any way to get this sort of optimization out of the compiler. I suppose it would be difficult because the compiler doesn’t know what the mutable vs immutable pairs are or if such a pair even exists (array doesn’t have appending()).

The (somewhat naïve) assumption that some optimization of this sort might be going on is what led me to do the speed test in the first place. However, when you think about it, it’d be really quite hard to do. A reduce that builds an array consists of the closure that adds something to an array, and the reduce function itself. With the code to both of these, it’s not inconceivable that the compiler could figure out what you’re doing, but unfortunately the two components live in different modules / compilation units. The closure doesn’t know that its return value is just going to be replacing the passed-in value, and the reduce function doesn’t know that the closure isn’t going to store the original array somewhere, so neither can really know that it’s safe to modify the array in place.

Charles


(Sean Heber) #18

`reuse`

Then we just need an excuse for a function named ‘recycle’...

l8r
Sean

···

On Jan 17, 2017, at 7:36 PM, T.J. Usiyan via swift-evolution <swift-evolution@swift.org> wrote:

`reduceInout`

On Tue, Jan 17, 2017 at 6:30 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:
Agree. The functional style should keep the functional name.

On Tue, Jan 17, 2017 at 16:18 David Sweeris via swift-evolution <swift-evolution@swift.org> wrote:

On Jan 17, 2017, at 16:11, Karl Wagner via swift-evolution <swift-evolution@swift.org> wrote:

On 17 Jan 2017, at 23:09, Karl Wagner <karl.swift@springsup.com> wrote:

On 16 Jan 2017, at 14:49, Chris Eidhof via swift-evolution <swift-evolution@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

+1

I would even argue for it to be the default.

I mean, assuming having two “reduce”s would stress the typechecker, as Joe suggested it might, I would say “inout” makes sense to be the default and the other one can find itself a new name.

IIRC, the "reduce" name comes from functional programming... should the functional style keep the functional name?

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Xiaodi Wu) #19

A serious possibility would be: `reduce(mutableCopyOf: x) { ... }`.

It's verbose, but the nicer-looking `reduce(mutating: x) { ... }` is
incorrect since, as Charles pointed out to Dave, it's not `x` that's
mutated but rather a mutable copy of it, so it doesn't matter if `x` itself
is declared with `let` or `var`.

···

On Tue, Jan 17, 2017 at 7:46 PM, Sean Heber <sean@fifthace.com> wrote:

`reuse`

Then we just need an excuse for a function named ‘recycle’...

l8r
Sean

> On Jan 17, 2017, at 7:36 PM, T.J. Usiyan via swift-evolution < > swift-evolution@swift.org> wrote:
>
> `reduceInout`
>
> On Tue, Jan 17, 2017 at 6:30 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:
> Agree. The functional style should keep the functional name.
>
> On Tue, Jan 17, 2017 at 16:18 David Sweeris via swift-evolution < > swift-evolution@swift.org> wrote:
>
> On Jan 17, 2017, at 16:11, Karl Wagner via swift-evolution < > swift-evolution@swift.org> wrote:
>
>>
>>> On 17 Jan 2017, at 23:09, Karl Wagner <karl.swift@springsup.com> > wrote:
>>>
>>>
>>>> On 16 Jan 2017, at 14:49, Chris Eidhof via swift-evolution < > swift-evolution@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
>>>> _______________________________________________
>>>> swift-evolution mailing list
>>>> swift-evolution@swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>
>>> +1
>>>
>>> I would even argue for it to be the default.
>>
>> I mean, assuming having two “reduce”s would stress the typechecker, as
Joe suggested it might, I would say “inout” makes sense to be the default
and the other one can find itself a new name.
>
> IIRC, the "reduce" name comes from functional programming... should the
functional style keep the functional name?
>
> - Dave Sweeris
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution


(TJ Usiyan) #20

`reduceInout`

···

On Tue, Jan 17, 2017 at 6:30 PM, Xiaodi Wu via swift-evolution < swift-evolution@swift.org> wrote:

Agree. The functional style should keep the functional name.

On Tue, Jan 17, 2017 at 16:18 David Sweeris via swift-evolution < > swift-evolution@swift.org> wrote:

On Jan 17, 2017, at 16:11, Karl Wagner via swift-evolution < >> swift-evolution@swift.org> wrote:

On 17 Jan 2017, at 23:09, Karl Wagner <karl.swift@springsup.com> wrote:

On 16 Jan 2017, at 14:49, Chris Eidhof via swift-evolution < >> swift-evolution@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

+1

I would even argue for it to be the default.

I mean, assuming having two “reduce”s would stress the typechecker, as
Joe suggested it might, I would say “inout” makes sense to be the default
and the other one can find itself a new name.

IIRC, the "reduce" name comes from functional programming... should the
functional style keep the functional name?

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution