/*
 * Written by Gil Tene, based on Apache Harmony version of java.util.HashMap.
 */

PauselessHashMap: A java.util.HashMap compatible Map implementation that
performs background resizing for inserts, avoiding the common "resize/rehash"
outlier experienced by normal HashMap.

get() and put() operations are "pauseless" in the sense that they do not
block during resizing of the map. Other operations, like remove(), putAll(),
clear(), and the derivation of keysets and such *will* block for pending
resize operations.

Like HashMap, PauselessHashMap provides no synchronization or thread-safe
behaviors on it's own, and MUST be externally synchronized if used by multiple
threads. The background resizing mechanism relies on the calling program
enforcing serialized access to all methods, and behavior is undefined if
concurrent access (for modification or otherwise) is allowed.

And like HashMap, PauselessHashMap is an implementation of Map. All optional
operations (adding and removing) are supported. Keys and values can be any objects.


-----------------------------

Here is some more background and commentary I included in my posting
on the mechanical sympathy group on the subject:
https://groups.google.com/forum/#!topic/mechanical-sympathy/DY8vysxdmj4

Pauseless HashMap

Some background: As those of you who have read my various rants may have
noticed, I spend a lot of my time thinking about the behavior of
latency/response-time/reaction-time. In addition to trying to understand
and teach about the behavior better (with monitoring and measurement tools
like HdrHistogram, LatencyUtils, and jHiccup), I actually work on things
that try to improve bad behavior (for some definitions of "improve" and
"bad"). Eliminating pausing behavior in GC was the lowest hanging fruit,
but more recent work has focused on eliminating pauses due to things like
at-market-open deoptimzations, or lock deflation, or de-basing, or all
sorts of TTSP (time to safepoint) issues. I've also learned a lot about
how to bring down Linux's contribution to latency spikes.

But the JVM and the OS are not the only things that cause latency spikes.
Sometimes your code is just "spiky". In my day job, I keep running into in
actual, real-world low latency system code that is typically super-fast,
but occasionally spikes in actual work latency due to some rare but huge
piece of work that needs to be done, most often due to some state
accumulation. After we eliminate GC pauses (which tend to dominate latency
spikes, and which simply disappear immediately when Zing is applied), we
often see this nice pattern of growing latency spikes at growing intervals,
with a near-perfect doubling in both magnitude and interval between the
spikes. This happens so often that we've studied the common causes, and
(by far) the most common culprits are HashMaps used to accumulate something
during the trading day. And it's all about resizing work.

I've had "build a Pauseless HashMap" on my weekend project list for over a
year now, but finally got around to actually building it (at the request of
someone on this list). There are probably at least 17 ways to skin a HashMap
so it won't stall puts and gets when it resizes, but this is my simple take
on it:

https://github.com/giltene/PauselessHashMap

Keep in mind that this is a "probably-working draft" that's gone through
some bench testing, but is not yet battle hardened (scrutiny is welcome).

I intentionally based this version on Apache Harmony's version of HashMap,
and not on OpenJDK's, in order to make it available without GPLv2 license
restrictions (for those who may want to include it in non-GPL products).
The background resizing concept itself is simple, and can be applied just
as easily to the OpenJDK version (e.g. if some future Java SE version
wants to use it). You can use 
(https://svn.apache.org/repos/asf/harmony/enhanced/java/trunk/classlib/modules/luni/src/main/java/java/util/HashMap.java)
as a baseline comparison for the code I started with.

This is also a classic example of how GC makes this sort of concurrent
programming thing both fast and simple. This is a classic case of an
asymmetric speed need between two concurrent actors that share mutable
state. I worked hard to make the fast path get() and put() cheap, and
managed (I think) to not even use volatiles in the fast path. In doing
this, I shifted all the cost I could think of to the background work,
where latency doesn't matter nearly as much. This sort of trick would
be much harder (or slower) to do if GC wasn't there to safely pick up
the junk behind us, as it would (invariably, I think) add a need for
additional synchronizing work in the fast path.