C++ Streams

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

by zyngaro • 11 years ago

108 47 11 years ago

jscheiny.github.io

Just for comparison, in Haskell:

  total = sum $ take 10 (map (\x->x*x) [1..])

For this C++ code:

  int total = MakeStream::counter(1)
      | map_([] (int x) { return x * x; })
      | limit(10)
      | sum();

C++ code doesn't look that bad!

amelius• 11 years ago

It would be nice to see a performance comparison here. I wouldn't be surprised if Haskell would win, given the fact that lazy evaluation is its bread and butter.

kzhahou• 11 years ago

For a fully-evaluated sequence, where would Haskell find any perf improvement?

kibwen• 11 years ago

I'm sure that Haskell is fabulously performant here, but I'm not sure that it would be either significantly faster or slower than a C++ library that properly implements laziness. I can't speak for Streams, but Rust makes use of lazy iterators pervasively (all implemented entirely in the stdlib), and I'd expect the equivalent Rust code:

  let total = (1..).map(|x| x*x).take(10).sum();

to have no more overhead than the ideal Haskell code (though I could be oblivious to some very important GHC optimization... when posed this question my Haskell-using friends simply respond with "it's complicated").

Kutta• 11 years ago

Laziness slows everything down by a constant factor. In this example, Haskell would perform about the same as C++, because of optimizations that turn operations on linked list cells into loops (arriving at a result much like the external iterators of Rust and the expression template based iterators of C++).

CUViper• 11 years ago

Here's Rust:

    let total = (1..).map(|x| x*x).take(10).fold(0, |acc, x| acc+x);

You could replace the fold with ".sum()" if you use the unstable std::iter::AdditiveIterator. Or you could incorporate the squaring map into the fold, but then we're no longer comparing the same thing.

jonreem• 11 years ago

You can also replace the closure in the fold with Add::add, where Add is std::ops::Add:

  let total = (1..).map(|x| x * x).take(10).fold(0, Add::add);

This is an application of UFCS, which allows you to call methods as regular functions.

eco• 11 years ago

While we are playing this game, here it is in D:

    int total =  recurrence!"n+1"(0)
                .map!(x => x*x)
                .take(10)
                .sum();

Replacing that last sum() with reduce() from std.parellelism and you can sum them using multiple threads (obviously not useful with a set this small but the documentation for reduce() coincidentally includes a benchmark for the sum of squares running 2.5x faster when done in parallel).

spullara• 11 years ago

Java 8

int total = iterate(0, n -> n + 1).map(x -> x*x).limit(10).sum();

sanderjd3• 11 years ago

As someone who last used Java 5, that's really amazing! Need to write some more modern Java one of these days.

ajtulloch2• 11 years ago

With folly::gen

    using namespace folly::gen;
    auto total = seq(1) | mapped([](auto i) { return i * i; }) | take(10) | sum;

timtadh• 11 years ago

While we are at it Python:

    >>> sum(x*x for x in xrange(1,11))
    385

You could use a map in Python as well, but really, the generator expression is much cleaner:

    >>> sum(map(lambda x: x*x, xrange(1,11)))
    385

jlarocco• 11 years ago

Those compute the same value, but I think the point of the C++ stream version is to compute the value using a lazily evaluated infinite list.

The C++ equivalent of your Python would be something like:

    typedef boost::counting_iterator<int> ci;
    auto sum = std::accumulate(ci(0), ci(10), 0, [](auto x, auto y) { return x + (y*y); });

No special streaming library required.

father_of_two• 11 years ago

A solution in the spirit of the post using itertools:

    >>> from itertools import islice,count
    >>> sum(x*x for x in islice(count(1),10))
    385

burke• 11 years ago

Here it is in J:

    +/*:>:i.10

It's kind of cheating because J doesn't really do lazy evaluation of infinite sequences AFAIK, but I thought it was fun.

EDIT:

    i.  integer range
    *:  square
    >:  increment
    +/  sum

so this reads sort of like: sum(square_each(increment_each(integer_range(10)))

eggy2• 11 years ago

You beat me to the J solution, but here it is in APL:

  +/2*⍨⍳10

No need for increment, since index is set to start at 1. You can set it to 0 too, if you work that way.

+ addition

/ reduce

2 (to be fed to exponential operator * for square)

* exponential

⍨ commute

⍳ iota - index generator

I would consider C++ with this library over Haskell just because you get the world of C++, but with a bit more of the expressiveness I like in the functional languages.

omgtehlion• 11 years ago

looks like brainfuck to me ;)

wyager• 11 years ago

alternate Haskell:

    sum [x^2 | x <- [1..10]]

jheriko3• 11 years ago

don't confuse standard libraries, libraries and languages :)

Prelude is functional, C++ STL and the C library are imperative.

There is a valid argument that a 'good ol' fashioned' bit of procedural code (for loop) makes this same algorithm easier to read than either of these (it certainly makes it shorter), since it tells you explicitly what it is doing rather than assuming (usually a safe assumption) that programmers can understand and trust things like sum, map and take/limit.

i'm thinking of something like:

  int iTotal = 0;
  for( int i = 0; i < 10; ++i )
  {
      iTotal += i * i;
  }

sanderjd3• 11 years ago

That argument is not invalid, but the counter-argument is that the functional version does a much better job of capturing the intention of the code, rather than the procedure of it. The intention is to get the sum of the squares of the first 10 numbers counting from 1. My gut tells me that I have fewer bugs when I'm capturing intention rather than process, but I won't claim that it's definitely true.

(Not to say this is an example of bug-due-to-process-over-intention, but you do have a bug – you're summing from 0 to 9 instead of 1 to 10.)

winterbe• 11 years ago

For JavaScript using Stream.js https://github.com/winterbe/streamjs

  var total = Stream
        .iterate(0, function (n) {
            return n + 1;
        })
        .map(function (x) {
            return x * x;
        })
        .limit(10)
        .sum();

rikkus• 11 years ago

Lazy.js, with ES6 arrow functions:

  var Lazy = require('lazy.js');

  var total = Lazy
    .generate(i => i + 1)
    .map(i => i * i)
    .take(10)
    .sum();

C#, with LINQ:

  IEnumerable<int> NaturalNumbers()
  {
    var i = 1;
	
    while (true)
      yield return i++;
  }

  var total = NaturalNumbers().Select(n => n * n).Take(10).Sum();

As, of course, int has a maximum, it would be more sensible to use:

  Enumerable.Range(1, int.MaxValue).Select(n => n * n).Take(10).Sum();

And if you already know that you want 10, as in the above, you'd likely do:

  Enumerable.Range(1, 10).Select(n => n * n).Sum();

mateuszf• 11 years ago

Clojure:

  (->> (rest (range)) (map #(* % %)) (take 10) (reduce +))

Matthias247• 11 years ago

F#:

    let total = Seq.initInfinite ((+) 1)
                |> Seq.map (fun x -> x*x)
                |> Seq.take 10
                |> Seq.sum

Alternatively one could use [1..System.Int32.MaxValue] to create the initial sequence.

millstone• 11 years ago

I'm not able to scroll the left sidebar in the docs page (http://jscheiny.github.io/Streams/api.html). Using Safari on OS X Yosemite.

caipre• 11 years ago

Working here, Firefox + Yosemite.

Tried Safari, it's working as well.

taternuts• 11 years ago

In the second example, you define `next_collatz`, but pass in `collatz_next`

corysama• 11 years ago

Very nice. I'm interested to know what features of C++14 are used that are not available in C++11.

__float• 11 years ago

A very (very) quick look gives an obvious answer of return type deduction and auto in lambda parameters (so, generic lambdas).

It's definitely possible (même likely?) there are other more subtle things in use too.

ThatGeoGuy• 11 years ago

I would expect that the project also uses const iterators (cbegin, cend, etc) which didn't make it into C++11, and probably make_unique<T>, which also never made it into C++11, even though it very well would have (if it had been implemented before the cutoff date).

In any case, most of C++14 (outside of automatic lambda parameter deduction) can be emulated or straight copied into C++ using C++11. Most of the implementations of library specific things can be found at [1], so if you find a feature in C++14 that you're missing, go ahead and search the draft standard files (most of which are verbatim the same implementation) and copy into your own project.

To be fair though, one of the bigger features of C++11 / C++14 brings to the table is just easier template / std::algorithm usage (via lambdas), and smart pointers. Beyond that, most things aren't as necessary or as widespread in use even within std / STL. So for the most part, if you (or parent) has been interested in learning some modern C++, for the most part you can start leveraging a lot of the more useful tools / tricks immediately, even if the compilers haven't fully implemented C++14 yet [2].

[1] https://isocpp.org/files/papers/

[2] My understanding is that libc++ and clang are fully caught up, but g++ / libstdc++ won't be 100% C++14 compliant until after gcc-5.0. Either way, the corner cases exist, but for the most part you can take advantage of most of the great areas of modern C++ without waiting for gcc-5.0.

ajtulloch2• 11 years ago

Facebook's folly::gen library (some examples at [1]) is another approach at this idea. It also has some nice features like buffered file reading, fork-join parallelism, etc.

[1] https://github.com/facebook/folly/blob/75278c6326af4e6a81b87...

hatred• 11 years ago

Looks slightly similar to Boost Range Adaptors ?

http://www.boost.org/doc/libs/1_57_0/libs/range/doc/html/ran...

mavam• 11 years ago

Similar to this effort, Eric Niebler's range library [1,2] aims at improving algorithm composability. The range library offers both an eager and lazy API. This is the lazy version (views):

  int sum = accumulate(view::ints(1)
                   | view::transform([](int i) {return i * i;})
                   | view::take(10), 0);

And this the eager (via actions):

   extern std::vector<int> read_data();
   std::vector<int> vi = read_data(); action::unique;
   vi = std::move(vi) | action::sort | action::unique;

Eric puts in a lot of effort to make this library part of the C++ standard (see proposal N4128 [3]).

[1] https://github.com/ericniebler/range-v3

[2] User Manual with code examples: https://ericniebler.github.io/range-v3/index.html

[3] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n412...

tonyedgecombe• 11 years ago

I really dislike the use of operator overloading for things like this, I prefer a more verbose but idiomatic solution.

scott_s• 11 years ago

Using "|" to indicate flow of data from producer to consumer is idiomatic, if you consider the Unix command line. Personally, I find this kind of operator overloading tasteful and sensical.

jheriko3• 11 years ago

isn't this name confusing?

interesting stuff... although i do not enjoy the novel operator overloading, it does keep it tidy.

easytiger• 11 years ago

Err, you can't call it that if the std library already has a completely unrelated core concept with the same name.

stinos• 11 years ago

A good point actually. 'streams' makes me think of a lot things, but not one of those comes close to what is shown in the samples

g1236627• 11 years ago

Show some compiler errors or it did not happen.

lfj• 11 years ago

On a side note, the page has 40 H1 headers. Yikes!

C++ Streams

Related Stories