+
Skip to content

Unexpected behaviors under large number of data #73

@G-M-twostay

Description

@G-M-twostay

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions

      点击 这是indexloc提供的php浏览器服务,不要输入任何密码和下载