6 ms·

Cmapv2: A high performance, concurrent map

41 points by sirgallo 1y ago

sirgallo 1y ago
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 1y ago
  Looks interesting, it would be nice to have the performance comparisons front and center on the readme.
  - sirgallo 1y ago
    sounds good, they are a bit hidden right now. also am most likely going to update the other docs.
- latchkey 1y ago
  I've been using this one for years, can you do comparisons against it? https://github.com/cornelk/hashmap https://github.com/cornelk/hashmap
  - jzelinskie 1y ago
    Another good comparison would be against https://pkg.go.dev/github.com/puzpuzpuz/xsync/v3#Map https://pkg.go.dev/github.com/puzpuzpuz/xsync/v3#Map
    - sirgallo 1y ago
      definitely, I can expand my comparisons and benchmarks
      - latchkey 1y ago
        Honestly, if you're better than the rest, I would suggest collaborating with the existing solutions.
  - sirgallo 1y ago
    yes I can take a look, thanks for passing that along
gttalbot 1y ago
Is it anywhere close to swisstables?
- vlovich123 1y ago
  No because swisstables generally don't do concurrency (i.e. concurrency ==> atomics which are inherently more expensive due to HW reasons).
kiitos 1y ago
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/280e3017ae4ba212f6f8b121e342b7606e1cfc0e/operation.go#L25-L58 https://github.com/sirgallo/cmapv2/blob/280e3017ae4ba212f6f8...
- kiitos 1y ago
  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 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-L46 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#L59-L67 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#L18-L57 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#L119-L126 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 1y ago
Here's a better implementation if anyone is interested (not mine) https://github.com/puzpuzpuz/xsync#map https://github.com/puzpuzpuz/xsync#map

41 points by sirgallo 1y ago

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 1y ago
Looks interesting, it would be nice to have the performance comparisons front and center on the readme.
- sirgallo 1y ago
  sounds good, they are a bit hidden right now. also am most likely going to update the other docs.
latchkey 1y ago
I've been using this one for years, can you do comparisons against it? https://github.com/cornelk/hashmap https://github.com/cornelk/hashmap
- jzelinskie 1y ago
  Another good comparison would be against https://pkg.go.dev/github.com/puzpuzpuz/xsync/v3#Map https://pkg.go.dev/github.com/puzpuzpuz/xsync/v3#Map
  - sirgallo 1y ago
    definitely, I can expand my comparisons and benchmarks
    - latchkey 1y ago
      Honestly, if you're better than the rest, I would suggest collaborating with the existing solutions.
- sirgallo 1y ago
  yes I can take a look, thanks for passing that along

gttalbot 1y ago

Is it anywhere close to swisstables?

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

kiitos 1y ago

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/280e3017ae4ba212f6f8b121e342b7606e1cfc0e/operation.go#L25-L58 https://github.com/sirgallo/cmapv2/blob/280e3017ae4ba212f6f8...

kiitos 1y ago
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 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-L46 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#L59-L67 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#L18-L57 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#L119-L126 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 1y ago

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