cocoon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Berin Loritsch <blorit...@apache.org>
Subject Re: [Heads Up] Utility for efficiency
Date Fri, 18 Jan 2002 15:00:51 GMT
Piroumian, Konstantin wrote:

> Sylvain, Berin,
> 
> you are very convincing ;)
> I told that only because just yesterday have read about it in Bruce Eckel's
> "Thinking in Java 2nd Edition" (Appendix C, Implementation section, 14). It
> sounds something like (have read it in Russian and will try to translate it
> back to English):
> 
> 14. ...
> <quot>
> Use containers from standart Java libs. Becoming more professional in
> container usage, you will also improve your perfomance. Prefer to use
> ArrayList for sequences, HashSet for sets, HashMap for associated arrays and
> LinkedList for stacks (instead of Stack) and queries.
> </quot>



You know what, I created my simple test, and found out something very interesting!

For stack operations (add last/remove last), the performance times of the
Lists are _very_ different!

Here are the results form running the following command line:

$java -cp ./build/scratchpad StackTest 123456 1000000

Time: 260
Time: 381
Time: 381
Time: 290


Where the stacks were populated with 123,456 items (much more than the buffers),
and the push/pop (or equivalent) operations were performed 1,000,000 times.  The
order of the results are ArrayList, LinkedList, Stack, ArrayStack.

The interesting thing to note is that *all* collections performed with constant
access time heuristics.  It didn't matter whether there was 624 items or 123,456
items in the stack--with 1,000,000 iterations it performed the same.

What is particularly interesting to note is that there is no real advantage of
using LinkedList over Stack with JDK 1.3 on windows.  In fact you lose synchronization,
but gain no time.  ArrayStack beat both LinkedList and Stack as was expected.
However, what I didn't expect was for ArrayList to beat everything!

While the actual times will vary accross machines, the relative speed of these
approaches is the same.

The final verdict:

Use ArrayList for Stack operations (by simply using add() and remove(lastindex)).
Use FixedSizeBuffer for FIFO buffer operations if you know the max size--otherwise
use VariableSizeBuffer.


BTW, here is the source code for StackTest:

--------------------------------------------------------------------------------
import java.util.*;
import org.apache.avalon.excalibur.collections.ArrayStack;

public class StackTest
{
  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();
   Stack lStack = new Stack();
   ArrayStack lArrayStack = new ArrayStack();
   long lBegin, lEnd;

   for (int i = 0; i < lInitialSize; i++)
   {
    lArrayList.add(new Integer(i));
    lLinkedList.add(new Integer(i));
    lStack.push(new Integer(i));
    lArrayStack.push(new Integer(i));
   }

   lBegin = System.currentTimeMillis();
   for (int i = 0; i < lIterations; i++)
   {
    lArrayList.add(new Integer(i));  // Add to the tail
    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.addLast(new Integer(i));  // Add to the tail
    lLinkedList.removeLast();  // Remove from the tail
   }
   lEnd = System.currentTimeMillis();
   System.out.println("Time: " + (lEnd - lBegin));

   lBegin = System.currentTimeMillis();
   for (int i = 0; i < lIterations; i++)
   {
    lStack.push( new Integer(i) );
    lStack.pop();  // Remove from the tail
   }
   lEnd = System.currentTimeMillis();
   System.out.println("Time: " + (lEnd - lBegin));

   lBegin = System.currentTimeMillis();
   for (int i = 0; i < lIterations; i++)
   {
    lArrayStack.push( new Integer(i) );
    lArrayStack.pop();
   }
   lEnd = System.currentTimeMillis();
   System.out.println("Time: " + (lEnd - lBegin));
  }
}
---------------------------------------------------------------------




-- 

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


---------------------------------------------------------------------
To unsubscribe, e-mail: cocoon-dev-unsubscribe@xml.apache.org
For additional commands, email: cocoon-dev-help@xml.apache.org


Mime
View raw message