Repository: puzpuzpuz/xsync
Pull request #52 (2022-10-23 13:40:22)

Reduce map bucket size to 1CL
Top hashes now include 2 bytes instead of a single byte which improves top hash look up efficiency

codecov-commenter: # [Codecov](https://codecov.io/gh/puzpuzpuz/xsync/pull/52?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov) Report
Base: **95.01**% // Head: **94.56**% // Decreases project coverage by **`-0.44%`** :warning:
> Coverage data is based on head [(`9462af8`)](https://codecov.io/gh/puzpuzpuz/xsync/pull/52?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov) compared to base [(`458dbca`)](https://codecov.io/gh/puzpuzpuz/xsync/commit/458dbca5936dc3abc297fe6ab804f0c923bf20b1?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov).
> Patch coverage: 100.00% of modified lines in pull request are covered.

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


```diff
@@            Coverage Diff             @@
##             main      #52      +/-   ##
==========================================
- Coverage   95.01%   94.56%   -0.45%     
==========================================
  Files           6        6              
  Lines         902      902              
==========================================
- Hits          857      853       -4     
- Misses         36       39       +3     
- Partials        9       10       +1     
```


| [Impacted Files](https://codecov.io/gh/puzpuzpuz/xsync/pull/52?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov) | Coverage Δ | |
|---|---|---|
| [map.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/52/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov#diff-bWFwLmdv) | `93.92% <100.00%> (-0.94%)` | :arrow_down: |

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=Andrey+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=Andrey+Pechkurov)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/puzpuzpuz/xsync/pull/52?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+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=Andrey+Pechkurov).


Patch:
diff --git a/.github/workflows/build-1.18.yml b/.github/workflows/build-1.17.yml
similarity index 67%
rename from .github/workflows/build-1.18.yml
rename to .github/workflows/build-1.17.yml
index 058c88b..ac4c9bc 100644
--- a/.github/workflows/build-1.18.yml
+++ b/.github/workflows/build-1.17.yml
@@ -1,4 +1,4 @@
-name: build-1.18
+name: build-1.17
 on: [push]
 
 jobs:
@@ -6,7 +6,7 @@ jobs:
     runs-on: ubuntu-latest
     strategy:
       matrix:
-        go-version: [1.18.x]
+        go-version: [1.17.x]
     name: Build with Go ${{ matrix.go-version }}
     steps:
       - uses: actions/checkout@v2.3.4
@@ -16,6 +16,14 @@ jobs:
           stable: false
           go-version: ${{ matrix.go-version }}
 
+      - name: Install staticcheck
+        run: go get honnef.co/go/tools/cmd/staticcheck
+
+      - name: Run linters
+        run: |
+          go vet ./...
+          staticcheck ./...
+
       - name: Run tests
         run: go test -v ./...
 
diff --git a/.github/workflows/build-32-bit.yml b/.github/workflows/build-32-bit.yml
index 3812652..db5d108 100644
--- a/.github/workflows/build-32-bit.yml
+++ b/.github/workflows/build-32-bit.yml
@@ -6,7 +6,7 @@ jobs:
     runs-on: ubuntu-latest
     strategy:
       matrix:
-        go-version: [1.18.x]
+        go-version: [1.19.x]
     name: Build with Go ${{ matrix.go-version }} 32-bit
     steps:
       - uses: actions/checkout@v2.3.4
diff --git a/.github/workflows/build.yml b/.github/workflows/build.yml
index 9a97d48..62d8ea5 100644
--- a/.github/workflows/build.yml
+++ b/.github/workflows/build.yml
@@ -6,7 +6,7 @@ jobs:
     runs-on: ubuntu-latest
     strategy:
       matrix:
-        go-version: [1.17.x]
+        go-version: [1.19.x]
     name: Build with Go ${{ matrix.go-version }}
     steps:
       - uses: actions/checkout@v2.3.4
@@ -16,14 +16,6 @@ jobs:
           stable: false
           go-version: ${{ matrix.go-version }}
 
-      - name: Install staticcheck
-        run: go get honnef.co/go/tools/cmd/staticcheck
-
-      - name: Run linters
-        run: |
-          go vet ./...
-          staticcheck ./...
-
       - name: Run tests
         run: go test -v ./...
 
diff --git a/.github/workflows/coverage.yml b/.github/workflows/coverage.yml
index 19d15e5..5ba6773 100644
--- a/.github/workflows/coverage.yml
+++ b/.github/workflows/coverage.yml
@@ -6,7 +6,7 @@ jobs:
     runs-on: ubuntu-latest
     strategy:
       matrix:
-        go-version: [1.18.x]
+        go-version: [1.19.x]
     name: Build with Go ${{ matrix.go-version }}
     steps:
       - uses: actions/checkout@v2.3.4
diff --git a/map.go b/map.go
index f48f7ea..8adc8f9 100644
--- a/map.go
+++ b/map.go
@@ -17,16 +17,16 @@ const (
 )
 
 const (
-	// number of entries per bucket; 7 entries lead to size of 128B
-	// (2 cache lines) on 64-bit machines
-	entriesPerMapBucket = 7
+	// number of entries per bucket; 3 entries lead to size of 64B
+	// (one cache line) on 64-bit machines
+	entriesPerMapBucket = 3
 	// threshold fraction of table occupation to start a table shrinking
 	// when deleting the last entry in a bucket chain
 	mapShrinkFraction = 128
 	// map load factor to trigger a table resize during insertion;
 	// a map holds up to mapLoadFactor*entriesPerMapBucket*mapTableLen
-	// key-value pairs
-	mapLoadFactor = 1.0
+	// key-value pairs (this is a soft limit)
+	mapLoadFactor = 0.75
 	// minimal table size, i.e. number of buckets; thus, minimal map
 	// capacity can be calculated as entriesPerMapBucket*minMapTableLen
 	minMapTableLen = 16
@@ -78,7 +78,7 @@ type counterStripe struct {
 
 type bucketPadded struct {
 	//lint:ignore U1000 ensure each bucket takes two cache lines on both 32 and 64-bit archs
-	pad [2*cacheLineSize - unsafe.Sizeof(bucket{})]byte
+	pad [cacheLineSize - unsafe.Sizeof(bucket{})]byte
 	bucket
 }
 
@@ -88,10 +88,10 @@ type bucket struct {
 	values [entriesPerMapBucket]unsafe.Pointer
 	// topHashMutex is a 2-in-1 value.
 	//
-	// First, it contains packed top bytes (8 MSBs) of hash codes for
+	// First, it contains packed top 2 bytes (16 MSBs) of hash codes for
 	// keys stored in the bucket:
-	// | key 0's top hash | ... | key 7's top hash | bitmap for keys |
-	// |      1 byte      | ... |      1 byte      |     1 byte      |
+	// | key 0's top hash | key 1's top hash | key 2's top hash | unused | bitmap for keys |
+	// |      2 bytes     |      2 bytes     |      2 bytes     | 1 byte |     1 byte      |
 	//
 	// Second, the least significant bit in the bitmap for keys byte
 	// is used for the mutex (TTAS spinlock).
@@ -610,17 +610,17 @@ func topHashMatch(hash, topHashes uint64, idx int) bool {
 		// Entry is not present.
 		return false
 	}
-	top := uint8(hash >> 56)
-	topHashes = topHashes >> (8 * (entriesPerMapBucket - idx))
-	return top == uint8(topHashes)
+	top := uint16(hash >> 48)
+	topHashes = topHashes >> (16 * (entriesPerMapBucket - idx))
+	return top == uint16(topHashes)
 }
 
 func storeTopHash(hash, topHashes uint64, idx int) uint64 {
 	// Zero out top hash at idx.
-	mask := uint64(255) << (8 * (entriesPerMapBucket - idx))
+	mask := uint64(65535) << (16 * (entriesPerMapBucket - idx))
 	topHashes = topHashes &^ mask
 	// Store top byte of the given hash.
-	top := (hash >> 56) << (8 * (entriesPerMapBucket - idx))
+	top := (hash >> 48) << (16 * (entriesPerMapBucket - idx))
 	topHashes = topHashes | top
 	topHashes = topHashes | (1 << (idx + 1))
 	return topHashes | (1 << (idx + 1))


Test patch:
diff --git a/map_test.go b/map_test.go
index 3bad123..26e2cb5 100644
--- a/map_test.go
+++ b/map_test.go
@@ -42,12 +42,9 @@ func init() {
 }
 
 func TestMap_BucketStructSize(t *testing.T) {
-	if bits.UintSize != 64 {
-		return // skip for 32-bit builds
-	}
 	size := unsafe.Sizeof(BucketPadded{})
-	if size != 128 {
-		t.Errorf("size of 128B (2 cache lines) is expected, got: %d", size)
+	if size != 64 {
+		t.Errorf("size of 64B (one cache line) is expected, got: %d", size)
 	}
 }
 
@@ -622,7 +619,7 @@ func TestMapTopHashMutex_Set_WhileLocked(t *testing.T) {
 }
 
 func testMapTopHashMutex_Set(t *testing.T, topHashes *uint64) {
-	hash := uint64(0xd400000000000000) // top hash is 11010100
+	hash := uint64(0xd4ab000000000000) // top hash is 1101010010101011
 	for i := 0; i < EntriesPerMapBucket; i++ {
 		if TopHashMatch(hash, *topHashes, i) {
 			t.Errorf("top hash match for all zeros for index %d", i)
@@ -656,7 +653,7 @@ func TestMapTopHashMutex_Delete_WhileLocked(t *testing.T) {
 }
 
 func testMapTopHashMutex_Delete(t *testing.T, topHashes *uint64) {
-	hash := uint64(0xabababababababab) // top hash is 10101011
+	hash := uint64(0xabababababababab) // top hash is 1010101110101011
 	for i := 0; i < EntriesPerMapBucket; i++ {
 		*topHashes = StoreTopHash(hash, *topHashes, i)
 		ones := bits.OnesCount64(*topHashes)
@@ -686,9 +683,9 @@ func TestMapTopHashMutex_SetAfterDelete_WhileLocked(t *testing.T) {
 }
 
 func testMapTopHashMutex_SetAfterDelete(t *testing.T, topHashes *uint64) {
-	hashOne := uint64(0xd400000000000000) // top hash is 11010100
-	hashTwo := uint64(0xab00000000000000) // top hash is 10101011
-	idx := 3
+	hashOne := uint64(0xd4d4000000000000) // top hash is 1101010011010100
+	hashTwo := uint64(0xabab000000000000) // top hash is 1010101110101011
+	idx := 2
 
 	*topHashes = StoreTopHash(hashOne, *topHashes, idx)
 	if !TopHashMatch(hashOne, *topHashes, idx) {