[SE-0515] Allow reduce to produce noncopyable results

안녕하세요. 그린입니다 🍏

이번 포스팅에서는 SE-0515 Allow reduce to produce noncopyable results에 대해 정리해보겠습니다 🙋🏻

---

Intro

Swift의 reduce는 정말 유용한 함수이지만, 몇 가지 한계가 있었습니다.

noncopyable 타입을 다룰 수 없었고, initial value를 borrow하는 방식이라 불필요한 복사가 발생했어요.

 

SE-0515는 reduce를 개선합니다 😁

• Noncopyable initial value와 result를 허용하고
• Copyable일 때도 initial value를 consume하도록 변경합니다

이미 PR이 Accepted 상태이고 구현도 완료되었으니, 곧 현업에서도 쓸 수 있을 것 같습니다 🚀

 

---

왜 필요한가?

Noncopyable 타입은 SE-0390에서 도입되어 타입의 의미론과 성능을 제어하는 강력한 메커니즘을 제공합니다.

Sequence는 (아직은) noncopyable 타입을 담을 수 없지만, reduce의 accumulation argument는 sequence와 독립적입니다.

따라서 initial value를 borrow 대신 consume하면, 복사 능력에 의존하지 않고도 reduce를 구현할 수 있습니다.

 

---

현재 reduce의 문제점

현재 reduce 구현은 parameter를 borrow합니다.

func reduce<Result>(
  _ initialResult: Result,
  _ nextPartialResult:
    (_ partialResult: Result, Element) throws -> Result
) rethrows -> Result {
  var accumulator = initialResult
  for element in self {
    accumulator = try nextPartialResult(accumulator, element)
  }
  return accumulator
}

여기서 borrow는 암묵적입니다.

initializer가 아닌 argument의 기본값이니까요.

 

그래서 문제가..?

첫 단계가 항상 initialResult의 mutable copy를 만드는 겁니다.

var accumulator = initialResult  // 복사 발생!

 

이 패턴은 initial의 올바른 calling convention이 consuming이어야 한다는 걸 강하게 암시합니다.

 

만약 값이 copyable이면,

• 호출자가 복사를 만듭니다
• 단, optimizer가 마지막 사용임을 확인하면 복사를 완전히 제거할 수 있습니다

이런 경우는 reduce에서 매우 흔합니다. "initial value"가 종종 reduction만을 위해 생성되니까요.

 

---

솔루션

reduce를 noncopyable 값에서도 동작하도록 일반화하면, initial value를 consume하는 게 필수가 됩니다.

var accumulator = initialResult가 더 이상 컴파일되지 않으니까요.

 

즉, 새 버전의 reduce는 이렇게 작성됩니다.

 

extension Sequence {
  public func reduce<Result: ~Copyable>(
    _ initialResult: consuming Result,
    _ nextPartialResult:
      (_ partialResult: consuming Result, Element) throws -> Result
  ) rethrows -> Result

  public func reduce<Result: ~Copyable>(
    into initialResult: consuming Result,
    _ updateAccumulatingResult:
      (_ partialResult: inout Result, Element) throws -> ()
  ) rethrows -> Result
}

 

실제 구현

public func reduce<Result: ~Copyable>(
  _ initialResult: consuming Result,
  _ nextPartialResult:
    (_ partialResult: consuming Result, Element) throws -> Result
) rethrows -> Result {
  for element in self {
    initialResult = try nextPartialResult(initialResult, element)
  }
  return initialResult
}

 

더 이상 initialResult 값을 복사할 필요가 없습니다. consuming(즉, owned not borrowed)으로 받으니까요!

 

---

reduce(::)와 reduce(into:_:)의 차이

이 시점에서 두 함수는 거의 동일해지고, reduce(into:_:)의 동기가 줄어듭니다.

어떤 걸 쓸지는 주로 개발자 선택의 문제가 됩니다.

 

---

성능 개선

"세계에서 가장 느린 map" 문제

이 변경은 고전적인 세 가지 원인 중 하나를 제거합니다.

array.reduce([]) { $0 + [$1] }

 

이건 여전히 O(n²)입니다.

• +가 argument를 borrow하고 모든 element를 복사한 새 array를 반환
• [$1]이 버릴 거면서도 새 array buffer를 할당

하지만 새 reduce로는 이렇게 쓸 수 있습니다.

array.reduce([]) { $0.append($1); return $0 }

 

이제 다음과 같은 성능을 얻습니다.

array.reduce(into: []) { $0.append($1) }

 

약간은 더 reduce(into:_:)와 동일한 성능이죠!

 

---

주의사항

물론 이런 모든 비효율성은 optimizer가 heroic optimization을 수행하면 제거될 수 있습니다.

하지만 이런 heroic optimization은 조금만 복잡한 예시에서는 무너지는 경향이 있어서, 성능 절벽으로 이어집니다.

 

reduce(into:_:)는?

reduce(into:_:)는 이미 argument를 consuming으로 받습니다.

따라서 유일한 변경은 Result: ~Copyable 추가뿐입니다.

 

---

향후 방향

~Escapable 지원

reduce는 ~Escapable 값에서도 동작하도록 업데이트될 수 있습니다.

이를 위해서는 함수와 closure parameter 모두에 lifetime annotation이 필요한데, 후자는 Swift에서 아직 지원되지 않습니다.

 

---

Conclusion

SE-0515는 이미 Accepted되었고 구현도 완료된 상태입니다.

개인적으로는 정말 합리적인 개선이라고 생각합니다.

reduce가 initial value를 borrow하는 건 원래부터 이상했어요.

첫 줄에서 바로 복사하는데 말이죠.

이제 noncopyable 타입도 지원하고, copyable 타입에서도 불필요한 복사를 줄일 수 있게 되었습니다.

 

"세계에서 가장 느린 map" 같은 실수도 조금 덜 치명적으로 만들어주는 좋은 변경이네요 😃

 

---

References

swift-evolution/proposals/0515-noncopyable-reduce.md at main · swiftlang/swift-evolution

[Pitch] Allow `reduce` to produce noncopyable results

SE-0515: Allow `reduce` to produce noncopyable results

[Accepted] SE-0515: Allow `reduce` to produce noncopyable results