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
>
[hidden email]
>
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project>
_______________________________________________
Pharo-project mailing list
[hidden email]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Locked
