Here's a short recap. Given a struct Employee, there is a function that filters out developers based on their salary. The original code looked like this:
The code is by no means difficult to understand, but it lacks in flexibility, and loops like this spread over many places in the code base becomes a maintenance liability.
Enter a kind of filter function template, that like the devs_who_make_at_least() function, returns a vector of pointers to the elements given, but using a provided predicate instead of a hard coded condition:
This is more generic. It works on any STL-like container and accepts any predicate that works on the value type. A few sample higher order functions were introduced to select elements just as in the original example:
Here pred_and() is used to create a new predicate from two others, returning true only if both contained predicates return true. Creating a vector of pointers to all developers that earn 1M or more simply becomes:
This was also shown to give performance gains over the original code.
So far so good, but what if the desired result is not a vector of pointers? What if we just want to calculate the accumulated salary of those selected? It doesn't make sense to pay the cost of populating an array for that. What if not all developers are needed, but you just need to browse through the selected ones until some other criteria is met? Then it is unnecessary to have populated the vector with all of them.
Enter lazy evaluation. The idea is to create yet another level of indirection, and defer calling the predicate until the actual iteration is done.
What is wanted is something like this:
From this a design emerges. The type of megadevs, returned by the call to filter(), must have member functions begin() and end(). The iterators returned must have access to the iterators into employees, and must have access to the predicate.
Here's an outline for the type returned by filter():
Each instance must refer to the original container, and must access the predicate, so these types are template parameters. The alias CI is just there for typographical purposes, making blog code shorter. The class iterator is deferred for a while. I'll get back to it soon. The interesting part is the member function begin(). We want it to create an iterator that refers to the first element in the container that fulfils the predicate, or end if there is no such element. It does this by checking the predicate and incrementing until true. The returned filter iterator must have the found iterator, the end, and the predicate, otherwise it cannot implement its increment operators.
The natural implementation would be to use std::find_if() instead of incrementing and checking manually, but this was unexpectedly slow.Now we can look at the iterator class:
It's quite a code block, but most is obvious. The aliases on lines 5-9 are there to make the iterator cooperate with algorithms in the standard library. See std::iterator_traits<> for details.
The other interesting part is operator++() on lines 15-21. As when created from the begin() member function of filter_t<>, it searches for the next iterator in the referenced container until the predicate matches or the end is reached. Also here, a hand written loop is used, after performance measurements showed an unexpected need.
With this in place, the filter() function template becomes nearly trivial:
Here's a good time to warn that this is a proof of concept code, intended to show the idea. For real world use, you would for example need variants with mutable access and variants that take ownership of the container if it is an rvalue, otherwise you cannot safely chain operations. These variants change nothing in performance, but they do make the implementation rather more complex.
Now is a good time to see if this did any good. A slight modification is made from the sample program of yesterday. The program populates a vector of 5000 employees. 1/4 of them with title = "Developer", and an unrealistically uniform random distribution salary in the range 50000 - 250000. With those the program did 500000 loops, each filtering out the developers that make 150000 or more and calculates the accumulated salary of the first 500.
Using g++ 6.2 and -O3, perf yields this result:
Slightly rewriting the test program to add using the vector version from yesterday as:
gives the result:
Here the advantage of lazy evaluation becomes obvious. We're only interested in the first 500 matches, so not populating a vector with the remaining is a gain. However, in all fairness, it should be said that there is a cost to this generality. The filter iterator shows much worse branch prediction results, and for large data sets, this can be noticeable.
There it is. Higher order functions are by no means a necessity for lazy evaluation, but when you have them, it's not a huge job to implement, and using it becomes natural. The lazy evaluation can give large performance gains, but there is an added complexity which may back fire.
Expanding further on this sooner or later leads to a range library, but that is another story.