Re: [boost] Re: FC++ formal review

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-03-02 05:31:36

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_at_[hidden])