Cannot set maps above a certain size

[nightwolfz]

go 1.19

func TestMakeHaxmap(t *testing.T) {
    for f := 1; f < 1000000; f *= 5 {
        m := haxmap.New[int, string]()
        t.Logf("creating %d", f)

        for i := 0; i < f; i++ {
            m.Set(i, fmt.Sprintf("a%d", i))
        }

        t.Logf("size: %d", m.Size())
    }
}

Randomly hangs forever...

[alphadose]

Hi @nightwolfz , can you try it with an initial size such as m := haxmap.New[int, string](1 << 12) ?

Also you are allocating the hashmap in each round of the for loop, can you move it outside the loop or is that intentional ?

[nightwolfz]

@alphadose That's just an example to illustrate the issue.

You can simplify it to

func TestMakeHaxmap(t *testing.T) {
    m := haxmap.New[int, string]()

    for i := 0; i < 65000; i++ {
        m.Set(i, fmt.Sprintf("a%d", i))
    }
    t.Logf("size: %d", m.Size())
}

At test.cpu=1, this hangs indefinitely at around 5500 At test.cpu=2, this hangs around 52000 At test.cpu>2, the test sometimes finishes, sometimes hangs.

If I add runtime.Gosched() to the loop, the issue never shows up. Probably since it gives enough time for the grow goroutine to execute?

If this is by design, it might be worth mentioning in the README.

[alphadose]

@nightwolfz yes rapid map growth via Set() creates a lot of grow() goroutines which causes choking and as you said using runtime.Gosched() frees up the CPU hence more time for the growth.

One of haxmap's future goals is a better growth policy which wont choke and hence there is lots more room for improvement

If this is by design, it might be worth mentioning in the README.

Yes, I will mention it

Also the current workaround for this behaviour would be initializing the map with a good size which will cause lesser grow operations and wont choke

[nightwolfz]

A few ideas for https://github.com/alphadose/haxmap/blob/main/map.go#L140

1. Give the goroutine some time.

       if resizeNeeded(uintptr(len(data.index)), count) {
           runtime.Gosched()
           if m.resizing.CompareAndSwap(notResizing, resizingInProgress) {
               go m.grow(0, true)
           }
       }

2. Or remove the goroutine (and the loop in m.grow) and let it happen sync.

       if resizeNeeded(uintptr(len(data.index)), count) && m.resizing.CompareAndSwap(notResizing, resizingInProgress) {
           m.growSync(0, true)
       }

goos: linux
goarch: amd64
pkg: github.com/alphadose/haxmap/benchmarks
cpu: AMD Ryzen 7 5800X 8-Core Processor             
BenchmarkHaxMapReadsWithWritesX
BenchmarkHaxMapReadsWithWritesX/grow-current
BenchmarkHaxMapReadsWithWritesX/grow-current-4            114321         10393 ns/op        1976 B/op        247 allocs/op
BenchmarkHaxMapReadsWithWritesX/grow-sched
BenchmarkHaxMapReadsWithWritesX/grow-sched-4              120441         10284 ns/op        1977 B/op        247 allocs/op
BenchmarkHaxMapReadsWithWritesX/grow-sync
BenchmarkHaxMapReadsWithWritesX/grow-sync-4               117235         10278 ns/op        1987 B/op        248 allocs/op
PASS

[alphadose]

Yes, this sounds plausible, if possible can you checkout a branch with these changes ? It would be much easier for both of us to test that way.

I like the 2nd option:- letting everything happen in sync

[alphadose]

@nightwolfz I have updated the main branch with this https://github.com/alphadose/haxmap/commit/d071dd5f749f86017a32bc126ea40eaade5f3dfc

With this commit growth happens synchronously and the benchmarks and tests are passing as well

can you run your tests once again and tell me the results ?

[nightwolfz]

Much better now.