sync: improve Map performance with lock free list

[alphadose]

Reference -> https://github.com/alphadose/haxmap

Hashing algorithm used -> https://github.com/Cyan4973/xxHash

Map buckets were implemented using Harris lock-free list

[ianlancetaylor]

If there are no API changes, this doesn't need to be a proposal, so taking out of the proposal process.

CC @bcmills

[mvdan]

Worth noting that this uses the xxhash hashing algorithm, which I believe is not in the standard library right now. Could we use Go's maphash instead, perhaps?

[egonelbre]

Looks neat. Although, while testing the implementation, this benchmark doesn't seem to complete:

func BenchmarkHaxMapReadsConcurrentWritesEmpty(b *testing.B) {
	const mapSize = 256
	const epochs = 10000

	m := haxmap.New[uintptr, uintptr](mapSize)
	var writer uintptr
	b.RunParallel(func(pb *testing.PB) {
		if atomic.AddUintptr(&writer, 1)&1 == 1 {
			for pb.Next() {
				for i := uintptr(0); i < epochs; i++ {
					m.Set(i, i)
				}
			}
		} else {
			for pb.Next() {
				for i := uintptr(0); i < epochs; i++ {
					m.Get(i)
				}
			}
		}
	})
}

Running with concurrency 32, amd64. If I change mapSize = 1 in the tests, then other tests also seem to fail.

I also recommend using the same resize algorithm as map uses, otherwise you might be benchmarking parts of the sizing algorithms instead of the lock-free part.

And as @mvdan mentioned, try benchmarking using the same hashing algorithm as std; this shows that the benefit isn't just from replacing the hashing algorithm.

[alphadose]

Running with concurrency 32, amd64. If I change mapSize = 1 in the tests, then other tests also seem to fail.

Will look into it

I also recommend using the same resize algorithm as map uses, otherwise you might be benchmarking parts of the sizing algorithms instead of the lock-free part.

Agreed I was also looking to improve the current resizing algorithm of haxmap as well

And as @mvdan mentioned, try benchmarking using the same hashing algorithm as std; this shows that the benefit isn't just from replacing the hashing algorithm.

Got it, I will try benchmarking with golang std hash as well and compare it with the current xxHash based implementation

[alphadose]

Looks neat. Although, while testing the implementation, this benchmark doesn't seem to complete:

This happens because of small map size and lots of grow operations which run as goroutines. These goroutines cause the slowdown.

One option is handle grow() synchronously with the writer threads

There is an open issue for this as well alphadose/haxmap#2

[egonelbre]

Also, I recommend comparing with #54766

[bcmills]

Compare #47643 (CC @puzpuzpuz), #21035, #21032.

How would this affect pointer overheads in the steady state? (See #21031.)

[gopherbot]

Timed out in state WaitingForInfo. Closing.

(I am just a bot, though. Please speak up if this is a mistake or you have the requested information.)

[alphadose]

I was fixing most of the issues in haxmap to make it a stable version as in https://github.com/alphadose/haxmap/releases/tag/v1.0.0

Wanted it to work correctly before making any comparisons

Hence there is no need to close this issue, it is being actively worked upon

[mvdan]

That's fine. Typically we use the bot to close issues which were waiting on a reply for too long because the majority simply become stale and non-actionable.

[alphadose]

@mvdan comparison of xxHash vs golang maphash in the context of haxmap over 20 cases

name                      time/op
XXHashReadsOnly-8         7.18µs ± 6%
XXHashReadsWithWrites-8   8.50µs ± 5%
MapHashReadsOnly-8        9.64µs ± 3%
MapHashReadsWithWrites-8  11.3µs ± 3%

name                      alloc/op
XXHashReadsOnly-8          0.00B
XXHashReadsWithWrites-8   1.24kB ± 4%
MapHashReadsOnly-8         0.00B
MapHashReadsWithWrites-8  1.38kB ± 5%

name                      allocs/op
XXHashReadsOnly-8           0.00
XXHashReadsWithWrites-8      155 ± 4%
MapHashReadsOnly-8          0.00
MapHashReadsWithWrites-8     172 ± 5%

Benchmarking code is available here https://github.com/alphadose/haxmap/blob/hash-comparison/benchmarks/map_test.go, kindly crosscheck to ensure the comparisons are done fairly