Wednesday, September 16, 2009

Fibonacci Strings and Performance

Fibonacci strings are related to Fibonacci numbers in that the length of the nth Fibonacci string is the nth Fibonacci number. Here's pseudocode for a function that generates them:

fibstr: int -> string
if n is 0
return the empty string
else if n is 1
return the string "b"
else if n is 2
return the string "a"
return fibstr(n-1) concatenated with fibstr(n-2)

The strings generated by this function for n > 2 have the interesting property that if you delete the last two letters the resulting string is a palindrome. Anyway, for kicks I decided to use Fibonacci strings to test the string performance of popular programming languages. The test was simple: run fibstr(31) 31 times. I was lazy in writing the tests, but the results were consistent across many cups of Bhakti chai and many executions of the test yesterday morning , so as far as I'm concerned they're valid representations of the relative performance of the languages with respect to string concatenation and, to some extent, memory management.

Java (StringBuilder w/JIT2.807s2.652s0.084s
Java (String w/JIT)2.819s2.692s0.076s
JavaScript (Rhino 1.6.r5-34.240s4.100s0.080s
Python (2.4.4)4.708s3.992s0.012s
Perl (5.8.8)7.528s7.484s0.008s
Java (StringBuilder w/o JIT)8.171s8.053s0.040s
Java (String w/o JIT)11.707s11.553s0.068s
Ruby (1.8.6)21.348s18.565s2.488s

Off-the-cuff ... Ruby's performance speaks for itself. I expected Perl to do better, since it's been around quite a while. I can see why Sun responded to early complaints about Java's performance with JIT. It's clearly effective, but I'd like to know more about how the JRE decides to compile to native code. With JIT, StringBuilder doesn't buy you anything if it's compiled to native code; without it, StringBuilder can make a noticeable (on paper) difference over plain String, but I wonder whether the difference shows up much in real workloads. If a string-manipulating function is a hot spot, it'll probably be compiled to native code. I suppose one would have to examine the memory impact of String v. StringBuilder as well.

I wouldn't be surprised if most of the time a language spends in system mode comes from calls to brk(2).

1 comment:

Ken Anderson said...

Interesting to see the difference between StringBuilder and String with JIT off. JIT appears to nullify that distinction... If you have a chance, I'd be interested in comparing the various versions of Python.. 2.4, 2.5, 2.6 and now 3.1. Apparently, 3.0 was dog slow with respect to strings but that (supposedly) got addressed in 3.1.

Thanks for this, I enjoyed the results!