Comparing Collections speeds..!

The speed of different collections tends to depend on their usage pattern however it can be useful to have an idea of their relative performance.

The test:

In this test I compare both single thread and thread safe collections of different sizes.

Adding is from lowest to highest values. Removal is from start and end,
finishing with the middle value. This disadvantages ArrayList and
LinkedList relatively equally.

Collection	Size	Adding	Iterating	Removing
ArrayList	100,000	30.1	14.5	67,359
ArrayList	10,000	8.3	11.2	6,323
ArrayList	1,000	6.4	9.4	585
ArrayList	100	6.8	9.5	92.9
ArrayList	10	9.7	13.2	36.6
LinkedList	100,000	46.4	41.4	139,326
LinkedList	10,000	9.3	30.3	13,413
LinkedList	1,000	8.7	27.6	1,025
LinkedList	100	7.8	19.8	110
LinkedList	10	11.2	30.3	38.7
HashSet	100,000	28.6	115	69.5
HashSet	10,000	25.7	324	58.6
HashSet	1,000	26.0	2,521	59.2
HashSet	100	30.0	24,490	64.6
HashSet	10	51.7	244,045	131
LinkedHashSet	100,000	35.9	103	69.2
LinkedHashSet	10,000	30.3	101	65.0
LinkedHashSet	1,000	29.2	100	65.8
LinkedHashSet	100	31.5	98.8	60.6
LinkedHashSet	10	45.4	110	69.8
TreeSet	100,000	159	106	187
TreeSet	10,000	99.6	77.6	111
TreeSet	1,000	78.5	57.5	93.7
TreeSet	100	54.0	47.9	83.7
TreeSet	10	30.2	51.0	49.4
newSetFromMap IdentityHashMap	100,000	74.1	216	153
newSetFromMap IdentityHashMap	10,000	65.5	370	126
newSetFromMap IdentityHashMap	1,000	60.4	1,644	115
newSetFromMap IdentityHashMap	100	21.1	14,216	48.9
newSetFromMap IdentityHashMap	10	46.7	140,162	109
newSetFromMap WeakHashMap	100,000	52.4	148	87.4
newSetFromMap WeakHashMap	10,000	33.5	217	71.2
newSetFromMap WeakHashMap	1,000	32.9	1,088	72.2
newSetFromMap WeakHashMap	100	32.1	9,717	64.3
newSetFromMap WeakHashMap	10	48.0	98,769	93.0
Thread Safe Collections
synchronized ArrayList	100,000	22.6	101	98,735
synchronized ArrayList	10,000	12.1	101	10,084
synchronized ArrayList	1,000	11.5	99.5	1,023
synchronized ArrayList	100	11.4	101	144
synchronized ArrayList	10	14.0	111	54.0
Vector	100,000	23.9	298	64,333
Vector	10,000	20.4	372	5,919
Vector	1,000	19.4	372	612
Vector	100	19.3	375	145
Vector	10	22.9	397	97.5
synchronized LinkedList	100,000	37.6	100	132,660
synchronized LinkedList	10,000	19.2	99.6	13,049
synchronized LinkedList	1,000	22.2	99.1	1,005
synchronized LinkedList	100	23.7	102	134
synchronized LinkedList	10	26.1	115	62.6
synchronized HashSet	100,000	50.1	138	95.7
synchronized HashSet	10,000	43.0	347	93.1
synchronized HashSet	1,000	42.7	2,555	95.3
synchronized HashSet	100	47.0	24,608	97.4
synchronized HashSet	10	85.7	245,343	204
synchronized LinkedHashSet	100,000	48.6	103	93.1
synchronized LinkedHashSet	10,000	45.6	101	88.1
synchronized LinkedHashSet	1,000	48.7	106	94.6
synchronized LinkedHashSet	100	48.1	101	86.8
synchronized LinkedHashSet	10	57.8	114	93.4
synchronized TreeSet	100,000	116	105	179
synchronized TreeSet	10,000	74.1	75.4	122
synchronized TreeSet	1,000	63.5	53.9	103
synchronized TreeSet	100	50.8	46.2	90.4
synchronized TreeSet	10	29.1	49.1	57.6
CopyOnWriteArrayList	100,000	35,354	65.8	165,197
CopyOnWriteArrayList	10,000	2,115	97.7	36,269
CopyOnWriteArrayList	1,000	217	75.1	1,828
CopyOnWriteArrayList	100	60.0	63.4	227
CopyOnWriteArrayList	10	48.2	71.0	103
CopyOnWriteArraySet	100,000	106,116	63.3	165,708
CopyOnWriteArraySet	10,000	28,736	91.2	29,820
CopyOnWriteArraySet	1,000	1,143	75.1	1,852
CopyOnWriteArraySet	100	134	63.4	233
CopyOnWriteArraySet	10	55.3	73.0	109
newSetFromMap ConcurrentHashMap	100,000	70.6	291	149
newSetFromMap ConcurrentHashMap	10,000	57.2	485	120
newSetFromMap ConcurrentHashMap	1,000	53.4	2,869	121
newSetFromMap ConcurrentHashMap	100	54.7	24,150	140
newSetFromMap ConcurrentHashMap	10	68.7	93,921	197
newSetFromMap ConcurrentSkipListMap	100,000	135	96.8	365
newSetFromMap ConcurrentSkipListMap	10,000	113	95.1	285
newSetFromMap ConcurrentSkipListMap	1,000	97.8	94.7	234
newSetFromMap ConcurrentSkipListMap	100	83.3	95.2	192
newSetFromMap ConcurrentSkipListMap	10	64.2	112	151

THe code that performs the above given test:

/*
 * MailTodoNew - AddIterateRemoveTest.java, Aug 9, 2011 5:23:37 PM
 *
 * Copyright 2011 MindTree Ltd, Inc. All rights reserved.
 * MindTree proprietary/confidential. Use is subject to license terms.
 */
package com.mt.util.testing;

import org.junit.Test;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CopyOnWriteArraySet;

/**
 * The Class AddIterateRemoveTest.
 *
 * @author Karthikeyan V. Reddy
 * @version 1.0
 */
public class AddIterateRemoveTest
{
   
    /** The Constant RUNS_TIME_MS. */
    static final int RUNS_TIME_MS = 10 * 1000;
   
    /** The Constant LARGEST_SIZE. */
    static final int LARGEST_SIZE = 100 * 1000;
   
    /** The Constant INTS. */
    static final int[] INTS = new int[LARGEST_SIZE];
   
    static
    {
        for (int i = 0; i < LARGEST_SIZE; i++)
            INTS[i] = i;
    }
   
    /**
     * Performance test.
     */
    @Test
    public void performanceTest()
    {
        test(new TreeSet<Integer>());
        test(Collections.synchronizedSortedSet(new TreeSet<Integer>()), "synchronized TreeSet");
        test(new ArrayList<Integer>());
        test(new LinkedList<Integer>());
        test(new HashSet<Integer>());
        test(new LinkedHashSet<Integer>());
        test(Collections.newSetFromMap(new IdentityHashMap<Integer, Boolean>()), "newSetFromMap IdentityHashMap");
        test(Collections.newSetFromMap(new WeakHashMap<Integer, Boolean>()), "newSetFromMap WeakHashMap");
       
        test(Collections.synchronizedList(new ArrayList<Integer>()), "synchronized ArrayList");
        test(new Vector<Integer>());
        test(Collections.synchronizedList(new LinkedList<Integer>()), "synchronized LinkedList");
        test(Collections.synchronizedSet(new HashSet<Integer>()), "synchronized HashSet");
        test(Collections.synchronizedSet(new LinkedHashSet<Integer>()), "synchronized LinkedHashSet");
        test(new CopyOnWriteArrayList<Integer>());
        test(new CopyOnWriteArraySet<Integer>());
        test(Collections.newSetFromMap(new ConcurrentHashMap<Integer, Boolean>()), "newSetFromMap ConcurrentHashMap");
        test(Collections.newSetFromMap(new ConcurrentSkipListMap<Integer, Boolean>()),
                "newSetFromMap ConcurrentSkipListMap");
    }
   
    /**
     * Test.
     *
     * @param ints
     *            the ints
     */
    private void test(Collection<Integer> ints)
    {
        test(ints, ints.getClass().getSimpleName());
    }
   
    /**
     * Test.
     *
     * @param ints
     *            the ints
     * @param collectionName
     *            the collection name
     */
    private void test(Collection<Integer> ints, String collectionName)
    {
        for (int size = LARGEST_SIZE; size >= 10; size /= 10)
        {
            long adding = 0;
            long removing = 0;
            long iterating = 0;
           
            int runs = 0;
            long endTime = System.currentTimeMillis() + RUNS_TIME_MS;
            do
            {
                runs++;
                long start = System.nanoTime();
                testAdding(ints, size);
               
                adding += System.nanoTime() - start;
               
                start = System.nanoTime();
                for (int repeat = 0; repeat < 100; repeat++)
                    testIterating(ints);
                iterating += System.nanoTime() - start;
               
                start = System.nanoTime();
                testRemoving(ints, size);
                removing += (System.nanoTime() - start) * 2;
               
                ints.clear();
            } while (endTime > System.currentTimeMillis());
            System.out.println("<tr><td>" + collectionName + "</td><td aligned=\"right\">" + String.format("%,d", size)
                    + "</td><td aligned=\"right\">" + format(10 * adding / runs / size) + "</td><td aligned=\"right\">"
                    + format(iterating / runs / size) + "</td><td aligned=\"right\">"
                    + format(10 * removing / runs / size) + "</td></tr>");
        }
    }
   
    /**
     * Format.
     *
     * @param l
     *            the l
     * @return the string
     */
    private String format(long l)
    {
        return l < 1000 ? "" + (l / 10.0) : l < 10000 ? "" + l / 10 : String.format("%,d", l / 10);
    }
   
    /**
     * Test adding.
     *
     * @param ints
     *            the ints
     * @param size
     *            the size
     */
    private static void testAdding(Collection<Integer> ints, int size)
    {
        // adding
        for (int i = 0; i < size; i++)
            ints.add(INTS[i]);
    }
   
    /**
     * Test iterating.
     *
     * @param ints
     *            the ints
     * @return the long
     */
    private static long testIterating(Collection<Integer> ints)
    {
        // iterating
        long sum = 0;
        for (Integer i : ints)
            sum += i;
        return sum;
    }
   
    /**
     * Test removing.
     *
     * @param ints
     *            the ints
     * @param size
     *            the size
     */
    private void testRemoving(Collection<Integer> ints, int size)
    {
        // forward and reverse
        for (int i = 0; i < size / 2; i++)
        {
            ints.remove(INTS[i]);
            ints.remove(INTS[size - i - 1]);
        }
    }
}