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

[David Holmes]

On 2/05/2018 11:56 PM, Robbin Ehn wrote:
> On 2018-05-02 14:40, David Holmes wrote:
>> 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.
> 
> Generally I agree with you. But in this case I didn't find the volatile
> qualifier helpful, it just clobbered the code. I didn't see any readability
> improvements from having essential all lines with Node* also having 
> volatile in them.

I'm not concerned with readability I'm concerned with doing the minimum 
to try to ensure that a variable that can be concurrently mutated and 
accessed in a lock-free manner is at least flagged to the compiler as 
something it should be careful about dealing with!

> What I would like is a type that forces the use of the correct ordering, 
> e.g.
> Atomic<Node*, memory_order_acq_rel> _next;

Meanwhile

Node * volatile _next;

is the closest thing we have.

David
-----

> /Robbin
> 
>>
>> 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
>>>>