On Sat, 13 Mar 2010, Stephan Eggermont wrote:
Levente wrote:
How bad do they perform? Do you have benchmarks?
With a
coll := OrderedCollection new.
1 to: 10000000 do: [:i | coll add: i].
a profile of:
1 to: 100 do: [:i | coll add: i beforeIndex: 10]
here takes 1438 ms. Moving memory gets to be slow.
All operations that start taking O(#elements) time are
no longer funny.
I don't know why do you expect insertion to be fast into the middle of an
OrderedCollection? It just shouldn't be, OrderedCollection doesn't
support this. I think it's fair to assume that developers know what the
collections can and can't be used to.
The usual thing to do is to start using multiple blocks
of memory (like a BTree). Doubling size when growing
If it would depend on the size of the memory chunk, these values wouldn't
be linear:
Array streamContents: [ :stream |
| size |
size := 10.
[ size <= 10000000 ] whileTrue: [
| coll |
coll := OrderedCollection new.
Smalltalk garbageCollect.
stream nextPut: size -> [ 1 to: size do: [ :i | coll add: i ] ]
timeToRun.
size := size * 10 ] ]
"==> {10->0 . 100->0 . 1000->0 . 10000->2 . 100000->22 . 1000000->282 .
10000000->2490}"
is also not an acceptable strategy when getting close to
total ram capacity.
If the growth is not exponentional, the O(1) and O(n) runtime will
quickly become O(n) and O(n^2).
If a single data structure's size is getting close to the total ram
capacity you have three options:
- buy more ram (this is really cheap nowadays)
- use another data struture/another way to represent your data
- use another language which is closer to your hardware
But this is really an edge case. In the last five years I only had two
such cases. I took the hard way and rewrote the programs in C++. It was
pretty easy because I just had to translate the Smalltalk code to C++.
Levente
Stephan
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
