CyclicMap - A Map implementation perfect for games and faster than HashMap

Shared Code
#1

I dislike the map implementation in Java because it instantiates a new Iterator & Entry all the time. Here’s an implementation of my own Map, it also has way more functionality. For example, you can multiple entries with the same key, and there are various methods to manipulate those entries.

Here’s the output comparing HashMap and my implementation:

Mine obviously is only slightly better, but given all the functionality I added I’m kinda suprised I can easily match HashMap in speed.

Here’s the description of the class:

Here are it’s method signatures:


public class CyclicMap<K, V>
{
	public CyclicMap( int tablePower )
	public void add(final K key, final V value)
	public void addAll(final Map<K, V> map)
	public void addAll(final CyclicMap<K, V> map)
	public boolean addIfAbsent(final K key, final V value)
	public V put(final K key, final V value)
	public <D extends Collection<V>> D putAll(final CyclicMap<K, V> map, final D destination)
	public <D extends Collection<V>> D putAll(final Map<K, V> map, final D destination)
	public V get(final K key)
	public <D extends Collection<V>> D getAll(final K key, final D destination)
	public K getKey(final V value)
	public <D extends Collection<K>> D getAllKeys(final V value, final D destination)
	public V remove(final K key)
	public void removeAll(final K key)
	public void removeAll(final K ... keyArray)
	public void removeAll(final Iterable<K> keyIterable)
	public int countOf(final K key)
	public K removeValue(final V value)
	public void removeAllValue(final V value)
	public void removeAllValue(final V ... valueyArray)
	public void removeAllValue(final Iterable<V> valueIterable)
	public int countOfValue(final V value)
	public boolean has(final K key)
	public boolean hasValue(final V value)
	public Entry<K, V> beforeKey(final K key)
	public Entry<K, V> beforeValue(final V value)
	public int hash(final K key)
	public K removeFirstKey()
	public V removeFirstValue()
	public Entry<K, V> removeFirstEntry()
	public Iterable<Entry<K, V>> entries()
	public Iterable<Entry<K, V>> entriesWithKey(final K key)
	public Iterable<Entry<K, V>> entriesWithValue(final V value)
	public Iterable<V> values()
	public Iterable<K> keys()
	public void clear( final boolean freeEntries )
	public int size()
	public boolean isEmpty()
	public void free( final Entry<K, V> entry )
	public static void removeAllFromIterator( final Iterable<?> iterable )
	public static <E, C extends Collection<E>> C removeAllFromIterator( final Iterable<E> iterable, final C destination )
	public static int countIterator( final Iterable<?> iterable ) 
	public static <K, V, D extends Collection<V>> D stripValues( final Iterable<Entry<K, V>> entries, final D destination )
	public static <K, V, D extends Collection<K>> D stripKeys( final Iterable<Entry<K, V>> entries, final D destination )
	public static void initPool(final int size)
	
	public static class Entry<K, V> 
	{
		public int hash;
		public K key;
		public V value;
		public Entry<K, V> next;
	}
}

Here’s the full code:

http://www.java-gaming.org/?action=pastebin&id=423

Here are the JUnit tests for it:

http://www.java-gaming.org/?action=pastebin&id=425

Let me know how it performs on your machine!

Thanks,

Clicker Monkey

#2

Java 7 server VM
HashMap.put: 0 us 031.052 ns per entry
CyclicMap.put: 0 us 027.538 ns per entry
HashMap.get: 0 us 008.564 ns per entry
CyclicMap.get: 0 us 008.765 ns per entry
HashMap.keySet: 0 us 000.116 ns per entry
CyclicMap.keys: 0 us 002.420 ns per entry
HashMap.entrySet: 0 us 000.109 ns per entry
CyclicMap.entries: 0 us 002.361 ns per entry
HashMap.values: 0 us 000.108 ns per entry
CyclicMap.values: 0 us 002.380 ns per entry

Java 7 client VM
HashMap.put: 0 us 048.839 ns per entry
CyclicMap.put: 0 us 054.689 ns per entry
HashMap.get: 0 us 025.714 ns per entry
CyclicMap.get: 0 us 021.434 ns per entry
HashMap.keySet: 0 us 000.157 ns per entry
CyclicMap.keys: 0 us 002.393 ns per entry
HashMap.entrySet: 0 us 000.178 ns per entry
CyclicMap.entries: 0 us 002.409 ns per entry
HashMap.values: 0 us 000.157 ns per entry
CyclicMap.values: 0 us 002.417 ns per entry

Be careful with microbenchmarks.
You need to let the VM warm up, especially if the slow implementation comes first each time.
I ran the test with 204800 iterations each.
There are empty loops which might got optimized.

What is a use case for multiple values per key ?

#3

Ahh thanks, I thought 2048 iterations of doing 1024 puts was warmup enough, I guess not! My VM is Java 6, I haven’t tested it with 7 yet.

Also, not sure of the usecase for typical users. I found a use case for my game, so I created this.

Any who, I wonder how HashMap’s values(), entrySet(), and keySet() are so low for you? Something must be going on with my code that it’s getting treated differently by the VM.

Thanks!

#4

Having linked entries can be very nice when it is needed, but of course has a small penalty if you don’t.

Here are some other threads about maps:


http://www.java-gaming.org/index.php/topic,23102
End result of all that is here:
#5

I always forget about Cuckoo hashing, thanks for the Uber information Nate! I wish I could just insert my code into all those tests to see how it stacks up.

#6

Because you clear the map while measuring.
Also, the warm up period should be separated from the measuring part but running the exact same code.
Then I would rather measure the time for one complete iteration set to prevent timer inaccuracies and for benchmarking hash maps I would create a more random set of key values.

#7

WOW, that’s what I get for copying and pasting… it’s clearing all over :o

Whys that?

I was only measuring the last, but times were “all” over the place.

#8

Just because compiling hot spots takes time and could distort the measurements.
On slower machines it is clearly noticable that the server vm does a quiet aggressive compilation and optimization job.
According to the “Java Performance” book, the server VM needs 10000 iterations before it compiles to native code and the client VM 1500 iterations.

#9

If you are looking at optimising HashMaps, you could have a look at raphfrk’s findings at http://forums.spout.org/threads/hashmap-micro-optimisations.6648/

#10

His micro benchmark is poor. JAVA_HASH, etc aren’t final, currentTimeMillis, no warmup, etc. Plus I doubt Java’s HashMap double hashing is what makes it slow. It degrades to a linked list when hashing is poor (lots of .equals()!) and it allocates on put().

#11

Well maybe you can talk to him about it. It’s still twice the speed with his optimisation, and I’m fairly sure currentTimeMillis doesn’t go 80ms off (at least most of the time).

#12

The usefulness of a micro benchmark is questionable, but the uselessness of a flawed micro benchmark isn’t. :slight_smile: So, his benchmark doesn’t say anything about how much faster it is. My main point though is that even if you made the second hashing instantaneous, I doubt you would have sped up HashMap. In other words, the hashing isn’t what is slow.