[swift-evolution] Additional methods for removing elements from a collection in Swift

[Ben Cohen]

> On Sep 26, 2017, at 2:59 AM, Xiaodi Wu via swift-evolution <swift-evolution at swift.org> wrote:
> 
> On Tue, Sep 26, 2017 at 00:15 Jonathan Hull <jhull at gbis.com <mailto:jhull at gbis.com>> wrote:
> As he says, it is an in-place equivalent of filter, so the use-cases would be similar.  I could see this being extremely useful.  Off the top of my head:
> 
> 	views.remove(where: {$0.isHidden}) //Remove all views which are hidden from the list.
> 
> Is such a method ever going to be different (in performance, say) from:
> 
> views = Views(views.lazy.filter { $0.isHidden })

Potentially yes, in a few different ways:

In-place removal doesn’t require an additional storage allocation. Assuming the Views type is like Array (or if it is an Array or backed by an Array) then with the filter approach, the old buffer would need to be freed, and the new buffer allocated.

.lazy.filter is a good way to avoid allocating a temporary array. But you still have the issue of not being able to pre-allocate the right amount of storage in the target. So either two passes are needed to keep to 1 allocation, or the target array will need to reallocate its buffer multiple times as it grows.

When a small number of elements need to be removed, an in-place remove can skip to the first element to remove and shuffle the remainder over the top of the removed elements. In the extreme version of the above, if there’s nothing to remove, then other than that initial scan, the in-place remove is a no-op. By contrast, the filter/copy approach is a full copy of every element even when there’s nothing to remove.

For in-place removal, a type like Array that is backed by raw memory can potentially perform memory moves to shuffle the elements down in-place, helping to avoid things like unnecessary arc traffic. When composing the operation from higher-level types, you’re relying on the optimizer to eliminate unnecessary reference counting. And the more you layer in (like .lazy) the tougher it is for the optimizer to do that – it might not even be possible if the type is defined behind a barrier like a module boundary etc.

It’s for these reasons I pitched https://github.com/apple/swift-evolution/pull/675 previously, but it didn’t make it into Swift 4 as we ran out of time. I took an action in the core team meeting recently to revisit it wrt to the naming and symmetry with filter. I’ll open up a separate thread.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170926/bb27d4a4/attachment.html>