[swift-evolution] [pitch] Substring performance affordances

[David Hart]

Purely additive, so +1 from me. Side note, I’m wondering how problematic these same discussions will be in third-party library code. Should authors use StringProtocol or String as often as possible?

> On 28 Jun 2017, at 18:37, Ben Cohen via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Hi swift-evolution,
> 
> Below is a short pitch for some performance improvements to be made to String to accommodate Substrings. 
> 
> As outlined in SE-0163, the more general question of implicit conversion from Substring to String was deferred pending feedback on the initial implementation. To date, the feedback we’ve received hasn’t suggested that such an implicit conversion is necessary – that migrations from 3.2 to 4.0 haven’t led to an extensive need to perform Substring->String conversion. Any further input, either on or off list, about this particular aspect of migration would be very gratefully received.
> 
> # Substring performance affordances
> 
> * Proposal: [SE-NNNN](NNNN-substring-affordances.md)
> * Authors: [Ben Cohen](https://github.com/airspeedswift <https://github.com/airspeedswift>)
> * Review Manager: TBD
> * Status: **Awaiting review**
> 
> ## Introduction
> 
> This proposal modifies a small number of methods in the standard library that
> are commonly used with the `Substring` type:
> 
> - Modify the `init` on floating point and integer types, to construct them
>   from `StringProtocol` rather than `String`. 
> - Change `join` to be an extension `where Element: StringProtocol`
> - Add extensions to `Dictionary where Key == String` and `Set where Element ==
>   String` to test for presence of a `Substring`.
> 
> ## Motivation
> 
> Swift 4 introduced `Substring` as the slice type for `String`. Previously,
> `String` had been its own slice type, but this leads to issues where string
> buffers can be unexpectedly retained. This approach was adopted instead of the
> alternative of having the slicing operation make a copy. A copying slicing
> operation would have negative performance consequences, and would also conflict
> with the requirement that `Collection` be sliceable in constant time. In cases
> where an API requires a `String`, the user must construct a new `String` from a
> `Substring`. This can be thought of as a "deferral" of the copy that was
> avoided at the time of the slice.
> 
> There are a few places in the standard library where it is notably inefficient
> to force a copy of a substring in order to use it with a string: performing
> lookups in hashed containers, joining substrings, and converting substrings to
> integers. In particular, these operations are likely to be used inside a loop
> over a number of substrings extracted from a string. For example, suppose you
> had a string of key/value pairs, where the values were integers and you wanted
> to sum them by key. You would be forced to convert both the `Substring` keys
> and values to `String` to do this.
> 
> ## Proposed solution
> 
> Add the following to the standard library:
> 
> ```swift
> extension FixedWidthInteger {
>  public init?<S : StringProtocol>(_ text: S, radix: Int = 10)
> }
> 
> extension Float/Double/Float80 {
>  public init?<S : StringProtocol>(_ text: S, radix: Int = 10)
> }
> 
> extension Sequence where Element: StringProtocol {
>  public func joined(separator: String = "") -> String
> }
> 
> extension Dictionary where Key == String {
>  public subscript(key: Substring) -> Value? { get set }
>  public subscript(key: Substring, default defaultValue: @autoclosure () -> Value) -> Value { get set }
> }
> 
> extension Set where Element == String {
>  public func contains(_ member: Substring) -> Bool
>  public func index(of member: Substring) -> Index?
>  public mutating func insert(_ newMember: Substring) -> (inserted: Bool, memberAfterInsert: Element)
>  public mutating func remove(_ member: Substring) -> Element?
> }
> ```
> 
> These additions are deliberately narrow in scope. They are _not_ intended to
> solve a general problem of being able to interchange substrings for strings (or
> more generally slices for collections) generically in different APIs. See the
> alternatives considered section for more on this.
> 
> ## Source compatibility
> 
> No impact, these are either additive (in case of hashed containers) or
> generalize an existing API to a protocol (in case of numeric
> conversion/joining).
> 
> ## Effect on ABI stability
> 
> The hashed container changes are additive so no impact. The switch from conrete
> to generic types for the numeric conversions needs to be made before ABI
> stability.
> 
> ## Alternatives considered
> 
> While they have a convenience benefit as well, this is not the primary goal of
> these additions, but a side-effect of helping avoid a performance problem. In
> many other cases, the performance issues can be avoided via modified use e.g.
> `Sequence.contains` of a `Substring` in a sequence of strings can be written as
> `sequence.contains { $0 == substring }` .
> 
> These changes are limited in scope, and further additions could be considered
> in the future. For example, should the `Dictionary.init(grouping:by:) where Key
> == String` operation be enhanced to similarly take a sequence of substrings?
> There is a long tail of these cases, and the need to keep unnecessary overloads
> to a minimum, avoiding typechecker work and code bloat, must be weighed against
> the likelyhood that string copies will be a performance problems.
> 
> There is a more general problem of interoperating between collections and
> slices. In the future, there may be other affordances for converting/comparing
> them. For example, it might be desirable to require equatable collections to
> have equatable slices, and to automatically provide default implementations of
> `==` that efficiently compare a collection to its default slice. These
> enhancements rely on features such as conditional conformance, and so may be
> worth considering in later versions of Swift but are not an option currently.
> _______________________________________________
> 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/20170628/2577a22b/attachment.html>