Fast thread-safe read optimised Map[Long, _]

Question

I am looking for suggestions to a fast Map with Long keys. It will have a lot of read accesses and rather small write/update accesses. Performance should thus focus on read (get) access. It must be thread-safe. Some ideas:

1. regular collection.Map[Long, _] has to box keys
2. bare bones collection.mutable would have to wrap synchronized all the time, penalising read access
3. bare bones collection.immutable could have unsynchronized read access if stored in a @volatile var. Update could synchronize.
4. perhaps TMap from Scala-STM? But then a Ref[Map[Long, _]] probably is as good because concurrent reads should be allowed in STM

To me No. 3 sound best?

Answer 1

There is an immutable LongMap, and 2.11 will have a mutable LongMap. The latter is not thread-safe, but you could wrap accesses (probably with a read-write lock from java.util.concurrent, if you're mostly reading and can reason through possible deadlocks). If you have a lot of contention, you're unlikely to do much better than just using java.util.concurrent.ConcurrentHashMap; threading issues will be much more expensive then than a bit of extra boxing.

Answer 2

collection.Map isn't thread-safe by default, but has to use the SynchronizedMap trait which is just locking around all accesses - performance wise not so great, probably slower than a simple ConcurrentHashMap.

Using an immutable map and a volatile variable which is replaced when updating would work and would be the cheapest possible option read wise (can't get cheaper than a simple volatile read). Expensive when updating though.

No idea how good Scala's STM is, so certainly worth a try too.

One option you should definitely consider, would be Cliff's non-blocking hashmap though, see here. It does have a Long version so you avoid boxing and it's performance-wise hard to beat (depending on the situation faster to extremely faster compared to the ConcurrentHashMap in the java stdlib which again is a good deal quicker than just using a normal hashmap and locking around every access).

Answer 3

Sounds like a good use of the either a regular HashMap or the fastutil Long2Object map and a ReentrantReadWriteLock. That lock will let you have multiple simultaneously open read locks, but write locks have to be exclusive. I'd still benchmark it against ConcurrentHashMap because its implementation is known to be pretty good.

Doh! You probably want a Scala answer and not the Java flavor.