Highly Scalable Java / News: Recent posts

Fixed a bug with a put that triggers a table resize, immediately followed by a get of that key. The get was not tracking to the new table (value was inserted, and when the table copy completed the get would find it).

Closed a narrow race with putIfAbsent on a table-slot that is mid-copy (and not 'absent') accidentally allowing the putIfAbsent to succeed on the new table. Flaw was with the implementation and not the algorithm - and I am eagerly awaiting the results of model-checking on the implementation!
Cliff

This version includes a drop-in lock-free replacement for java.util.Hashtable.

The direct replacements match the API - but not all behaviors are covered by the API, and so they may not work for your program. In particular, the
replacement for java.util.Hashtable is NOT synchronized (that is the point!), although it is multi-threaded safe. If you rely on the undocumented synchronization behavior of the JDK Hashtable, your program may not work. Similarly, the iteration order is different between this version and the JDK version (this exact issue broke the SpecJBB benchmark when the iteration order was changed slightly (via using a slightly different hash function) between JDK rev's).... read more

Finally I got around to adding basic JavaDocs.

Create a highly scalable counter class, called Counter. Counter is somewhat slower than using raw Unsafe or Java 5's 'lock' API for single threads, and about the same speed as a well-striped Unsafe counter up to ~32 CPUs but continues to scaling linearly to 768 cpus where other approaches top out much sooner.

Change NonBlockingXXX classes to use this Counter class - note that they already used the same infrastructure before, just under a less convenient name. ... read more

Flip NBHMLong to use the new State Machine.
Add a space-for-speed tradeoff flag - 2x space for about 10% more speed; defaults to 'space'.

NonBlockingHashMap has moved to a new State Machine! The new FSM is much simpler, reasoning behind it is also simpler, and so is the code. This version has no known bugs (theoretical or otherwise), and I will be actively seeking to get it model-checked.

NBHMLong is next to move to this State Machine, NBSet is a thin wrapper over NBHM so is also on the new State Machine, and NBSetInt has been there awhile.

Big News: NBHM is being model-checked by Gene Novark using the SPIN tool. He's found 2 (thankfully minor) implementation errors so far.

I've been re-writing the basic state machine behind NBHM. (Gene is model-checking the OLD state machine right now, which I know has a minor algorithmic issue). This new version is functional in CVS but performance isn't quite up to par vs the existing code (the 'churn' test is not running fast enough yet). NonBlockingSetInt is already using the new style of state machine.... read more

A non-blocking variant of a primitive-int key'd Set. The bits are stored in a bit-vector, so it's best for densely populated sets. Set size is roughly equal to (max-bit/8 + 64) bytes. Fully non-blocking even during built-in resize. Should be bit-vector fast when not doing a resize (handful of load/shift/extract ops).

Cliff

Renamed the file but failed to include it in last release; it's in v0.6.5 now.
Thanks,
Cliff

Iterators for NonBlockingHashMap and NonBlockingHashMapLong appear to be complete.

Functional version of NonBlockingHashMapLong.
This non-blocking hashmap uses primitive long keys.
Not yet tested on a Big Box, but identical algorithm to the generic NonBlockingHashMap, but faster (e.g. trivial key-compare) and less memory required (no boxing of "long" into Long).

Initial cut of a primitive-long key'd NonBlockingHashMap, for those folks with enough primitive longs that turning them into Longs is expensive. Also more cleanup (some findbugs stuff, some PMD stuff).
Cliff

bug fixed; some code cleanup as well

Known bug with putIfAbsent; fix coming soon.
Cliff