Is there a parallel processing implementation of HashMap available to Java? Is it even possible?

Question

Searching for the magic ParallelHashMap class

More succinctly, can you use multiple threads to speed up HashMap lookups? Are there any implementations out there that do this already?

In my project, we need to maintain a large map of objects in memory. We never modify the map after it is created, so the map is strictly read-only. However, read and look-up performance on this map is absolutely critical for the success of the application. The systems that the application will be installed on typically have many hardware threads available. Yet, our look-ups only utilize a single thread to retrieve values from the HashMap. Could a divide and conquer approach using multiple threads (probably in a pool) help improve look-up speed?

Most of my google searches have been fruitless - returning lots of results about concurrency problems rather than solutions. Any advice would be appreciated, but if you know of an out of the box solution, you are awesome.

Also of note, all keys and values are immutable. Hash code values are precomputed and stored in the objects themselves on instantiation.

As for the details of the implementation, the Map has about 35,000 items in it. Both keys and values are objects. Keys are a custom look-up key and values are strings. Currently, we can process about 5,000 look-ups per second max (this included a bit of overhead from some other logic, but the main bottleneck is the map implementation itself). However, in order to keep up with our future performance needs, I want to get this number up to around 10,000 look-ups per second. By most normal standards our current implementation is fast - it is just that we need it faster.

In our Map of 35,000 values we have about one hash code collision on average, so I'm guessing that the hash codes are reasonably well-distributed.

Answer 1

HashMaps have constant lookup times. Not sure how you could really speed that up since trying to have multiple threads execute the hashing function will only cause it to go slower.

Answer 2

Sounds like you should profile. You could have a high collision rate. You could also try using a lower loadFactor in the HashMap - to reduce collision probability.

Also, if the hashCodes are precomputed, then there is not much work for get() to do except mod and a few equals(). How fast is equals() on your key objects?

Answer 3

From the HashMap documentation (I've changed the emphasis):

Note that this implementation is not synchronized. If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

Since your HashMap is never modified you can safely let multiple threads read from it. Implementing locking is not necessary. (The same is true for any case where threads share access to immutable data; in general the simplest way to achieve thread safety is not to share any writable memory)

To ensure that your code doesn't modify the map by accident, I would wrap the map with Collections.unmodifiableMap immediately after its construction. Don't let any references to the original modifiable map linger.

Answer 4

So your hash codes are precomputed and the equals function is fast - your hashmap gets should be very fast in this case.

Have you profiled your application to prove that the hashmap gets are indeed the bottleneck?

If you have multiple application threads, they should all be able to perform their own gets from the hashmap at the same time - since you aren't modifying the map, you don't need to externally synchronize the gets. Is the application that uses the hashmap sufficiently threaded to be able to make use of all your hardware threads?

Since the contents of the hash table are immutable, it might be worth looking into perfect hashing - with a perfect hash function, you should never have collisions or need chaining in the hash table, which may improve performance. I don't know of a java implementation off hand, but in know in C/C++, there is gperf

Answer 5

To answer your question: yes, absolutely. AS LONG AS YOU AREN'T WRITING TO IT.

You're going to have to make it by hand, and it's going to be a little tricky. Before trying that, have you optimized as much as possible?

In C++, check out Google's dense hash map class in their sparsehash package.

In Java, if you're mapping with a primitive key, use Trove or Colt maps.

That said, here's a start for your parallel hash map: if you choose n hash functions and spawn n threads to search down each path (probing/chaining at each of the n insertion points) you'll get a decent speedup. Be careful because there's a high cost to creating threads, so spawn the threads on construction and then block them until they're needed.

Hopefully the cost of locking won't be higher than the cost of lookup, but that's up to you to experiment with.

Answer 6

You mentioned this in a comment:

I'm doing equals checks between 5 numbers referenced

From this I infer that your hash computation is also doing some calculations with these 5 numbers. For good HashMap performance, the results of this computation should be randomly dispersed over all possible int values. From the HashMap documentation:

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

In other words, look-up times should remain constant regardless of the element count, if you have a good hash function. Example of a good hashCode() function for a class that stores three numbers (using a prime number to reduce the chance of the XOR yielding zero as suggested by comment):

return this.a.hashCode() ^ (31 * (this.b.hashCode() ^ (31 * this.c.hashCode())));

Example of a bad hashCode function:

return (this.a + this.b + this.c);

Answer 7

I think you need evidence that the get() method on the HashMap is where you delay is. I think this is highly unlikely. Put a loop around your get() method to make it repeat 1,000 times and your application probably won't slow down at all. Then you'll know that the delay is elsewhere.