The way you wrote it causes an explosive number of function calls for increase of n. You're computing fib(n-1)+fib(n-2) each time, but you don't need to do that, because in the process of computing each value of fib(n-1), you also need to compute fib(n-2). That causes an unnecessary doubling of the code path, for each level of recursion, meaning that it is way longer than it needs to be (I think by a factor of n**(2**n), but I haven't done a proper analysis, so complexity buffs needn't bother to shoot me down).


The whole purpose of pycxx is to provide a function wrapper. The wrapper is doing a lot, and obviously it has quite a bit of overhead. By importing this overhead into each function call of an already horribly inefficient recursive algorithm, it's not surprising you get performance numbers you don't like.


To convince yourself of this, put a counter or a print statement into your code to show you how many times you are calling fib(). Once you are sufficiently horrified, Google for alternative Fibonacci implementations to reduce the number of times you have to go between Python and C++, and you should see a dramatic improvement.


Paul Keating


From: []
Sent: 22 November 2011 04:40
To: cxx-users
Subject: the performance of pycxx


I wrote a py extension to calculate fibonacci sequence (i.e. 1 1 2 3 5 ... ) as following

however, I found it is too slow as the table says


so, what is the problem? Diid I do something wrong? thanks


M    | speed for pure py | speed for pycxx


30    |      0.93 sec          |         6.35 sec

40    |     116.64 sec       |        789.91 sec



[py code]

import time

def fib(n):
    if n<=1:
        return 1
        return fib(n-1)+fib(n-2)

print fib(M)
for i in range(M):
print 'pure py=%.2f secs' % (et-st)

[/py code]



[pycxx code]

#ifdef _MSC_VER

#pragma warning(disable: 4786)



#include "CXX/Objects.hxx"

#include "CXX/Extensions.hxx"


class fib_module : public Py::ExtensionModule<fib_module>{


    fib_module():Py::ExtensionModule<fib_module>( "fib" ){

    add_varargs_method("fib", &fib_module::fib, "fibonacci sequence function");

    initialize( "this is the test module" );



  virtual ~fib_module(){}



    Py::Object fib (const Py::Tuple &args){


        Py::Long res = args[0];

        if (res<=Py::Long(1))  return Py::Long(1);


            Py::Tuple a(1), b(1); a[0]=Py::Long(res-2); b[0]=Py::Long(res-1);

            return fib(a)+fib(b);





#if defined( _WIN32 )

#define EXPORT_SYMBOL __declspec( dllexport )





extern "C" EXPORT_SYMBOL void initfib(){




    static fib_module* fib = new fib_module;



extern "C" EXPORT_SYMBOL void initfib_d(){ initfib(); }

[/pycxx code]

The information contained in this e-mail is confidential and may be privileged. It may be read, copied and used only by the intended recipient. If you have received it in error, please contact the sender immediately by return e-mail. Please delete this e-mail and do not disclose its contents to any person. NIBC Holding N.V. nor its subsidiaries accept liability for any errors, omissions, delays of receipt or viruses in the contents of this message which arise as a result of e-mail transmission. NIBC Holding N.V. (Chamber of commerce nr. 27282935), NIBC Bank N.V. (Chamber of commerce nr. 27032036) and NIBC Investment Management N.V. (Chamber of commerce nr. 27253909) all have their corporate seat in The Hague, The Netherlands.

De informatie in dit e-mailbericht is vertrouwelijk en uitsluitend bestemd voor de geadresseerde. Wanneer u dit bericht per abuis ontvangt, gelieve onmiddellijk contact op te nemen met de afzender per kerende e-mail. Wij verzoeken u dit e-mailbericht te Vernietigen en de inhoud ervan aan niemand openbaar te maken. NIBC Holding N.V. noch haar dochterondernemingen aanvaarden enige aansprakelijkheid voor onjuiste, onvolledige dan wel ontijdige overbrenging van de inhoud van een verzonden e-mailbericht, noch voor door haar daarbij overgebrachte virussen. NIBC Holding N.V. (KvK nr. 27282935), NIBC Bank N.V. (KvK nr. 27032036) en NIBC Investment Management N.V. (KvK nr. 27253909) zijn statutair gevestigd te Den Haag, Nederland.