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
> Pharo-project at lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>