I worked out how you would do an open addressing hashmap in c++ using
Cliff Clicks algorithm just for fun. Readers would be wait-free and
writers would be completly lock-free. All the necessary info would be
in the array element cell rather than being linked would lose the array scanning performance advantage putting it on par with chained hashing performance wise.

Not going to implement it as there are probably a bunch of these out
there already but it was good practice in how to implement concurrent
semantics correctly in different ways in lock-free programming.

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 10/21/2026 12:39 PM, Joseph Seigh wrote:

I worked out how you would do an open addressing hashmap in c++ using
Cliff Clicks algorithm just for fun.ÿ Readers would be wait-free and
writers would be completly lock-free.ÿ All the necessary info would be
in the array element cell rather than being linked would lose the array scanning performance advantage putting it on par with chained hashing performance wise.

Not going to implement it as there are probably a bunch of these out
there already but it was good practice in how to implement concurrent semantics correctly in different ways in lock-free programming.

Oh yeah. I have read many papers on concurrent hash maps in the past.
Too many to count now. The simple one, hash a pointer into an array.
Link it. Collisions simply link. The readers just use RCU and iterate
the shit out of it. The writers are all lock-free. Removing them can be interesting for the writers. Didn't you do an old tree thing way back in
cpt?

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 10/21/26 3:57 PM, Chris M. Thomasson wrote:

On 10/21/2026 12:39 PM, Joseph Seigh wrote:

I worked out how you would do an open addressing hashmap in c++ using
Cliff Clicks algorithm just for fun.ÿ Readers would be wait-free and
writers would be completly lock-free.ÿ All the necessary info would be
in the array element cell rather than being linked would lose the array
scanning performance advantage putting it on par with chained hashing
performance wise.

Not going to implement it as there are probably a bunch of these out
there already but it was good practice in how to implement concurrent
semantics correctly in different ways in lock-free programming.

Oh yeah. I have read many papers on concurrent hash maps in the past.
Too many to count now. The simple one, hash a pointer into an array.
Link it. Collisions simply link. The readers just use RCU and iterate
the shit out of it. The writers are all lock-free. Removing them can be interesting for the writers. Didn't you do an old tree thing way back in cpt?

The thing you are describing is chained hashing. The array entries are
called hash buckets which are linked lists.

Removing nodes isn't real tricky. Just tombstone the entries and then
remove them at your leisure using lock-free list manipulation.

With a linked list you have those dependent loads and a higher
likelyhood of cache thrashing. Not so much with array scanning
plus you can fetch ahead into cache.

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 10/21/2026 5:05 PM, Joseph Seigh wrote:

On 10/21/26 3:57 PM, Chris M. Thomasson wrote:

On 10/21/2026 12:39 PM, Joseph Seigh wrote:

I worked out how you would do an open addressing hashmap in c++ using
Cliff Clicks algorithm just for fun.ÿ Readers would be wait-free and
writers would be completly lock-free.ÿ All the necessary info would be
in the array element cell rather than being linked would lose the array
scanning performance advantage putting it on par with chained hashing
performance wise.

Not going to implement it as there are probably a bunch of these out
there already but it was good practice in how to implement concurrent
semantics correctly in different ways in lock-free programming.

Oh yeah. I have read many papers on concurrent hash maps in the past.
Too many to count now. The simple one, hash a pointer into an array.
Link it. Collisions simply link. The readers just use RCU and iterate
the shit out of it. The writers are all lock-free. Removing them can
be interesting for the writers. Didn't you do an old tree thing way
back in cpt?

The thing you are describing is chained hashing.ÿ The array entries are called hash buckets which are linked lists.

Removing nodes isn't real tricky.ÿ Just tombstone the entries and then
remove them at your leisure using lock-free list manipulation.

With a linked list you have those dependent loads and a higher
likelyhood of cache thrashing.ÿ Not so much with array scanning
plus you can fetch ahead into cache.

Totally agreed. For some reason, I remember making one way back using
arrays around 2003 ish, iirc. Never posted it, got side tracked. But it
used Cantor Pairing for a hash: Completely experimental. I cannot
remember if it did any good wrt putting it under load.

Actually, and fwiw, that reminds me. At least Cantor pairing makes some
good music... Here is an example of mine:
_______________
(Cantor Pairing)
https://youtu.be/XkwgJt5bxKI

Another MIDI try using a Cantor pairing as a bass guitar to create two
notes out of a monotonically increasing index starting at zero. Has an interesting sound. Some of the drums, channel 10, are mod 3. ;^) _______________

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 10/21/26 3:39 PM, Joseph Seigh wrote:

Not going to implement it as there are probably a bunch of these out
there already but it was good practice in how to implement concurrent semantics correctly in different ways in lock-free programming.

One of the downsides of focusing on the semantics rather than the implementation is realizing you are using more synchronization than
is needed. Scratch one unnecessary hack.

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

It's no problem if a concurrent hash map uses mutexes, but just one
per bucket and a number of buckets that there's a small likehood of
a collision. With a futex the amount of storage needed is very small.
So no need for lock free stuff.


--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 10/23/2026 8:46 AM, Bonita Montero wrote:

It's no problem if a concurrent hash map uses mutexes, but just one
per bucket and a number of buckets that there's a small likehood of
a collision. With a futex the amount of storage needed is very small.
So no need for lock free stuff.

Are you sure about that?

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 10/23/26 11:46 AM, Bonita Montero wrote:

It's no problem if a concurrent hash map uses mutexes, but just one
per bucket and a number of buckets that there's a small likehood of
a collision. With a futex the amount of storage needed is very small.
So no need for lock free stuff.

https://web.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf



--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)