Cmapv2: A high performance, concurrent map

[kiitos]

This repo is completely unsound, code like [1] is pervasive and demonstrates a total misunderstanding of what guarantees are provided -- or, really, not provided -- by "atomic" reads of unsafe.Pointer values. Data races everywhere!

Not safe, do not pass go, do not collect $200, absolutely do not use.

[1] https://github.com/sirgallo/cmapv2/blob/280e3017ae4ba212f6f8...

[sapiogram]

Thank you for debunking it so I didn't have to. I don't think I've ever seen someone post a low-level/concurrent data structure in Go that wasn't wildly unsound, so I assumed this was too.

[kiitos]

Be more specific? OK

---

CopyNode broken

`CopyNode` duplicates only the parent; every child pointer is still shared

    nodeCopy.setChildren(make([]*node, len(n.children)))
    copy(nodeCopy.children, n.children) // pointers reused

https://github.com/sirgallo/cmapv2/blob/main/node.go#L11-L17

Any later mutation (for example `setValue`) writes through those shared pointers, so readers and historical snapshots are modified concurrently -- invalid, data race, memory model violation

---

Bitmap corruption

`SetBit` uses XOR rather than “set”:

    func SetBit(bitmap uint32, position int) uint32 { return bitmap ^ (1 << position) }

https://github.com/sirgallo/cmapv2/blob/main/utils.go#L41-L4...

Calling it twice on the same index flips the bit back to 0. During branch-creation on insert and during delete, this function is invoked multiple times on the same index, clearing a bit that should remain set and leaving orphaned children.

---

Invalid assumptions re: interior pointers

Only the root pointer is read with `atomic.LoadPointer`. All deeper fields like `children[pos]`, `bitmap`, and the byte-slice keys/values, are accessed directly after a successful CAS. Readers therefore race with writers that mutate these fields in place -- race condition, memory model violation, etc.

    pos := cMap.getPosition(node.Bitmap(), hash, level)
    if node.Child(pos).IsLeaf() && bytes.Equal(key, node.Child(pos).Key()) {
        return node.Child(pos).Value()
    }

https://github.com/sirgallo/cmapv2/blob/main/operation.go#L5...

---

All xxxRecursive functions rely on those invalid interior pointer assumptions

Sequence in `putRecursive` / `deleteRecursive` is

    1. `curr := atomic.LoadPointer(ptr)`
    2. Build `nodeCopy`
    3. Recurse; grandchildren are mutated in place
    4. `atomic.CompareAndSwap(ptr, curr, nodeCopy)`

https://github.com/sirgallo/cmapv2/blob/main/operation.go#L1...

If another goroutine has already swapped in a different copy of `curr` (and mutated it) the CAS still succeeds because the pointer value is unchanged, merging incompatible sub-tries and corrupting the data

---

Use-after-free in sync.Pool

On CAS failure the freshly built `nodeCopy` is immediately returned to a `sync.Pool` -- undefined behavior

    cMap.pool.PutNode(nodeCopy) // may race with outstanding readers

https://github.com/sirgallo/cmapv2/blob/main/operation.go#L1...

Other goroutines still holding references to that node can now access a reclaimed object, oops.

---

K/V Aliasing

Keys and values (both []byte slices, which are not safe for concurrent r/w access) are stored by reference, a mistake:

    n.setKey(key)
    n.setValue(value)

If the caller mutates those slices later (or concurrently in another goroutine), data races ahoy

---

Reader panics, etc.

    - `getRecursive` accesses `children[pos]` without bounds or nil checks, concurrent shrink can make `pos` invalid
    - `GetIndex` allows a negative `shiftSize` once `level >= 7` with `chunkSize = 5`, producing nonsense indices and potential slice-out-of-bounds

[derekperkins]

Here's a better implementation if anyone is interested (not mine) https://github.com/puzpuzpuz/xsync#map

[sirgallo]

Performance comparisons are made against go sync.Map, with cmapv2 on par or sometimes exceeding is on different workloads. It is both lock-free and thread safe, using atomic operations. It also supports sharding out of the box. cmapv2 with 10m k/v pairs where keys and values are 64bytes was able to achieve 1.5m w/s and 3m r/s.

[pstuart]

Looks interesting, it would be nice to have the performance comparisons front and center on the readme.

[latchkey]

I've been using this one for years, can you do comparisons against it?

https://github.com/cornelk/hashmap

[gttalbot]

Is it anywhere close to swisstables?

[vlovich123]

No because swisstables generally don't do concurrency (i.e. concurrency ==> atomics which are inherently more expensive due to HW reasons).