Update: Turns out that both C# and Mono actually have the same problem as Java. I don't know C# though, so it would be great if someone reviewed the code of the benchmark (bottom of the post).

Recently I noticed that switching from HashSet to TreeSet in a Java program increased performance by several times. Since it didn't make any sense, I decided to investigate the issue, and here is what I found.

In my program I extracted an arbitrary member from a set in the following manner:

Integer elem = set.iterator().next();
set.remove(elem);

It turns out that implementation of HashSet.iterator() method in Java is poor: it always scans the bucket table from the very beginning. An excerpt from JDK code:

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

In my situation the total number of buckets was 2¹⁸, and each time a new element was extracted some part of the table had to be traversed to find the first non-empty bucket... you get the idea. As far as I understand, the implementation is the same in Java 6, 7 and 8.

I did benchmarks for C++ and C# as well.

• Visual C++ 2012, Visual C# 2012 and Mono 2.10 all have the same problem.
• g++ 4.6.3 doesn't. Looking at the code, they maintain the index of the first non-empty bucket. In certain situations (e.g. if we have a long sequence of insertions followed by a long sequence of removals) it guarantees that each bucket will be traversed only once.

The code of benchmarks is below. What puzzles me further about Java version is that if HashSet is tested after TreeSet, the performance is even worse than when tested in isolation. I'm using OpenJDK 1.7 if that matters.

import java.util.*;

public class TestSets {
    public static void main(String[] args) {
        testSet(new TreeSet<Integer>());
        testSet(new HashSet<Integer>());
    }

    static void testSet(Set<Integer> set) {
        long start = System.currentTimeMillis();

        final int N = 100000;
        for (int i = 0; i < N; ++i)
            set.add(i);
        for (int i = 0; i < N; ++i) {
            Integer elem = set.iterator().next();
            set.remove(elem);
        }

        long end = System.currentTimeMillis();
        double elapsed = (end - start) * 0.001;
        System.out.println("Elapsed time: " + elapsed + "s");
    }
}

#include <chrono>
#include <iostream>
#include <set>
#include <unordered_set>

template<typename Set>
void testSet() {
    auto start = std::chrono::system_clock::now();

    Set set;
    const int N = 600000;
    for (int i = 0; i < N; ++i)
        set.insert(i);

    for (int i = 0; i < N; ++i) {
        auto elem = *set.begin();
        set.erase(elem);
    }

    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cerr << "Elapsed time: " << elapsed_seconds.count() << "s\n";
}

int main() {
    testSet< std::set<int> >();
    testSet< std::unordered_set<int> >();
    return 0;
}

using System;
using System.Collections.Generic;

class TestSets
{
	static void testSet (ISet<int> set)
	{
		var start = System.DateTime.Now;
		
		const int N = 50000;
		for (int i = 0; i < N; ++i)
			set.Add (i);
		for (int i = 0; i < N; ++i) {
			var e = set.GetEnumerator();
			e.MoveNext();
			var elem = e.Current;
			set.Remove(elem);
		}
		
		var end = System.DateTime.Now;
		var elapsed = end - start;
		System.Console.Out.WriteLine ("Elapsed time: " + elapsed);
	}
	
	public static void Main (string[] args)
	{
		testSet (new SortedSet<int> ());
		testSet (new HashSet<int> ());
	}
}