Bonjour Fr�d�ric,
Thanks you for initiating this discussion.
My tests show that the in the LinkedList loop the inside of the loop is never exercised.
static double loopLinkedList() {
long before = System.currentTimeMillis();
ListIterator litcc;
for(int i = 0; i < RUN_LENGTH; i++) {
litcc = llhead;
while(litcc.hasNext()) {
tmp = (String) litcc.next(); <---- WE NEVER GET HERE
}
}
... etc
I very much doubt that any abstract data structure found in java.util.* can compete with the specialized structure we currently have for looping on filters. The current stuff is limited in functionality but highly optimized for the task.
To justify this pompous assertion, I'd like to note that in tests on my machine the current code is faster than just calling litcc.hasNext() method only *once* in the conditional of the while loop within loopLinkedList() method. I mean while the chain with the current code in the time the chained data structure completes a whole loop around the filter chain, the linked list structure is only able to invoke the hasNext() method of the iterator just once without actually looping through the elements of the data structure.
At 10:05 PM 9/27/2004, Fr�d�ric Delanoy wrote:
Hi all,
I made some tests in org.apache.log4j.performance.ListVsVector. (Whose purpose is "Compares the performance of looping through a list versus a Vector.")
You said there that "Chain looping is *20* times faster than vector access on JDK 1.1.7B on NT".
I made the same test with jdk1.4.1_01 on Windows 2000 ; it seems that Vector are "only" little more than 3 times slower.
However, the tests are not really "fair" for me cause Vector are synchronized while Chains are not.
I added some tests : I compared both initialization time and loop time for : Chain, Vector, ArrayList and LinkedList. Here are the results I got (on a PII 350):
Initialization time : similars Chain looping : 0.2654 Vector looping : 0.8733 ArrayList looping : 0.721 LinkedList looping : 0.0961
These results show that linked list looping is 2.71 times faster than chain looping. I would therefore suggest you to use linked list instead of Chains. (I attached the modified file so you can make your own tests)
What do you think about it ?
NB: FYI, I go through the list via a java.util.ListIterator
/* * Copyright (C) The Apache Software Foundation. All rights reserved. * * This software is published under the terms of the Apache Software * License version 1.1, a copy of which has been included with this * distribution in the LICENSE.txt file. */
//package org.apache.log4j.performance;
import java.util.Vector; import java.util.ArrayList; import java.util.LinkedList; import java.util.ListIterator; /**
Compares the performance of looping through a list versus a Vector.
Chain looping is *20* times faster than vector access on JDK 1.1.7B on NT
*/ public class ListVsVector {
static int RUN_LENGTH = 10000000; static Vector v = new Vector(); static ArrayList al = new ArrayList(); static LinkedList ll, ll2, ll3, head3; static ListIterator litcc, llhead; static Chain head; static String tmp;
static public void main(String[] args) {
double t; long before;
before = System.currentTimeMillis(); v.addElement("aaa"); v.addElement("bbb"); v.addElement("ccc"); v.addElement("ddd"); v.addElement("eee"); t=(System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; System.out.println("Initializing the vector took "+t);
before = System.currentTimeMillis(); al.add("aaa"); al.add("bbb"); al.add("ccc"); al.add("ddd"); al.add("eee"); t=(System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; System.out.println("Initializing the array list took "+t);
before = System.currentTimeMillis(); ll = new LinkedList(); litcc = ll.listIterator(0); llhead = litcc; litcc.add("aaa"); litcc.add("bbb"); litcc.add("ccc"); litcc.add("ddd"); litcc.add("eee"); t=(System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; System.out.println("Initializing the linked list took "+t);
ll2 = new LinkedList(); ll2.add("aaa"); ll2.add("bbb"); ll2.add("ccc"); ll2.add("ddd"); ll2.add("eee");
ll3 = (LinkedList) ll2.clone(); head3 = ll3;
before = System.currentTimeMillis(); Chain c = new Chain("aaa"); head = c; c.next = new Chain("bbb"); c = c.next; c.next = new Chain("ccc"); c = c.next; c.next = new Chain("ddd"); c = c.next; c.next = new Chain("eee"); t=(System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; System.out.println("Initializing the chain took "+t);
t = loopChain(); System.out.println("Looping through the chain took " + t);
t = loopVector(); System.out.println("Looping through the vector took " + t);
t = loopArrayList(); System.out.println("Looping through the arraylist took " + t);
t = loopLinkedList(); System.out.println("Looping through the linked list took " + t); }
static double loopChain() { long before = System.currentTimeMillis(); Chain c; for(int i = 0; i < RUN_LENGTH; i++) { c = head; while(c != null) { tmp = c.s; c = c.next; } } return (System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; }
static double loopLinkedList() { long before = System.currentTimeMillis(); ListIterator litcc; for(int i = 0; i < RUN_LENGTH; i++) { litcc = llhead; while(litcc.hasNext()) { tmp = (String) litcc.next(); } } return (System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; }
static double loopLinkedList2() { long before = System.currentTimeMillis(); for(int i = 0; i < RUN_LENGTH; i++) { int len = ll2.size(); for (int k=0; k<len; k++) { tmp = (String) ll2.get(k); } } return (System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; }
static double loopLinkedList3() { long before = System.currentTimeMillis(); LinkedList ll3; for(int i = 0; i < RUN_LENGTH; i++) { ll3 = head3; ListIterator li3 = ll3.listIterator(0); while (li3.hasNext()) { tmp = (String) li3.next(); } } return (System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; }
static double loopVector() { long before = System.currentTimeMillis(); int size = v.size(); for(int i = 0; i < RUN_LENGTH; i++) { for(int j = 0; j < size; j++) tmp = (String) v.elementAt(j); } return (System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; }
static double loopArrayList() { long before = System.currentTimeMillis(); int size = al.size(); for(int i = 0; i < RUN_LENGTH; i++) { for(int j = 0; j < size; j++) tmp = (String) al.get(j); } return (System.currentTimeMillis() - before)*1000.0/RUN_LENGTH; }
static class Chain { public String s; public Chain next;
Chain(String s) { this.s = s; }
void setNext(Chain c) { next = c; } } }
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
-- Ceki G�lc�
For log4j documentation consider "The complete log4j manual"
ISBN: 2970036908 http://www.qos.ch/shop/products/clm_t.jsp
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
