SE-0232: Remove Some Customization Points from the Standard Library's Collection Hierarchy

The review of SE-0232: Remove Some Customization Points from the Standard Library's Collection Hierarchy begins now and runs through Tuesday, October 30th, 2018.

The proposal is written by @Ben_Cohen.

Reviews are an important part of the Swift evolution process. All review feedback should be either on this forum thread or, if you would like to keep your feedback private, directly to me as the review manager via email or direct message on the forums. If you send me email, please put "SE-0232" somewhere in the subject line.

What goes into a review of a proposal?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift.

When reviewing a proposal, here are some questions to consider:

  • What is your evaluation of the proposal?

  • Is the problem being addressed significant enough to warrant a change to Swift?

  • Does this proposal fit well with the feel and direction of Swift?

  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Thank you for contributing to Swift!

Ted Kremenek
Review Manager

5 Likes

The proposal focuses on methods that are problematic for move-only types. However, I wonder if there are other methods that we could give the same treatment.

Are there sequences for which filter, drop*, prefix, suffix, and/or split have more-efficient implementations than the obvious?

1 Like

It's a good question.

filter could probably be added to the list to drop. It's only slightly different, in that it is redeclared on RangeReplaceableCollection, where it returns Self rather than [Element]. But this probably doesn't mean it needs to remain a customization point on Sequence.

drop*, prefix , suffix , and *shudder* split are a different matter. They are customization points because they return an associated type. This is a whole different issue, and one tied up with the future of Sequence and SubSequence. Which is an important discussion, but not one we should have in this particular review thread.

1 Like

I see. What about prefix(upTo:), prefix(through:) and suffix(from:) on Collection? Those have implementations in terms of subscript(bounds:), and I can’t imagine doing anything else.

I don't really have much to say about this proposal, other than to point out that forEach and map can be implemented using recursion when navigating a tree structure, which is probably more efficient than an iterator-based implementation.

The BTree library does exactly this. Using the iterator involves maintaining the current tree path using arrays.

Thank you for pointing this out. These are perfect candidates for removal.

I put up a PR EDIT: wrong link including them too. Benchmarks suggest no impact (like you say, why would there be?) but some nice improvements to both user and library code size.

Hi Ben,

Is this just a formality? Can the core team make a wholesale decision on all the customization points necessary to support this future feature post review and amend this as the swift 5 window closes? Or do you foresee more similar proposals coming about supporting this future feature?

I lack the complete picture to properly comment so I much rather defer to core team on this one.

Thank you

1 Like

I thought so, too, so I did some light benchmarking on binary trees when Ben originally pitched this. I could indeed measure a slight improvement, but at -4% it was nowhere near what I expected. I think 4% is not worth the code size cost of keeping these customization points -- we can win that back by spending some effort on optimizing iterators instead.

Keep in mind that binary trees are a pathological case in this regard. I expect the difference would be even less significant for less fragmented data structures like B-trees, where >99% of iteration is over elements that are within the same node as the last. (We can also guarantee a (quite low) maximum depth for B-trees, which enables iterator/index optimizations that aren't easily emulated with recursion.)

Unfortunately I can't recall my original performance measurements for the BTree package, but I think the difference used to be large enough to make it worth customizing map/forEach. This doesn't seem to be the case any more!

7 Likes
  • What is your evaluation of the proposal?

I think this is a reasonable set of changes. +1

  • Is the problem being addressed significant enough to warrant a change to Swift?

Yes.

  • Does this proposal fit well with the feel and direction of Swift?

Yes.

  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

N/A

  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

I read the proposal and the other feedback on it, as well as previous threads about this issue.

Off topic:

Is it possible that the improved performance was caused by the new +0 refcount calling convention?

@Ben_Cohen There persistent data structures that could specialize filter(_:), implementing it by returning a collection that points to slices of the original buffer. Each slice would contain all contiguously stored members that satisfy the predicate.

I think that's something worth being open to, if possible.

That would require more just than a customization point. It would need a separate associated type as the return value. Currently filter returns [Element] (unless you're a range-replaceable collection).

Such a return type was proposed in SE-0174 but never implemented, because at the time it required recursive constraints (the filtered return type should be constrained to the same point in the protocol, similar to how SubSequence or Indices is). This was back in the days before proposals needed implementations.

Despite being the author of that proposal, I now feel like it would be a mistake to do this based on later experience. But if we wanted to do it at some point in the future, removing the customization point now would actually be a big step towards that, because we wouldn't then have the situation of needing to keep the old customization point and having it interact oddly with the new one with a different return type on the same protocol.

3 Likes

After discussion with the review manager, I've updated the proposal to include the additional customization points proposed above:

  • filter on Sequence
  • prefix(upTo:) , prefix(through:), and suffix(from:) on Collection
4 Likes

We did discuss whether customization points strictly speaking are an implementation detail (which don't usually go through review) rather than part of the public API. The conclusion was that it was better to just run a review in case someone brings up some key point we're missing. It's probably better to avoid the core team deciding on a case by case basis what does or doesn't need a review.

5 Likes

It is possible! Although I expect that also improved the recursive case, possibly even more so. (The recent benchmark was also compiled as a single module, which limits the effect of the default calling convention.)

1 Like

Proposal Accepted

The Core Team has decided to accept the proposal as written (with the refinements incorporated during the review). Thank you to everyone who participated in the review!

2 Likes
Terms of Service

Privacy Policy

Cookie Policy