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:

  1. 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

    ReplyDelete
  2. @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.

    ReplyDelete