On 11/11/2014 07:58 PM, David Chase wrote:
I’ve incorporated your other changes (not yet the linear-scan hash table) and
will be retesting.
One thing I wonder about for both hash table and binary search is if the first
try should be attempted with no lock to avoid the overhead of synchronization;
I expect that looking will be more common than interning, which in turn will be
(vastly) more common than class redefinition.
Hi David,
Yes, that's why I implemented the hash table in a way where lookups are
lock-free. Binary-search would be trickier to implement without locking,
but maybe not impossible. Surely not with Arrays.binarySearch() but
perhaps with a separate implementation. The problem with
Arrays.binarySearch is that it returns an index. By the time you
retrieve the element at that index, it can already move. I'm also not
sure that "careful" concurrent insertion of new element would not break
the correctness of binary search. But there is another way I showed
before: using StampedLock. It is a kind of optimistic/pessimistic
read-write lock. Its beauty is in that optimistic read part is almost
free (just a volatile read at start and a readFence followed by another
volatile read at the end). You just have to be sure that the algorithm
guarded by an optimistic read lock terminates normally (that it doesn't
spin in an endless loop or throw exceptions) in the presence of
arbitrary concurrent modifications of looked-up state. Well, binary
search is such an algorithm.
Regards, Peter
David
