Streams – Lazy evaluation in C++14

http://jscheiny.github.io/Streams/

by normanv • 12 years ago

61 23 12 years ago

jscheiny.github.io

ris2• 12 years ago

Ah, python's itertools available in c++, at last.

pixelglow• 12 years ago

There's a previous implementation of itertools in C++: https://github.com/ryanhaining/cppitertools.

srean3• 12 years ago

Thanks for the reminder. I had come across cppitertools before and wanted to explore it and then totally forgot. Not sure why you got downvoted here, have tried to compensate.

BTW your handle rung a bell. I was wracking my brain to remember where have I heard of it before, then finally, oh yes MacSTL. It really deserves more love. Have not used it, but sure browsed the code.

ris2• 12 years ago

Thanks for this - hadn't picked up on it.

wwwwwwwwww• 12 years ago

honest question: is there any reason to add lazy evaluation to c++ other than to just add more features to the language?

lazy evaluation is one of those features where i have absolutely no idea what benefit it actually provides

wyager2• 12 years ago

lazy evaluation is one of those features where i have absolutely no idea what benefit it actually provides

Good question.

Let's say you have a program like this little python example:

    inputs = [raw_read() for i in range(1000)] # Read numbers from command line
    numbers = map(int, inputs) # Turn them into integers
    for num in numbers: # Check for 42
      if num == 42:
        return true
    return false # It's not there

If you use lazy evaluation, each item in the "map" object will only be calculated as needed. So if the first item in the "inputs" list is "42", it will only do a single string-to-integer conversion.

If you use greedy evaluation, it will map all strings to integers at once, which might be wasteful.

There are other benefits as well; this is the most obvious.

ori_b• 12 years ago

But in a language with mutating side effects, and iterators, I'm not sure what this buys you over:

    for (auto& num = file.line_iterator(); num != file.end(); num++) {
        if (atoi(num) == 42)
            return true;
    return false;

Note that 'line_iterator()' isn't something that (as far as I know) is defined in the C++ standard library, but there's nothing preventing it.

chas• 12 years ago

Edward Kmett's answer to this[1] question on Quora does a good job of explaining the value of lazy evaluation.

[1] http://www.quora.com/Programming-Languages/When-did-you-real...

Dewie• 12 years ago

|| and && operators in C-like languages are "short-circuited", i.e. (true || predicate) just returns (true) without evaluating (predicate). This is a form of lazy evaluation.

wz1000• 12 years ago

I would also like to add that laziness adds a lot of power and flexibility to common procedures.

For example, let's look at a canonical quicksort in Haskell:

  quicksort :: Ord a => [a] -> [a]

  quicksort []     = []

  quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)

      where

          lesser  = filter (< p) xs

          greater = filter (>= p) xs

This is nothing too interesting, but now let's say you want to write a function to find the minimum value of a list

In Python, this would probably be done like this:

  def min_list(lst):

      current_minimum = lst[0]

      for e in lst[1:]:

          if e < current_minimum:

              current_minimum = e

      return current_minimum

However, in Haskell, a very similar procedure can be defined like this:

  minimum xs = head (quicksort xs)

(head returns the first element of a list)

Now, if have the slightest care for efficiency, you would never, ever write a function like this in a strict language.

However, in Haskell, minimum [5,2,7,1,3] would be evaluated like this:

  > minimum [5,2,7,1,3]

  > head (quicksort [5,2,7,1,3])

Now, head 'demands' one element from quicksort, so quicksort would start getting evaluated

  > head (lesser ++ ...)  [p = 5]

(++) is nonstrict, and only evaluates the elements you really need. Since right now only one element is demanded, we can expect that nothing to the right of (++) would be evaluated

  > head ((quicksort (filter (<5) [2,7,1,3]) ) ++ ...)

Now filter is also lazy, and it will only evaluate elements as needed. Right now, only one element is demanded by quicksort(notice the (p:xs) in the definition. quicksort only cares about the 'p' right now)

  > head ((quicksort (2:(filter (<5) [7,1,3])) ++ ...)

  > head ((quicksort (filter (<2) 

                              xs) ++ ... ) ++ ...)                                     [p = 2, xs = filter (<5) [7,1,3]]

Now, quicksort demands another element from filter (<2) ..., so filter (<5) runs until it finds the first element that is also (<2) > head ((quicksort (1:(filter (<2) (filter (<5) [3] ++ ...)) ) ++ ...) ++ ...)

Filter will run through the entire list, comparing each element to 5,2 and 1 in order, and find nothing, returning [], which will hit the base case for quicksort []= []

  > head ( [] ++ [1] ++ ...)

Simplifying to

  > head ([1] ++ ...)

(++) has enough evaluated elements to give '1' to head, which finally returns

> 1

Notice that we passed through the list only once, just like in the python, in contrast to running an entire quicksort. While this is not as efficient as the python version as it keeps a few unnessary elements in memory, and compares elements to all previously found minimums, it is much more efficient than evaluating quicksort, and is pretty damn cool. With some GHC magic, the memory usage is also reduced somewhat.

I personally believe that the expressiveness gained through this procedure(we wrote quicksort and gained minimum for free!) offsets the loss in efficiency.

srean3• 12 years ago

@wwwwwwwwww you have been hell-banned and I dont see anything particularly offensive in your immediate comment history.

is there any reason to add lazy evaluation to c++ [...]

I think you are suffering from a misapprehension. Nothing is being added to C++ the language. This is just an implementation of lazy streams in C++14. Think of it as an optional 3rd party library.

lazy evaluation is one of those features where i have absolutely no idea what benefit it actually provides

Let me give you two examples. First try and solve this problem in your favorite language. Produce a sequence of k numbers that are multiples of 2,3 and 5 only, but produce them in sorted order. Yes of course this is contrived, but it will give you and idea of the conveniences that laziness can give you. [sorry, I gave away the important spoiler]

Second example say you want to compute

   (x + y)*z - w

where each of them are objects representing long vectors. You also want to keep the code readable and close to the mathematical notation of the domain. Naive way to do it will create lots of temporaries and unnecessary loops. Every binary operation is going to create a temporary (and entail a loop). But if you have laziness you just need one loop.

[EDIT: If one has laziness one need not instantiate the actual vector (x+y). One can return an object that only represents the operation. So one can keep building on the parse tree and finally when the result is actually used somewhere do you evaluate the expression encoded in the parse tree. Now since you have the entire expression tree you can evaluate it in just one loop. If you are curious you can search for deforestation and expression templates. You can of course do the same thing even if the language does not support laziness, but laziness is the key enabler here, if the language does not support it, _you_ have to implement it]. Without this features it is pretty much impossible to approach Fortran like speeds and expressiveness in array operations in C++.

A reason why basic Numpy is slow is because is that written naively it creates all these temporaries. There are a few ways to avoid it. Numexpr uses laziness (and tiling). You could also use the 'out' feature of Numpy functions creatively.

So in short, laziness has a lot of practical value, and I am not even bringing up aspects of purity etc. I had to roll something on my own for these needs. Would have been happier if there were such libraries available. [Ok full disclosure, I would have likely rolled my own anyway to understand how it works] There are a few libraries that do these things or help a lot in building these things. Some of the are Spirit and Fusion. Although I am conflating two different topics (i) fusion/deforestation and (ii) laziness, but they are related enough.

@dang thanks for the clarification, wwwwwwww's comment was indeed showing up as dead on this thread. wwwwwwww must have deleted his comment because at that time there was only one.

dang• 12 years ago

wwwwwwwwww you have been hell-banned

That is false. A comment was killed because it was a duplicate. We unkilled it.

thinkpad20• 12 years ago

Without this features it is pretty much impossible to approach Fortran like speeds and expressivness in array operations in C++.

Fortran is strict, though, is it not?

ufo• 12 years ago

Fortran has some built-in array operations that are tricky to implement in C. I think srean is saying that lazyness would help do that.

ptfoobar• 12 years ago

Second example say you want to compute

(x + y) * z - w

where each of them are long vectors but want to keep the look of the code readable and explicit. Naive way to do it will create lots of temporaries and unnecessary loops. Every binary operation is going to create a temporary (and entail a loop). But if you have laziness you just need one loop.

Can you elaborate on this? Why can laziness provide better code here?

fanssex• 12 years ago

1. loop: x + y, loop (x + y) * z, loop (x + y) * z - w.

2. loop: (x[i,...,n] + y[i,...,n]) * z[i,...,n] - w[i,...,n]

although I don't think the loops are going to be the main overhead in this case.

jzwinck• 12 years ago

If each of the four variables is a vector, naively you might do (x + y) first, producing a new vector. Then you would multiply by z, producing a second new vector. Finally, subtract w, producing a third new vector. You have now iterated over the length of the vectors three times, and allocated three new vectors (two of which are no longer needed).

A better way to do all that would be to allocate a single result vector and populate it with the full computed expression for each element. This can be much faster for large vectors. Python's numexpr (among others) is designed to do just this.

jeorgun• 12 years ago

How would this lazy-vector-mapping compare to the optimizations used in std::valarray? Or are those optimizations just the ones you mention here?

srean3• 12 years ago

Apologies, I did not see your question in time. Note that valarray is just a standard API, an implementer can write it as they wish. That said, these kinds of optimizations were indeed a motivation for creating valarray. Standard libraries do use exactly these optimizations in valarray (with some SIMD vectorization thrown in as well). You can also take a look at pixelglow's implementation, he has a comment downstream. It is pity that no one in the standards committee took ownership of valarray and it was included in a semi broken state.

mattpodwysocki• 12 years ago

Seems very close in implementation to RxCPP for push based streams and IxCPP for pull based, which has been created by Microsoft and now controlled by Microsoft Open Technologies. This library though does not require C++14 and is being actively developed: https://github.com/Reactive-Extensions/RxCPP

aetherspawn• 12 years ago

The performance isn't going to be very good without stream fusion, I would imagine.

Streams – Lazy evaluation in C++14

Related Stories