until nil {

Recursive Fibonacci Benchmark

23 Sep 2010

Now for something entirely different: lets have some recursive fun! The type of fun only a recursive Fibonacci benchmark could bring!
*Update! This benchmark has been extended here. *

The benchmark consist of 8 fibonacci sequences, from a short 5 numbers sequence to a long 40 numbers sequence, applied to 9 different language runtime configurations:

All the benchmarks were implemented in a recursive fashion, and so highlight the languages runtime ability to deal with deep recursion. And as a side-show, when fibonacci is called on smaller numbers, the benchmark provide us with a comparison on runtime initialization delay.

I chose to work with 2 yummy glue-code languages for Objective-C, Nu and MacRuby. The benchmark will nicely allow us to compare their respective performance but also their Objective-C runtime integration against Objective-C itself. To crank the fun factor up, add Ruby and Python, the coolest guys in town, and SBCL as a reference figure in recursion optimization, with and without compiled fibonacci function. All languages fibonacci implementations can be found on github.

now, The bench

Case value: 5
                     objc: | 0 failed |   0.009s overall | score:   1.000 |
                     ruby: | 0 failed |   0.010s overall | score:   1.177 |
                   python: | 0 failed |   0.032s overall | score:   3.647 |
                       nu: | 0 failed |   0.065s overall | score:   7.457 |
                nu w/objc: | 0 failed |   0.065s overall | score:   7.475 |
            sbcl compiled: | 0 failed |   0.082s overall | score:   9.371 |
                  macruby: | 0 failed |   0.105s overall | score:  12.072 |
                     sbcl: | 0 failed |   0.110s overall | score:  12.651 |
           macruby w/objc: | 0 failed |   0.198s overall | score:  22.704 |

Case value: 10
                     ruby: | 0 failed |   0.006s overall | score:   1.000 |
                     objc: | 0 failed |   0.009s overall | score:   1.565 |
                   python: | 0 failed |   0.032s overall | score:   5.680 |
                nu w/objc: | 0 failed |   0.065s overall | score:  11.739 |
                       nu: | 0 failed |   0.068s overall | score:  12.180 |
            sbcl compiled: | 0 failed |   0.082s overall | score:  14.804 |
                  macruby: | 0 failed |   0.096s overall | score:  17.251 |
                     sbcl: | 0 failed |   0.109s overall | score:  19.625 |
           macruby w/objc: | 0 failed |   0.201s overall | score:  36.150 |

Case value: 15
                     ruby: | 0 failed |   0.007s overall | score:   1.000 |
                     objc: | 0 failed |   0.009s overall | score:   1.267 |
                   python: | 0 failed |   0.033s overall | score:   4.803 |
                nu w/objc: | 0 failed |   0.065s overall | score:   9.381 |
            sbcl compiled: | 0 failed |   0.082s overall | score:  11.773 |
                       nu: | 0 failed |   0.094s overall | score:  13.571 |
                  macruby: | 0 failed |   0.098s overall | score:  14.032 |
                     sbcl: | 0 failed |   0.108s overall | score:  15.543 |
           macruby w/objc: | 0 failed |   0.200s overall | score:  28.778 |

Case value: 20
                     objc: | 0 failed |   0.009s overall | score:   1.000 |
                     ruby: | 0 failed |   0.023s overall | score:   2.630 |
                   python: | 0 failed |   0.041s overall | score:   4.602 |
                nu w/objc: | 0 failed |   0.065s overall | score:   7.243 |
            sbcl compiled: | 0 failed |   0.083s overall | score:   9.272 |
                  macruby: | 0 failed |   0.099s overall | score:  11.117 |
                     sbcl: | 0 failed |   0.108s overall | score:  12.065 |
           macruby w/objc: | 0 failed |   0.198s overall | score:  22.210 |
                       nu: | 0 failed |   0.428s overall | score:  47.885 |

Case value: 25
                     objc: | 0 failed |   0.011s overall | score:   1.000 |
                nu w/objc: | 0 failed |   0.065s overall | score:   6.083 |
            sbcl compiled: | 0 failed |   0.087s overall | score:   8.087 |
                  macruby: | 0 failed |   0.106s overall | score:   9.860 |
                     sbcl: | 0 failed |   0.113s overall | score:  10.569 |
                   python: | 0 failed |   0.130s overall | score:  12.113 |
                     ruby: | 0 failed |   0.196s overall | score:  18.290 |
           macruby w/objc: | 0 failed |   0.200s overall | score:  18.616 |
                       nu: | 0 failed |   4.196s overall | score: 390.787 |

Case value: 30
                     objc: | 0 failed |   0.032s overall | score:    1.000 |
                nu w/objc: | 0 failed |   0.094s overall | score:    2.980 |
            sbcl compiled: | 0 failed |   0.148s overall | score:    4.693 |
                  macruby: | 0 failed |   0.169s overall | score:    5.375 |
                     sbcl: | 0 failed |   0.172s overall | score:    5.470 |
           macruby w/objc: | 0 failed |   0.221s overall | score:    7.004 |
                   python: | 0 failed |   1.121s overall | score:   35.579 |
                     ruby: | 0 failed |   2.122s overall | score:   67.337 |
                       nu: | 0 failed |  41.131s overall | score: 1305.347 |

Case value: 35
                     objc: | 0 failed |   0.258s overall | score:    1.000 |
                nu w/objc: | 0 failed |   0.317s overall | score:    1.229 |
           macruby w/objc: | 0 failed |   0.441s overall | score:    1.712 |
            sbcl compiled: | 0 failed |   0.808s overall | score:    3.134 |
                     sbcl: | 0 failed |   0.834s overall | score:    3.233 |
                  macruby: | 0 failed |   0.885s overall | score:    3.433 |
                   python: | 0 failed |  11.875s overall | score:   46.056 |
                     ruby: | 0 failed |  23.474s overall | score:   91.042 |
                       nu: | 0 failed | 466.516s overall | score: 1809.332 |

Case value: 40
                     objc: | 0 failed |     2.798s overall | score:    1.000 |
           macruby w/objc: | 0 failed |     2.892s overall | score:    1.034 |
                nu w/objc: | 0 failed |     4.017s overall | score:    1.436 |
            sbcl compiled: | 0 failed |     8.251s overall | score:    2.949 |
                  macruby: | 0 failed |     8.815s overall | score:    3.150 |
                     sbcl: | 0 failed |    11.644s overall | score:    4.161 |
                   python: | 0 failed |   131.329s overall | score:   46.929 |
                     ruby: | 0 failed |   260.043s overall | score:   92.924 |
                       nu: | 0 failed | 10280.748s overall | score: 3673.710 |

Totals:
                     objc: |     3.134 seconds overall | score:    8.832 |
                nu w/objc: |     4.754 seconds overall | score:   47.565 |
            sbcl compiled: |     9.623 seconds overall | score:   64.082 |
                  macruby: |    10.373 seconds overall | score:   76.289 |
                     sbcl: |    13.198 seconds overall | score:   83.319 |
           macruby w/objc: |     4.551 seconds overall | score:  138.208 |
                   python: |   144.593 seconds overall | score:  159.409 |
                     ruby: |   285.882 seconds overall | score:  275.399 |
                       nu: | 10793.246 seconds overall | score: 7260.268 |

Interpretation

What does this tells us? First, as we may have forecasted, compiled code is the only sane way to survive under heavy loads. Objective-C is undoubtedly the first on the line, followed by Nu helped by Objective-C. From this, Nu shows its runtime implementation is a light efficient layer over Objective-C, while its performance without Objective-C proves any recursion should be avoided natively even if the interpreter seems fast enough for other purposes. Contrary to Nu, MacRuby seems to do better without any help (??!). We can see that MacRuby load times are not that great, this fact is confirmed when looking at the smaller numbers benchmarks, add the burden of loading an external framework and you kill its performance… It must be noted though that of all the pure interpreted implementations, MacRuby is the only one, with SBCL, which doesn’t fail exponentially under high recursive load. Then, Python surprisingly only scores average… While its startup time is possibly improved in a more recent version, it would probably not be enough to improve its heavy recursion performance. Finally, I can’t and won’t say much about SBCL, as it was more of a curiosity for me, but still, its compiled function performed noticeably better than the interpreted version which was not bad anyway.

Special Highlights:

As a final note, welcome my distinguished special purposes mentions:

  • Nu, for its handles and integration with Objective-C
  • MacRuby, for its ability to sustain deep recursions natively
  • Objective-C, being the reference case and the language in which both Nu and MacRuby are coded.
blog comments powered by Disqus

}

Older Posts... Blog powered by Jekyll.
Built using Liquid, RedCloth, Pygments and Blueprint.

Copyright © 2008-2010 Louis-Philippe Perron