Idea: use Relativistic Hash Tables

[stereobooster]

As of now implementation use LinkedHashTable, which is Double Linked List plus HashMap, which in turn is Robin Hood Hash Table.

How about to try to implement Relativistic Hash Tables which suppose to handle concurency much better.

Quote from paper

Applying this algorithm to memcached removes a scalability limit for get requests, allowing memcached to scale linearly and service up to 46% more requests per second.

---

Other interesting papers to explore:

• High-Performance Memory Management from Off-the-Shelf Components
• CPHASH: A Cache-Partitioned Hash Table
• Highly-Concurrent Doubly-Linked Lists
• Lock-Free and Practical Doubly Linked List-Based Deques Using Single-Word Compare-and-Swap
• multi-way atomic compare-and-swap with x64/TSX
• nonblockinghashmap
• https://rcoh.me/posts/rust-linked-list-basically-impossible/

Alternatives:

• https://github.com/reeze/remcached
• cachelot
• mdbm, zero-copy, netmap_sys
• groupcache

Malloc:

• Malloc implementations
• Benchmarks allocator
• https://github.com/redox-os/ralloc

[denji]

Malloc: scalloc, llalloc, jemalloc, hoard, tcmalloc, ptmalloc2, tbbmalloc_proxy, supermalloc

• https://github.com/cksystemsgroup/scalloc
  • https://github.com/cksystemsgroup/scalloc-artifact/blob/master/env.sh#L30