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

[Robbin Ehn]

On 05/03/2018 12:17 AM, David Holmes wrote:
> 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!

The minimum is la/sr. Mutating it as a volatile is a bug. Hiding bugs with 
volatile is not something I like to do. E.g. if code crashes and volatile makes 
the crash go away, you have not fixed the bug.
So yes this is _only_ readability and consistency.

It seem most people favor the consistency of hotspot-style, therefore I will 
follow the hotspot-style and make those volatile (_first/_next).

I'll send new version on RFR thread.

Thanks, Robbin

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