[swift-evolution] [Proposal Draft] Provide Custom Collections for Dictionary Keys and Values

[Said Sikira]

+1


On October 12, 2016 at 8:54:45 AM, Rien via swift-evolution (
swift-evolution at swift.org) wrote:

Beautiful, +1

Rien

> On 11 Oct 2016, at 23:28, Nate Cook via swift-evolution <
swift-evolution at swift.org> wrote:
>
> Introduction
>
> This proposal addresses significant unexpected performance gaps when
using dictionaries. It introduces type-specific collections for a
Dictionary instance's keys and values properties.
>
> New DictionaryKeys and DictionaryValues collections provide efficient key
lookup and mutable access to dictionary values, enabling updates to be
performed in-place and allowing copy-on-write optimization of stored values.
>
> Motivation
>
> This proposal address two problems:
>
> • The Dictionary type keys implementation is inefficient, because
LazyMapCollection doesn't know how to forward lookups to the underlying
dictionary storage.
> • Dictionaries do not offer value-mutating APIs. The mutating key-based
subscript wraps values in an Optional. This prevents types with
copy-on-write optimizations from recognizing they are singly referenced.
> This proposal uses the following [String: [Int]] dictionary to
demonstrate these problems:
>
> var dict = ["one": [1], "two": [2, 2], "three": [3, 3, 3]]
> Inefficient dict.keys Search
>
> Swift coders normally test key membership using nil checks or underscored
optional bindings:
>
> if dict["one"] != nil
> {
>
> // ...
>
> }
>
> if let _ = dict["one"
> ] {
>
> // ...
>
> }
>
> These approaches provide the expected performance of a dictionary lookup
but they read neither well nor "Swifty". Checking keys reads much better
but introduces a serious performance penalty: this approach requires a
linear search through a dictionary's keys to find a match.
>
> if dict.keys.contains("one") {
> // ...
> }
>
> A similar dynamic plays out when comparing dict.index(forKey:) and
dict.keys.index(of:).
>
> Inefficient Value Mutation
>
> Dictionary values can be modified through the keyed subscript by direct
reassignment or by using optional chaining. Both of these statements append
1 to the array stored by the key "one":
>
> // Direct re-assignment
>
> dict[
> "one"] = (dict["one"] ?? []) + [1
> ]
>
>
> // Optional chaining
>
> dict[
> "one"]?.append(1)
> Both approaches present problems. The first is complex and hard to read.
The second ignores the case where "one" is not a key in the dictionary. It
forces its check into a higher branch and encourages forced unwrapping.
Furthermore, neither approach allows the array to grow in place. They
introduce an unnecessary copy of the array's contents even though dict is
the sole holder of its storage.
>
> Adding mutation to a dictionary's index-based subscripting isn't
possible. Changing a key stored at a particular index would almost
certainly modify its hash value, rendering the index incorrect. This
violates the requirements of the MutableCollection protocol.
>
> Proposed Solution
>
> This proposal adds a custom collection for the keys and values dictionary
properties. This follows the example set by String, which presents multiple
views of its contents. A new DictionaryKeys collection introduces efficient
key lookup, while a new DictionaryValues collection provides a mutable
collection interface to dictionary values.
>
> These changes introduce a simple and efficient way of checking whether a
dictionary includes a key:
>
> // Performant
> if dict.keys.contains("one"
> ) {
>
> // ...
>
> }
>
> As a mutable collection, values enables modification without copies or
clumsy code:
>
> if let i = dict.index(forKey: "one"
> ) {
> dict
> .values[i].append(1) // no copy here
>
> }
> else
> {
> dict[
> "one"] = [1
> ]
> }
>
> Both the keys and values collections share the same index type as
Dictionary. This allows the above sample to be rewritten as:
>
> // Using `dict.keys.index(of:)`
> if let i = dict.keys.index(of: "one"
> ) {
> dict
> .values[i].append(1
> )
> }
> else
> {
> dict[
> "one"] = [1
> ]
> }
>
> Detailed design
>
> • The standard library introduces two new collection types:
DictionaryKeys and DictionaryValues.
> • A Dictionary's keys and values property types change from
LazyMapCollection to these new types.
> • The new collection types are not directly constructable. They are
presented only as views into a dictionary.
> struct Dictionary<Key: Hashable, Value>: ...
> {
>
> var keys: DictionaryKeys<Key, Value> { get
> }
>
> var values: DictionaryValues<Key, Value> { get set
> }
>
>
> // Remaining declarations
>
> }
>
>
> /// A collection view of a dictionary's keys.
> struct DictionaryKeys<Key: Hashable, Value>
> : Collection {
>
> typealias Index = DictionaryIndex<Key, Value>
>
>
> subscript(i: Index) -> Key { get
> }
>
>
> // Other `Collection` requirements
>
> }
>
>
> /// A mutable collection view of a dictionary's values.
> struct DictionaryValues<Key: Hashable, Value>
> : MutableCollection {
>
> typealias Index = DictionaryIndex<Key, Value>
>
>
> subscript(i: Index) -> Value { get set
> }
>
>
> // Other `Collection` requirements
>
> }
>
> A sample implementation of this proposal can be found in this branch.
>
> Impact on existing code
>
> The performance improvements of using the new DictionaryKeys type and the
mutability of the DictionaryValuescollection are both additive in nature.
>
> Most uses of these properties are transitory in nature. Adopting this
proposal should not produce a major impact on existing code. The only
impact on existing code exists where a program explicitly specifies the
type of a dictionary's keysor values property. The fix is to change the
specified type.
>
> Alternatives considered
>
> The Generics Manifesto lists nested generics as a goal. This could impact
the naming and structure of these new collection types.
>
> Instead of DictionaryKeys<Key, Value> and DictionaryValues<Key, Value>,
these types could be Dictionary<Key, Value>.Keys and Dictionary<Key,
Value>.Values. However, because many types in the standard library may be
revisited once such a feature is available (indices, iterators, etc.), the
current lack of nesting shouldn't prevent consideration of this proposal.
>
> It could be possible to add additional compiler features that manage
mutation through existing key-based subscripting without the copy-on-write
problems of the current implementation. I don't know enough about how that
would be implemented to speak to its feasibility or level of effort. Such a
feature would reduce the need for a mutable DictionaryValues collection.
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution at swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161012/6c026834/attachment.html>