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

[Robbin Ehn]

Hi Gerard,

On 2018-04-30 21:23, Gerard Ziemski wrote:
> hi Robbin,
> 
> Still reviewing, but I have a couple of questions and some feedback I wanted to ask/share with you so far:
> 
> 
> #1 Where does the choice of "12" for _task_size_log2  come from in:
> 
>   BucketsOperation(ConcurrentHashTable<VALUE, CONFIG, F>* cht)
>     : _cht(cht), _next_to_claim(0), _task_size_log2(12),
>     _stop_task(0), _size_log2(0) {}
> 

2^12 comes from benchmarking the stringstable using this hashtable.
Where we do not want to delay a safepoint but still have enough work to get some 
throughput.

> Shouldn't "12" be a constant?

Fixed.

> 
> 
> #2 Where does "8192" come from in:

It comes from spinYield.hpp

> 
>   // SpinYield would be unfair here
>   while (!this->trylock()) {
>     if ((++i) == 8192) {
> 
> Shouldn't "8192" be a constant?
> 

Fixed.

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

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