Comparing Runtime Performance of Perl and C (Practical mod

13.12. Comparing Runtime Performance of Perl and C

Perl is commonly used for web scripting because it is quick and easy to write, and very easy to change. Compiled languages usually take a lot more time and effort to write and debug and can be time-consuming to change. But compiled code often runs faster (sometimes a lot faster) than bytecode-interpreted languages such as Perl or Java. In most projects it is programmer time that is paramount, because programmers are expensive, but some projects demand performance above all other considerations. How do we compare the performance of a Perl script to that of a C program?

We know we can use the Benchmark module to compare Perl code. There are equivalent tools for C also, but how are we going to use two different tools and keep the comparison fair? Since Perl is a glue language in addition to its own merits, we can glue the C code into Perl and then use the Benchmark module to run the benchmark.

To simplify the task, we are going to demonstrate only the fact that C is more suitable than Perl for mathematical and memory-manipulation tasks. The purpose is to show how to use the best of both worlds.

We will use a very simple task that we will implement in Perl and C: the factorial function written both recursivly and iteratively. If you have ever taken a basic programming course you will be familiar with this example.

In mathematical language, we define the factorial function as follows:

1! = 1
N! = N * (N-1)!

So if we start from 1 and go up, we get these numbers:

1! =                1
2! = (2)(1)       = 2
3! = (3)(2)(1)    = 6
4! = (4)(3)(2)(1) = 24
... and so on.

The factorial grows very fast—e.g., 10! = 3,628,800 and 12! = 4.790016e+08 (479 million)—so you can imagine that the calculation of the factorial of large numbers is a memory-intensive operation.

Now since we have a recursive definition of the solution:

fact(1) = 1;
fact(N) = N * fact(N-1)

the easiest way to implement it is to write a recursive function. In Perl we just reproduce the definition:

sub factorial_recursive_perl {
    return 1 if $_[0] < 2;
    return $_[0] * factorial_recursive_perl($_[0] - 1);
}

Computer science teaches us that while recursive functions are often easy to write they are usually slower to run than their iterative equivalents. The iterative implementation is as easy as the recursive one in our example, and it should run much faster, since there is no function-call overhead. This is the iterative algorithm to calculate fact(N):

result = 1
for (i = 2; i <= N; i++) {
    result *= i;
}

By adjusting it to use idiomatic Perl, we get the following function:

sub factorial_iterative_perl {
    my $return = 1;
    $return *= $_ for 2..$_[0];
    return $return;
}

The implementations in C are again similar to the algorithm itself:

double factorial_recursive_c(int x) {
    if (x < 2)  return 1;
    return x * factorial_recursive_c(x - 1);
}

double factorial_iterative_c(int x) {
    int i;
    double result = 1;
    for (i = 2; i <= x; i++)
        result *= i;
    return result;
}

To jump ahead, when we run the final benchmark we get the following results:

Benchmark: timing 300000 iterations of iterative_c, iterative_perl,
           recursive_c, recursive_perl...
   iterative_c:  0 wallclock secs ( 0.47 usr +  0.00 sys =  0.47 CPU)
   recursive_c:  2 wallclock secs ( 1.15 usr +  0.00 sys =  1.15 CPU)
iterative_perl: 28 wallclock secs (26.34 usr +  0.00 sys = 26.34 CPU)
recursive_perl: 75 wallclock secs (74.64 usr +  0.11 sys = 74.75 CPU)

All functions under test were executing 100!, which is 9.33262154439441e+157 using scientific notation.

The iterative implementation is about two and a half times as fast in C and three times as fast in Perl, where function calls are more expensive. Comparing C to Perl, the iterative implementation in C is about 56 times faster than the same algorithm implemented in Perl, and in the case of the recursive algorithm, C is 65 times faster.

There are at least three approaches to embedding other languages into Perl: XS, SWIG, and Inline.pm. We will implement the C functions we've written using the XS and Inline.pm techniques in the following sections. While SWIG is easier to use than XS for simple tasks, it's not as powerful as XS and it's not bundled with Perl. If you work on code that may later be distributed on CPAN, you'd better use XS or Inline.pm.

13.12.1. Building Perl Extensions with XS and h2xs

Perl comes with a nifty utility called h2xs that builds a skeleton for a new module. It's useful whether you are going to write a module with extensions in C/C++ or just in plain Perl.

When you run this utility it creates a new directory named after the module, and a skeleton of the Makefile.PL, test.pl, Module.xs, Module.pm, Changes, and MANIFEST files. If you have a C header file, it tries to guess the XS code based on it and write the correct XS file. Depending on how complicated your interface is, it may or may not do the right thing, but it helps anyway since it creates a boilerplate (which saves quite a lot of work).

First we prepare a C source file and its header file (see Examples 13-21 and 13-22).

Example 13-21. factorial.h

double factorial_recursive_c(int x);
double factorial_iterative_c(int x);

Example 13-22. factorial.c

double factorial_recursive_c(int x) {
    if (x < 2)  return 1;
    return x * factorial_recursive_c(x - 1);
}

double factorial_iterative_c(int x) {
    int i;
    double result = 1;
    for (i = 2; i <= x; i++)
        result *= i;
    return result;
}

It's easy to get lost in directories when creating a new module; therefore, we will show the exact directory we are in, using the prompt:

/home/stas/dev/fact>

Assuming that we work in this directory, we will save both files in this working directory. Let's check:

/home/stas/dev/fact> find /home/stas/dev/fact -type f
/home/stas/dev/fact/factorial.c
/home/stas/dev/fact/factorial.h

Now we are ready to create the skeleton of the new module:

/home/stas/dev/fact> h2xs -n Book::Factorial -A -O -x \
  -F '-I ../..' factorial.h
Scanning typemaps...
Scanning /usr/lib/perl5/5.6.1/ExtUtils/typemap
Scanning factorial.h for functions...
Scanning factorial.h for typedefs...
Writing Book/Factorial/Factorial.pm
Writing Book/Factorial/Factorial.xs
Writing Book/Factorial/Makefile.PL
Writing Book/Factorial/README
Writing Book/Factorial/test.pl
Writing Book/Factorial/Changes
Writing Book/Factorial/MANIFEST

We'll explain the h2xs arguments we used:

-n Book::Factorial specifies the name of the new module. It is also used to create the base directory (in our case, Book/Factorial/).
-A omits all autoload facilities.
-O allows us to overwrite a directory with the new module if one already exists.
-x automatically generates XSUBs based on function declarations in the header file (factorial.h in our case).
-F `-I../..' specifies where the header file is to be found. When h2xs runs, it changes into the newly created directory (Book/Factorial/ in our example), so in order to see the header file, we have to tell h2xs to look two directories back. (You may also need to add -F '-I.' during the make stage.)
The header file (factorial.h in our case) comes last.

Our next step is to copy the C file and header into the newly created directory and cd into it:

/home/stas/dev/fact> cp factorial.c factorial.h Book/Factorial/
/home/stas/dev/fact> cd Book/Factorial/

Since we have a really simple header file with only two function declarations, we just need to adjust Makefile.PL to build the factorial.o object file and Factorial.o, the actual extension library. We adjust Makefile.PL by adding the following line:

'OBJECT'            => 'Factorial.o factorial.o',

We fix the INC attribute to point to the current directory so the copied include file will be found.

Now Makefile.PL looks like Example 13-23 (remember that h2xs does most of the work for us).

Example 13-23. Makefile.PL

use ExtUtils::MakeMaker;
# See lib/ExtUtils/MakeMaker.pm for details of how to influence
# the contents of the Makefile that is written.
WriteMakefile(
    'NAME'              => 'Book::Factorial',
    'VERSION_FROM'      => 'Factorial.pm', # finds $VERSION
    'PREREQ_PM'         => {  }, # e.g., Module::Name => 1.1
    'LIBS'              => [''], # e.g., '-lm'
    'DEFINE'            => '', # e.g., '-DHAVE_SOMETHING'
    'INC'               => '-I .', # e.g., '-I/usr/include/other'
    'OBJECT'            => 'Factorial.o factorial.o',
);

Now we remove parts of the default module created by h2xs and add the Perl functions to Factorial.pm, since our module mixes pure Perl and C functions. We also write some simple documentation in POD format. After we add the Perl code and documentation and do some patching, Factorial.pm looks like Example 13-24.

Example 13-24. Book/Factorial.pm

package Book::Factorial;

require 5.006;
use strict;

use vars  qw($VERSION);
$VERSION = '0.01';

use base qw(DynaLoader);

bootstrap Book::Factorial $VERSION;

sub factorial_recursive_perl {
    return 1 if $_[0] < 2;
    return $_[0] * factorial_recursive_perl($_[0] - 1);
}

sub factorial_iterative_perl {
    my $return = 1;
    $return *= $_ for 2..$_[0];
    return $return;
}

1;
_ _END_ _

=head1 NAME

Book::Factorial - Perl and C, Recursive and Iterative Factorial
Calculation Functions

=head1 SYNOPSIS

  use Book::Factorial;
  $input = 5;
  $result = Book::Factorial::factorial_iterative_c(   $input);
  $result = Book::Factorial::factorial_recursive_c(   $input);
  $result = Book::Factorial::factorial_iterative_perl($input);
  $result = Book::Factorial::factorial_recursive_perl($input);

=head1 DESCRIPTION

This module provides functions to calculate a factorial using
recursive and iterative algorithms, whose internal implementation are
coded in Perl and C.

=head2 EXPORTS

None.

=head1 AUTHORS

Eric Cholet <email address> and Stas Bekman <email address>

=head1 SEE ALSO

perl(1).

=cut

If you've written pure Perl modules before, you'll see that the only unusual part is the code:

use base qw(DynaLoader);

bootstrap Book::Factorial $VERSION;

The base pragma specifies that the package Book::Factorial inherits from DynaLoader. Alternatively, you can write this as:

require DynaLoader;
@Book::Factorial::ISA = qw(DynaLoader);

where @ISA is the array that's used when inheritance relations are specified.

bootstrap is the place where the C extension Factorial.o is loaded, making the C functions available as Perl subroutines.

It's very important to document the module, especially when the package's functions don't reside within the module itself. Doing so will let you and your users know what functions are available, how they should be called, and what they return.

We have written very basic documentation. Usually it's a good idea to document each method.

In our example we decided not to export any functions to the callers; therefore, you always need to prefix the functions with the package name if used outside of this module:

use Book::Factorial;
$result = Book::Factorial::factorial_iterative_c(5);

We are almost done. Let's build the Makefile:

/home/stas/dev/fact/Book/Factorial> perl Makefile.PL
Checking if your kit is complete...
Looks good
Writing Makefile for Book::Factorial

Next we run make to compile the extension and get the module ready for testing:

/home/stas/dev/fact/Factorial> make

In addition to building the extension, make also renders the POD documentation in nroff format, which will be installed as a manpage when make install is run.

It's now time to test that the C extension was successfully linked and can be bootstrapped. h2xs has already created test.pl, which does this basic testing:

/home/stas/dev/fact/Book/Factorial> make test
PERL_DL_NONLAZY=1 /usr/bin/perl -Iblib/arch -Iblib/lib 
-I/usr/lib/perl5/5.6.1/i386-linux -I/usr/lib/perl5/5.6.1 test.pl
1..1
ok 1

As we can see, the testing phase has passed without any problems. Is that all? Not really. We actually have to test that the functions are working as well, so we extend the test suite with an exhaustive set of tests.

In product-validation terminology this is sometimes known as comparing the results from the good and the bad machine, where the good machine is known to produce a correct result. In our case the good machine is either our head or a simple calculator. We know that:

4! =  = 24

So we know that if the function works correctly, for a given input of 4, the output should be 24. Of course, in some cases this test is not enough to tell a good function from a broken one. The function might work correctly for some inputs but misbehave for others. You may need to come up with more elaborate tests.

The testing procedure is based on printing the number of tests to be run in the BEGIN block and, for each test, printing either ok or not ok, followed by the number of the current test. Example 13-25 is a modified test.pl that exercises the bootstrapping (as provided by h2xs), plus two C functions and two Perl functions.

Example 13-25. test.pl

use Test;

BEGIN { plan tests => 5; }
use Book::Factorial;
ok 1; # module loaded OK

my $input = 4;
my $correct_result = 24; # the good machine: 4! = 24
my $result = 0;
my $s = 1;

# testing iterative C version
$result = Book::Factorial::factorial_iterative_c($input);
ok $result =  = $correct_result;

# testing recursive C version
$result = Book::Factorial::factorial_recursive_c($input);
ok $result =  = $correct_result;

# testing iterative Perl version
$result = Book::Factorial::factorial_iterative_perl($input);
ok $result =  = $correct_result;

# testing recursive Perl version
$result = Book::Factorial::factorial_recursive_perl($input);
ok $result =  = $correct_result;

Note the magic BEGIN block, which ensures that the test reports failure if it failed to load the module.

Now we run the test again using our new test.pl:

/home/stas/dev/fact/Book/Factorial> make test
PERL_DL_NONLAZY=1 /usr/bin/perl -Iblib/arch -Iblib/lib 
-I/usr/lib/perl5/5.6.1/i386-linux -I/usr/lib/perl5/5.6.1 test.pl
1..5
ok 1
ok 2
ok 3
ok 4
ok 5

Fortunately all the tests have passed correctly. Now all we have to do is to install the module in our filesystem and start using it. You have to be root to install the module into the system-wide area:

/home/stas/dev/fact/Book/Factorial# su
/home/stas/dev/fact/Book/Factorial# make install
Installing /usr/lib/perl5/site_perl/5.6.1/i386-linux/auto/Book/Factorial/Factorial.so
Installing /usr/lib/perl5/site_perl/5.6.1/i386-linux/auto/Book/Factorial/Factorial.bs
Installing /usr/lib/perl5/site_perl/5.6.1/i386-linux/Book/Factorial.pm
Installing /usr/lib/perl5/man/man3/Book::Factorial.3

That's it. Neither very complicated nor very simple. We mentioned the XS macro language earlier but didn't actually use it—this is because the code was simple, and h2xs wrote the Factorial.xs file (shown in Example 13-26) for us based on the header file we provided (factorial.h).

Example 13-26. Factorial.xs

#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include <factorial.h>

MODULE = Book::Factorial        PACKAGE = Book::Factorial

double
factorial_iterative_c(x)
  int x

double
factorial_recursive_c(x)
  int x

This file actually implements the real gluing specification. During the make phase it was macro-processed by the xsubppsubroutine into the C code version Factorial.c, which was then compiled into the Factorial.o object file and finally converted into the Factorial.so loadable object and installed in the architecture-dependent module library tree (/usr/lib/perl5/site_perl/5.6.1/i386-linux/auto/Book/Factorial on our machine).

When a more complicated C interface is used, the glue code might be much more involved and require knowledge of the XS language. XS is explained in the perlxs manpage. The following manpages might be useful too:

perlembed   Perl ways to embed Perl in your C or C++ application
perlapio    Perl internal I/O abstraction interface
perldebguts Perl debugging guts and tips
perlxs      Perl XS application programming interface
perlxstut   Perl XS tutorial
perlguts    Perl internal functions for those doing extensions
perlcall    Perl calling conventions from C
perlapi     Perl API listing (autogenerated)
perlintern  Perl internal functions (autogenerated)

The POD documentation format is explained in the perlpod manpage.

You may also want to read Advanced Perl Programming, by Sriram Srinivasan (O'Reilly), which covers XS and SWIG, and Extending and Embedding Perl, by Tim Jenness and Simon Cozens (Manning Publications).

13.12.2. The Benchmark

We are now ready to write the benchmark code. Take a look at Example 13-27.

Example 13-27. factorial_benchmark.pl

use strict;
use Benchmark;
use Book::Factorial ( );

my $top = 100;

timethese(300_000, {
  recursive_perl => sub {Book::Factorial::factorial_recursive_perl($top)},
  iterative_perl => sub {Book::Factorial::factorial_iterative_perl($top)},
  recursive_c    => sub {Book::Factorial::factorial_recursive_c($top)   },
  iterative_c    => sub {Book::Factorial::factorial_iterative_c($top)   },
});

As you can see, this looks just like normal Perl code. The Book::Factorial module is loaded (assuming that you have installed it system-wide) and its functions are used in the test.

We showed and analyzed the results at the beginning of our discussion, but we will repeat the results here for the sake of completeness:

panic% ./factorial_benchmark.pl
Benchmark: timing 300000 iterations of iterative_c, iterative_perl,
           recursive_c, recursive_perl...
   iterative_c:  0 wallclock secs ( 0.47 usr +  0.00 sys =  0.47 CPU)
   recursive_c:  2 wallclock secs ( 1.15 usr +  0.00 sys =  1.15 CPU)
iterative_perl: 28 wallclock secs (26.34 usr +  0.00 sys = 26.34 CPU)
recursive_perl: 75 wallclock secs (74.64 usr +  0.11 sys = 74.75 CPU)

If you want to do the benchmarking after the module has been tested but before it's installed, you can use the blib pragma in the build directory:

panic% perl -Mblib factorial_benchmark.pl

13.12.3. Inline.pm

Using XS and SWIG may seem like a lot of time and work, especially for something as simple as our factorial benchmark. Fortunately, there is a new module called Inline.pm that makes using Perl with C almost as easy as writing Perl by itself.

Inline.pm allows you to put the source code of other programming languages directly inside your Perl script or module. It currently supports C, C++, Python, Tcl, and Java. The idea is that you can write functions, subroutines, or methods in these languages, and Inline.pm will automatically do whatever it takes to make them callable by Perl. It will analyze your code, compile it if necessary, bind the appropriate routines, and load all the required components. This means that you can simply run your code as if it were any other Perl program.

For example, the entire factorial benchmark program can be written as shown in Example 13-28.

Example 13-28. factorial_benchmark_inline.pl

use strict;
use Benchmark;
use Inline 'C';

my $top = 150;

timethese(500000,
      {
       recursive_perl => sub {factorial_recursive_perl($top)},
       iterative_perl => sub {factorial_iterative_perl($top)},
       recursive_c    => sub {factorial_recursive_c(   $top)},
       iterative_c    => sub {factorial_iterative_c(   $top)},
      });

sub factorial_recursive_perl {
    return 1 if $_[0] < 2;
    return $_[0] * factorial_recursive_perl($_[0] - 1);
}

sub factorial_iterative_perl {
    my $return = 1;
    $return *= $_ for 2..$_[0];
    return $return;
}

_ _END_ _

_ _C_ _

double factorial_recursive_c(int x) {
    if (x < 2)  return 1;
    return x * factorial_recursive_c(x - 1);
}

double factorial_iterative_c(int x) {
    int i;
    double result = 1;
    for (i = 2; i <= x; i++) result *= i;
    return result;
}

That's all there is to it. Just run this Perl program like any other, and it will work exactly as you expect. The first time you run it, Inline.pm takes time to compile the C code and build an executable object. On subsequent runs, Inline.pm will simply load the precompiled version. If you ever modify the C code, Inline.pm will detect that and recompile automatically for you.

The results of this benchmark should be similar to the benchmark of the XS version of Book::Factorial, developed in the previous section.

Example 13-29 is an example of a simple mod_perl handler using Inline.pm with C.

Example 13-29. Apache/Factorial.pm

package Apache::Factorial;
use strict;

use Apache::Constants qw(:common);

use Inline 'Untaint';
use Inline Config => DIRECTORY => '/tmp/Inline';
use Inline 'C';
Inline->init;

sub handler {
    my $r = shift;
    $r->send_http_header('text/plain');
    printf "%3d! = %10d\n", $_, factorial($_) for 1..10;
    return OK;
}
1;

_ _DATA_ _

_ _C_ _

double factorial(int x) {
    int i;
    double result = 1;
    for (i = 2; i <= x; i++) result *= i;
    return result;
}

This handler will list out all of the factorial numbers between 1 and 10. The extra Inline.pm commands are needed because of mod_perl's unique environment requirements. It's somewhat tricky to make Inline.pm work with mod_perl because of the file permissions. The best approach is to force Inline.pm to compile the module before starting the server. In our case, we can do:

panic% mkdir /tmp/Inline
panic% perl -I/home/httpd/perl -MApache::Factorial \
-e 'Apache::Factorial::handler'

Now all we need is for the /tmp/Inline directory to be readable by the server. That's where Inline.pm has built the loadable object and where it's going to read from.

Inline.pm is an extremely versatile tool and can be used instead of XS in almost any application. It also has features that go well beyond the capabilities of XS. Best of all, you can get an Inline.pm program up and running in minutes.

The Inline.pm distribution comes with copious documentation, including a cookbook of common C-based recipes that you can adapt to your taste. It is also actively supported by the inline@perl.org mailing list.

Just like with XS, you can prepare a package with Makefile.PL and a test suite for a distribution on CPAN. See the Inline.pm manpage for more details.

13.12.4. Perl Extensions Conclusion

We have presented two techniques to extend your Perl code with the power of other languages (the C language in particular, but Inline.pm lets you embed other languages as well).

If you find that some sections of your code are better written in other languages that may make them more efficient, it may be worth experimenting. Don't blindly use Perl to solve all your problems—some problems are better solved in other languages. The more languages you know, the better.

Because Perl is so good at gluing other languages into itself, you don't necessarily have to choose between Perl and other languages to solve a problem. You can use Perl and other languages together to get the best out of them all.