Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  CyclicMap - A Map implementation perfect for games and faster than HashMap  (Read 2337 times)
0 Members and 1 Guest are viewing this topic.
Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Posted 2013-02-15 17:04:43 »

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:

Quote
HashMap.put:        0 us  115.082 ns per entry
CyclicMap.put:      0 us  088.690 ns per entry
HashMap.get:        0 us  065.522 ns per entry
CyclicMap.get:      0 us  043.357 ns per entry
HashMap.entrySet:   0 us  003.988 ns per entry
CyclicMap.entries:  0 us  003.549 ns per entry
HashMap.keySet:     0 us  003.832 ns per entry
CyclicMap.keys:     0 us  003.499 ns per entry
HashMap.values:     0 us  003.869 ns per entry
CyclicMap.values:   0 us  003.505 ns per entry

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:

Quote
A map with circular references so that all entries have a next entry and the table is pre-populated with null-key and null-value entries to hold the initial chain of entries. Having circular references enables quick iteration of entries. This map implementation also supports multiple entries with the same key value via the add(Object, Object) method.

There are supporting methods to handle multiple keys like entriesWithKey(Object), removeAll(Object), countOf(Object), removeAll(Object), getAll(Object, Collection), and removeAll(Iterable).

There are also supporting methods to handle multiple values like entriesWithValue(Object), removeAllValue(Iterable), removeAllValue(Object), getAllKeys(Object, Collection), and countOfValue(Object).

This map implementation caches iterators for it's entries, values, keys, entries with a specific key, and entries with a specific value. This is to avoid needless allocation of iterators. The one drawback with this design however is that you must avoid nested iterations over the same iterator - this will not work.

This map implementation can also cache entries and reuse them between all instances via the initPool(int) method.

This map was built with speed and minimizing garbage in mind.

The fields of the Entry class are all public, do not modify these values.

Here are it's method signatures:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
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

Offline 65K
« Reply #1 - Posted 2013-02-15 18:08:52 »

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 ?

Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #2 - Posted 2013-02-15 18:13:27 »

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 ?

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!

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #3 - Posted 2013-02-15 18:33:42 »

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/topics/map-performance/21395/view.html
http://www.java-gaming.org/index.php/topic,23102
End result of all that is here:
https://github.com/libgdx/libgdx/blob/master/gdx/src/com/badlogic/gdx/utils/ObjectMap.java

Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #4 - Posted 2013-02-15 19:38:48 »

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.

Offline 65K
« Reply #5 - Posted 2013-02-16 10:23:20 »

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.
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.

Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #6 - Posted 2013-02-16 16:05:32 »

Because you clear the map while measuring.

WOW, that's what I get for copying and pasting... it's clearing all over  Shocked

Also, the warm up period should be separated from the measuring part but running the exact same code.

Whys that?

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.

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

Offline 65K
« Reply #7 - Posted 2013-02-16 17:56:39 »

Also, the warm up period should be separated from the measuring part but running the exact same code.

Whys that?
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.

Offline DziNeIT

Senior Newbie


Exp: 3 years



« Reply #8 - Posted 2013-03-29 14:53:46 »

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/
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #9 - Posted 2013-03-29 15:09:02 »

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().

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline DziNeIT

Senior Newbie


Exp: 3 years



« Reply #10 - Posted 2013-03-29 15:14:41 »

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).
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #11 - Posted 2013-03-29 17:51:49 »

The usefulness of a micro benchmark is questionable, but the uselessness of a flawed micro benchmark isn't. Smiley 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.

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (49 views)
2014-10-17 03:59:02

Norakomi (38 views)
2014-10-16 15:22:06

Norakomi (31 views)
2014-10-16 15:20:20

lcass (34 views)
2014-10-15 16:18:58

TehJavaDev (65 views)
2014-10-14 00:39:48

TehJavaDev (65 views)
2014-10-14 00:35:47

TehJavaDev (55 views)
2014-10-14 00:32:37

BurntPizza (72 views)
2014-10-11 23:24:42

BurntPizza (43 views)
2014-10-11 23:10:45

BurntPizza (84 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!