joh.dev
A map using a lock-free concurrency using left-right algo, written in Go
1package leftright
2
3import (
4 "math"
5 "runtime"
6 "sync/atomic"
7 "testing"
8)
9
10func TestHundred(t *testing.T) { testHundred(t) }
11func BenchmarkTestHundred(b *testing.B) {
12 for i := 0; i < b.N; i++ {
13 testHundred(b)
14 }
15}
16func testHundred(t testing.TB) {
17 lrm := New[int, int]()
18
19 rh := lrm.NewReadHandler()
20 defer rh.Close()
21
22 for i := 1; i < 100; i += 2 {
23 k, v := i, i
24
25 lrm.Set(k, v)
26 }
27
28 lrm.Commit()
29
30 for i := 1; i < 100; i += 2 {
31 k, v := i, i
32
33 rh.Enter()
34 if _v := rh.Get(k); _v != v {
35
36 t.Errorf("Get(%d) want %d, got %d", k, v, _v)
37 }
38 rh.Leave()
39 }
40
41 for i := 0; i < 100; i += 2 {
42 k, v := i, i
43 lrm.Set(k, v)
44 }
45
46 lrm.Commit()
47
48 for i := 0; i < 100; i++ {
49 rh.Enter()
50 k, v := i, i
51
52 if _v := rh.Get(k); _v != v {
53 t.Errorf("Get(%d) want %d, got %d", k, v, _v)
54 }
55 rh.Leave()
56 }
57
58 lrm.Commit()
59
60 rh.Enter()
61 for i := 0; i < 100; i++ {
62 k, v := i, i
63
64 if _v := rh.Get(k); _v != v {
65 t.Errorf("Get(%d) want %d, got %d", k, v, _v)
66 }
67 }
68 rh.Leave()
69
70 for i := 0; i < 100; i += 2 {
71 k := i
72 lrm.Delete(k)
73 }
74
75 lrm.Commit()
76
77 rh.Enter()
78 for i := 0; i < 100; i++ {
79 k, v := i, i
80
81 _v, ok := rh.GetOK(k)
82 if i%2 == 0 {
83 if ok || _v != 0 {
84 t.Errorf("GetOK(%d), want (0, false), got (%d, %t)", i, _v, ok)
85 }
86 } else {
87 if !ok || _v != v {
88 t.Errorf("GetOK(%d), want (%d, true), got (%d, %t)", i, v, _v, ok)
89 }
90 }
91 }
92 rh.Leave()
93
94 lrm.Commit()
95
96 rh.Enter()
97 for i := 0; i < 100; i++ {
98 k, v := i, i
99
100 _v, ok := rh.GetOK(k)
101 if i%2 == 0 {
102 if ok || _v != 0 {
103 t.Errorf("GetOK(%d), want (0, false), got (%d, %t)", i, _v, ok)
104 }
105 } else {
106 if !ok || _v != v {
107 t.Errorf("GetOK(%d), want (%d, true), got (%d, %t)", i, v, _v, ok)
108 }
109 }
110 }
111 rh.Leave()
112}
113
114func TestSerialOverflow(t *testing.T) {
115 var maxEven uint64 = math.MaxUint64 - 1
116 t.Logf("maxEven(%d)", maxEven)
117 if maxEven%2 == 1 {
118 t.Errorf("maxEven(%d) is odd", maxEven)
119 }
120
121 maxOdd := maxEven + 1
122 t.Logf("maxOdd(%d)", maxOdd)
123 if maxOdd%2 == 0 {
124 t.Errorf("maxOdd(%d) is even", maxOdd)
125 }
126
127 overflow := maxOdd + 1
128 t.Logf("overflow(%d)", overflow)
129 if overflow%2 == 1 {
130 t.Errorf("overflow(%d) is odd", overflow)
131 }
132}
133
134func TestCleanup(t *testing.T) {
135 const n = 1000
136
137 lrmap := New[int, int]()
138 lrmap.recordMetrics()
139
140 readHandlers := make([]*ReadHandler[int, int], n)
141 for i := 0; i < n; i++ {
142 readHandlers[i] = lrmap.NewReadHandler()
143 }
144
145 runtime.GC()
146
147 if created, cleanedUp := atomic.LoadUint64(&lrmap.metrics.readHandlersCreated), atomic.LoadUint64(&lrmap.metrics.readHandlersCleanedUp); created != n || cleanedUp != 0 {
148 t.Errorf("created %d read handlers, cleaned up %d read handlers", created, cleanedUp)
149 }
150
151 lrmap.mu.Lock()
152 if nn := len(lrmap.readHandlers); nn != n {
153 t.Errorf("expected %d read handlers, got %d", n, nn)
154 }
155 lrmap.mu.Unlock()
156
157 for i := range readHandlers {
158 readHandlers[i] = nil
159 }
160
161 check := func() (uint64, uint64) {
162 return atomic.LoadUint64(&lrmap.metrics.readHandlersCreated), atomic.LoadUint64(&lrmap.metrics.readHandlersCleanedUp)
163 }
164
165Retry:
166 for i := 0; i < 100; i++ {
167 runtime.GC()
168
169 if created, cleanedUp := check(); created == n && cleanedUp == n {
170 break Retry
171 }
172 }
173
174 if created, cleanedUp := check(); created != n || cleanedUp != n {
175 t.Errorf("created %d read handlers, cleaned up %d read handlers", created, cleanedUp)
176 }
177
178 lrmap.mu.Lock()
179 if nn := len(lrmap.readHandlers); nn != 0 {
180 t.Errorf("expected no read handlers, got %d", nn)
181 }
182 lrmap.mu.Unlock()
183}