[swift-dev] What to do with the rest of SE-0174?

[Dave Abrahams]

on Thu Jul 20 2017, Gmail <swift-dev-AT-swift.org> wrote:

> Hi.
>
> I was looking to implement SE-0174
> <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md>
> (Change filter to return an associated type) but noticed that a different
> RangeReplaceableCollection.filter implementation had already been added in fd2ac31 to make
> String.filter return a String.
>
> The RangeReplaceableCollection.filter implementation in SE-0174 eagerly enumerates self to filter
> its elements:
>
> var result = Self()    
> for element in self {        
>     if try isIncluded(element) {
>         result.append(element)
>     }
> }   
> return result
>
> whereas the current implementation creates Self from a lazy filter:
>
> return try Self(self.lazy.filter(isIncluded))
>
> Which of these implementations is preferred for SE-0174?

The advantage of the second implementation is that when the source is a
Collection, the filtered result will be counted before the first
allocation so the new array can be allocated once before elements are
copied into it.  The first implementation does more allocations and more
element copies, but it only traverses the source collection once, and
passes each element through the filter once.  I can easily come up with
an example that performs *much* better under each of the two
implementations.  Picking a winner depends on making judgement calls
about the cost of traversing a representative source collection and
calling a representative filter function, and balancing that against the
cost of array reallocations.  This is not an analysis we've ever taken
the time to do, so there's no simple answer, unfortunately.

> The intended behavior of SE-0174 is already there with Data, Set,
> String, etc. returning Self when filtered. As far as I can tell the
> only remaining work is to add the associated type and specify the type
> alias in a few places to disambiguate which implementation is used to
> satisfy the Sequence protocol, essentially making this a non
> functional change. Or am I missing something?
>
> Regards,
> David
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev
>

-- 
-Dave