cocoon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Berin Loritsch <>
Subject [Heads Up] Utility for efficiency
Date Thu, 17 Jan 2002 21:37:17 GMT
The current version of Excalibur that is in Cocoon's CVS has new buffer classes
that are very efficient.  Many times we need to temporarily buffer objects as
a sort of queue.  When order is important, we have to use a List.  In these
applications, we do not need the indexing features of a List, and merely need
to add and remove elements to and from the buffer.

That is the purpose of the Buffer class.  The interface is:

interface Buffer
     int size();
     boolean isEmpty();

     void add(Object o);
     Object remove();

The two implementations are:


The cool thing about these buffer implementations is that they provide a constant
time for adding/removing elements in the buffer.  This is in contrast to
ArrayList whose time grows linearly with the size of the list.  Here is the output
of the ListTest class included with Excalibur's CVS:

$ java -cp build/scratchpad/ ListTest 624 1000000

Time: 1752
Time: 1593
Time: 360
Time: 291

ListTest fills the List or Buffer with 624 entries (the first parameter), and
then adds and removes 1 additional entry 1,000,000 times (the second parameter).

The output is in this order:

ArrayList, LinkedList, VariableSizeBuffer, FixedSizeBuffer

With my tests the following classes exhibit constant access time behavior: LinkedList,
VariableSizeBuffer, and FixedSizeBuffer.  ArrayList is the only one that has
a linear access time behavior.

As you can see, LinkedList is very inefficient and should never be used for small
lists.  The point where a LinkedList is more efficient than an ArrayList is different
for each machine--on mine it happened at around 624 elements.  On another machine it
happened as low as ~256 elements.

Also, the VariableSizeBuffer is a little less efficient than the FixedSizeBuffer,
but that is the price you pay to never receive a BufferOverflowException.  If
either buffer is told to remove() an object when it is empty, it will throw a

Both of those exceptions are RuntimeExceptions.  Also, the Buffers are *not*
syncrhonized or considered ThreadSafe--this is by design.  It is for the same
reasons that Java Lists are not synchronized.  It is trivial to add a wrapper
to synchronize access to the Buffer.

Have fun!


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

To unsubscribe, e-mail:
For additional commands, email:

View raw message