avalon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Berin Loritsch <blorit...@apache.org>
Subject Re: [Report] Efficiencies of FixedSize and Default Queues
Date Wed, 19 Dec 2001 19:22:19 GMT
Chad Stansbury wrote:

> Is there a reason you're using an ArrayList rather than a LinkedList for the
> DefaultQueue?  ArrayLists are great for indexing, but suck for
> variable-sized lists w/ lots off adds & removes.  LinkedLists, on the other
> hand, excel at variable-sized lists with lots of adds/removes, but suck at
> indexing.  Are you using indexing?


No, I am not using indexing.  I will try your suggestions, and report back.


> 
> Also, for the FixedSizedQueue, you might want to consider a circular buffer,
> which is already part of the Excalibur Collection classes.
> 
> Chad
> 
> ----- Original Message -----
> From: "Berin Loritsch" <bloritsch@apache.org>
> To: <avalon-dev@jakarta.apache.org>
> Sent: Wednesday, December 19, 2001 12:04 PM
> Subject: [Report] Efficiencies of FixedSize and Default Queues
> 
> 
> 
>>My initial testing (consisting of running the TestCases several times)
>>reveals the cost of an enqueue/dequeue operation.  This consists of
>>both single element vs. multiple element enqueue/dequeue operations.
>>All calls are paired.
>>
>>The average cost of using the Default Queue is 1.156 usecs per
>>enqueue/dequeue operation.  This is pretty decent considering that the
>>Queue is ThreadSafe (i.e. locking is performed).  It uses an ArrayList
>>to perform it's duties.
>>
>>The average cost of using the Fixed Size Queue is 884.0 nsecs per
>>enqueue/dequeue operation.  This is a little over half the cost of
>>the DefaultQueue, and it is also ThreadSafe.  It directly manipulates
>>an array to perform it's duties.
>>
>>The array manipulation works like this:
>>
>>| 1 | 2 | 3 | 4 | 5 |
>>   *   *
>>   S   E
>>
>>S = Start
>>E = End
>>
>>The current figure shows a queue with 1 element enqueued.  When S=E,
>>there are no elements enqueued.  The next figure shows what happens
>>when the element is dequeued:
>>
>>| 1 | 2 | 3 | 4 | 5 |
>>       **
>>       SE
>>
>>The Start pointer moves forward when there are elements to dequeue,
>>and the End pointer moves forward when a new element is enqueued.  It
>>is also important to note that the entry where start is is nulled after
>>it is retrieved.
>>
>>The algorithm wraps the pointers back to 0 when they reach the maximum.
>>
>>This moving pointer system works quite well, and never requires useless
>>creation of objects or new queue sizes during the life of the Queue.
>>
>>--
>>
>>"They that give up essential liberty to obtain a little temporary safety
>>  deserve neither liberty nor safety."
>>                 - Benjamin Franklin
>>
>>
>>--
>>To unsubscribe, e-mail:
>>
> <mailto:avalon-dev-unsubscribe@jakarta.apache.org>
> 
>>For additional commands, e-mail:
>>
> <mailto:avalon-dev-help@jakarta.apache.org>
> 
>>
> 
> 
> --
> To unsubscribe, e-mail:   <mailto:avalon-dev-unsubscribe@jakarta.apache.org>
> For additional commands, e-mail: <mailto:avalon-dev-help@jakarta.apache.org>
> 
> .
> 
> 



-- 

"They that give up essential liberty to obtain a little temporary safety
  deserve neither liberty nor safety."
                 - Benjamin Franklin


--
To unsubscribe, e-mail:   <mailto:avalon-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:avalon-dev-help@jakarta.apache.org>


Mime
View raw message