Repository: puzpuzpuz/xsync
Pull request #71 (2022-10-29 16:49:41)

Optimize Counter thread-to-stripe distribution
* The number of stripes is now calculated dynamically based on the number of cores and GOMAXPROCS
* The performance is close enough to the old one with 64 stripes while the memory footprint is significantly lower and, what's also important, unlucky distribution isn't a problem anymore

Note: this is a breaking change due to the new `NewCounter` method.

codecov-commenter: # [Codecov](https://codecov.io/gh/puzpuzpuz/xsync/pull/71?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov) Report
Base: **97.03**% // Head: **96.78**% // Decreases project coverage by **`-0.25%`** :warning:
> Coverage data is based on head [(`5d46309`)](https://codecov.io/gh/puzpuzpuz/xsync/pull/71?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov) compared to base [(`051117f`)](https://codecov.io/gh/puzpuzpuz/xsync/commit/051117f622763ecb6d970af5d2e8130bcb0e0e96?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov).
> Patch coverage: 91.17% of modified lines in pull request are covered.

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##             main      #71      +/-   ##
==========================================
- Coverage   97.03%   96.78%   -0.26%     
==========================================
  Files           6        6              
  Lines         912      932      +20     
==========================================
+ Hits          885      902      +17     
- Misses         22       24       +2     
- Partials        5        6       +1     
```


| [Impacted Files](https://codecov.io/gh/puzpuzpuz/xsync/pull/71?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov) | Coverage Δ | |
|---|---|---|
| [util.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/71/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov#diff-dXRpbC5nbw==) | `85.71% <81.25%> (-14.29%)` | :arrow_down: |
| [counter.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/71/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov#diff-Y291bnRlci5nbw==) | `100.00% <100.00%> (ø)` | |
| [rbmutex.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/71/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov#diff-cmJtdXRleC5nbw==) | `94.87% <100.00%> (ø)` | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/puzpuzpuz/xsync/pull/71?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrei+Pechkurov).


Patch:
diff --git a/README.md b/README.md
index 4793deb..3c80bb8 100644
--- a/README.md
+++ b/README.md
@@ -12,10 +12,10 @@ Benchmark results may be found [here](BENCHMARKS.md).
 
 ## Counter
 
-A `Counter` is a striped `int64` counter inspired by the j.u.c.a.LongAdder class from Java standard library.
+A `Counter` is a striped `int64` counter inspired by the `j.u.c.a.LongAdder` class from Java standard library.
 
 ```go
-var c xsync.Counter
+c := xsync.NewCounter()
 // increment and decrement the counter
 c.Inc()
 c.Dec()
@@ -23,7 +23,7 @@ c.Dec()
 v := c.Value()
 ```
 
-Works better in comparison with a single atomically updated int64 counter in high contention scenarios.
+Works better in comparison with a single atomically updated `int64` counter in high contention scenarios.
 
 ## Map
 
diff --git a/counter.go b/counter.go
index 3e77826..bd078ec 100644
--- a/counter.go
+++ b/counter.go
@@ -3,12 +3,8 @@ package xsync
 import (
 	"sync"
 	"sync/atomic"
-	"unsafe"
 )
 
-// number of counter stripes; must be a power of two
-const cstripes = 64
-
 // pool for P tokens
 var ptokenPool sync.Pool
 
@@ -29,7 +25,8 @@ type ptoken struct {
 //
 // A Counter must not be copied after first use.
 type Counter struct {
-	stripes [cstripes]cstripe
+	stripes []cstripe
+	mask    uint32
 }
 
 type cstripe struct {
@@ -38,6 +35,15 @@ type cstripe struct {
 	pad [cacheLineSize - 8]byte
 }
 
+func NewCounter() *Counter {
+	nstripes := nextPowOf2(parallelism())
+	c := Counter{
+		stripes: make([]cstripe, nstripes),
+		mask:    nstripes - 1,
+	}
+	return &c
+}
+
 // Inc increments the counter by 1.
 func (c *Counter) Inc() {
 	c.Add(1)
@@ -53,11 +59,17 @@ func (c *Counter) Add(delta int64) {
 	t, ok := ptokenPool.Get().(*ptoken)
 	if !ok {
 		t = new(ptoken)
-		// Since cstripes is a power of two, we can use & instead of %.
-		t.idx = uint32(mixhash64(uintptr(unsafe.Pointer(t))) & (cstripes - 1))
+		t.idx = fastrand() & c.mask
+	}
+	for {
+		stripe := &c.stripes[t.idx]
+		cnt := atomic.LoadInt64(&stripe.c)
+		if atomic.CompareAndSwapInt64(&stripe.c, cnt, cnt+delta) {
+			break
+		}
+		// Give a try with another randomly selected stripe.
+		t.idx = fastrand() & c.mask
 	}
-	stripe := &c.stripes[t.idx]
-	atomic.AddInt64(&stripe.c, delta)
 	ptokenPool.Put(t)
 }
 
@@ -66,7 +78,7 @@ func (c *Counter) Add(delta int64) {
 // presence of concurrent modifications of the counter.
 func (c *Counter) Value() int64 {
 	v := int64(0)
-	for i := 0; i < cstripes; i++ {
+	for i := 0; i < len(c.stripes); i++ {
 		stripe := &c.stripes[i]
 		v += atomic.LoadInt64(&stripe.c)
 	}
@@ -77,7 +89,7 @@ func (c *Counter) Value() int64 {
 // This method should only be used when it is known that there are
 // no concurrent modifications of the counter.
 func (c *Counter) Reset() {
-	for i := 0; i < cstripes; i++ {
+	for i := 0; i < len(c.stripes); i++ {
 		stripe := &c.stripes[i]
 		atomic.StoreInt64(&stripe.c, 0)
 	}
diff --git a/rbmutex.go b/rbmutex.go
index 836f019..10b8148 100644
--- a/rbmutex.go
+++ b/rbmutex.go
@@ -5,7 +5,6 @@ import (
 	"sync"
 	"sync/atomic"
 	"time"
-	"unsafe"
 )
 
 const (
@@ -59,7 +58,7 @@ func (m *RBMutex) RLock() *RToken {
 		if !ok {
 			t = new(RToken)
 			// Since rslots is a power of two, we can use & instead of %.
-			t.slot = uint32(mixhash64(uintptr(unsafe.Pointer(t))) & (rslots - 1))
+			t.slot = uint32(fastrand() & (rslots - 1))
 		}
 		if atomic.CompareAndSwapInt32(&m.readers[t.slot], 0, 1) {
 			if atomic.LoadInt32(&m.rbias) == 1 {
diff --git a/util.go b/util.go
index 70090a7..7a2b6be 100644
--- a/util.go
+++ b/util.go
@@ -2,6 +2,8 @@ package xsync
 
 import (
 	"hash/maphash"
+	"runtime"
+	_ "unsafe"
 )
 
 // test-only assert()-like flag
@@ -15,15 +17,6 @@ const (
 	cacheLineSize = 64
 )
 
-// mixhash64 is murmurhash3 64-bit finalizer.
-func mixhash64(v uintptr) uint64 {
-	x := uint64(v)
-	x = ((x >> 33) ^ x) * 0xff51afd7ed558ccd
-	x = ((x >> 33) ^ x) * 0xc4ceb9fe1a85ec53
-	x = (x >> 33) ^ x
-	return x
-}
-
 // hashString calculates a hash of s with the given seed.
 func hashString(seed maphash.Seed, s string) uint64 {
 	var h maphash.Hash
@@ -31,3 +24,29 @@ func hashString(seed maphash.Seed, s string) uint64 {
 	h.WriteString(s)
 	return h.Sum64()
 }
+
+// nextPowOf2 computes the next highest power of 2 of 32-bit v.
+// Source: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
+func nextPowOf2(v uint32) uint32 {
+	v--
+	v |= v >> 1
+	v |= v >> 2
+	v |= v >> 4
+	v |= v >> 8
+	v |= v >> 16
+	v++
+	return v
+}
+
+func parallelism() uint32 {
+	maxProcs := uint32(runtime.GOMAXPROCS(0))
+	numCores := uint32(runtime.NumCPU())
+	if maxProcs < numCores {
+		return maxProcs
+	}
+	return numCores
+}
+
+//go:noescape
+//go:linkname fastrand runtime.fastrand
+func fastrand() uint32


Test patch:
diff --git a/counter_test.go b/counter_test.go
index e65765b..2564852 100644
--- a/counter_test.go
+++ b/counter_test.go
@@ -9,7 +9,7 @@ import (
 )
 
 func TestCounterInc(t *testing.T) {
-	var c Counter
+	c := NewCounter()
 	for i := 0; i < 100; i++ {
 		if v := c.Value(); v != int64(i) {
 			t.Fatalf("got %v, want %d", v, i)
@@ -19,7 +19,7 @@ func TestCounterInc(t *testing.T) {
 }
 
 func TestCounterDec(t *testing.T) {
-	var c Counter
+	c := NewCounter()
 	for i := 0; i < 100; i++ {
 		if v := c.Value(); v != int64(-i) {
 			t.Fatalf("got %v, want %d", v, -i)
@@ -29,7 +29,7 @@ func TestCounterDec(t *testing.T) {
 }
 
 func TestCounterAdd(t *testing.T) {
-	var c Counter
+	c := NewCounter()
 	for i := 0; i < 100; i++ {
 		if v := c.Value(); v != int64(i*42) {
 			t.Fatalf("got %v, want %d", v, i*42)
@@ -39,7 +39,7 @@ func TestCounterAdd(t *testing.T) {
 }
 
 func TestCounterReset(t *testing.T) {
-	var c Counter
+	c := NewCounter()
 	c.Add(42)
 	if v := c.Value(); v != 42 {
 		t.Fatalf("got %v, want %d", v, 42)
@@ -59,11 +59,11 @@ func parallelIncrementor(c *Counter, numIncs int, cdone chan bool) {
 
 func doTestParallelIncrementors(t *testing.T, numModifiers, gomaxprocs int) {
 	runtime.GOMAXPROCS(gomaxprocs)
-	var c Counter
+	c := NewCounter()
 	cdone := make(chan bool)
 	numIncs := 10000
 	for i := 0; i < numModifiers; i++ {
-		go parallelIncrementor(&c, numIncs, cdone)
+		go parallelIncrementor(c, numIncs, cdone)
 	}
 	// Wait for the goroutines to finish.
 	for i := 0; i < numModifiers; i++ {
@@ -83,7 +83,7 @@ func TestCounterParallelIncrementors(t *testing.T) {
 }
 
 func benchmarkCounter(b *testing.B, writeRatio int) {
-	var c Counter
+	c := NewCounter()
 	b.RunParallel(func(pb *testing.PB) {
 		foo := 0
 		for pb.Next() {