hashmap
hashmap copied to clipboard
Unexpected behaviors under large number of data
Describe the bug Under certain cases of large data it seems that the map performs unexpectedly, meaning it performs differently from sync.Map, a normal map with a RWMutex, and what's expected. I don't know whether these behaviors are expected or whether I'm using the map wrong, but I think I used it correctly.
To Reproduce Code 1:
func BenchmarkHashMap_Case1(b *testing.B) {
b.StopTimer()
wg := sync.WaitGroup{}
for i := 0; i < b.N; i++ {
M := hashmap.New[int, int]()
b.StartTimer()
for k := 0; k < iter0; k++ {
wg.Add(1)
go func(l, h int) {
for j := l; j < h; j++ {
M.Insert(j, j)
}
for j := l; j < h; j++ {
_, a := M.Get(j)
if !a {
b.Error("key doesn't exist", j)
}
}
for j := l; j < h; j++ {
x, _ := M.Get(j)
if x != j {
b.Error("incorrect value", j, x)
}
}
wg.Done()
}(k*elementNum0, (k+1)*elementNum0)
}
wg.Wait()
b.StopTimer()
}
}
Code 2:
func BenchmarkHashMap_Case3(b *testing.B) {
b.StopTimer()
wg := &sync.WaitGroup{}
for a := 0; a < b.N; a++ {
M := hashmap.New[int, int]()
b.StartTimer()
for j := 0; j < iter0; j++ {
wg.Add(1)
go func(l, h int) {
defer wg.Done()
for i := l; i < h; i++ {
M.Insert(i, i)
}
for i := l; i < h; i++ {
_, x := M.Get(i)
if !x {
b.Errorf("not put: %v\n", O(i))
}
}
for i := l; i < h; i++ {
M.Del(i)
}
for i := l; i < h; i++ {
_, x := M.Get(i)
if x {
b.Errorf("not removed: %v\n", O(i))
}
}
}(j*elementNum0, (j+1)*elementNum0)
}
wg.Wait()
``` b.StopTimer()
}
}
Set `elementNum0=1024; iter0=8`. You can remove the benchmark part and all those timing stuffs.
**Expected behavior**
What these 2 functions are doing is that each thread is performing operations(read/write/delete) on different set of keys. Since different threads aren't interfering with each other, so operations are performed sequentially with respect to each thread; therefore, no errors should occur. This is the behavior for sync.Map and a default map with RWMutex. However, errors occur for this implementation.
**System (please complete the following information): AMD **
- OS: win10 64 bit
- Version / Commit: newest
- Go 1.19.2
**Additional context**
I didn't thoroughly read the code of this hashmap, but I assume that this behavior is potentially caused by concurrent modifications during resizing?
I also have a case2 benchmark which involves using M.set(), but I don't know whether is M.set() really slow or performing unexpectedly, the benchmark usually results in a timeout.
Thanks.