[swift-evolution] [RFC] New collections model: collections advance indices

[Dave Abrahams]

on Tue Mar 08 2016, Károly Lőrentey <swift-evolution at swift.org> wrote:

> On 2016-03-04 02:00:36 +0000, Dave Abrahams via swift-evolution said:
>
>>
>> on Thu Mar 03 2016, Dmitri Gribenko <swift-evolution at swift.org> wrote:
>>
>>> On Thu, Mar 3, 2016 at 9:56 AM, plx via swift-evolution
>>> <swift-evolution at swift.org> wrote:
>>>>
>>>> # Concern: Linearity Baked-In
>>>>
>>>> Even with this change, I have some concern that the proposed
>>>> protocol hierarchy from `Collection` onward feels like it has a
>>>> foreseeable lack of generality due to how strongly "linear" the
>>>> design wants `Collection` to be.
>>>>
>>>> Is this the right time to raise such concerns (e.g. in-scope for
>>>> this discussion)?
>>>
>>> We can definitely dive into more details about this.  One thing that I
>>> would want to understand is whether this non-linearity concept could
>>> be added later without a re-design.
>>>
>>> Could you provide more information about the linearity issues that you
>>> have in mind?  Are you thinking of something like Segmented Iterators
>>> and Hierarchical Algorithms [1]?
>>>
>>> [1] http://lafstern.org/matt/segmented.pdf
>>
>> Awesome paper; everybody should read it ;-)
>
> Indeed; I just read it, and it has given me Ideas.
>
> Off-list, I've been thinking about implementing a low-level optimization
> in stdlib that turns out to be essentially a narrow-minded
> implementation of segmented iterators, dedicated to one specific usecase:
> copying data out of a collection.
>
> See e.g. https://github.com/apple/swift/pull/1194#discussion_r55251606
> (scroll down to the section about _copyContents; I'm bad at succinct
> commenting.)

I really want to handle this in a more general way.  The same principle
comes up in so many contexts: b-trees, deques, hash tables, circular
buffers, blocking matrix math, ...

That said, having a special-purpose function as an implementation detail
of the standard library is fine.

-- 
-Dave