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" <[EMAIL PROTECTED]>
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:[EMAIL PROTECTED]>
For additional commands, e-mail:
<mailto:[EMAIL PROTECTED]>
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
.
--
"They that give up essential liberty to obtain a little temporary safety
deserve neither liberty nor safety."
- Benjamin Franklin
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
