This is why it takes me so long to write (or rewrite) a book. Examples like this, which I think are done, rear up and gobble lots of time. The good thing is that I end up understanding all the problems in much more depth. But it makes books -- especially one the size of Thinking in Java fourth edition -- take forever. The following was taken directly from the book:
To prevent code duplication and to provide consistency among tests, I’ve put the basic functionality of the test process into a framework. The following code establishes a base class from which you create a list of anonymous inner classes, one for each different test. Each of these inner classes is called as part of the testing process. This approach allows you to easily add and remove new kinds of tests.
//: containers/Test.java
// Framework for performing timed tests of containers.
public abstract class Test {
String name;
public Test(String name) { this.name = name; }
// Override this Template Method for different tests.
// Returns actual number of repetitions of test.
abstract int test(C container, TestParam tp);
} ///:~
Each Test object stores the name of that test. When you call the test() method, it must be given the container to be tested along with a “messenger” or “data transfer object” that holds the various parameters for that particular test. The parameters include size, indicating the number of elements in the container, and loops, which control the number of iterations for that test. These parameters may or may not be used in every test.
Each container will undergo a sequence of calls to test(), each with a different TestParam, so TestParam also contains static array() methods that make it easy to create arrays of TestParam objects. The first version of array() takes a variable argument list containing alternating size and loops values, and the second version takes the same kind of list except that the values are inside Strings—this way it can be used to parse command-line arguments:
//: containers/TestParam.java
// A "data transfer object."
import java.util.*;
public class TestParam {
public final int size;
public final int loops;
public TestParam(int size, int loops) {
this.size = size;
this.loops = loops;
}
// Create an array of TestParam from a varargs sequence:
public static TestParam[] array(int... values) {
int size = values.length/2;
TestParam[] result = new TestParam[size];
int n = 0;
for(int i = 0; i < vals =" new" i =" 0;">
To use the framework, you pass the container to be tested along with a List of Test objects to a Tester.run() method (these are overloaded generic convenience methods which reduce the amount of typing necessary to use them). Tester.run() calls the appropriate overloaded constructor, then calls timedTest(), which executes each test in the list for that container. timedTest() repeats each test for each of the TestParam objects in paramList. Because paramList is initialized from the static defaultParams array, you can change the paramList for all tests by reassigning defaultParams, or you can change the paramList for one test by passing in a custom paramList for that test:
//: containers/Tester.java
// Applies Test objects to lists of different containers.
import java.util.*;
public class Tester {
public static int fieldWidth = 8;
public static TestParam[] defaultParams= TestParam.array(
10, 5000, 100, 5000, 1000, 5000, 10000, 500);
// Override this to modify pre-test initialization:
protected C initialize(int size) { return container; }
protected C container;
private String headline = "";
private List<> tests;
private static String stringField() {
return "%" + fieldWidth + "s";
}
private static String numberField() {
return "%" + fieldWidth + "d";
}
private static int sizeWidth = 5;
private static String sizeField = "%" + sizeWidth + "s";
private TestParam[] paramList = defaultParams;
public Tester(C container, List<> tests) {
this.container = container;
this.tests = tests;
if(container != null)
headline = container.getClass().getSimpleName();
}
public Tester(C container, List<> tests,
TestParam[] paramList) {
this(container, tests);
this.paramList = paramList;
}
public void setHeadline(String newHeadline) {
headline = newHeadline;
}
// Generic methods for convenience :
public static void run(C cntnr, List<> tests){
new Tester(cntnr, tests).timedTest();
}
public static void run(C cntnr,
List<> tests, TestParam[] paramList) {
new Tester(cntnr, tests, paramList).timedTest();
}
private void displayHeader() {
// Calculate width and pad with '-':
int width = fieldWidth * tests.size() + sizeWidth;
int dashLength = width - headline.length() - 1;
StringBuilder head = new StringBuilder(width);
for(int i = 0; i < i =" 0;"> test : tests) {
C kontainer = initialize(param.size);
long start = System.nanoTime();
// Call the template method:
int reps = test.test(kontainer, param);
long duration = System.nanoTime() - start;
long timePerRep = duration / reps; // Nanoseconds
System.out.format(numberField(), timePerRep);
}
System.out.println();
}
}
} ///:~
The stringField() and numberField() methods produce formatting strings for outputting the results. The standard width for formatting can be changed by modifying the static fieldWidth value. The displayHeader() method formats and prints the header information for each test.
If you need to perform special initialization, override the initialize( ) method. This produces an initialized container object of the appropriate size—you can either modify the existing container object or create a new one. You can see in test( ) that the result is captured in a local reference called kontainer, which allows you to replace the stored member container with a completely different initialized container.
The return value of each Test.test() method must be the number of operations performed by that test, which is used to calculate the number of nanoseconds required for each operation. You should be aware that System.nanoTime() typically produces values with a granularity that is greater than one (and this granularity will vary with machines and operating systems), and this will produce a certain amount of rattle in the results.
The results may vary from machine to machine; these tests are only intended to compare the performance of the different containers.
Here is a performance test for the most essential of the List operations. For comparison, it also shows the most important Queue operations. Two separate lists of tests are created for testing each class of container. In this case, Queue operations only apply to LinkedLists.
//: containers/ListPerformance.java
// Demonstrates performance differences in Lists.
// {Args: 100 500} Small to keep build testing short
import java.util.*;
import net.mindview.util.*;
public class ListPerformance {
static Random rand = new Random();
static int reps = 1000;
static List>> tests =
new ArrayList>>();
static List>> qTests =
new ArrayList>>();
static {
tests.add(new Test>("add") {
int test(List list, TestParam tp) {
int loops = tp.loops;
int listSize = tp.size;
for(int i = 0; i < j =" 0;">>("get") {
int test(List list, TestParam tp) {
int loops = tp.loops * reps;
int listSize = list.size();
for(int i = 0; i <>>("set") {
int test(List list, TestParam tp) {
int loops = tp.loops * reps;
int listSize = list.size();
for(int i = 0; i <>>("iteradd") {
int test(List list, TestParam tp) {
final int LOOPS = 1000000;
int half = list.size() / 2;
ListIterator it = list.listIterator(half);
for(int i = 0; i <>>("insert") {
int test(List list, TestParam tp) {
int loops = tp.loops;
for(int i = 0; i <>>("remove") {
int test(List list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i <> 5)
list.remove(5); // Minimize random access cost
}
return loops * size;
}
});
// Tests for queue behavior:
qTests.add(new Test>("addFirst") {
int test(LinkedList list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < j =" 0;">>("addLast") {
int test(LinkedList list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < j =" 0;">>("rmFirst") {
int test(LinkedList list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i <> 0)
list.removeFirst();
}
return loops * size;
}
});
qTests.add(new Test>("rmLast") {
int test(LinkedList list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i <> 0)
list.removeLast();
}
return loops * size;
}
});
}
static class ListTester extends Tester> {
public ListTester(List container,
List>> tests) {
super(container, tests);
}
// Fill to the appropriate size before each test:
@Override protected List initialize(int size){
container.clear();
container.addAll(new CountingIntegerList(size));
return container;
}
// Convenience method:
public static void run(List list,
List>> tests) {
new ListTester(list, tests).timedTest();
}
}
public static void main(String[] args) {
if(args.length > 0)
Tester.defaultParams = TestParam.array(args);
// Can only do these two tests on an array:
Tester> arrayTest =
new Tester>(null, tests.subList(1, 3)){
// This will be called before each test. It
// produces a non-resizeable array-backed list:
@Override protected
List initialize(int size) {
Integer[] ia = Generated.array(Integer.class,
new CountingGenerator.Integer(), size);
return Arrays.asList(ia);
}
};
arrayTest.setHeadline("Array as List");
arrayTest.timedTest();
Tester.defaultParams= TestParam.array(
10, 5000, 100, 5000, 1000, 1000, 10000, 200);
ListTester.run(new ArrayList(), tests);
ListTester.run(new LinkedList(), tests);
ListTester.run(new Vector(), tests);
Tester.fieldWidth = 12;
Tester> qTest =
new Tester>(
new LinkedList(), qTests);
qTest.setHeadline("Queue tests");
qTest.timedTest();
}
} /* Output: (Sample)
--- Array as List ---
size get set
10 130 183
100 130 164
1000 129 165
10000 129 165
--------------------- ArrayList ---------------------
size add get set iteradd insert remove
10 121 139 191 435 3952 446
100 72 141 191 247 3934 296
1000 98 141 194 839 2202 923
10000 122 144 190 6880 14042 7333
--------------------- LinkedList ---------------------
size add get set iteradd insert remove
10 182 164 198 658 366 262
100 106 202 230 457 108 201
1000 133 1289 1353 430 136 239
10000 172 13648 13187 435 255 239
----------------------- Vector -----------------------
size add get set iteradd insert remove
10 129 145 187 290 3635 253
100 72 144 190 263 3691 292
1000 99 145 193 846 2162 927
10000 108 145 186 6871 14730 7135
-------------------- Queue tests --------------------
size addFirst addLast rmFirst rmLast
10 199 163 251 253
100 98 92 180 179
1000 99 93 216 212
10000 111 109 262 384
*///:~
Each test requires careful thought to ensure that you are producing meaningful results. For example, the “add” test clears the List and then refills it to the specified list size. The call to clear() is thus part of the test, and may have an impact on the time, especially for small tests. Although the results here seem fairly reasonable, you could imagine rewriting the test framework so that there is a call to a preparation method (which would, in this case, include the clear() call) outside of the timing loop.
Note that for each test, you must accurately calculate the number of operations that occur and return that value from test(), so the timing is correct.
The “get” and “set” tests both use the random number generator to perform random accesses to the List. In the output, you can see that, for a List backed by an array and for an ArrayList, these accesses are fast and very consistent regardless of the list size, whereas for a LinkedList the access times grow very significantly for larger lists. Clearly, linked lists are not a good choice if you will be performing many random accesses.
The “iteradd” test uses an iterator in the middle of the list to insert new elements. For an ArrayList this gets expensive as the list gets bigger, but for a LinkedList it is relatively cheap, and constant regardless of size. This makes sense because an ArrayList must create space and copy all its references forward during an insertion. This becomes expensive as the ArrayList gets bigger. A LinkedList only needs to link in a new element, and doesn’t have to modify the rest of the list, so you expect the cost to be roughly the same regardless of the list size.
The “insert” and “remove” tests both use location number 5 as the point of insertion or removal, rather than either end of the List. A LinkedList treats the end points of the List specially—this improves the speed when using a LinkedList as a Queue. However, if you add or remove elements in the middle of the list, you include the cost of random access, which we’ve already seen varies with the different List implementations. By performing the insertions and removals at location five, the cost of the random access should be negligible and we should see only the cost of insertion and removal, but we will not see any specialized optimization for the end of a LinkedList. You can see from the output that the cost of insertion and removal in a LinkedList is quite cheap and doesn’t vary with the list size, but with an ArrayList, insertions especially are very expensive, and the cost increases with list size.
From the Queue tests, you can see how quickly a LinkedList can insert and remove elements from the endpoints of the list, which is optimal for Queue behavior.
Normally, you can just call Tester.run(), passing the container and the tests list. Here, however, we must override the initialize() method so that the List is cleared and refilled before each test—otherwise the List control over the size of the List would be lost during the various tests. ListTester inherits from Tester and performs this initialization using CountingIntegerList. The run() convenience method is also overridden.
We’d also like to compare array access to container access (primarily against ArrayList). In the first test in main(), a special Test object is created using an anonymous inner class. The initialize() method is overridden to create a new object each time it is called (ignoring the stored container object, so null is the container argument for this Tester constructor). The new object is created using Generated.array( ) (which was defined in the Arrays chapter) and Arrays.asList(). Only two of the tests can be performed in this case, because you cannot insert or remove elements when using a List backed by an array, so the List.subList() method is used to select the desired tests from the tests list.
For random-access get( ) and set( ) operations, a List backed by an array is slightly faster than an ArrayList, but the same operations are dramatically more expensive for a LinkedList because it is not designed for random-access operations.
Vector should be avoided; it’s only in the library for legacy code support (the only reason it works in this program is because it was adapted to be a List for forward compatibility).
The best approach is probably to choose an ArrayList as your default and to change to a LinkedList if you need its extra functionality or you discover performance problems due to many insertions and removals from the middle of the list. If you are working with a fixed-sized group of elements, either use a List backed by an array (as produced by Arrays.asList( )), or if necessary, an actual array.
CopyOnWriteArrayList is a special implementation of List used in concurrent programming, and will be discussed in the Concurrency chapter.
Depending on the behavior you desire, you can choose a TreeSet, a HashSet, or a LinkedHashSet. The following test program gives an indication of the performance trade-off between these implementations:
//: containers/SetPerformance.java
// Demonstrates performance differences in Sets.
// {Args: 100 5000} Small to keep build testing short
import java.util.*;
public class SetPerformance {
static List>> tests =
new ArrayList>>();
static {
tests.add(new Test>("add") {
int test(Set set, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < j =" 0;">>("contains") {
int test(Set set, TestParam tp) {
int loops = tp.loops;
int span = tp.size * 2;
for(int i = 0; i < j =" 0;">>("iterate") {
int test(Set set, TestParam tp) {
int loops = tp.loops * 10;
for(int i = 0; i <> it = set.iterator();
while(it.hasNext())
it.next();
}
return loops * set.size();
}
});
}
public static void main(String[] args) {
if(args.length > 0)
Tester.defaultParams = TestParam.array(args);
Tester.fieldWidth = 10;
Tester.run(new TreeSet(), tests);
Tester.run(new HashSet(), tests);
Tester.run(new LinkedHashSet(), tests);
}
} /* Output: (Sample)
------------- TreeSet -------------
size add contains iterate
10 746 173 89
100 501 264 68
1000 714 410 69
10000 1975 552 69
------------- HashSet -------------
size add contains iterate
10 308 91 94
100 178 75 73
1000 216 110 72
10000 711 215 100
---------- LinkedHashSet ----------
size add contains iterate
10 350 65 83
100 270 74 55
1000 303 111 54
10000 1615 256 58
*///:~
The performance of HashSet is generally superior to TreeSet, but especially when adding elements and looking them up, which are the two most important operations. TreeSet exists because it maintains its elements in sorted order, so you use it only when you need a sorted Set. Because of the internal structure necessary to support sorting and because iteration is something you’re more likely to do, iteration is usually faster with a TreeSet than a HashSet.
Note that LinkedHashSet is more expensive for insertions than HashSet; this is because of the extra cost of maintaining the linked list along with the hashed container.
This program gives an indication of the trade-off between Map implementations:
//: containers/MapPerformance.java
// Demonstrates performance differences in Maps.
// {Args: 100 5000} Small to keep build testing short
import java.util.*;
public class MapPerformance {
static List
Insertions for all the Map implementations except for IdentityHashMap get significantly slower as the size of the Map gets large. In general, however, lookup is much cheaper than insertion, which is good because you’ll typically be looking items up much more often than you insert them.
Hashtable performance is roughly the same as HashMap. Since HashMap is intended to replace Hashtable, and thus uses the same underlying storage and lookup mechanism (which you will learn about later) this is not too surprising.
A TreeMap is generally slower than a HashMap. As with TreeSet, a TreeMap is a way to create an ordered list. The behavior of a tree is such that it’s always in order and doesn’t have to be specially sorted. Once you fill a TreeMap, you can call keySet( ) to get a Set view of the keys, then toArray( ) to produce an array of those keys. You can then use the static method Arrays.binarySearch( ) to rapidly find objects in your sorted array. Of course, this only makes sense if the behavior of a HashMap is unacceptable, since HashMap is designed to rapidly find keys. Also, you can easily create a HashMap from a TreeMap with a single object creation or call to putAll(). In the end, when you’re using a Map, your first choice should be HashMap, and only if you need a constantly sorted Map will you need TreeMap.
LinkedHashMap tends to be slower than HashMap for insertions because it maintains the linked list (to preserve insertion order) in addition to the hashed data structure. Because of this list, iteration is faster.
IdentityHashMap has different performance because it uses == rather than equals( ) for comparisons. WeakHashMap is described later in this chapter.
