Cliff Click - April 1st, 2007
In a previous blog I talked about my Non-Blocking Hash Table, and how to implement 'get()'. This blog will focus on 'put()' and all variations. The hard part will be figuring out how to include state machine diagrams in a blog! Quick recap: the HashTable is a closed power-of-2 sized table. The table holds Key/Value pairs in even/odd entries in a large Java Object[] array. Key slots are limited to States {null,K} and make a 1-time transition from null to K (when a new Key is inse
Cliff Click - April 1st, 2007
Chris Purcell writes:Re. your talk: State machines permeate my algorithms, too. I suspect it's because they are easy to do atomically, make the "progress" through an algorithm obvious (simplifying concurrent assistance), and make enumerating all cases (the bane of lock-free algorithms) both explicit and fundamental.
Cliff Click - March 28th, 2007
[Part 2 : 'put' of my NonBlockingHashMap presentation will appear later] I presented my NonBlockingHashMap at Google yesterday. Overall, the talk went over very well with lots of intelligent questions. This bodes well for presenting this stuff at JavaOne. To be blunt, I was very concerned that I'd be talking over most folks' heads at JavaOne, but maybe not.
Cliff Click - March 26th, 2007
I've been wrestling with concurrent algorithms again. This time, it's a Non-Blocking (concurrent, lock-free) HashTable. I've had it basically figured out for a few months now and I'm slowing widening the circle of people I expose it too. This HashTable seems too good to be true, which is why I'm trying hard to vet it's correctness before claiming victory. It's single-threaded performance appears to equal java.util.HashTable, and at high CPU count (750 cpus on a high-end Azul machine) it's
Cliff Click - March 20th, 2007
Here's the most common data-race I see: if( *p != null ) { // other thread does 'p=null' *p->xxx; } This is just my personal observation, both on code I've written and code other people have written but I've had to debug. This is the most common race, by far.
Cliff Click - March 14th, 2007
Ben Zorn and I had a long talk while working off dinner at CGO yesterday. One of the things we noticed was how Ben's recent work on surviving data races and Azul's work with detecting data races in the Java Collection classes had a lot in common: both came about because data races are killing the average programmer, both run with little overhead and detect only a limited set of data-races, and are easy enough for somebody to hand-code into their code today.
