[swift-evolution] [Proposal] Fix lazy filter
Антон Жилин
antonyzhilin at gmail.com
Sun Jun 19 14:24:33 CDT 2016
I've written a simple wrapper sequence that should be optimized out, and
performed a couple of microbenchmarks. Code:
===begin===
struct WrapperSequence<S: Sequence> : Sequence {
let base: S
init(_ base: S) { self.base = base }
func makeIterator() -> S.Iterator { return base.makeIterator() }
}
func predicate(num: Int) -> Bool {
return true
}
let sequence = WrapperSequence(1...400000000).lazy.filter(predicate) // or
remove WrapperSequence
let array = Array(sequence)
===end===
Results:
1. Double-pass wins: num % 2 == 0
2. Single-pass wins: num % 2 == 0 && num % 3 == 0
3. Double-pass wins: num % 2 == 0 || num % 3 == 0
4. Double-pass wins: num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num %
7 == 0 || num % 11 == 0
5. Single-pass wins: num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num %
7 == 0 || num % 11 == 0 || num % 13 == 0
But I have to admit that double-pass algorithm CAN be faster if the one
knows what he is doing.
I conclude that we need an API to choose between the two algorithms, and
single-pass should be the safe default.
- Anton
2016-06-19 19:56 GMT+03:00 Антон Жилин <antonyzhilin at gmail.com>:
> It's not a bug. Measuring the length of the source before allocating
>> the destination array is usually a big win when compared to repeatedly
>> growing the array's memory and copying all its elements.
>> --
>> -Dave
>
>
> Usually yes, but not in the case of lazy filter. If predicate contains
> anything more than a dozen CPU instructions, single-pass version is faster.
>
> We often want the predicate to have side effects, but we cannot with
> current implementation: the side effects will be doubled.
>
> I also wonder if it's possible to allocate array with capacity of
> underlying collection (before all lazy stuff) and shrink it in the end.
>
> - Anton
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160619/89a95198/attachment.html>
More information about the swift-evolution
mailing list