Closed mdznr closed 3 years ago
I made the closure belongsInSecondCollection
, which is consistent with the other partitioned functions, but in terms of the return values, feels backwards ((second, first)
).
I ran some benchmarks using the awesome swift-collections-benchmark package, as suggested by @timvermeulen:
The output does confirm that using partitioned(_:)
is faster than calling filter(_:)
twice.
Using the Collection
-based implementation with the fixed buffer size is faster than the Sequence
-base implementation. However, the function’s overhead makes it slightly slower for collections fewer than 8 elements. For that reason, we could check count < 8
in the start of the Collection
implementation and conditionally run the Sequence
-based approach, which is slightly faster.
I was initially surprised partitioned(_:)
wasn’t significantly faster than calling filter(_:)
twice, though. With more experimentation, I learned how much the overall cost depends on the cost of the closure’s evaluation. The more costly the closure, the more valuable it was to avoid calling the closure twice (obviously). In very simple cases, the cost of evaluating the closure is extremely insignificant compared to the cost of adding each element to the output collection. However, in all cases, it is still faster to use partitioned(_:)
than calling filter(_:)
twice.
Using a slighty more expensive closure yielded these results:
Those graphs look good! It's nice to see that the added complexity seems to be worth it for most sizes. I think it'd be useful to benchmark another version that returns a
(ArraySlice, ArraySlice)
pair (or even(ArraySlice, ReversedCollection<ArraySlice>)
) just so we can see how much performance we're missing out on by allocating two new arrays.
I’m a bit surprised that the (Array, Array)
implementation was actually faster in many cases (from a few hundred to a couple hundred thousand elements). Thinking it was a fluke, I’ve re-run this several times and continue to get similar results. I’m not sure yet why that could be.
I wish there were a clear best implementation from a performance point of view. However, since the performance for the non-Array
return values weren’t better in all cases, I would say the tradeoff of having non-Array
types as the return values aren’t worth it, as it does expose some implementation details and would make it difficult to change the implementation (and possibly the signature) later without it being a non-backwards-compatible breaking change.
I’m a bit surprised that the
(Array, Array)
implementation was actually faster in many cases (from a few hundred to a couple hundred thousand elements). Thinking it was a fluke, I’ve re-run this several times and continue to get similar results. I’m not sure yet why that could be.
That's interesting and indeed surprising.
I wish there were a clear best implementation from a performance point of view. However, since the performance for the non-
Array
return values weren’t better in all cases, I would say the tradeoff of having non-Array
types as the return values aren’t worth it, as it does expose some implementation details and would make it difficult to change the implementation (and possibly the signature) later without it being a non-backwards-compatible breaking change.
I completely agree with your conclusions here. I'd still be interested to see how returning (Array(lhs), Array(rhs.reversed()))
rather than reversing the right side in-place could improve the (Array, Array)
version even more, but judging by the tiny difference between the two slice versions it probably won't make a huge difference.
I wish there were a clear best implementation from a performance point of view. However, since the performance for the non-
Array
return values weren’t better in all cases, I would say the tradeoff of having non-Array
types as the return values aren’t worth it, as it does expose some implementation details and would make it difficult to change the implementation (and possibly the signature) later without it being a non-backwards-compatible breaking change.I completely agree with your conclusions here. I'd still be interested to see how returning
(Array(lhs), Array(rhs.reversed()))
rather than reversing the right side in-place could improve the(Array, Array)
version even more, but judging by the tiny difference between the two slice versions it probably won't make a huge difference.
I think if I’m following you correctly, that should be the same as the test I ran earlier:
When would the reversal happen? If removing line 315 here and instead reversing the
ArraySlice
right before its conversion to anArray
, it makes it slower.
I think if I’m following you correctly, that should be the same as the test I ran earlier:
I missed that, my bad. Looks like ReversedCollection
is just too slow to make this worthwhile.
@swift-ci Please test
@swift-ci Please test
Thank you @timvermeulen, @natecook1000, @xwu, @LucianoPAlmeida, @fedeci, and @CTMacUser for helping me get this function integrated into swift-algorithms!
Description
Adds a
partitioned(by:)
algorithm. This is very similar tofilter(_:)
, but instead of just getting an array of the elements that do match a given predicate, also get a second array for the elements that did not match the same predicate.This is more performant than calling
filter(_:)
twice on the same input with mutually-exclusive predicates since:Detailed Design
Naming
At a high-level, this acts similarly to the
partition
family of functions in that it separates all the elements in a given collection in two parts, those that do and do not match a given predicate. Thanks, @timvermeulen for help with naming!Documentation Plan
Test Plan
Source Impact
This is purely additive
Checklist