Why doesn't "reduce(into:)" include a variant that takes an "inout" input?

Evolution Discussion
1

After seeing the "Reducing a sequence onto its own elements to simplify code and reduce errors" pitch, I was considering that it should have an inout variant, and that got me to wondering why reduce(into:) didn't have an additional variant that mutated its initial value.

I found @dabrahams' comment from the original review:

But I ran some naive benchmarks and found that this kind of code can still require copies depending on the value being accumulated.

  func testRawAccumulation() {
    let ys = Array(repeating: 1, count: 1_000_000)
    var xs: [Int] = []
    xs.reserveCapacity(5_000_000)
    measure {
      for y in ys { xs.append(y) }
      for y in ys { xs.append(y) }
      for y in ys { xs.append(y) }
      for y in ys { xs.append(y) }
      for y in ys { xs.append(y) }
    }
  }

  func testReduceInto() {
    let ys = Array(repeating: 1, count: 1_000_000)
    var xs: [Int] = []
    xs.reserveCapacity(5_000_000)
    measure {
      xs = ys.reduce(into: xs) { xs, y in xs.append(y) }
      xs = ys.reduce(into: xs) { xs, y in xs.append(y) }
      xs = ys.reduce(into: xs) { xs, y in xs.append(y) }
      xs = ys.reduce(into: xs) { xs, y in xs.append(y) }
      xs = ys.reduce(into: xs) { xs, y in xs.append(y) }
    }
  }

The testReduceInto runs about 10x slower in an optimized build than testRawAccumulation.

This overload, however, performs the same as testRawAccumulation:

extension Sequence {
  @inlinable
  public func reduce<Result>(
    into result: inout Result,
    _ updateAccumulatingResult: (inout Result, Element) throws -> Void
    ) rethrows {

      for element in self {
        try updateAccumulatingResult(&result, element)
      }
  }
}

Is this a bug in the compiler? Should we revisit adding an overload?

3 Likes
2

Can a compiler or standard library engineer weigh in here? Any reason not to make a pitch?

1 Like
3

I don't think it's quite accurate to describe this as a bug in the compiler. Rather, I'd describe it as a feature that the compiler doesn't have but could be added. In particular, it would need to be a guaranteed transformation that happens every time in every situation, rather than something you can hope the optimizer is going to do in -O builds. While it's fine to accept significant performance hits in debug mode, it's probably not reasonable to get different complexity between -Onone and -O, or between un-/specialized or un-/inlinable functions.

That said, I think it's an important transformation to guarantee. Essentially we're saying that this:

var xs = a.reduce(into: initial, someReduction)
    xs = b.reduce(into: xs, someReduction)

ought to be rewritten as:

let xs  = a.reduce(into: initial, combine)
let xs' = b.reduce(into: xs, combine)

thus guaranteeing that each call to reduce were the last use of the into argument, so it could be passed without bumping the ref count (as the initial value is taken __owned).

(and much more complex control flow examples, like reassigning the var in a loop)

If you think about move-only types, we would have to support this kind of transformation in order to allow the var form to compile at all (assuming some implementation of move-only types means passing an uncopyable var as an argument does something like return the variable to an uninitialized state). So I think it's reasonable to say it's something that ought to be added in the future. I spoke a bit to @Erik_Eckstein and @Andrew_Trick about this and they think it would be doable, but only once we have a few more features that are on the roadmap, such as opaque values in SIL (note not the same as opaque return types, that's a different feature).

Assuming that this guaranteed transformation were coming in the future, is it still worth adding a version of reduce that takes an inout now? I'm not sure. We'd be talking about a fifth version (assuming we end up adding the 2 proposed in this thread). That's.... a lot of versions of reduce. You could argue that's getting out of hand for something that's really on the edge of being trivially composable in the first place when you compare it to a similar for loop.

Then again there are other reasons why it might be a good idea. The uniquely-referenced thing doesn't work with computed properties for example, so a version that took its initial value inout might always be useful.

9 Likes