Gennadiy, I didn't reply to your earlier message about FC++ performance, because I agreed with your major point (or what I thought was your major point). That is, the tw_xxx.cpp example programs/benchmarks which compare FC++ performance and Haskell performance have no business being in Boost, as C++ users will not care about comparisons with Haskell. However, I think you are implying that FC++ lazy evaluation is very slow, and this is not true; see below. On Tue, Mar 02, 2004 at 03:44:43AM -0500, Gennadiy Rozental wrote:
2. There is nothing cool about class designed and implemented the way so it works 320 times slower then similar solution written in different style. And I am not talking about minor issues related to abstraction overhead and portability workarounds. There should be something wrong in the very heart of the design, for this to happened.
There is a misunderstanding here. The "similar solution" you posted is not similar at all. Whereas the FC++ version computes primality by creating a list of all the integers from 1 to N, then filtering out all of the factors of N, and then comparing this list to the list [1,N], your solution simply tests for divisors in a loop from 2..N/2. The whole point of the tw_primes.cpp example was to use (or abuse) HOFs and lazy evaluation at every point in the computation (in order to mimic a Haskell program which did the same) so as to create a microbenchmark which stress-tests these aspects of the implementation. The algorithm chosen for the primality test is absurdly inefficient; it was chosen because the straightforward/efficient approach does not stress-test the desired elements. Below I am attaching a revised version of your code and the FC++ code, where the FC++ version uses your primality test. The FC++ version still computes an "infinite list of primes" and then just inspects the Nth element. But this version runs nearly as fast as your version on my machine (there's about a 2% difference). Again, the summary point is that it was the choice of algorithm in the example (and not the library design/implementation) which made the example so slow. That said, it's still all my fault. :) This misunderstanding is just another example of my own failure to create documentation/examples which are useful to C++ers (and instead presenting docs/examples tailored to FPers). Revised code: ---------------------------------------------------------------------- #define BOOST_FCPP_ENABLE_LAMBDA #include "prelude.hpp" using namespace boost::fcpp; #include <iostream> using std::cin; using std::cout; using std::endl; // Gennadiy's code bool is_prime( int i ) { for( int c = 2; c <= i/2; ++c ) { if( i % c == 0 ) return false; } return true; } int nth_prime( int N ) { int i = 1; while( N > 0 ) { i++; if( is_prime( i ) ) N--; } return i; } // My revised code, which uses is_prime() for the primality test struct Prime : public c_fun_type<int,bool> { bool operator()( int x ) const { return is_prime(x); } } prime; struct Primes : public c_fun_type<int,odd_list<int> > { odd_list<int> operator()( int n ) const { return take( n, filter( prime, enum_from(1) ) ); } } primes; int main() { int i, N, t; cin >> N; { Timer timer; // please substitute your own timing mechanism i = nth_prime( N ); t = timer.ms_since_start(); cout << t << " " << i << endl; } { Timer timer; i = at( primes( N+1 ), N+1 ); t = timer.ms_since_start(); cout << t << " " << i << endl; } } ---------------------------------------------------------------------- -- -Brian McNamara (lorgon@cc.gatech.edu)