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 20:29:03 GMT
Chad Stansbury wrote:

> Your results piqued my interest.  I have created a test program to determine
> at which point the linked list becomes more efficient than the array list.
> Here are my results:
> 
> List Size = 16 elements
> Iterations = 1,000,000
> ArrayList = 331 ms
> LinkedList = 761 ms
> 
> List Size = 32 elements
> Iterations = 1,000,000
> ArrayList = 391 ms
> LinkedList = 761 ms
> 
> List Size = 64 elements
> Iterations = 1,000,000
> ArrayList = 460 ms
> LinkedList = 751 ms
> 
> List Size = 128 elements
> Iterations = 1,000,000
> ArrayList = 601 ms
> LinkedList = 751 ms
> 
> List Size = 256 elements
> Iterations = 1,000,000
> ArrayList = 881 ms
> LinkedList = 761 ms
> 
> As you can see, the linked list's add/remove time remains constant, while
> the array list experiences linear degradation.  The crossover point being
> somewhare around 200 some elements.  Anyway, it was an interesting exercise.
> Below is the program I used to test this, and all results above were
> generated w/ a P4 @ 1.4GHz, 512 MB RAM.



This also applies to the CircularBuffer which is more efficient than ArrayList
implementation.  I did notice that the performance degraded when the buffer
was set with 32 elements instead of 10.  The average is at 1.09 usecs per
enqueue/dequeue operation.

I am going to replace my DefaultQueue with the CircularQueue implementation.
I may have the LinkedList implementation in the library for completeness.
Once I have the instrumentation code completed, all Queues will be instrumented.
That will help the system administrator determine when it is worth changing
queue implementations.

Concidering the relative efficiency of CircularBuffer to ArrayList, I would
be interested in finding the crossover point for CircularBuffer to LinkedList.


> 
> Chad
> 
> import java.util.*;
> 
> public class ListTest
> {
>  public static void main(String[] args)
>  {
>   int lInitialSize = Integer.parseInt(args[0]);
>   int lIterations = Integer.parseInt(args[1]);
>   ArrayList lArrayList = new ArrayList(lInitialSize + 1);
>   LinkedList lLinkedList = new LinkedList();
>   long lBegin, lEnd;
> 
>   for (int i = 0; i < lInitialSize; i++)
>   {
>    lArrayList.add(new Integer(i));
>    lLinkedList.add(new Integer(i));
>   }
> 
>   lBegin = System.currentTimeMillis();
>   for (int i = 0; i < lIterations; i++)
>   {
>    lArrayList.add(0, new Integer(i));  // Add to the head
>    lArrayList.remove(lInitialSize);  // Remove from the tail
>   }
>   lEnd = System.currentTimeMillis();
>   System.out.println("Time: " + (lEnd - lBegin));
> 
>   lBegin = System.currentTimeMillis();
>   for (int i = 0; i < lIterations; i++)
>   {
>    lLinkedList.addFirst(new Integer(i));  // Add to the head
>    lLinkedList.removeLast();  // Remove from the tail
>   }
>   lEnd = System.currentTimeMillis();
>   System.out.println("Time: " + (lEnd - lBegin));
>  }
> }
> 
> 
> 
> ----- Original Message -----
> From: "Berin Loritsch" <bloritsch@apache.org>
> To: "Avalon Developers List" <avalon-dev@jakarta.apache.org>
> Sent: Wednesday, December 19, 2001 12:37 PM
> Subject: Re: [Report] Efficiencies of FixedSize and Default Queues
> 
> 
> 
>>NOTE:
>>
>>Test environment is 750 MHz Athlon using JDK 1.3.0_02 with 256MB RAM
>>on Win2K.
>>
>>Berin Loritsch wrote:
>>
>>
>>>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