RFR(L): Low latency hashtable for read-mostly scenarios (original) (raw)
Robbin Ehn robbin.ehn at oracle.com
Thu Apr 26 07:38:02 UTC 2018
- Previous message: RFR: 8202230: Provide accessors for JNIHandles storage objects
- Next message: RFR(L) 8195099: Low latency hashtable for read-mostly scenarios
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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
- Previous message: RFR: 8202230: Provide accessors for JNIHandles storage objects
- Next message: RFR(L) 8195099: Low latency hashtable for read-mostly scenarios
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]