[SE-0510] Introduce Dictionary.mapValuesWithKeys

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

이번 포스팅에서는 SE-0510 Introduce Dictionary.mapValuesWithKeys에 대해 정리해보겠습니다 🙋🏻

---

Intro

Dictionary의 값을 변환할 때 key 정보도 함께 필요한 경우가 종종 있습니다.

하지만 현재는 이런 작업을 하려면 init(uniqueKeysWithValues:)나 reduce(into:)를 써야 하는데, 이들은 불필요하게 dictionary를 rehashing하거나 재할당하는 비용이 발생합니다.

 

SE-0510은 이 문제를 해결하기 위해 mapValuesWithKeys라는 새로운 메서드를 제안합니다.

Key 정보를 transformation closure에 전달하면서도 성능 오버헤드 없이 값만 변환할 수 있습니다 🚀

 

현재 시점에서는 리뷰가 드래프트 상태이고 진행중이지만 곧 반영되지 않을까 싶습니다.

 

---

왜 필요한가?

Dictionary 값을 변환하면서 key도 함께 사용해야 하는 경우, 현재는 이렇게 해야 합니다.

let new: [Key: NewValue] = .init(
    uniqueKeysWithValues: old.lazy.map { ($0, transform(id: $0, payload: $1)) }
)
// or
let new: [Key: NewValue] = old.reduce(into: [:]) {
    $0[$1.key] = transform(id: $1.key, payload: $1.value)
}

 

두 방법 모두 심각하게 비효율적입니다.

• 첫 번째 방법: 모든 key를 다시 hashing
• 두 번째 방법: 여러 번의 중간 재할당 발생

벤치마크를 돌려보면 첫 번째가 중간 재할당이 적어서 그나마 조금 덜 나쁜 정도입니다.

 

Dictionary key를 변환하는 케이스도 있지만, 이 제안은 key는 절대 수정하지 않고 컨텍스트로만 사용하는 케이스에 집중하고 있습니다.

 

---

제안된 솔루션

 

Dictionary에 새로운 메서드를 추가합니다.

extension Dictionary {
    @inlinable public func mapValuesWithKeys<T, E>(
        _ transform: (Key, Value) throws(E) -> T
    ) throws(E) -> Dictionary<Key, T>
}

 

사용 예시

let balances: [Currency: Int64] = [.USD: 13, .EUR: 15]
let displayText: [Currency: String] = balances.mapValuesWithKeys {
    "\($0.alpha3) balance: \($1)"
}

간단하죠?
Key 정보를 사용하면서도 rehashing 없이 깔끔하게 값만 변환합니다.

 

---

상세 설계

구현은 기존 mapValues와 유사하지만, storage iteration loop 내부에서 key와 value를 함께 transformation closure에 전달합니다.

 

---

Apple 플랫폼 호환성

Apple 플랫폼에서 Dictionary는 Cocoa dictionary로 backing될 수 있습니다.

하지만 큰 문제는 없다고 말하고 있습니다.

__CocoaDictionary에도 _NativeDictionary와 본질적으로 동일한 메커니즘을 추가하면 되고, 새로운 mapValuesWithKeys가 기존 mapValues처럼 두 구현 사이에서 dispatch하면 됩니다.

 

---

고려된 대안들

기존 mapValues 오버로딩?

원래 초안에서는 기존 mapValues 메서드를 오버로딩해서 Key와 Value를 모두 받는 closure를 지원하려고 했습니다.

하지만 이게 source-breaking인 걸 발견했어요.

 

드물지만 value 타입이 2-tuple인 dictionary에서 mapValues를 호출하는 경우가 있거든요.

let dict: [String: (Int, String)] = ["a": (1, "x")]
dict.mapValues { ... } // 모호해짐

 

 

그래서 source compatibility를 위해 새로운 이름 mapValuesWithKeys를 선택했습니다.

 

---

 

compactMapValues도 추가?

mapValuesWithKeys를 추가하면 compactMapValues와 API 비대칭이 생깁니다.

compactMapValues는 key context를 지원하지 않으니까요.

하지만 compactMapValues는 본질적으로 reduce(into:)의 shorthand라서 성능 측면의 동기가 훨씬 약하거든요.

---

아무것도 하지 않기?

Dictionary는 extensively frozen type이라서, 개발자가 user space에서 stable-but-unspecified implementation detail에 의존해서 key context를 지원하도록 retrofit할 수도 있습니다.

하지만 이건 좋은 워크플로우가 아니고 권장해서도 안 됩니다.

 

---

향후 방향

mapValues 이름 재할당?

미래에는 기존 mapValues 메서드를 mapValuesWithoutKeys 같은 이름으로 바꿀 수도 있습니다.

그러면 mapValues 이름을 key context를 제공하는 버전에 재할당할 수 있겠죠.

다음 언어 모드에서 가능할 것 같습니다.

 

---

OrderedDictionary 변경 (swift-collections)

이 제안의 자연스러운 확장으로, swift-collections 패키지의 OrderedDictionary 타입도 mapValuesWithKeys 메서드를 가질 수 있습니다.

 

extension OrderedDictionary {
    @inlinable public func mapValuesWithKeys<T, E>(
        _ transform: (Key, Value) throws(E) -> T
    ) throws(E) -> OrderedDictionary<Key, T>
}

 

OrderedDictionary의 성능 향상은 Dictionary보다 더 클 수 있습니다.

OrderedDictionary는 keys와 values를 위한 표준 Array와 lookup을 위한 sidecar hash table을 유지하거든요.

현재 workaround(reduce나 init)는 전체 hash table을 재구성하고 keys array를 eager copy해야 합니다.

 

대신 zipped iteration을 사용해서 underlying _keys와 _values array를 새로운 values array로 매핑하고, _keys table(hash table __storage 포함)을 복사하면 됩니다.

 

이건 mutate하지 않으면 O(1) copy-on-write이고, 나중에 mutate하면 O(n)입니다.

 

 

 

---

Conclusion

Dictionary 값을 변환하면서 key도 사용하는 건 흔한 패턴인데, 지금까지는 불필요한 성능 비용을 감수해야 했는데 이런 메서드가 제공되면 조금 더 편하게 사용될 수 있을것 같네요.

특히 Currency 같은 enum을 key로 쓰면서 display text를 만드는 예시처럼, key가 formatting context를 제공하는 경우가 많잖아요 😁

간단한 추가지만 현업에서 많이 쓰일 것 같네요 😃

 

---

References

Giving Dictionary.mapValues(_:) access to the associated key

SE-0510: Dictionary mapValuesWithKeys