Repository: puzpuzpuz/xsync
Pull request #54 (2022-10-23 21:38:02)

Use all available bits in map top hashes

codecov-commenter: # [Codecov](https://codecov.io/gh/puzpuzpuz/xsync/pull/54?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: **95.67**% // Increases project coverage by **`+0.66%`** :tada:
> Coverage data is based on head [(`256c8f7`)](https://codecov.io/gh/puzpuzpuz/xsync/pull/54?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov) compared to base [(`92ae151`)](https://codecov.io/gh/puzpuzpuz/xsync/commit/92ae151fd31844746b5c6643a52283f108c5f3f2?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      #54      +/-   ##
==========================================
+ Coverage   95.01%   95.67%   +0.66%     
==========================================
  Files           6        6              
  Lines         902      902              
==========================================
+ Hits          857      863       +6     
+ Misses         36       31       -5     
+ Partials        9        8       -1     
```


| [Impacted Files](https://codecov.io/gh/puzpuzpuz/xsync/pull/54?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/54/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov#diff-bWFwLmdv) | `96.02% <100.00%> (+1.16%)` | :arrow_up: |
| [rbmutex.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/54/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov#diff-cmJtdXRleC5nbw==) | `87.17% <0.00%> (-7.70%)` | :arrow_down: |
| [mapof.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/54/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov#diff-bWFwb2YuZ28=) | `94.73% <0.00%> (+1.23%)` | :arrow_up: |

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/54?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/map.go b/map.go
index 8adc8f9..b8707b0 100644
--- a/map.go
+++ b/map.go
@@ -29,11 +29,20 @@ const (
 	mapLoadFactor = 0.75
 	// minimal table size, i.e. number of buckets; thus, minimal map
 	// capacity can be calculated as entriesPerMapBucket*minMapTableLen
-	minMapTableLen = 16
+	minMapTableLen = 32
 	// maximum counter stripes to use; stands for around 8KB of memory
 	maxMapCounterLen = 64
 )
 
+var (
+	topHashMask       = uint64((1 << 20) - 1)
+	topHashEntryMasks = [3]uint64{
+		^(topHashMask << 44),
+		^(topHashMask << 24),
+		^(topHashMask << 4),
+	}
+)
+
 // Map is like a Go map[string]interface{} but is safe for concurrent
 // use by multiple goroutines without additional locking or
 // coordination. It follows the interface of sync.Map.
@@ -88,13 +97,12 @@ type bucket struct {
 	values [entriesPerMapBucket]unsafe.Pointer
 	// topHashMutex is a 2-in-1 value.
 	//
-	// First, it contains packed top 2 bytes (16 MSBs) of hash codes for
-	// keys stored in the bucket:
-	// | 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      |
+	// It contains packed top 20 bits (20 MSBs) of hash codes for keys
+	// stored in the bucket:
+	// | key 0's top hash | key 1's top hash | key 2's top hash | bitmap for keys | mutex |
+	// |      20 bits     |      20 bits     |      20 bits     |     3 bits      | 1 bit |
 	//
-	// Second, the least significant bit in the bitmap for keys byte
-	// is used for the mutex (TTAS spinlock).
+	// The least significant bit is used for the mutex (TTAS spinlock).
 	topHashMutex uint64
 }
 
@@ -610,19 +618,19 @@ func topHashMatch(hash, topHashes uint64, idx int) bool {
 		// Entry is not present.
 		return false
 	}
-	top := uint16(hash >> 48)
-	topHashes = topHashes >> (16 * (entriesPerMapBucket - idx))
-	return top == uint16(topHashes)
+	top := uint32(hash >> 44)
+	topHashes = topHashes >> (20*(2-idx) + 4)
+	return top == uint32(topHashes&topHashMask)
 }
 
 func storeTopHash(hash, topHashes uint64, idx int) uint64 {
 	// Zero out top hash at idx.
-	mask := uint64(65535) << (16 * (entriesPerMapBucket - idx))
-	topHashes = topHashes &^ mask
-	// Store top byte of the given hash.
-	top := (hash >> 48) << (16 * (entriesPerMapBucket - idx))
+	topHashes = topHashes & topHashEntryMasks[idx]
+	// Chop top 20 MSBs of the given hash and position them at idx.
+	top := (hash >> 44) << (20*(2-idx) + 4)
+	// Store the MSBs.
 	topHashes = topHashes | top
-	topHashes = topHashes | (1 << (idx + 1))
+	// Mark the entry as present.
 	return topHashes | (1 << (idx + 1))
 }
 


Test patch:
diff --git a/map_test.go b/map_test.go
index 26e2cb5..ad81e1e 100644
--- a/map_test.go
+++ b/map_test.go
@@ -619,7 +619,7 @@ func TestMapTopHashMutex_Set_WhileLocked(t *testing.T) {
 }
 
 func testMapTopHashMutex_Set(t *testing.T, topHashes *uint64) {
-	hash := uint64(0xd4ab000000000000) // top hash is 1101010010101011
+	hash := uint64(0b1101_0100_1010_1011_1101 << 44)
 	for i := 0; i < EntriesPerMapBucket; i++ {
 		if TopHashMatch(hash, *topHashes, i) {
 			t.Errorf("top hash match for all zeros for index %d", i)
@@ -653,7 +653,7 @@ func TestMapTopHashMutex_Delete_WhileLocked(t *testing.T) {
 }
 
 func testMapTopHashMutex_Delete(t *testing.T, topHashes *uint64) {
-	hash := uint64(0xabababababababab) // top hash is 1010101110101011
+	hash := uint64(0xababaaaaaaaaaaaa) // top hash is 1010_1011_1010_1011_1010
 	for i := 0; i < EntriesPerMapBucket; i++ {
 		*topHashes = StoreTopHash(hash, *topHashes, i)
 		ones := bits.OnesCount64(*topHashes)
@@ -683,8 +683,8 @@ func TestMapTopHashMutex_SetAfterDelete_WhileLocked(t *testing.T) {
 }
 
 func testMapTopHashMutex_SetAfterDelete(t *testing.T, topHashes *uint64) {
-	hashOne := uint64(0xd4d4000000000000) // top hash is 1101010011010100
-	hashTwo := uint64(0xabab000000000000) // top hash is 1010101110101011
+	hashOne := uint64(0b1101_0100_1101_0100_1101 << 44)
+	hashTwo := uint64(0b1010_1011_1010_1011_1010 << 44)
 	idx := 2
 
 	*topHashes = StoreTopHash(hashOne, *topHashes, idx)