On Sat, 16 Oct 2010, Igor Stasenko wrote:
Hello,
just out of interest, i tried to compare the speed of my FIFOQueue
implementation and SharedQueue,
using Levente's benchmarks for stack:
"The linked Stack implementation"
(1 to: 5) collect: [ :run |
| stack |
Smalltalk garbageCollect.
stack := FIFOQueue new.
{
[ 1 to: 1000000 do: [ :each | stack nextPut: each ] ] timeToRun.
[ 1 to: 1000000 do: [ :each | stack next ] ] timeToRun } ]
#(#(291 69) #(170 65) #(168 66) #(168 65) #(168 65))
Then i changed FIFOQueue to SharedQueue and run it again..
waiting 1 minute.. wait a bit more.. then i came to smoke.. and after
returning, it was still running..
i interrupted it, and inspected the queue size.. it was slightly above
300000 items.
Of course, SharedQueue usually not used in scenarios, where you need
to push such large number of items.
So, its just a warning.
SharedQueue's code for "growing" (#makeRoomAtEnd) is crap IMHO. Because of
that it takes O(n) time to add or remove and element to or from the queue.
SharedQueue2 is a lot better approach, because it doesn't try to
reimplement a dynamic array, but uses OrderedCollection instead.
Btw calling a LIFO datastructure a queue is strange, because
a queue is always FIFO. Please call it a stack.
Levente
Btw, here is another comparison (Stack vs thread-safe LIFO queue):
(1 to: 5) collect: [ :run |
| stack |
Smalltalk garbageCollect.
stack := Stack new.
{
[ 1 to: 1000000 do: [ :each | stack push: each ] ] timeToRun.
[ 1 to: 1000000 do: [ :each | stack pop ] ] timeToRun } ]
Stack:
#(#(166 94) #(160 90) #(162 91) #(162 92) #(160 92))
LIFOQueue:
#(#(172 250) #(174 248) #(172 250) #(174 252) #(172 250))
Yes, it is slower (mainly for reading). But it is price for being thread safe :)
--
Best regards,
Igor Stasenko AKA sig.
_______________________________________________
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
