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...
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...
posted by John Duimovich at 11:54 PM
1 Comments:
I don't really know how the Python list are implemented. Anyone ?
Not sure you need to "take back the numbers", they are what they are. The way I see it, is that a programmer will do exactly this kind of code in their application. Add some stuff to a list and remove it. The difference from C is that it is unlikely they will write their own lists. They will use the library that comes with the language. So that library better be well implemented.
The Smalltalk I tried, uses vectors and a start and end offset into it to represent first and last. insert can be fast (it also keeps room for inserts) and delete first/last is fast and they are index increment or decrement operations. The expensive operation is grow.
In the end, it's one benchmark and as you note in your recent blog, dynamic languages on VMs are becoming real so the VM part will get better. May be an opportunity to take a look at the algorithms used for common library implementations as well.
Post a Comment
<< Home