4 ms·

C++ Algorithms, Boost and function currying

11 points by spivey 16y ago

dkersten 16y ago
The author went from this: int Dice::total() const { int total = 0; for(const_iterator current = dice.begin(); current != dice.end(); ++current) total += (*current)->faceValue(); return total; } to this: int Dice::total() const { return std::accumulate( dice.begin(), dice.end(), 0, bind(std::plus<int>(), _1, bind(&Die::faceValue, _2)) ); } and shows his intermediate steps. I took his last variant and converted it to the following, using Intel Threading Building Blocks to perform a parallel reduce: class Sum { const std::vector<Face*>& v; public: int sum; void operator()( const tbb::blocked_range<size_t>& r ) { const std::vector<Face*>& a = v; for( size_t i = r.begin(); i != r.end(); ++i ) sum += a[i]->faceValue(); } Sum( Sum& x, tbb::split ) : v(x.v), sum(0) {} void join( const Sum& y ) {sum += y.sum;} Sum(const std::vector<Face*>& a ) : v(a), sum(0) {} }; int Dice::parallel_total () const { Sum s(dice); tbb::parallel_reduce(tbb::blocked_range<size_t>(0, dice.size()), s, tbb::auto_partitioner()); return s.sum; } I had to guess what his Dice implementation contained and if I wrote in from scratch, I may have done it differently (eg, I'd handle that vector in Sum differently). Also, it doesn't really seem worth it performance-wise ;-) but still interesting to see it in action.
tman 16y ago
Where functional programming in C++ falls apart is this step: bind(std::plus<int>(), _1, bind(&Die::faceValue, _2)) When I first learned the STL, I worked pretty hard to figure out bind, etc., and get rid of all my for loops. The problem is that it doesn't actually buy you that much. The for loop is uglier, but simpler to maintain, read, and debug. Luckily the lambda syntax from the new standard already appears to be available in experimental gcc. This is going to be a game-changer.
- rubashov 16y ago
  The lambda stuff is in g++ 4.5, which is a stable release, right? It's not really experimental.
  - tman 16y ago
    http://gcc.gnu.org/gcc-4.5/cxx0x_status.html http://gcc.gnu.org/gcc-4.5/cxx0x_status.html : "Status of Experimental C++0x Support in GCC 4.5" Last month's release of 4.5.0 is stable, but the C++0x support is experimental.
  - deleted 16y ago
    [deleted]
  - DCoder 16y ago
    Lambdas are also supported in MSVC++ 2010.
steveklabnik 16y ago
This is also currently on HN as part of zedshaw's post on Shedding Bikes: http://sheddingbikes.com/posts/1276445247.html http://sheddingbikes.com/posts/1276445247.html http://news.ycombinator.com/item?id=1427599 http://news.ycombinator.com/item?id=1427599
d0m 16y ago
why use bind and not a "c++ lambda" if you are using boost? The expression: bind(std::plus<int>(), _1, bind(&Die::faceValue, _2)) makes the code harder to read instead of easier, which isn't an improvement.
ANH 16y ago
Okay, I admit this is the first time I've seen the word 'currying'. I've heard it spoken and thought it was a neologism derived from "courier", but it's apparently named after a man called Haskell: http://en.m.wikipedia.org/wiki/Currying?wasRedirected=true http://en.m.wikipedia.org/wiki/Currying?wasRedirected=true
Chris_Newton 16y ago
A more declarative programming style has many potential benefits. The trouble is, the version in that style is supposed to look something like this: total dice = sum (map faceValue dice) C++ is showing its age now, as ideas from other programming styles are entering the mainstream. Modern programming languages, designed with the benefit of hindsight, support those idioms natively and much more effectively than a bolted-on library, the cleverness of the Boost implementers notwithstanding. In this context, I think one of the commenters on the original article probably had it right: given that C++ is essentially an imperative language, using the new range-based for loops is a more natural way to write this algorithm.

11 points by spivey 16y ago

The author went from this: int Dice::total() const { int total = 0; for(const_iterator current = dice.begin(); current != dice.end(); ++current) total += (*current)->faceValue(); return total; } to this: int Dice::total() const { return std::accumulate( dice.begin(), dice.end(), 0, bind(std::plus<int>(), _1, bind(&Die::faceValue, _2)) ); } and shows his intermediate steps. I took his last variant and converted it to the following, using Intel Threading Building Blocks to perform a parallel reduce: class Sum { const std::vector<Face*>& v; public: int sum; void operator()( const tbb::blocked_range<size_t>& r ) { const std::vector<Face*>& a = v; for( size_t i = r.begin(); i != r.end(); ++i ) sum += a[i]->faceValue(); } Sum( Sum& x, tbb::split ) : v(x.v), sum(0) {} void join( const Sum& y ) {sum += y.sum;} Sum(const std::vector<Face*>& a ) : v(a), sum(0) {} }; int Dice::parallel_total () const { Sum s(dice); tbb::parallel_reduce(tbb::blocked_range<size_t>(0, dice.size()), s, tbb::auto_partitioner()); return s.sum; } I had to guess what his Dice implementation contained and if I wrote in from scratch, I may have done it differently (eg, I'd handle that vector in Sum differently). Also, it doesn't really seem worth it performance-wise ;-) but still interesting to see it in action.

tman 16y ago

Where functional programming in C++ falls apart is this step: bind(std::plus<int>(), _1, bind(&Die::faceValue, _2)) When I first learned the STL, I worked pretty hard to figure out bind, etc., and get rid of all my for loops. The problem is that it doesn't actually buy you that much. The for loop is uglier, but simpler to maintain, read, and debug. Luckily the lambda syntax from the new standard already appears to be available in experimental gcc. This is going to be a game-changer.

rubashov 16y ago
The lambda stuff is in g++ 4.5, which is a stable release, right? It's not really experimental.
- tman 16y ago
  http://gcc.gnu.org/gcc-4.5/cxx0x_status.html http://gcc.gnu.org/gcc-4.5/cxx0x_status.html : "Status of Experimental C++0x Support in GCC 4.5" Last month's release of 4.5.0 is stable, but the C++0x support is experimental.
- deleted 16y ago
  [deleted]
- DCoder 16y ago
  Lambdas are also supported in MSVC++ 2010.

steveklabnik 16y ago

This is also currently on HN as part of zedshaw's post on Shedding Bikes: http://sheddingbikes.com/posts/1276445247.html http://sheddingbikes.com/posts/1276445247.html http://news.ycombinator.com/item?id=1427599 http://news.ycombinator.com/item?id=1427599

d0m 16y ago

why use bind and not a "c++ lambda" if you are using boost? The expression: bind(std::plus<int>(), _1, bind(&Die::faceValue, _2)) makes the code harder to read instead of easier, which isn't an improvement.

ANH 16y ago

Okay, I admit this is the first time I've seen the word 'currying'. I've heard it spoken and thought it was a neologism derived from "courier", but it's apparently named after a man called Haskell: http://en.m.wikipedia.org/wiki/Currying?wasRedirected=true http://en.m.wikipedia.org/wiki/Currying?wasRedirected=true

Chris_Newton 16y ago

A more declarative programming style has many potential benefits. The trouble is, the version in that style is supposed to look something like this: total dice = sum (map faceValue dice) C++ is showing its age now, as ideas from other programming styles are entering the mainstream. Modern programming languages, designed with the benefit of hindsight, support those idioms natively and much more effectively than a bolted-on library, the cleverness of the Boost implementers notwithstanding. In this context, I think one of the commenters on the original article probably had it right: given that C++ is essentially an imperative language, using the new range-based for loops is a more natural way to write this algorithm.