Monday, July 22, 2013

Logistic Map

A recent blog post discusses the relative performance between Haskell and C when calculating the billionth iteration of a particular logistic map function:

f(x) = 3.57 * x * (1-x)

A bit curious about how Factor would perform, I decided to do a comparison.

C

A simple implementation in C...

#include <stdio.h>

int main() {
    double x = 0.5;
    for(int i = 0; i < 1000000000; ++i){
        x = 3.57 * x * (1-x);
    }
    printf("x=%f\n", x);
}

...yields an answer in about 4.5 seconds on my machine:

$ time ./answer
x=0.495618

real 0m4.501s
user 0m4.495s
sys 0m0.005s

Factor

A simple implementation in Factor...

: logistic-chaos ( x -- y )
    [ 3.57 * ] [ 1 swap - * ] bi ; inline

: answer ( -- n )
    0.5 1,000,000,000 [ logistic-chaos ] times ;

...yields an answer in about 4.5 seconds on my machine!

IN: scratchpad [ answer ] time .
Running time: 4.478111574 seconds

0.4956180832934247
Note: Part of the speed comes from the Factor compiler using the inline request to determine that this is always called with floating point numbers. If the word was not inlined, the overhead of generic dispatch on every call would make this calculation take 19 seconds. If the calculation was not compiled into a word (as it is above), and just typed into the listener and executed with the non-optimizing compiler, the calculation would take 57 seconds.

2 comments:

Jon said...

I was surprised by the results, how did you compile the C code ? On my machine, I get:
jon@zik:~/aze$ gcc --version
gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3
jon@zik:~/aze$ gcc -O0 -std=c99 -o aze aze.c
jon@zik:~/aze$ time ./aze
x=0.495618

real 0m13.747s
user 0m13.717s
sys 0m0.004s
jon@zik:~/aze$ gcc -O2 -std=c99 -o aze aze.c
jon@zik:~/aze$ time ./aze
x=0.495618

real 0m5.997s
user 0m5.860s
sys 0m0.112s


versus factor:
IN: scratchpad [ answer ] time
Running time: 13.443373655 seconds

Additional information was collected.
dispatch-stats. - Print method dispatch statistics
gc-events. - Print all garbage collection events
gc-stats. - Print breakdown of different garbage collection events
gc-summary. - Print aggregate garbage collection statistics

--- Data stack:
0.4956180832934247

mrjbq7 said...

@Jon, Hah! I said Factor was as fast as C not that C couldn't be faster! :)

Yep, without optimizations (in my case just doing "clang foo.c") its as fast, but with optimizations the C program takes half the time or so.