C++ Streams | Hacker News Reader

C++ Streams

jscheiny.github.io

108 pointszyngaro48 comments

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...

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

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.

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!

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.

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

Hell, if anything on a short sequence the naive (one loop at a time) approach might be faster if it keeps the instruction and data caches more coherent.

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").

It's certainly complicated and my answer probably does not apply to such a trivial example code that is using mostly stdlib functions. But the potential gain for Haskell is with loop fusion. The user could implement all of those functions themselves (sum, take, etc) and then loop fusion will bind them into a single performant loop that the lower optimizers will turn into a straight-line code, whereas in procedural languages only stdlib functions and certain patterns of general functions get the fusion treatment. Worse, throw in an unfortunate alias into the procedure and the whole thing collapses into sequential loops.

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++).

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.

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.

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).

Java 8

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

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

Yes, you do. :-) Alternative Java 8 solution:

int total = IntStream.rangeClosed(1, 10).map(x -> x*x).sum();

With folly::gen

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

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

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.

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

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)))

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.

looks like brainfuck to me ;)

Syntax is like getting used to math symbols, but once you do, you can really do a lot with a little - very expressive. I find myself in the J interpreter or APL workspace to hack away at solutions much more so than in any other language. I am not a web developer.

alternate Haskell:

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

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;
  }

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.)

why is it not valid? these things are part of the libraries involved. as languages both Haskell and C++ are extremely free form to the point where you can abuse them into behaving like domain specific languages.

or do you mean the bit about it being less code and easier to read?

well done on catching the bug. :)

this is my own fault for being sloppy and not paying attention.

You (understandably, due to the double-negative) misread! I said it is not invalid. Which was really a weaselly way of saying that it's valid but I don't really agree with it – sorry about that!

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();

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();

Clojure:

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

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.

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

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

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

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.

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.

> 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).

Const iterators in the form of cbegin() and cend() member functions on the standard containers were part of C++11, I'm pretty sure. It's either that or the C++ Primer 5e included some post-C++11 things in it.

What was missing from C++11, and probably an oversight, was std::cbegin() and std::cend() free functions, a la std::begin() and std::end(), for overloading and C arrays and so forth.

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...

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.

Working here, Firefox + Yosemite.

Tried Safari, it's working as well.

Looks slightly similar to Boost Range Adaptors ?

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

Show some compiler errors or it did not happen.

isn't this name confusing?

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

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

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

Reply on news.ycombinator.com