mesos/spark — pull request #823 by mateiz (2013-08-14 01:23:24+00:00)
Title: Added a fast and low-memory append-only map for shuffle operations

This is an attempt to reduce the CPU cost and memory usage of shuffles by taking advantage of the properties their hashmaps need. In particular, the hashmaps there are append-only, and a common operation is updating a key's value based on the old value. The included AppendOnlyMap class uses open hashing to use less space than Java's (by not having a linked list per bucket), does not support deletes, and has a changeValue operation to update a key in place without following the hash chain twice.

This is just an experiment now because it remains to test it in real Spark apps, but in micro-benchmarks against java.util.HashMap, scala.collection.mutable.HashMap, this is 20-30% smaller and 10-40% faster depending on the number and type of keys. It's also noticeably faster than fastutil's Object2ObjectOpenHashMap.