Algorithms matter

Brian commented on the my previous entry, calling the benchmark comparison unfair.

To quote.

"This is a rather unfair comparison though, as it is comparing completely different data structures with a test that caters to the strengths of one. Python and Ruby's lists are implemented via vectors, not linked lists, so have O(n) time to remove the first element. Linked lists (with a reference to their end) are O(1) for both insert at start, and delete from end."

I agree, it is unfair to compare an O(1) algorithm vs an O(n) algorithm. I don't know how Ruby libraries implements insert or pop but Brian implies it's O(n) because it's using vectors. For the record , OrderedCollection uses Arrays (vectors) under the covers and it does ok. Anyhow, I decided to see how well the Smalltalk version would do if I did with some "less than optimal" code (Just for fun you know).

So, the original benchmark used OrderedCollections

| l |
l := OrderedCollection new.
^Time millisecondsToRun: [
1 to: 5000000 do: [:x |
0 to: 9 do: [:i| l addFirst: i].
[ l isEmpty ] whileFalse: [l removeFirst]
].
]

I changed it to use an ordinary Array. Smalltalk Arrays can't grow or shrink, so to insert an element you have to create a new array. I do this with some bogus code which simply concatenates a new array containing the new element with the previous array. This is an O(n) operation. To remove the first element, I just copy all but the first element into a new array, again O(n).
This makes the inner loop of n insertions and n deletions actually O(n^2).

| l |
l := Array new.
^Time millisecondsToRun: [
1 to: 5000000 do: [:x |
0 to: 9 do: [:i| l := (Array with: i), l].
[ l size <= 0 ] whileFalse: [l := l copyFrom: 2 to: l size]
]
]

So, the original loop using #addFirst:, and #removeFirst is about 6 seconds. The second version with the O(n) insert and delete is a much slower 34 seconds. Still faster than the Ruby version, so I think this is good news for Ruby fans, it is possible to do better and I fully expect it to happen. My fearless prediction ? some performance improvements will be due to VM improvements, and others will be algorithm improvements.

Now, the thing about the O(n) version is that it should be sensitive to the values of the inner loop. Let's test that ...

In Smalltalk if you vary the values of the loops (outer,inner) here's what you get.
The original code, using OrderedCollections finishes all three variations in about 6 seconds.

The Array code comes back with this.

Outer,Inner Time
5000000,9 - 34 seconds
500000, 99 - 47 seconds
50000, 999 - 170 seconds

no great surprise, given the fact that each insert makes a full copy of the array, of course it peforms worse when the arrays are larger. Yes, the O(n) insertion and deletion hurts.

The Ruby numbers are (same bench as before, just vary the loop counters)

Outer,Inner Time
5000000,9 - 104 seconds
500000, 99 - 119 seconds
50000, 999 - 180 seconds

What does this tell me ? Ruby is probably using some O(n) insert and deletion. However this is just me guessing... What this really tells me is simple ... algorithms matter...

Performance is not optional

Interesting read here, on languages and choice and the conclusion is even right (the ability to mix and match languages, with proper interop will be key - frankenstein solutions need not apply). More on that some other time but referenced from that blog, I saw this which did some bashing comparisons of C/C++, Python and Ruby performance and my curiosity got the better of me ... I had to try my Smalltalk implementation (VisualAge Smalltalk) to compare.

The Ruby benchmark shown by the author is shown here (testlist.rb) . On the authors machine, it completes in "~100 secs". In comparison the author's C++ code took ~7 seconds and you can read his entry to determine his conclusions on the suitability of Ruby or Python for some applications. So, to compare and set a baseline on my own hardware, I first ran the Ruby code on my laptop and it completed in 111 seconds which for this purpose will be considered close enough to ~100 seconds to claim that our machines are roughly equivalent (I do know better but for this purpose... I declare it "close enough for government work" so I just squint a little and I can do a direct comparison to the authors C++ numbers.

I translated the Ruby code to Smalltalk, trying to keep the code as close as possible to the Ruby version. Here it is.

| l start stop |
l := OrderedCollection new.
start := Time millisecondClockValue.
1 to: 5000000 do: [:x |
0 to: 9 do: [:i|
l addFirst: i.
].
[ l isEmpty ] whileFalse: [
l removeFirst]
].
stop := Time millisecondClockValue.
stop - start

On the same machine it runs in (drum roll please ...) 7.2 seconds which is umm, "approximately" 7 seconds and comparable to the optimized C++ numbers quoted by the author. (For complete truth in advertising, if you use different permutations of #addLast, #removeLast, the times can go up to about 9 seconds).

What does this tell me ? Clearly, Smalltalk is as fast as C++ ? Wooo hooo... sure, and sometimes faster, and ok, sometimes slower too. What does it really show ? That Ruby and Python have a way to go performance wise and if you apply modern implementation techniques like the ones used in commercial (and some open source) Smalltalks, improved performance is well within reach. Using a Smalltalk VM for Ruby has been discussed here and with the release of Strongtalk, this is a possibility.

Anyone want to guess what the numbers for the same benchmark is in Java ? (Hint - think linked list of primitive types).

So, despite some of the crazy rhetoric you have to wade though these days, one of the nice things that has happened as part of the recent rise in interest in dynamic languages are these performance comparisons, which in turn is leading to a rediscovery of the "old ways" :). This can only be good for all. Remember kids, "performance is not optional" (and neither is interop).

Yes, Virginia there is an Unreachable Clause.

(with apologies to Francis Church)

From Neil's update to closures being considered for Java.

I like closures as a powerful programming construct but after reading it, I can only say ...



"DEAR EDITOR of SRR: I am 44 years old.
"Some of my Java friends say there is no Unreachable Clause.
"Papa says, 'If you see it in THE SUN it's so.'
"Please tell me the truth; is there a Unreachable Clause?


"VIRGINIA O'HANLON."

VIRGINIA, your Java friends are wrong. They have been confused by dynamic languages in this web services age. They do not believe except [what] they type. They think that nothing can be which is not fixable by their little type declarations. In this great universe of ours the source is a key artifact, and using ant, javac, and lots of developer intellect, you can create a boundless platform (in source and in size), and be joyous by our intelligence capable of grasping the whole of truth and knowledge.

Yes, VIRGINIA, there is a Unreachable Clause. It exists as certainly as do generics, primitive types, exceptions and inner classes, and you know that they are bound to give to your code its highest beauty and joy. Alas! How dreary would be the world if there were no Unreachable Clause! It would be as dreary as if there were no java.lang.Object Smalltalk. There would be no childlike faith in type systems, no runtime errors, no exceptions to make tolerable this existence. We should have no enjoyment, no programming joy. The eternal light which complex type systems fills in programmer's heads would be extinguished.

Not believe in Unreachable Clause! You might as well not believe in Java! You might get your papa to hire men to watch in all the JSRs in the JCP to catch the Unreachable Clause, but even if they did not see Unreachable Clause coming down, what would that prove? Nobody sees the Unreachable Clause, but that is no sign that there is no Unreachable Clause. The most real things in the world are those that neither children nor men can subclass or instantiate. Have you ever declared an unchecked exception ? Of course not, but that's no proof that they are not there. Nobody can conceive or imagine all the wonders there are untyped and instantiatable in the world.

You tear apart the JVM and see what makes the ticking inside, but there is a veil covering the unseen world which not the strongest developer, nor even the united strength of all the type theorists that ever lived, could tear apart. Only faith, fancy, syntax, types, question marks and <> brackets can push aside that curtain and view and picture the supernal beauty and glory beyond. Is it all real? Ah, VIRGINIA, in all this world there is nothing else real and abiding. No Unreachable Clause! Thank GOD! that Unreachable lives, and it will live forever even if you cannot reach it. A thousand years from now, nay, ten times ten thousand years from now, Unreachable will continue to make glad the heart of developers.

The Editor of SRR

p.s. With this, I have received closure. It's not what I expected.