RFR(L) 8195099: Low latency hashtable for read-mostly scenarios

[David Holmes]

Not a review, one comment ...

On 2/05/2018 6:31 PM, Robbin Ehn wrote:
> On 2018-04-30 21:23, Gerard Ziemski wrote:
>> #3 How come "_first" doesn't need to be volatile to be used in 
>> Atomic::cmpxchg ?
>>
>> Node* _first;
>> ...
>>   if (Atomic::cmpxchg(node, &_first, expect) == expect) {
> 
> An implicit cast to the same compatible type which is volatile-qualified 
> is okey.

Any variable used in a lock-free manner should be declared volatile as 
general good practice IMHO.

David
-----

>>
>>
>> #4 Inconsistent parameter names - in:
>>
>>   template <typename LOOKUP_FUNC, typename VALUE_FUNC>
>>   bool get_insert_lazy(Thread* thread, LOOKUP_FUNC& lookup, 
>> VALUE_FUNC& val_f,
>>                        bool* grow_hint = NULL) {
>>     return get_insert_lazy(thread, lookup, val_f, noOp, grow_hint);
>>   }
>>
>> We use "val_f" with "_f” suffix, so we should have "lookup_f", not 
>> "lookup" (many other instances) and "found_f", not "foundf" in
>>
>>   template <typename LOOKUP_FUNC, typename FOUND_FUNC>
>>   bool get(Thread* thread, LOOKUP_FUNC& lookup, FOUND_FUNC& foundf,
>>            bool* grow_hint = NULL);
>>
> 
> Fixed.
> 
>>
>> #5 I wasn't familiar with CRTP, so I read up on it, but I still don't 
>> see the CRTP in BaseConfig - which is the base class and which is 
>> derived? In particular I don't see "class Derived : public 
>> Base<Derived>" pattern here?
> 
> It's the supplied config that extends the BaseConfig which is the derived.
> 
> In gtest (test_concurrentHashtable.cpp) you will see this:
> 
> // Simplest working CRPT implementation for the hash-table.
> struct Pointer : public SimpleTestTable::BaseConfig {
> 
>>
>> More to come…
>>
>>
>> btw. I edited the subject of the email slightly by adding the bug 
>> number to it, so it’s easy to search for.
>>
> 
> Thanks, I'll send the update to the original mail.
> 
> /Robbin
> 
> 
> 
>>
>> cheers
>>
>>
>>> On Apr 26, 2018, at 2:38 AM, Robbin Ehn <robbin.ehn at oracle.com> wrote:
>>>
>>>
>>> Hi all, please review.
>>>
>>> The lower latency of the new gcs have higher demands on runtime 
>>> data-structure
>>> in terms of latency. This is a concurrent hashtable using the 
>>> global-counter
>>> (8195099).
>>>
>>> Webrev:
>>> http://cr.openjdk.java.net/~rehn/8195098/v0/webrev/
>>>
>>> Bug:
>>> https://bugs.openjdk.java.net/browse/JDK-8195098
>>>
>>> * Readers never blocks or spins.
>>> * Inserts do CAS from a read-side, need to re-CAS during 
>>> re-size/deletion in targeted bucket or insert collision. (inserts are 
>>> conceptually a reader)
>>> * Deletes locks the targeted bucket, all other buckets are free for 
>>> operations.
>>> * Re-size locks one bucket at the time, all other buckets are free 
>>> for operations.
>>>
>>> It does concurrent re-size by doubling size and use one more bit from 
>>> hash.
>>> That means a bucket in the old table contains nodes to either one of 
>>> two buckets
>>> in the new table. Each node in the chain is sorted into one of the 
>>> two buckets
>>> with concurrent readers. Shrinking just take two node chains and put 
>>> them
>>> together in the corresponding bucket. To keep track of what is 
>>> visible to the
>>> concurrent readers it's uses a global-counter, needed during re-size 
>>> and for
>>> deletes.
>>>
>>> A gtest is provided which passes on our platforms, we also have a 
>>> prototype of the stringtable using this which passes tier 1-5 on our 
>>> platforms.
>>>
>>> Various people have pre-reviewed various parts, thanks! And a special 
>>> thanks to
>>> Coleen for a lot of reviewing!
>>>
>>> Thanks, Robbin
>>