view release on metacpan or  search on metacpan

ramblings/blogs-optimizing-2.md  view on Meta::CPAN

nbody - unboxed inlined arithmetic 2x faster
=============================================

In the [first part](http://blogs.perl.org/users/rurban/2012/09/optimizing-compiler-benchmarks-part-1.html) I showed some problems and possibilities of the B::C compiler and B::CC optimizing compiler with an example which was very bad to optimize, and...

The next days I went to Austin to meet with the [perl11.org](http://perl11.org/) group, which has as one of the goals an optimizing compiler for perl5, and to replace all three main parts of perl: the parser, the compiler/optimizer and the vm (the ru...

So I discussed the "stack smashing" problem with Will and my idea on the solution.

1. The "stack smashing" problem
-------------------------------

B::CC keeps two internal stacks to be able to optimize arithmetic and boolean operations on numbers, int IV and double NV.

The first stack, called "stack", keeps the perl operand stack, the arguments for each push/pop runtime pp\_* function.
The perl AST, called optree, is a bit disfunctional, as it not able to generate optimized variants on the operand types. So e.g there are integer optimized versions, used with "use integer", e.g. an i\_add variant for the add operator, which are used...

This B::CC stack, implemented in B::Stackobj keeps track of the types during the lifetime and can optimize and pessimize the used type of each stack variable. It can esp. optimize on bool, int and double, needs to exchange values on stringification a...
There is no nice picture in [illguts](http://search.cpan.org/dist/illguts/) describing operand stacks.

The second stack holds lexicals. For all perl lexical variables the same is done, the B::Stackobj::Padsv lexical stack mimics every function's PADLIST. Contrary to the stack, the access to this list is optimized by the compiler (op.c) already at comp...
See illguts for a [picture](http://cpansearch.perl.org/src/RURBAN/illguts-0.42/index.html#stack).

B::Stackobj::Padsv can use the perl type information for the packages int and double, but not yet for number and bool or CTypes nor Moose types. So `my int $i` already specifies an optimized integer, as an IV during the scope of `use integer`.

Specifying types via perl attributes, like `my $i :int;` would be nice also, but is technically impossible, since there is no compile-time method for attributes to be checked; only at run-time.

`B::CC` keeps a list of good ops (pp\_ functions), where the type or at least the number of arguments or return types is known at compile time. The same information is also available in the [Opcodes](http://search.cpan.org/dist/Opcodes/) module on CP...
Defined are op lists like, no\_stack, skip\_stack,  skip\_lexicals, skip\_invalidate, need\_curcop and for various other predefined op types needed for other optimizers or the Jit module. Does it branch, i.e. will it always return op->next or not?
Does it need to call PERL\_ASYNC\_CHECK?

On all unknown ops or ops which need to access lexicals, the current internal B::Stackobj::Padsv lexical stack values need to refreshed, written back from the internal compiler stack to the actual values on the heap, which is `PL_curpad[ix].` (sub wr...

So there is a lot of theoretical copying - "stack smashing" - going on.
But B::CC is cleverly keeping track of the stack areas which need to be written back, so in practice only the really needed values are handled.
In practice only numeric and boolean optimizations operate on private c variables on the C stack, rather than on referenced heap values, either on the perl stack or in the curpad. Simple sort callbacks also.
So only on unboxed numbers we need to copy the values back and force, before and after, as B::CC inlines most of these ops.

2. Benchmarks
-------------

I'll take a benchmark in which Perl is very slow compared to other scripting
languages, and which does a lot of arithmetic. Because I expect the
B::CC type optimizer to kick in, unboxing all the numbers, and inling
most of the arithmetic.

[nbody](http://shootout.alioth.debian.org/u32/performance.php?test=nbody)
performs a simple N-body simulation of the Jovian planets.
Perl is currently by far the slowest scripting language for nbody,
26 min compared to 9-18 min for ruby, php or python with n=50,000,000.

perl = perl5.14.2-nt (non-threaded, -Os -msse4.2 -march=corei7)

    $ time perl ../shootout/bench/nbody/nbody.perl 50000

    -0.169075164
    -0.169057007

     real	0m1.305s
     user	0m1.300s
     sys	0m0.000s

Compiled:

    $ perlcc --time -r -O -S -O1 --Wb=-fno-destruct,-Uwarnings,-UB,-UCarp,-DOscpSqlm,-v \
                  ../shootout/bench/nbody/nbody.perl 50000

    script/perlcc: c time: 0.171225
    script/perlcc: cc time: 0.984996
    -0.169075214
    -0.169078108
    script/perlcc: r time: 0.600024

So we get a **2x times faster run-time**, with a little bit of different results and a lot of interesting command line options.

**--time** prints the B::CC time as 'c time', the gcc and ld time as 'cc time', and the run-time as 'r time'. 0.625202s vs. 1.305s in pure perl. Even gcc plus ld with -OS is faster than perl. And B::CC's optimizer is also real fast here in this simpl...

**-r** runs the compiled program with the rest of the perlcc arguments

**-O** compiles with B::CC, not with the non-optimizing B::C

**-S** keeps the C source, to be able to inspect the generated optimized C code.

**-O1** adds some minor B::CC optimizations. -O2 is pretty unstable yet, and B::CC proper (-O0) already adds all B::C -O3 optimizations.

**--Wb** defines further B::CC options

**-fno-destruct** is a B::C option to skip optree destruction at the very end. It does thread, IO and object destruction in proper order, and of course does object destruction during run-time, but we do not care of memory leaks with normal executable...

-U defines packages to be **unused**. warnings, B, Carp are notorious compiler packages, which are innocently being pulled in, even if you do not use or call them.

B is used by the compiler itself, and since the B maintainer does a terrible job helping the B compiler modules, we have to manually force B get out of our way. warnings and Carp are also magically pulled in by some dependent core modules and cause a...

E.g. without -U the numbers are:

    cc pp_main