map performance

Nate · October 21, 2009, 5:32am

Edit: Latest source from later in the thread: http://n4te.com/temp/fast.7z

For kicks I benchmarked some map implementations on Android (G1):

http://chart.apis.google.com/chart?chtt=Get, Android&chs=700x327&chd=t:183105,244140,335693,396728,396728,427246,457763,610351,1617432,1678466,1708984,1739502,1770019,1831054,2014160,2288818,2532959&chds=0,2532959&chxl=0:|FastHashMap, Commons Collections|Hashtable, Java|FastMap, Javolution|HashMap, Java|IdentityMap, Commons Collections|THashMap, Trove|OpenIntObjectHashMap, Cern Cole|HashedMap, Commons Collections|CachingHashMap, JL235|IdentityHashMap, Java|TIntObjectHashMap, Trove|HashMapV2, Doug Lea|CachingFastMap, Nate|FastMap, Nate|FastIdentityMap, Nate|ApacheIntHashMap, Commons Lang|FastIntMap, Nate&cht=bhg&chbh=10&chxt=y&chco=660000|660033|660066|660099|6600CC|6600FF|663300|663333|663366|663399|6633CC|6633FF|666600|666633|666666

http://chart.apis.google.com/chart?chtt=Put, Android&chs=700x327&chd=t:1892090,1922608,2105713,2929687,2929687,2990723,3112793,3234863,3295899,3356933,3417968,3631592,3784179,4058838,4058838,4211426,4547119&chds=0,4547119&chxl=0:|Hashtable, Java|FastHashMap, Commons Collections|IdentityMap, Commons Collections|OpenIntObjectHashMap, Cern Cole|HashedMap, Commons Collections|HashMap, Java|FastMap, Nate|FastIdentityMap, Nate|ApacheIntHashMap, Commons Lang|FastMap, Javolution|FastIntMap, Nate|THashMap, Trove|CachingHashMap, JL235|IdentityHashMap, Java|HashMapV2, Doug Lea|TIntObjectHashMap, Trove|CachingFastMap, Nate&cht=bhg&chbh=10&chxt=y&chco=660000|660033|660066|660099|6600CC|6600FF|663300|663333|663366|663399|6633CC|6633FF|666600|666633|666666

http://chart.apis.google.com/chart?chtt=Total, Android&chs=700x327&chd=t:2288818,2380371,2532959,3295898,3540038,3540039,3692626,3814696,4547119,4730225,5249023,5462645,5462646,5767822,5828857,6744385,6835937&chds=0,6835937&chxl=0:|Hashtable, Java|FastHashMap, Commons Collections|IdentityMap, Commons Collections|OpenIntObjectHashMap, Cern Cole|HashMap, Java|HashedMap, Commons Collections|FastMap, Javolution|THashMap, Trove|CachingHashMap, JL235|FastMap, Nate|FastIdentityMap, Nate|ApacheIntHashMap, Commons Lang|IdentityHashMap, Java|FastIntMap, Nate|HashMapV2, Doug Lea|TIntObjectHashMap, Trove|CachingFastMap, Nate&cht=bhg&chbh=10&chxt=y&chco=660000|660033|660066|660099|6600CC|6600FF|663300|663333|663366|663399|6633CC|6633FF|666600|666633|666666

Android couldn’t run fastutil (too many classes in the JAR!) or alex14n’s FastHashMap (uses 1.6 methods and I’m too lazy to update it).

CachingHashMap is JL235’s class:
http://kenai.com/projects/sf-library/sources/sf/content/SF/src/com/studiofortress/sf/util/collections/CachingHashMap.java?rev=3
I thought it would be faster the second time (same map is used, just clear’ed) since the entry objects are reused, but the caching overhead came out the same as creating new objects. Of course GC is avoided.

The IntHashMap is this class:
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-common/src/com/esotericsoftware/skorpios/util/IntHashMap.java
The FastIdentityHashMap and FastObjectHashMap are the same code as IntHashMap, tweaked a little.

HashMapV2 is from here:
http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-June/001961.html

Would love if you guys can catch me doing anything stupid or have other ideas on fast/efficient maps.

jezek2 · October 21, 2009, 7:09am

Try GNU Trove, it has faster hashmaps, supports primitive types and it doesn’t need to allocate Entry objects when traversing the map. Also you can adapt their benchmark code to other collections you’re testing.

Nate · October 21, 2009, 10:02am

Updated first post with pretty charts and included Trove and some others.

Benchmark code:


import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Random;
import java.util.Map.Entry;

import javolution.util.FastMap;

import org.apache.commons.collections.map.HashedMap;
import org.apache.commons.collections.map.IdentityMap;

import cern.colt.map.OpenIntObjectHashMap;
import gnu.trove.map.hash.THashMap;
import gnu.trove.map.hash.TIntObjectHashMap;

public class MapTest {
	static int count = 1000000;
	static Integer[] randomInteger = new Integer[count];
	static int[] randomInt = new int[count];
	static boolean warmup = true;
	static HashMap<String, Long> testTimes = new HashMap();
	static ArrayList<Test> tests = new ArrayList();

	public static void main (String[] args) throws Exception {
		Random r = new Random();
		for (int i = 0; i < count; i++) {
			int value = -1;
			while (value == -1)
				value = r.nextInt();
			randomInt[i] = value;
			randomInteger[i] = value;
		}

		addTest("Java", new HashMapTest());
		addTest("Java", new IdentityHashMapTest());
		addTest("Javolution", new FastMapTest());
		addTest("JL235", new CachingHashMapTest());
		addTest("Nate", new FastObjectHashMapTest());
		addTest("Nate", new FastIdentityHashMapTest());
		addTest("Nate", new IntHashMapTest());
		addTest("Trove", new THashMapTest());
		addTest("Trove", new TIntObjectHashMapTest());
		addTest("Cern Cole", new OpenIntObjectHashMapTest());
		addTest("Commons Collections", new HashedMapTest());
		addTest("Commons Collections", new IdentityMapTest());
		addTest("Commons Lang", new ApacheIntHashMapTest());

		for (Test runnable : tests)
			for (int i = 0; i < 5; i++)
				runnable.run();
		warmup = false;

		for (Test runnable : tests) {
			for (int i = 0; i < 3; i++) {
				runnable.run();
			}
			System.out.println();
		}

		ArrayList<Entry> list = new ArrayList(testTimes.entrySet());
		Collections.sort(list, new Comparator<Entry>() {
			public int compare (Entry o1, Entry o2) {
				return (int)((Long)o1.getValue() - (Long)o2.getValue());
			}
		});
		chart("Get", list, " get");
		chart("Put", list, " put");

		HashMap totalTimes = new HashMap();
		for (String name : testTimes.keySet()) {
			name = name.replace(" get", "").replace(" put", "");
			long sum = 0;
			for (String name2 : testTimes.keySet())
				if (name2.equals(name + " get") || name2.equals(name + " put")) sum += testTimes.get(name2);
			totalTimes.put(name, sum);
		}
		list = new ArrayList(totalTimes.entrySet());
		Collections.sort(list, new Comparator<Entry>() {
			public int compare (Entry o1, Entry o2) {
				return (int)((Long)o1.getValue() - (Long)o2.getValue());
			}
		});
		chart("Get+Put", list, "");
	}

	static void addTest (String name, Test test) {
		test.name = test.getClass().getSimpleName().replace("Test", "") + ", " + name;
		tests.add(test);
	}

	static void chart (String title, ArrayList<Entry> list, String suffix) {
		StringBuilder names = new StringBuilder(512);
		StringBuilder times = new StringBuilder(512);
		long max = 0;
		int count = 0;
		for (Entry<String, Long> entry : list) {
			String name = entry.getKey();
			if (!name.endsWith(suffix)) continue;
			names.insert(0, '|');
			names.insert(0, name.substring(0, name.length() - suffix.length()));
			long time = entry.getValue();
			times.append(time);
			times.append(',');
			max = Math.max(max, time);
			count++;
		}
		times.setLength(times.length() - 1);
		names.setLength(names.length() - 1);
		int height = (count + 1) * 18;
		int width = Math.min(700, 300000 / height);
		System.out.println("http://chart.apis.google.com/chart?chtt=" + title + ", Desktop&" + "chs=" + width + "x" + height
			+ "&chd=t:" + times + "&chds=0," + max + "&chxl=0:|" + names + "&cht=bhg&chbh=10&chxt=y");
	}

	static void gc () {
		if (warmup) return;
		System.gc();
		System.gc();
		try {
			Thread.sleep(50);
		} catch (InterruptedException ignored) {
		}
		System.gc();
		System.gc();
	}

	static abstract class Test implements Runnable {
		String name;
		long s;
		Object someValue = new Object();

		void start () {
			s = System.nanoTime();
		}

		void end (String suffix) {
			if (warmup) return;
			long e = System.nanoTime();
			long time = e - s;
			Long oldTime = testTimes.get(name + " " + suffix);
			if (oldTime == null || time < oldTime) testTimes.put(name + " " + suffix, time);
			System.out.println(name + " " + suffix + ": " + time / 1000000f + " ms");
		}
	}

	static class HashMapTest extends Test {
		HashMap map = new HashMap(count * 2);

		public void run () {
			Object someValue = this.someValue;
			HashMap map = this.map;
			map.clear();
			Integer[] randomInteger = MapTest.randomInteger;
			int count = MapTest.count;
			gc();

			start();
			for (int i = 0; i < count; i++)
				map.put(randomInteger[i], someValue);
			end("put");

			start();
			for (int i = 0; i < count; i++)
				map.get(randomInteger[i]);
			end("get");
		}
	}

	static class FastMapTest extends Test {
		FastMap map = new FastMap(count * 2);

		public void run () {
			Object someValue = this.someValue;
			FastMap map = this.map;
			map.clear();
			Integer[] randomInteger = MapTest.randomInteger;
			int count = MapTest.count;
			gc();

			start();
			for (int i = 0; i < count; i++)
				map.put(randomInteger[i], someValue);
			end("put");

			start();
			for (int i = 0; i < count; i++)
				map.get(randomInteger[i]);
			end("get");
		}
	}

	static class IntHashMapTest extends Test {
		IntHashMap map = new IntHashMap(count * 2);

		public void run () {
			Object someValue = this.someValue;
			IntHashMap map = this.map;
			map.clear();
			Integer[] randomInteger = MapTest.randomInteger;
			int count = MapTest.count;
			gc();

			start();
			for (int i = 0; i < count; i++)
				map.put(randomInt[i], someValue);
			end("put");

			start();
			for (int i = 0; i < count; i++)
				map.get(randomInt[i]);
			end("get");
		}
	}

	static class CachingHashMapTest extends Test {
		CachingHashMap map = new CachingHashMap(count * 2);

		public void run () {
			Object someValue = this.someValue;
			CachingHashMap map = this.map;
			map.clear();
			Integer[] randomInteger = MapTest.randomInteger;
			int count = MapTest.count;
			gc();

			start();
			for (int i = 0; i < count; i++)
				map.put(randomInteger[i], someValue);
			end("put");

			start();
			for (int i = 0; i < count; i++)
				map.get(randomInteger[i]);
			end("get");
		}
	}

	static class IdentityHashMapTest extends Test {
		IdentityHashMap map = new IdentityHashMap(count * 2);

		public void run () {
			Object someValue = this.someValue;
			IdentityHashMap map = this.map;
			map.clear();
			Integer[] randomInteger = MapTest.randomInteger;
			int count = MapTest.count;
			gc();

			start();
			for (int i = 0; i < count; i++)
				map.put(randomInteger[i], someValue);
			end("put");

			start();
			for (int i = 0; i < count; i++)
				map.get(randomInteger[i]);
			end("get");
		}
	}

	static class FastIdentityHashMapTest extends Test {
		FastIdentityHashMap map = new FastIdentityHashMap(count * 2);

		public void run () {
			Object someValue = this.someValue;
			FastIdentityHashMap map = this.map;
			map.clear();
			Integer[] randomInteger = MapTest.randomInteger;
			int count = MapTest.count;
			gc();

			start();
			for (int i = 0; i < count; i++)
				map.put(randomInteger[i], someValue);
			end("put");

			start();
			for (int i = 0; i < count; i++)
				map.get(randomInteger[i]);
			end("get");
		}
	}

	static class FastObjectHashMapTest extends Test {
		FastObjectHashMap map = new FastObjectHashMap(count * 2);

		public void run () {
			Object someValue = this.someValue;
			FastObjectHashMap map = this.map;
			map.clear();
			Integer[] randomInteger = MapTest.randomInteger;
			int count = MapTest.count;
			gc();

			start();
			for (int i = 0; i < count; i++)
				map.put(randomInteger[i], someValue);
			end("put");

			start();
			for (int i = 0; i < count; i++)
				map.get(randomInteger[i]);
			end("get");
		}
	}

snip... you get the point. Forums won't let me post the whole thing.

Edit: Updated with even more maps. Looks like IntHashMap, FastIdentityHashMap, and FastObjectHashMap have the fastest gets for the 3 purposes. As mentioned, these are all basically the same code. Anyone see anything wrong with this code?

Abuse · October 21, 2009, 11:17am

While I like your pretty charts, I think they’d be more readable if they were sorted by their name, rather than their performance (as is the norm for performance comparison charts).

princec · October 21, 2009, 12:12pm

Depends if you just want to know which one’s the fastest

Cas

CommanderKeith · October 21, 2009, 1:52pm

Wow, nice work. Thanks for putting all of this together. 8)

Your FastIdentityHashMaps look like they’re king. Are these maps that you made yourself?

Nate · October 21, 2009, 4:09pm

Really? Ok, fixed and added some colors.

Sure, it was kind of fun. I lifted the ~10 lines that makes the charts from another benchmark. It is surprisingly easy to make charts, thanks Google! Hear that Riven? I expect not to see any more benchmarks without proper charts!

Of course, these results should be taken with a grain of salt. Memory usage isn’t considered, maps are tested with only one data set, not all maps use the same double hashing that HashMap uses, iteration isn’t tested, getting keys not in the map isn’t tested, etc.

Actually I resurrected the IntHashMap code from an old project… I really ought to find the original code and give proper recognition! I am pretty sure it was originally lifted from here…
http://www.koders.com/java/fid128CB47B2558DD20EA15852E444D7928D1E698DD.aspx
I will add the appropriate credits to source I distribute. It has been tweaked a little since then. Also, for FastIdentityHashMap I just made the keys Objects and called hashCode(), and for FastObjectHashMap I just replaced == with equals().

I added HashMapV2 from a recent mailing list discussion (linked in first post). It does amazingly well on Android for puts and holds its own for gets. It is probably more complete/robust than FastObjectHashMap (it is certainly fancier). Too bad it is GPL.

JL235 · October 21, 2009, 4:57pm

First thanks for putting this together. I will definitely be looking at the other types of maps as a result of this. But could you bring back the ordering? It’s now hard to compare implementations.

Using your code I made a few changes and ran my own benchmarks. This was only between the IdentifyMap, HashMap, CachingHashMap and FastMap (tbh I couldn’t be bothered to go get them all).

I upped the number of iterations to run per test from 3 to 60
It stores all times and then takes the average at the end (so you have an average time over 60 runs)
The gc call was removed from inside test iterations (I thought this was unfair because it gives maps some breathing space which they don’t get in real life)
I added the gc call to before the start of each test, to encourage the garbage collector to run and so not pass garbage on to the next test

The main goal was to try to benchmark longer-term performance and including the cost of garbage collection on top. At the very least this is more relevant for me (as I’ve personally found GC to sometimes become an issue). Here are the results:

When I scanned through the values as they were coming out I noticed that the HashMap would have an iteration that ran 5 to 10 times slower then the others. None of the other maps had these outlier values, and I’m presuming it must be the GC kicking in. This is what slows it down. It’s also interesting that mine is slower then the HashMap for get, but faster for put and when those times are combined. Which type of map people should use really depends on the situation.

To run the benchmark I also added the -Xmx512m command line so it ran with enough memory, but I found that if I also added Xms512m it improved the performance of the HashMap:

Presumably there is no (or very little) garbage collecting going on as a result.

Finally, identity maps are not real maps!

Nate · October 21, 2009, 5:12pm

Oy, take the order out, put the ordering in… I don’t know!?

I’ll post a zip of my code later today so you can more easily run all the tests.

GC is unpredictable, so I think it is better to remove it entirely rather than have it affect some of the tests sometimes. We can add memory usage pretty easily. I would like to find some way to reliably measure GC activity.

Interesting that bumping the JVM’s memory gave you better performance. I’ll give that a shot.

Re: identity maps, sometimes they are useful (eg, autoboxed primitive keys or when Class is your key), and they are fast. I really only care about the 3 scenarios: int keys, object keys, and identity keys. Memory usage and large data sets I’m not too worried about, mostly I just care about get. Oh, and I’d like the classes to be small (eg, not a half meg library – I’m looking at you, Javolution).

Nate · October 22, 2009, 4:21pm

I added a class called CachingFastMap. It is the same as FastMap (formerly known as FastObjectHashMap) except it keeps around its entry objects when entries are removed or the map is cleared. Like JL235’s CachingHashMap class, this is to avoid garbage collection if you are constantly putting and clearing a map. It scores very well for puts on Android, where memory allocation (and GC!) is expensive.

In the “fast.maps” package you’ll find the classes listed as “Nate” in the charts. All these are based on a modified version of IntHashMap from an Apache project. They are fast, minimal, and easy to customize. Eg, if you needed a ShortHashMap, a CachingLongHashMap, a different hashing algorithm, or whatever, you could modify one of these classes and have the map you need in a couple minutes.

I fixed up my classes quite a bit. You can get the source for it all here (3.1mb):
http://n4te.com/temp/fast.zip
Note fastutil is not included because the JAR is 13mb+! That makes Trove’s 2mb look like a good bargain!

The desktop tests are run with -Xms1024m. I added Hashtable. Also, I put the sorting back until someone complains again. With so many implementations, it is hard to see what is faster when they are alphabetical.

Riven · October 22, 2009, 4:36pm

[quote=“Nate,post:7,topic:34408”]
* Riven makes notes

[quote=“Nate,post:7,topic:34408”]
That works great, until you put nulls in your map.

I’m going to have a go at some fancy impl. !

Nate · October 22, 2009, 5:56pm

Yeah, I can get around that easily by not allowing null keys.

Looking forward to seeing what you come up with!

Riven · October 22, 2009, 6:10pm

or…

private static final Object NULL = new Object(); public void put(Object key, Object val) { if(key==null) key = NULL; ... } public Object get(Object key) { if(key==null) key = NULL; ... }

CommanderKeith · October 23, 2009, 12:26am

Hi Nate,

Thanks for making the CachingFastMap. I modified your source to make a CachingFastIdentityMap by copying the code from FastIdentityMap, and it seems to have made the code slower - after profiling I find that a large amount of CPU time is used calling:

java.lang.System.identityHashCode

What’s the reason for calling this? Is it ok to replace it with Object.hashcode() which appears to be faster?

Here’s my source for CachingFastIdentityMap without the calls to System.identityHashCode, replaced by Object.hashcode().

/*
 * Copyright 2002-2004 The Apache Software Foundation.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the
 * License. You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS"
 * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 */

package fast.maps;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * A hash map using primitive ints as keys rather than objects.
 * @author Justin Couch
 * @author Alex Chaffee (alex@apache.org)
 * @author Stephen Colebourne
 * @author Nathan Sweet
 */
public class CachingFastMap<K, V> implements Iterable<CachingFastMap.Entry<K, V>> {
	Entry[] table;
	private final float loadFactor;
	private int size, mask, capacity, threshold;
	private ArrayList<Entry> freeEntries;

	/**
	 * Same as: FastMap(16, 0.75f);
	 */
	public CachingFastMap () {
		this(16, 0.75f);
	}

	/**
	 * Same as: FastMap(initialCapacity, 0.75f);
	 */
	public CachingFastMap (int initialCapacity) {
		this(initialCapacity, 0.75f);
	}

	public CachingFastMap (int initialCapacity, float loadFactor) {
		if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large.");
		if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be greater than zero.");
		if (loadFactor <= 0) throw new IllegalArgumentException("initialCapacity must be greater than zero.");
		capacity = 1;
		while (capacity < initialCapacity)
			capacity <<= 1;
		this.loadFactor = loadFactor;
		this.threshold = (int)(capacity * loadFactor);
		this.table = new Entry[capacity];
		this.mask = capacity - 1;
		freeEntries = new ArrayList(capacity);
	}

	public void clearCache () {
		freeEntries.clear();
	}

	public void cache (int count) {
		for (int i = freeEntries.size(); i < count; i++)
			freeEntries.add(new Entry());
	}

	public V put (K key, V value) {
		int hash = key.hashCode();
		Entry[] table = this.table;
		int index = hash & mask;
		// Check if key already exists.
		for (Entry e = table[index]; e != null; e = e.next) {
			if (!e.key.equals(key)) continue;
			Object oldValue = e.value;
			e.value = value;
			return (V)oldValue;
		}
		int freeEntriesSize = freeEntries.size();
		Entry entry = freeEntriesSize > 0 ? freeEntries.remove(freeEntriesSize - 1) : new Entry();
		entry.hash = hash;
		entry.key = key;
		entry.value = value;
		entry.next = table[index];
		table[index] = entry;
		if (size++ >= threshold) {
			// Rehash.
			int newCapacity = 2 * capacity;
			Entry[] newTable = new Entry[newCapacity];
			int newMask = newCapacity - 1;
			for (int i = 0; i < table.length; i++) {
				Entry e = table[i];
				if (e == null) continue;
				do {
					Entry next = e.next;
					index = e.hash & newMask;
					e.next = newTable[index];
					newTable[index] = e;
					e = next;
				} while (e != null);
			}
			this.table = newTable;
			capacity = newCapacity;
			threshold *= 2;
			mask = capacity - 1;
		}
		return null;
	}

	public V get (K key) {
		int index = key.hashCode() & mask;
		for (Entry e = table[index]; e != null; e = e.next)
			if (e.key.equals(key)) return (V)e.value;
		return null;
	}

	public boolean containsValue (V value) {
		Entry[] table = this.table;
		for (int i = table.length - 1; i >= 0; i--)
			for (Entry e = table[i]; e != null; e = e.next)
				if (e.value.equals(value)) return true;
		return false;
	}

	public boolean containsKey (K key) {
		int index = key.hashCode() & mask;
		for (Entry e = table[index]; e != null; e = e.next)
			if (e.key.equals(key)) return true;
		return false;
	}

	public V remove (K key) {
		int index = key.hashCode() & mask;
		Entry prev = table[index];
		Entry e = prev;
		while (e != null) {
			Entry next = e.next;
			if (e.key.equals(key)) {
				size--;
				if (prev == e)
					table[index] = next;
				else
					prev.next = next;
				freeEntries.add(e);
				return (V)e.value;
			}
			prev = e;
			e = next;
		}
		return null;
	}

	public int size () {
		return size;
	}

	public boolean isEmpty () {
		return size == 0;
	}

	public void clear () {
		Entry[] table = this.table;
		for (int index = table.length - 1; index >= 0; index--) {
			for (Entry e = table[index]; e != null; e = e.next)
				freeEntries.add(e);
			table[index] = null;
		}
		size = 0;
	}

	public EntryIterator iterator () {
		return new EntryIterator();
	}

	public class EntryIterator implements Iterator<Entry<K, V>> {
		private int nextIndex;
		private Entry<K, V> current;

		EntryIterator () {
			reset();
		}

		public void reset () {
			current = null;
			// Find first bucket.
			Entry[] table = CachingFastMap.this.table;
			int i;
			for (i = table.length - 1; i >= 0; i--)
				if (table[i] != null) break;
			nextIndex = i;
		}

		public boolean hasNext () {
			if (nextIndex >= 0) return true;
			Entry e = current;
			return e != null && e.next != null;
		}

		public Entry<K, V> next () {
			// Next entry in current bucket.
			Entry e = current;
			if (e != null) {
				e = e.next;
				if (e != null) {
					current = e;
					return e;
				}
			}
			// Use the bucket at nextIndex and find the next nextIndex.
			Entry[] table = CachingFastMap.this.table;
			int i = nextIndex;
			e = current = table[i];
			while (--i >= 0)
				if (table[i] != null) break;
			nextIndex = i;
			return e;
		}

		public void remove () {
			CachingFastMap.this.remove(current.key);
		}
	}

	static public class Entry<K, V> {
		int hash;
		K key;
		V value;
		Entry next;

		public K getKey () {
			return key;
		}

		public V getValue () {
			return value;
		}
	}
}

Nate · October 23, 2009, 2:08am

I’m surprised System.identityHashCode is slower. Using System.identityHashCode means that if you are using objects that have overridden hashCode and equals, even if two objects are .equal() they will (probably) be put in a different hash buckets. Using Object.hashCode may cause more duplicate hashes, but in practice probably makes little difference. If your objects don’t override hashCode then there is no difference.

If you have a huge number of objects in your map, you should probably run the benchmarks with a higher number of objects (uses 10,000 currently). Java’s IdentityHashMap is pretty impressive. It puts the keys and values alternating in a single array (supposedly good for large data sets) and doesn’t need to create or reuse entry objects.

pjt33 · October 23, 2009, 7:24am

Yes. get and put both take int as the type of the key, but containsKey takes long and casts it to int. There may be a good reason for doing this, but I can’t see it.

Riven · October 23, 2009, 7:43am

I noticed that too yesterday.

You can see that it is immediately casted to int in the method body. So it must have been a typo, that was ‘corrected’ incorrectly.

delt0r · October 23, 2009, 5:05pm

I recently implemented a cuckoo hashMap for my work (3 hash functions for load factors ~.75). Its was 5x faster or more than the standard hashMap over all and much faster for contains and remove, and about 2-3x faster than using linear probing (IdentitiyHashMap uses this) and this is without tuning. I am surprised that none of these implementations use cuckoo probing as far as I can tell. You don’t even need to have Entry objects. It seems to offer big gains for primitives as well.

Nate · October 24, 2009, 7:46am

Ah. I should update the source I linked to. The FastIntMap class in the zip I posted is the latest and has this fixed. The original class was LongToIntHashMap and somehow a long got left in. I wasn’t using the containsKey method so didn’t catch it sooner.

delt0r, cuckoo hashing looks very interesting! It looks like it is better for my needs (fast for small tables, which ironically isn’t what the benchmarks are testing) and is easy to implement. Can you post your implementation, delt0r? I gave it a half assed try (not much time, have a big project to finish this weekend). I’ve updated the benchmarks (desktop only) in the first post and here is my class:


/*
 * Copyright 2002-2004 The Apache Software Foundation.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the
 * License. You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS"
 * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 */

/**
 * A hash map using primitive ints as keys rather than objects.
 * @author Justin Couch
 * @author Alex Chaffee (alex@apache.org)
 * @author Stephen Colebourne
 * @author Nathan Sweet
 */
public class CuckooFastMap<K, V> {
	Entry[] table;
	private final float loadFactor;
	private int size, mask, capacity, threshold;

	/**
	 * Same as: FastMap(16, 0.50f);
	 */
	public CuckooFastMap () {
		this(16, 0.50f);
	}

	/**
	 * Same as: FastMap(initialCapacity, 0.50f);
	 */
	public CuckooFastMap (int initialCapacity) {
		this(initialCapacity, 0.50f);
	}

	public CuckooFastMap (int initialCapacity, float loadFactor) {
		if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large.");
		if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be greater than zero.");
		if (loadFactor <= 0) throw new IllegalArgumentException("initialCapacity must be greater than zero.");
		capacity = 1;
		while (capacity < initialCapacity)
			capacity <<= 1;
		this.loadFactor = loadFactor;
		this.threshold = (int)(capacity * loadFactor);
		this.table = new Entry[capacity];
		this.mask = capacity - 1;
	}

	public V put (K key, V value) {
		int hash = key.hashCode();
		int index;
		while (true) {
			Entry[] table = this.table;
			index = hash & mask;
			// Check if key already exists.
			Entry e = table[index];
			if (e == null) break;
			index = (((hash >>> 15) * (mask + 1)) >>> 17) & mask;
			e = table[index];
			if (e == null) break;
			rehash(2 * capacity);
		}
		table[index] = new Entry(hash, key, value);
		if (size++ >= threshold) rehash(2 * capacity);
		return null;
	}

	private void rehash (int newCapacity) {
		Entry[] newTable = new Entry[newCapacity];
		int newMask = newCapacity - 1;
		for (int i = 0; i < table.length; i++) {
			Entry e = table[i];
			if (e == null) continue;
			int hash = e.hash;
			int index = hash & newMask;
			if (newTable[index] != null) {
				index = (((hash >>> 15) * (newMask + 1)) >>> 17) & newMask;
				if (newTable[index] != null) {
					rehash(newCapacity * 2);
					return;
				}
			}
			newTable[index] = e;
		}
		this.table = newTable;
		capacity = newCapacity;
		threshold *= 2;
		mask = capacity - 1;
	}

	public V get (K key) {
		Entry[] table = this.table;
		int hash = key.hashCode();
		int mask = this.mask;
		int index = hash & mask;
		Entry e = table[index];
		if (e != null && e.key.equals(key)) return (V)e.value;
		index = (((hash >>> 15) * (mask + 1)) >>> 17) & mask;
		e = table[index];
		if (e != null && e.key.equals(key)) return (V)e.value;
		return null;
	}

	public int size () {
		return size;
	}

	public boolean isEmpty () {
		return size == 0;
	}

	public void clear () {
		Entry[] table = this.table;
		for (int index = table.length - 1; index >= 0; index--)
			table[index] = null;
		size = 0;
	}

	static public class Entry<K, V> {
		final int hash;
		final K key;
		V value;

		Entry (int hash, K key, V value) {
			this.hash = hash;
			this.key = key;
			this.value = value;
		}

		public K getKey () {
			return key;
		}

		public V getValue () {
			return value;
		}
	}
}

When an object is put in with the first hash, this code doesn’t put it there and move the existing entry, it just tries to put it in the alternate hash slot and rehashes if entries are already in both slots. This causes it to rehash a lot but it was all I have time to do ATM. Also, I don’t know my second hash is the best idea (it is Riven’s random number algorithm, I now solve all my problems with it! :P). The get time is still extremely interesting! However it seems to vary quite a bit each time I run the test. I guess sometimes more lookups take the worst case scenario route (which would happen less often for smaller maps, the tests currently use 10,000 entries). Could also be due to my shoddy implementation.

delt0r · October 24, 2009, 12:17pm

My implementation does not conform to the java.util.map spec. In particular getValues keySet and entrySet are not backed by the hash map.

2ndly, I have not yet done a primitives version yet.

3rdly I use simple hash functions and rely on hashCode to be good. With the hash table itself being a power of 2 for simple masking rather than % which is painfully slow. For example the 3 hash values i use is given by the following code.


int hash =e.hashCode();
int hash2 =1 + ((hash * PRIME) + (hash >>> 16)); //EDIT to fix this line.. added () where it was needed. 
int hash3 =2 + (hash ^ (hash >>> 16)) * PRIME; //PRIME is a random 32 bit prime number (aka a prime with hamming weight of about 16). 
hash =hash & mask;
hash2 =hash2 & mask;
hash3 =hash3 & mask;

Finally I don’t use entry objects. I use a Object[] table where even entrys are keys and odd entrys are values. I am doing a lot of put/remove and this is where this table is much faster than others I have tried. However I have not tried all in the above list. The idea is that if the hashTable is small then everything will be in cache and it would be very fast. However it turned out it was very fast even with large sizes (millions or more) and modest load factors 0.75. In particular it has better performance with pathological cases than anything i tested. Basically it has no pathological cases.

I doubt this would beat everything on the list, and I want to add a better rehashing performance (use incremental hashing or whatever its called).

If you still want the code I can post it. BUT be warned its somewhat untested, quite uncommented and reasonably untuned/optimised (no profiling yet).