You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@avalon.apache.org by Berin Loritsch <bl...@apache.org> on 2001/12/19 20:04:19 UTC
[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: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Berin Loritsch <bl...@apache.org>.
Chad Stansbury wrote:
> Makes sense - If your queues are exceeding 624 elements, you've got bigger
> problems to worry about.
:)
For the interested, the results for my test runs with the three list types
folow:
Test method: add to head, remove from tail
Iterations: 1,000,000
Size ArrayList LinkedList CircularBuffer
---- --------- ---------- --------------
16 540 1443 360
32 580 1402 321
64 640 1392 331
128 761 1442 340
256 1011 1392 311
512 1502 1443 310
Test method: add to tail, remove from head
Iterations: 1,000,000
Size ArrayList LinkedList CircularBuffer
---- --------- ---------- --------------
512 1482 1562 341
1024 2423 1593 340
624 1672 1512 311
What is interesting to note is that ArrayList favors adding to the tail and
removing from the head. LinkedList favors adding to the head and removing
from the tail.
It is not fair to compare CircularBuffer to the Lists because it's purpose
is different from a List. Therefore, the only method of adding and removing
is optimal to the CircularBuffer.
It is encouraging that not only does the CircularBuffer exhibit a constant
access time, but it is also far more efficient than ArrayList!
I would like to clean up the API a little bit, though with more standard
add() and remove() methods as opposed to append() and get().
--
"They that give up essential liberty to obtain a little temporary safety
deserve neither liberty nor safety."
- Benjamin Franklin
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Chad Stansbury <st...@earthlink.net>.
Makes sense - If your queues are exceeding 624 elements, you've got bigger
problems to worry about.
Chad
----- Original Message -----
From: "Berin Loritsch" <bl...@apache.org>
To: "Avalon Developers List" <av...@jakarta.apache.org>
Sent: Wednesday, December 19, 2001 1:56 PM
Subject: Re: [Report] Efficiencies of FixedSize and Default Queues
> 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.
>
>
> I ran your test, and for my machine (arguably slower) the crossover point
> was 512 elements.
>
> I then altered it to be more in line with how I was using the Lists
before:
> I added to the tail, and removed from the head.
>
> Both CircularBuffer and LinkedList exibited constant time access. The
interesting
> thing is that ArrayList is more efficient operating the way I told it to.
The
> crossover point was pushed back to somewhere around 624 elements.
>
> Armed with this knowledge, I think the CircularBuffer is the better
approach,
> and am not likely to implement a LinkedList version 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:
<ma...@jakarta.apache.org>
> For additional commands, e-mail:
<ma...@jakarta.apache.org>
>
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Berin Loritsch <bl...@apache.org>.
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.
I ran your test, and for my machine (arguably slower) the crossover point
was 512 elements.
I then altered it to be more in line with how I was using the Lists before:
I added to the tail, and removed from the head.
Both CircularBuffer and LinkedList exibited constant time access. The interesting
thing is that ArrayList is more efficient operating the way I told it to. The
crossover point was pushed back to somewhere around 624 elements.
Armed with this knowledge, I think the CircularBuffer is the better approach,
and am not likely to implement a LinkedList version 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: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Berin Loritsch <bl...@apache.org>.
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" <bl...@apache.org>
> To: "Avalon Developers List" <av...@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:
>>
> <ma...@jakarta.apache.org>
>
>>For additional commands, e-mail:
>>
> <ma...@jakarta.apache.org>
>
>>
>
>
> --
> To unsubscribe, e-mail: <ma...@jakarta.apache.org>
> For additional commands, e-mail: <ma...@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: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Chad Stansbury <st...@earthlink.net>.
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.
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" <bl...@apache.org>
To: "Avalon Developers List" <av...@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:
<ma...@jakarta.apache.org>
> For additional commands, e-mail:
<ma...@jakarta.apache.org>
>
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Berin Loritsch <bl...@apache.org>.
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: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Berin Loritsch <bl...@apache.org>.
Chad Stansbury wrote:
> I suspect you're right - the Linked List has the added expense of
> instantiating a Node for every object you add to it, so even though it's
> O(1) for adds and removes from the head and/or tail, it's got a much higher
> constant than ArrayList - which is has O(n) for adds/removes from the
> head/tail. You mentioned small queues - I suspect that once your queue size
> (n) became large enough, the LinkedList would begin winning out over the
> ArrayList...
It would be interesting to find that threshold, but it is good practice to
minimize the size of the queues if at all possible. Sometimes there are
cases that cannot be helped such as slow connections not allowing events
to be dequeued fast enough, etc. Sometimes that effect can be minimized
using concurrency.
>>Berin Loritsch wrote:
>>
>>
>>>Chad Stansbury wrote:
>>>
>>>
>>>>Also, for the FixedSizedQueue, you might want to consider a circular
>>>>buffer,
>>>>which is already part of the Excalibur Collection classes.
>>>>
>>What I have works, and I have a feeling that it will still be more
>>
> performant
>
>>than the CircularBuffer. I will throw together a CircularBuffer based
>>
> Queue
>
>>for test results though.
Test results for CircularBuffer beat out the ArrayList implementation by
the same margin that ArrayList beat out LinkedList. The average
enqueue/dequeue time is 1.05 usecs--consistently 100 nsecs less than
the ArrayList implementation.
It would be good to base the DefaultQueue on CircularBuffer as CircularBuffer
does resize itself as needed (just like ArrayList). It is not a replacement
for a FixedSizeQueue as the maximum size may change.
--
"They that give up essential liberty to obtain a little temporary safety
deserve neither liberty nor safety."
- Benjamin Franklin
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Chad Stansbury <st...@earthlink.net>.
I suspect you're right - the Linked List has the added expense of
instantiating a Node for every object you add to it, so even though it's
O(1) for adds and removes from the head and/or tail, it's got a much higher
constant than ArrayList - which is has O(n) for adds/removes from the
head/tail. You mentioned small queues - I suspect that once your queue size
(n) became large enough, the LinkedList would begin winning out over the
ArrayList...
Chad
----- Original Message -----
From: "Berin Loritsch" <bl...@apache.org>
To: "Avalon Developers List" <av...@jakarta.apache.org>
Sent: Wednesday, December 19, 2001 12:36 PM
Subject: Re: [Report] Efficiencies of FixedSize and Default Queues
> Berin Loritsch wrote:
>
> > 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.
>
>
> My initial testing reveals that for small queues where the overall size is
> fairly constant, the ArrayList wins out by 100 nsecs consistently.
>
> Run five times each, the LinkedList version was a complete second behind
the
> ArrayList version. I have a feeling this has to do with the way that
LinkedLists
> are constructed (i.e. many small objects that merely reference entries and
the
> object in question). The overhead is minor, but why incur it if you don't
> need to?
>
>
>
> >> Also, for the FixedSizedQueue, you might want to consider a circular
> >> buffer,
> >> which is already part of the Excalibur Collection classes.
>
> What I have works, and I have a feeling that it will still be more
performant
> than the CircularBuffer. I will throw together a CircularBuffer based
Queue
> for test results though.
>
> --
>
> "They that give up essential liberty to obtain a little temporary safety
> deserve neither liberty nor safety."
> - Benjamin Franklin
>
>
> --
> To unsubscribe, e-mail:
<ma...@jakarta.apache.org>
> For additional commands, e-mail:
<ma...@jakarta.apache.org>
>
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Berin Loritsch <bl...@apache.org>.
Berin Loritsch wrote:
> 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.
My initial testing reveals that for small queues where the overall size is
fairly constant, the ArrayList wins out by 100 nsecs consistently.
Run five times each, the LinkedList version was a complete second behind the
ArrayList version. I have a feeling this has to do with the way that LinkedLists
are constructed (i.e. many small objects that merely reference entries and the
object in question). The overhead is minor, but why incur it if you don't
need to?
>> Also, for the FixedSizedQueue, you might want to consider a circular
>> buffer,
>> which is already part of the Excalibur Collection classes.
What I have works, and I have a feeling that it will still be more performant
than the CircularBuffer. I will throw together a CircularBuffer based Queue
for test results though.
--
"They that give up essential liberty to obtain a little temporary safety
deserve neither liberty nor safety."
- Benjamin Franklin
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Berin Loritsch <bl...@apache.org>.
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" <bl...@apache.org>
> To: <av...@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:
>>
> <ma...@jakarta.apache.org>
>
>>For additional commands, e-mail:
>>
> <ma...@jakarta.apache.org>
>
>>
>
>
> --
> To unsubscribe, e-mail: <ma...@jakarta.apache.org>
> For additional commands, e-mail: <ma...@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: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Report] Efficiencies of FixedSize and Default Queues
Posted by Chad Stansbury <st...@earthlink.net>.
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?
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" <bl...@apache.org>
To: <av...@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:
<ma...@jakarta.apache.org>
> For additional commands, e-mail:
<ma...@jakarta.apache.org>
>
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>