Why Does Filter(_:)'s Predicate Get Called So Many Times When Evaluating It Lazily

Why does filter(_:)’s predicate get called so many times when evaluating it lazily?

The Problems

The first culprit here is the slicing of the lazy filter collection through the use of prefix(_:) – which, in this case, returns a BidirectionalSlice of the LazyFilterBidirectionalCollection.

In general, the slicing of a Collection entails the storing of the base collection, along with the range of indices that are valid for the slice to ‘view’. Therefore, in order to create a slice of a LazyFilterBidirectionalCollection to view the first 5 elements, the range of indices stored must be startIndex ..< indexAfterTheFifthElement.

In order to get indexAfterTheFifthElement, the LazyFilterBidirectionalCollection must iterate through the base collection (numbers) in order to find the 6th element that meets the predicate (you can see the exact implementation of the indexing here).

Therefore all the elements in the range 0...15 from the above example need to be checked against the predicate simply in order to create a slice of the lazy filter collection.

The second culprit is Array’s init(_:), which accepts a Sequence of elements of the same type as the array’s Element type. The implementation of this initialiser calls _copyToContiguousArray() on the sequence, which, for most sequences, forwards the call to this function:

internal func _copySequenceToContiguousArray<S : Sequence>
                                    (_ source: S) -> ContiguousArray<S.Iterator.Element> {

  let initialCapacity = source.underestimatedCount // <- problem here

  var builder =
    _UnsafePartiallyInitializedContiguousArrayBuffer<S.Iterator.Element>(
      initialCapacity: initialCapacity)

  var iterator = source.makeIterator()

  // FIXME(performance): use _copyContents(initializing:).
  // Add elements up to the initial capacity without checking for regrowth.
  for _ in 0..<initialCapacity {
    builder.addWithExistingCapacity(iterator.next()!)
  }

  // Add remaining elements, if any.
  while let element = iterator.next() {
    builder.add(element)
  }

  return builder.finish()
}

The problem here is underestimatedCount. For plain sequences, this just has a default implementation that returns 0 – however, for collections, it has a default implementation which gets the count of the collection (I go into this in more detail here).

The default implementation for the count of a Collection (which BidirectionalSlice will use here) is simply:

public var count: IndexDistance {
    return distance(from: startIndex, to: endIndex)
} 

Which, for our slice, will walk through the indices up to indexAfterTheFifthElement, thus re-evaluating the elements in the range 0...15, again.

Finally, an iterator of the slice is made, and is iterated through, adding each element in the sequence to the new array’s buffer. For a BidirectionalSlice, this will use an IndexingIterator, which simply works by advancing indices and outputting the element for each index.

The reason why this walk over the indices doesn’t re-evaluate the elements up to the first element of the result (note in the question’s example, 0 is evaluated one time less) is due to the fact that it doesn’t directly access the startIndex of the LazyFilterBidirectionalCollection, which has to evaluate all elements up to the first element in the result. Instead, the iterator can work from the start index of the slice itself.

---

The Solution

The simple solution is to avoid slicing the lazy filter collection in order to get its prefix, but instead apply the prefixing lazily.

There are actually two implementations of prefix(_:). One is provided by Collection, and returns a SubSequence (which is some form of slice for most standard library collections).

The other is provided by Sequence, that returns an AnySequence – which, under the hood uses a base sequence of _PrefixSequence, which simply takes an iterator and allows iteration through it until a given number of elements have been iterated over – then just stops returning elements.

For lazy collections, this implementation of prefix(_:) is great, as it doesn’t require any indexing – it just lazily applies the prefixing.

Therefore, if you say:

let result : AnySequence = numbers.lazy
    .filter {
        // gets called 1x per element :)
        print("Calling filter for: \($0)")
        return $0 % 3 == 0
    }
    .prefix(5)

The elements of numbers (up to the 5th match) will only be evaluated once by filter(_:)’s predicate when passed to Array's initialiser, as you’re forcing Swift to use Sequence’s default implementation of prefix(_:).

The foolproof way of preventing all indexing operations on a given lazy filter collection is to simply use a lazy filter sequence instead – this can be done by just wrapping the collection you wish to perform lazy operations on in an AnySequence:

let numbers = Array(0 ..< 50)

let result = AnySequence(numbers).lazy
    .filter {
        // gets called 1x per element :)
        print("Calling filter for: \($0)")
        return $0 % 3 == 0
    }
    .dropFirst(5) // neither of these will do indexing,
    .prefix(5)    // but instead return a lazily evaluated AnySequence.


print(Array(result)) // [15, 18, 21, 24, 27]

However note that for bidirectional collections, this may have an adverse effect for operations on the end of the collection – as then the entire sequence will have to be iterated through in order to reach the end.

For such operations as suffix(_:) and dropLast(_:), it may well be more efficient to work with a lazy collection over a sequence (at least for small inputs), as they can simply index from the end of the collection.

Although, as with all performance related concerns, you should first check to see if this is even a problem in the first place, and then secondly run your own tests to see which method is better for your implementation.

---

Conclusion (TL;DR)

So, after all of that – the lesson to learn here is that you should be wary of the fact that slicing a lazy filter collection can re-evaluate every element of the base collection up to the end index which the slice can ‘view’.

Often it’s more desirable to treat a lazy filter collection as a sequence instead, which cannot be indexed, therefore meaning that lazy operations cannot evaluate any elements (doing so would risk destructively iterating over them) until an eager operation happens.

However, you should then be wary of the fact that you’re potentially sacrificing being able to index the collection from the end, which is important for operations such as suffix(_:).

Finally, it’s worth noting that this isn't a problem with lazy views such as LazyMapCollection, as their elements don’t depend on the ‘results’ of previous elements – therefore they can be indexed in constant time if their base collection is a RandomAccessCollection.

Lazy evaluation with a predicate

Here is an example of what you want

length $ take 10 $ filter even [1..]

[1..] is infinite, so if this weren't lazy, the program would hang.

You are pipeing [1..] through a filter even, then capping the number at 10.... Then you do something with that list. Instead of length, you could check if it reached the threshhold by using (>= 10) $ length).

How do I access a lazy sequence with an index?

You can access them in a similar fashion to how you access a string by an integer, i.e. using index(_:offsetBy:):

filtered[filtered.index(filtered.startIndex, offsetBy: 2)]

Accessing a lazy filter sequence is quite similar to accessing a string in that both are not O(1).

Alternatively, drop the first n items and then access the first item:

filtered.dropFirst(2).first

But I prefer the first one as "dropping" things just to access a collection, in my mind, is quite weird.

Are java streams able to lazilly reduce from map/filter conditions?

The actual term you’re asking for is short-circuiting

Further, some operations are deemed short-circuiting operations. An intermediate operation is short-circuiting if, when presented with infinite input, it may produce a finite stream as a result. A terminal operation is short-circuiting if, when presented with infinite input, it may terminate in finite time. Having a short-circuiting operation in the pipeline is a necessary, but not sufficient, condition for the processing of an infinite stream to terminate normally in finite time.

The term “lazy” only applies to intermediate operations and means that they only perform work when being requested by the terminal operation. This is always the case, so when you don’t chain a terminal operation, no intermediate operation will ever process any element.

Finding out whether a terminal operation is short-circuiting, is rather easy. Go to the Stream API documentation and check whether the particular terminal operation’s documentation contains the sentence

This is a short-circuiting terminal operation.

allMatch has it, reduce has not.

This does not mean that such optimizations based on logic or algebra are impossible. But the responsibility lies at the JVM’s optimizer which might do the same for loops. However, this requires inlining of all involved methods to be sure that this conditions always applies and there are no side effect which must be retained. This behavioral compatibility implies that even if the processing gets optimized away, a peek(System.out::println) would keep printing all elements as if they were processed. In practice, you should not expect such optimizations, as the Stream implementation code is too complex for the optimizer.

Limit the results of a Swift array filter to X for performance

The fastest solution in terms of execution time seems to be an
explicit loop which adds matching elements until the limit is reached:

extension Sequence {
    public func filter(where isIncluded: (Iterator.Element) -> Bool, limit: Int) -> [Iterator.Element] {
        var result : [Iterator.Element] = []
        result.reserveCapacity(limit)
        var count = 0
        var it = makeIterator()

        // While limit not reached and there are more elements ...
        while count < limit, let element = it.next() {
            if isIncluded(element) {
                result.append(element)
                count += 1
            }
        }
        return result
    }
}

Example usage:

let numbers = Array(0 ..< 2000)
let result = numbers.filter(where: { $0 % 3 == 0 }, limit: 5)
print(result) // [0, 3, 6, 9, 12]

Why does my lazy filtered list in scheme consume so much memory?

Here's how to fix your problem:

(define lazy-filter
  (lambda (pred seq)
    (delay
      (let loop ([sequence seq])
        ;; the following single line is added:   ------ NB!
        (set! seq sequence)
        (let ([forced (force sequence)])
          (cond [(null? forced) '()]
                [(pred (car forced))
                 (cons (car forced) (lazy-filter pred (cdr forced)))]
                [else (loop (cdr forced))]))))))

I tried (force (lazy-filter (lambda (v) (= v 100000000)) (lazy-arithmetic-sequence 0 1))) in Racket, and it finishes up, though slowly, running in constant memory as reported by my OS, returning

'(100000000 . #<promise:unsaved-editor:12:4>) 

Without the (set! seq sequence) the memory consumption reported by OS shots up by several gigabytes and then Racket reports it has run out of memory and the execution is aborted.

Some other re-writes of your code are found below, as are previous versions of this answer.

---

Trying your code in Racket's debugger, we get

forced and sequence are advancing along nicely, but seq is still at the start. And no wonder, nothing is changing it.

That's exactly what you suspected. A reference to the start of the sequence can not be released because seq is holding on to it until the result is found and returned (as the cons pair). For 100 elements it's not an issue, but for 1 billion it surely is.

Float loop up and out of lazy-filter and the problem seems to be gone:

This code transformation technique is known as lambda lifting.

The call to loop in lazy-filter becomes fully and manifestly tail because of it. Thanks to the tail call optimization the new call frame (for loop) can replace the old (for lazy-filter), which can now be discarded, together with its references into any data it held (here, seq).

The debugger snapshots show what's going on when the code is being debugged. Maybe without the debugging it is compiled differently, more efficiently. Maybe A Very Smart Compiler would in effect compile it by lambda lifting so the reference to seq could be relinquished, in the first code variant just as it is in the second. Looks like your Chez Scheme though compiles it just like Racket with debugging does (note, my version of Racket is old).

So it does seem like an implementation issue.

You will know for sure if you try the lambda-lifted code and see whether this fixes the problem:

(define (lazy-filter pred seq)
    (delay (lazy-filter-loop pred seq)))

(define (lazy-filter-loop pred sequence)
        (let ([forced (force sequence)])
          (cond [(null? forced) '()]
                [(pred (car forced))
                  (cons (car forced) 
                          (lazy-filter pred (cdr forced)))]
                [else  (lazy-filter-loop pred (cdr forced))])))

Although one could reasonably expect of Chez compiler to do this on its own. Maybe you are running interpreted code? Maybe you have the debugging information included? These are the questions to consider.

Another way to restructure your code is

(define lazy-filter
  (lambda (pred seq)
    (delay
      (let loop ([forced (force seq)])
          (cond [(null? forced) '()]
                [(pred (car forced))
                  (cons (car forced) 
                          (lazy-filter pred (cdr forced)))]
                [else  (set! seq (cdr forced))
                       (loop  (force (cdr forced)))])))))

---

(the older version of the answer follows:)

Let's see what forcing your expressions entails. I will use shorter names for your variables and functions, for more visual and immediate reading of the code.

We'll use SSA program transformation to make a function's operational meaning explicit, and stop only on encountering a delay form.

You don't include your delay and force definitions, but we'll assume that (force (delay <exp>)) = <exp>:

(define (lz-seq s n)  (delay  (cons s  (lz-seq (n s) n))))

(force (lz-seq s n))
 =
    (cons s  (lz-seq (n s) n))   ;; lz-seq is a function, needs its args eval'd
 =
    (cons s  (let* ([s2 (n s)])  (lz-seq s2 n)))
 =
    (let* ([s2   (n s)] 
           [lz2  (delay  (cons s2  (lz-seq (n s2) n))) ]) 
       (cons  s  lz2))

We've discovered that forcing your kind of lazy sequence forces its second element as well as the first!

(the following is incorrect:)

And this in fact exactly explains the behavior you're observing:

(force (lazy-filter (lambda (v) (= v 1000000000)) (lazy-arithmetic-sequence 0 1)))

needs to find out the second element of the filtered infinite stream before it can return the first cons cell of the result, but there's only one element in the filtered sequence, so the search for the second one never ends.

Clojure - Make first + filter lazy

This happens because range is a chunked sequence:

(chunked-seq? (range 1))
=> true

And it will actually take the first 32 elements if available:

(first (filter filter-even (range 1 100)))
1
2
. . .
30
31
32
=> 2

This overview shows an unchunk function that prevents this from happening. Unfortunately, it isn't standard:

(defn unchunk [s]
  (when (seq s)
    (lazy-seq
      (cons (first s)
            (unchunk (next s))))))

(first (filter filter-even (unchunk (range 1 100))))
2
=> 2

Or, you could apply list to it since lists aren't chunked:

(first (filter filter-even (apply list (range 1 100))))
2
=> 2

But then obviously, the entire collection needs to be realized pre-filtering.

This honestly isn't something that I've ever been too concerned about though. The filtering function usually isn't too expensive, and 32 element chunks aren't that big in the grand scheme of things.

Data filtering performance with dict comprehension

all evaluates both conditions, whereas and in TEST_2 is evaluated lazily which means the second condition is evaluated for ids >= 3 only.
Illustrating by simple print statements:

users = {
    1: {'id': 1, 'name': "toto"},
    2: {'id': 2, 'name': "titi"},
    3: {'id': 3, 'name': "tata"},
    4: {'id': 4, 'name': "tutu"},
    5: {'id': 5, 'name': "john"},
    6: {'id': 6, 'name': "jane"}
}

def check_1(item):
    print("check_1")
    return item['id'] >= 3

def check_2(item):
    print("check_2")
    return item['name'].find('a') != -1


# all condition
print("TEST AND")
for k, v in users.items():
    check_1(v) and check_2(v)

# all condition
print("TEST ALL")
for k, v in users.items():
    all([check_1(v), check_2(v)])

Out:

TEST AND
check_1
check_1
check_1
check_1
check_2
check_1
check_2
check_1
check_2
TEST ALL
check_1
check_2
check_1
check_2
check_1
check_2
check_1
check_2
check_1
check_2
check_1
check_2

Why is lazy evaluation useful?

Mostly because it can be more efficient -- values don't need to be computed if they're not going to be used. For example, I may pass three values into a function, but depending on the sequence of conditional expressions, only a subset may actually be used. In a language like C, all three values would be computed anyway; but in Haskell, only the necessary values are computed.

It also allows for cool stuff like infinite lists. I can't have an infinite list in a language like C, but in Haskell, that's no problem. Infinite lists are used fairly often in certain areas of mathematics, so it can be useful to have the ability to manipulate them.

---

Related Topics