[Openmcl-devel] impact of number of arguments and closures on performance

[Waldek Hebisch]

On Tue, May 12, 2020 at 07:39:14PM +0200, Taoufik Dachraoui wrote:
> how FriCAS does perform compared to CCL, for example, can you test for me
> the fibonacci function
> 
> on my computer ccl takes 7.22seconds, what about FriCAS on CCL?
> 
> ie. (defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
> ? (time (fib 45))
> (FIB 45)
> took 7,225,458 microseconds (7.225458 seconds) to run.
> During that period, and with 16 available CPU cores,
>      7,222,601 microseconds (7.222601 seconds) were spent in user mode
>          2,253 microseconds (0.002253 seconds) were spent in system mode
> 1134903170
> 

FriCAS on top of CCL 11.5:

(1) -> )set messages time on
(1) -> )read ../fib.input
fib(n) ==
    n < 2 => n
    fib(n - 1) + fib(n - 2)
 
                                                                   Type: Void
                                                                  Time: 0 sec
(2) -> fib(45)
   Compiling function fib with type Integer -> Integer 

   (2)  1134903170
                                                        Type: PositiveInteger
                         Time: 0.00 (IN) + 31.58 (EV) + 0.02 (OT) = 31.61 sec

Your code:

? (defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
FIB
? (time (fib 45))
(FIB 45)
took 28,400,276 microseconds (28.400276 seconds) to run.
During that period, and with 4 available CPU cores,
     28,400,000 microseconds (28.400000 seconds) were spent in user mode
              0 microseconds ( 0.000000 seconds) were spent in system mode
1134903170

Both on 2.40GHz Core 2.

> I am interested to know how fast can be an interpreter compared to the host
> language (few hundreds times slower or at best 10 times slower?)
> is there any benchmark tests of interpreters compared to their host
> languages?

As I wrote FriCAS compiles to Lisp.  In case of 'fib' function
above resulting code is:

(DEFUN |*1;fib;1;frame0| (\#1 |envArg|)
    (COND
        ((< \#1 2) \#1)
        ('T (+ (|*1;fib;1;frame0| (- \#1 1) NIL)
               (|*1;fib;1;frame0| (- \#1 2) NIL)))))


So there is overhead due to extra argument.  Main cost is that
in general FriCAS function call is compiled to indirect call
at Lisp level, so function calls are more exponsive and Lisp
compiler has limited opportunity to optimize.  But FriCAS
spend some effort to translate "simple" operations like '<'
or '+' into Lisp exivalents, so typicaly speed is comparable
to hand-written Lisp.

FriCAS interprets code only when static type checks fail.
This is hundreds times slower than compiled code, mostly
due to dynamic type checks, dynamic dispatch and type
convertions.

In general I saw few intepreters running a about 10 times
slower than host language, but the interpreted language
was quite low level.  I measured speed of several
interpreters and on simple low-level code speed was
about 100 times slower than host language (C in all
cases).  There were few outliers, about 10000 times
slower than host language.  One of outlieres was 'bash',
where semantic essentialy forces interprtetation on
string level.  Another outlier was 'ucblogo' where
most constructs were macros and author decided that
redefinition of macro should have immediate effect.
So 'ucblogo' was constatly re-reading macro definitions
from disk files.

Bottom line: unless you do something stupid (like
'bash' or 'ucblogo') your intepreter will be
about 50-500 times slower than host language
on low-level code.  Hard work can decrease this
maybe to 10.  OTOH in more realistic code most
time goes into library functions.  If you have
rich library of fast functions than on higher
level tasks slowdown will be much smaller.

With Lisp as host language you always have option
to compile.  When compilation is done right
slowdown will be negligible.

-- 
                              Waldek Hebisch