Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Benchmarks for concurrent hash map implementations in Go

github.com

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Benchmarks for concurrent hash map implementations in Go

#11

Post by hinkley »

tl2do wrote: post #7

I ran benchmarks comparing xsync.Map's memory allocation against orcaman/concurrent-map. Pure overwrite workload (pre-allocated values): xsync.Map: 24 B/op 1 alloc/op 31.89 ns/op orcaman/concurrent-map: 0 B/op 0 alloc/op 70.72 ns/op Real-world mixed (80% overwrites, 20% new): xsync.Map: 57 B/op 2 allocs/op 218.1 ns/op orcaman/concurrent-map: 63 B/op 3 allocs/op 283.1 ns/op Go maps reuse memory on overwrites, which is…

How does reuse avoid false sharing between cores? Since this is concurrent hashmap we are talking about.

Re: Benchmarks for concurrent hash map implementations in Go

#13

Post by tl2do »

hinkley wrote: post #11
tl2do wrote: post #7

I ran benchmarks comparing xsync.Map's memory allocation against orcaman/concurrent-map. Pure overwrite workload (pre-allocated values): xsync.Map: 24 B/op 1 alloc/op 31.89 ns/op orcaman/concurrent-map: 0 B/op 0 alloc/op 70.72 ns/op Real-world mixed (80% overwrites, 20% new): xsync.Map: 57 B/op 2 allocs/op 218.1 ns/op orcaman/concurrent-map: 63 B/op 3 allocs/op 283.1 ns/op Go maps reuse memory on overwrites, which is…

How does reuse avoid false sharing between cores? Since this is concurrent hashmap we are talking about.

I focused on B/op because it was the only apparent weakness I saw. My “reuse” note was about allocation behavior, not false sharing. We’re talking about different concerns.

Re: Benchmarks for concurrent hash map implementations in Go

#15

Post by hinkley »

tl2do wrote: post #13
hinkley wrote: post #11

Earlier quoted context omitted.

How does reuse avoid false sharing between cores? Since this is concurrent hashmap we are talking about.

I focused on B/op because it was the only apparent weakness I saw. My “reuse” note was about allocation behavior, not false sharing. We’re talking about different concerns.

Allocation behavior when one core deletes and another adds and they reuse the same memory allocation is what I thought you meant.

Is that what you meant? Because if it is then you now have potential for the problem I described.

Re: Benchmarks for concurrent hash map implementations in Go

#16

Post by puzpuzpuz-hn »

withinboredom wrote: post #4

Looks good! There's an important thing missing from the benchmarks though: - cpu usage under concurrency: many of these spin-lock or use atomics, which can use up to 100% cpu time just spinning. - latency under concurrency: atomics cause cache-line bouncing which kills latency, especially p99 latency

Yup, that's a valid point. I'll consider adding these metrics.

Re: Benchmarks for concurrent hash map implementations in Go

#17

Post by puzpuzpuz-hn »

umairnadeem123 wrote: post #14

[dead]

Allocation rates are also compared. Long story short, vanilla map + RWMutex (or a sharded variant of it like orcaman/concurrent-map) is the way to go if you want to minimize allocations. On the other hand, if reads dominate your workload, using one of custom concurrent maps may be a good idea.

Re: Benchmarks for concurrent hash map implementations in Go

#19

Post by puzpuzpuz-hn »

mappu wrote: post #9

A few release cycles back, Swiss Maps became popular (i think, particular thanks to CockroachDB) as a replacement for standard Go map[K]V. Later, Go's stdlib map implementation was updated to use Swiss Maps internally and everyone benefited. Do you think the xsync.Map could be considered for upstreaming? Especially if it outperforms sync.Map at all the same use cases.

There are multiple GH issues around better sync.Map. Among other alternatives, xsync.Map is also mentioned. But Golang core team doesn't seem interested in sync.Map (or a generic variant of it) improvements.

Re: Benchmarks for concurrent hash map implementations in Go

#20

Post by puzpuzpuz-hn »

kgeist wrote: post #12

Orcaman is a very straightforward implementation (just sharded RW locks and backing maps), but it limits the number of shards to a fixed 32. I wonder what the benchmarks would look like if the shard count were increased to 64, 128, etc.

My box is 12c/24t only, so it won't make any difference. But on a beefy box, it may improve performance in high cardinality key scenarios.
Post reply on HN