alphadose / haxmap

Fastest and most memory efficient golang concurrent hashmap

HaxMap

A lightning fast concurrent hashmap

The hashing algorithm used was xxHash and the hashmap's buckets were implemented using Harris lock-free list

Installation

You need Golang 1.18.x or above

$ go get github.com/alphadose/haxmap

Usage

package main

import (
	"fmt"

	"github.com/alphadose/haxmap"
)

func main() {
	// initialize map with key type `int` and value type `string`
	mep := haxmap.New[int, string]()

	// set a value (overwrites existing value if present)
	mep.Set(1, "one")

	// get the value and print it
	val, ok := mep.Get(1)
	if ok {
		println(val)
	}

	mep.Set(2, "two")
	mep.Set(3, "three")
	mep.Set(4, "four")

	// ForEach loop to iterate over all key-value pairs and execute the given lambda
	mep.ForEach(func(key int, value string) bool {
		fmt.Printf("Key -> %d | Value -> %s\n", key, value)
		return true // return `true` to continue iteration and `false` to break iteration
	})

	mep.Del(1) // delete a value
	mep.Del(0) // delete is safe even if a key doesn't exists

	// bulk deletion is supported too in the same API call
	// has better performance than deleting keys one by one
	mep.Del(2, 3, 4)

	if mep.Len() == 0 {
		println("cleanup complete")
	}
}

Benchmarks

Benchmarks were performed against golang sync.Map and the latest cornelk-hashmap

All results were computed from benchstat of 20 runs (code available here)

1. Concurrent Reads Only

name                         time/op
HaxMapReadsOnly-8            6.94µs ± 4%
GoSyncMapReadsOnly-8         21.5µs ± 3%
CornelkMapReadsOnly-8        8.39µs ± 8%

2. Concurrent Reads with Writes

name                         time/op
HaxMapReadsWithWrites-8      8.23µs ± 3%
GoSyncMapReadsWithWrites-8   25.0µs ± 2%
CornelkMapReadsWithWrites-8  8.83µs ±20%

name                         alloc/op
HaxMapReadsWithWrites-8      1.25kB ± 5%
GoSyncMapReadsWithWrites-8   6.20kB ± 7%
CornelkMapReadsWithWrites-8  1.53kB ± 9%

name                         allocs/op
HaxMapReadsWithWrites-8         156 ± 5%
GoSyncMapReadsWithWrites-8      574 ± 7%
CornelkMapReadsWithWrites-8     191 ± 9%

From the above results it is evident that haxmap takes the least time, memory and allocations in all cases making it the best golang concurrent hashmap in this period of time

Tips

1. HaxMap by default uses xxHash algorithm, but you can override this and plug-in your own custom hash function. Beneath lies an example for the same.

package main

import (
	"github.com/alphadose/haxmap"
)

// your custom hash function
// the hash function signature must adhere to `func(keyType) uintptr`
func customStringHasher(s string) uintptr {
	return uintptr(len(s))
}

func main() {
	m := haxmap.New[string, string]() // initialize a string-string map
	m.SetHasher(customStringHasher) // this overrides the default xxHash algorithm

	m.Set("one", "1")
	val, ok := m.Get("one")
	if ok {
		println(val)
	}
}

2. You can pre-allocate the size of the map which will improve performance in some cases.

package main

import (
	"github.com/alphadose/haxmap"
)

func main() {
	const initialSize = 1 << 10

	// pre-allocating the size of the map will prevent all grow operations
	// until that limit is hit thereby improving performance
	m := haxmap.New[int, string](initialSize)

	m.Set(1, "1")
	val, ok := m.Get(1)
	if ok {
		println(val)
	}
}

haxmap's Issues

Add clear all method

fantastic library , can you add a drop all/clear method.

Say after n period of time, I want to clear out everything but not resize down .

Json encoding support

Map type does not implement json.Marshaler and json.Unmarshaler.

Cannot set maps above a certain size

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...

When to use this package

In which cases using this package really needed vs standard go map with mutex?
For example if I have 10 entries?

Concurrency access has problems with set and delete (tests fail randomly)

I was trying to make a memory cache with auto-delete items and ran into the non-obvious problem that the tests sometimes fail

https://github.com/NikoMalik/memoryCache

--- FAIL: TestCacheConcurrentAccess (0.07s)
cache_test.go:113:

                                         /usr/lib/go-1.22/src/runtime/asm_amd64.s:1695
            Error:          Should be true
            Test:           TestCacheConcurrentAccess
            Messages:       Expected to find key

FAIL
exit status 1

--- FAIL: TestCacheConcurrentSetAndDeleteAsync (0.00s)
cache_test.go:333:
Error: Should be false
Test: TestCacheConcurrentSetAndDeleteAsync
Messages: Expected not to find key
cache_test.go:335: Expected not to find key, but found
FAIL
exit status 1
FAIL github.com/NikoMalik/MemoryCache 0.778s

Major Bug

I upgraded from v0.1.0 to v0.3.1 and it seems to hang in the set command. The CPU stays stuck at 100% and the application does not run but haxmap internals are the only things running. I did a profiler in this condition and here is the image. When I downgraded v0.1.0, all was ok. Problem appears to exist for anything above v.0.1.0

Incorrect fillrate value

Fillrate is not calculated correctly.

m := New[int, any]()
for i := 0; i < 1000; i++ {
	m.Set(i, nil)
}
for i := 0; i < 1000; i++ {
	m.Del(i)
}
fmt.Println(m.Fillrate())
// output: 38

It is caused by the index which is set when an element is removed from its index.

func (m *Map[K, V]) removeItemFromIndex(item *element[K, V]) {
	for {
		data := m.metadata.Load()
		index := item.keyHash >> data.keyshifts
		ptr := (*unsafe.Pointer)(unsafe.Pointer(uintptr(data.data) + index*intSizeBytes))

		next := item.next()
		if next != nil && item.keyHash>>data.keyshifts != index {
			next = nil // do not set index to next item if it's not the same slice index
		}
		atomic.CompareAndSwapPointer(ptr, unsafe.Pointer(item), unsafe.Pointer(next))
		...
	}
}

the index should be set to the next element only if the next element has the same index value

	...
	if next != nil && next.keyHash>>data.keyshifts != index {
		next = nil // do not set index to next item if it's not the same slice index
	}
	...

and also it would avoid the scenario to be emerged I mentioned in #33 (comment)

Outdated Documentation for Map.Grow

The map.Grow method's comment states:

Grow resizes the hashmap to a new size, gets rounded up to next power of 2
To double the size of the hashmap use newSize 0
This function returns immediately, the resize operation is done in a goroutine
No resizing is done in case of another resize operation already being in progress
Growth and map bucket policy is inspired from https://github.com/cornelk/hashmap

But commit d071dd5f749f86017a32bc126ea40eaade5f3dfc changed map.Grow to be sync, making this part of the comment inaccurate:

This function returns immediately, the resize operation is done in a goroutine

Iterate(ForEach) has no way to break

In the case of a lot of data, I need to stop this iteration after I get a piece of data.
But there is no way to top in the current iteration.

		syncmaps.Range(func(key, value any) bool {
		
			if ok {
	
				return false
			}
			return true
		})

Like in sync.Map I can return false to stop the iteration

Atomicly SetIfAbsent

Is there anyway to atomicly set a value if one does not already exist?

I have tried a couple different things and they don't seem to work for my use case, I have examples if wanted:

• CompareAndSwap(key, nil, value) which doesn't seem to work on unset keys.
• GetOrSet and GetOrCompute but those don`t seem to be threadsafe.

If there is currently no way to do this would you be open to a PR adding it?

Thanks

Race condition

Hi, I saw that the sorted linked list is based on Harris's linked list, but according to my understanding, it's not correctly written. Harris's linked list is based on 2 assumptions: 1. Atomic operation on node.next can see changes to node.delete. 2. node.next on a deleted node is still valid and can be used to track to the original next. In this implementation, I see that: 1. node.delete and node.next can't be dealt with in a single atomic operation. This is problematic, consider: node.delete can change immediately before(after the if checks) or during a CAS operation on node.next, and during this process, a successful physical deletion can happen before the CAS operation completes/starts, therefore, the new node is linked onto a deleted node. This is my understanding, correct me if I'm wrong.

I encountered the above problem in my initial attempts to implement such a hashmap using Harris's linked list.

With this in mind, I designed a few cases that can reflect the above problem. However, I'm not sure whether the failures in the below cases are solely caused by the above reason or is/are caused by other problems. It appears to me that at least on my end Case1 has some other problem because a given key is guaranteed to fail. Anyway, let's see these cases.
Case 1:

func BenchmarkHaxMap_Case1(b *testing.B) {
	b.StopTimer()
	wg := sync.WaitGroup{}
	for i := 0; i < b.N; i++ {
		M := haxmap.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.Set(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()
	}
}

Case 2:

func BenchmarkHaxMap_Case3(b *testing.B) {
	b.StopTimer()
	wg := &sync.WaitGroup{}
	for a := 0; a < b.N; a++ {
		M := haxmap.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.Set(i, i)
				}

				for i := l; i < h; i++ {
					_, x := M.Get(i)
					if !x {
						b.Errorf("not put: %v\n", 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", i)
					}
				}

			}(j*elementNum0, (j+1)*elementNum0)
		}
		wg.Wait()
		b.StopTimer()
	}

}

const (
	iter0       = 1 << 3
	elementNum0 = 1 << 10
)

If you increase the data size, this problem becomes more severe. You can delete all the benchmark and timing things.

Modifying these tests to sync.Map or an ordinary map with Mutex will show that no failures happen. In addition, cornelk's hashmap also fails at these tests.

Slow compared to map?

Hi, i was trying to benchmark haxmap vs map,

https://github.com/kokizzu/kokizzu-benchmark/blob/master/assoc/go-haxmap/haxmap.go
vs
https://github.com/kokizzu/kokizzu-benchmark/blob/master/assoc/map.go
the diff
https://pastebin.com/diff/V3Y04Uha

but haxmap took like 51s vs 14s using map

time go run go-haxmap/haxmap.go                                                                                                                    
6009354 6009348 611297
36186112 159701682 23370001

CPU: 51.86s     Real: 26.87s    RAM: 2 386 608KB

time go run map.go 
6009354 6009348 611297
36186112 159701682 23370001

CPU: 14.29s     Real: 12.43s    RAM: 2 271 672KB

Finding this project...

google "golang concurrent map" or "golang lockfree map" and this project does not come up. I only found it after following various links in issues reported on golang's sync.Map. You may want to do whatever's necessary to bring more attention to this rep (titles? README.md content? etc)

... I'm bothering to say this because some of the other projects that come up are riddled with bugs ...

[Question]: why are there empty structs in atomic?

In atomic.go:

type noCopy struct{}

func (c *noCopy) Lock()   {}
func (c *noCopy) Unlock() {}

type atomicUint32 struct {
  _ noCopy
  v uint32
}

is this filler (_ noCopy) for semantics or does it actually prevent copying?

now we can use xxh3 to speed up

https://github.com/zeebo/xxh3

// your custom hash function
func customStringHasher(s string) uintptr {
return uintptr(xxh3.HashString(s))
}

Delete performance would benefit from improvement

Very nice library for concurrent maps! For scenarios where you need to delete keys one at a time (not batching), the current performance makes it unusable.

I have an analysis application (https://github.com/lkarlslund/adalanche) and I've tried replacing some of the maps with yours (adding unsafe.Pointer in my fork).

With a nasty workaround where I don't delete keys, but set the value to a deleted flag, it works fairly good. But this is not the way.

Also looking at your code, I'm curious how you distinguish from a hash which is ^0 and the "marked" value which is the same?

Missed func LoadOrStore

Hi it's a great project but miss LoadOrStore func.

Can just Get first then set?

The issue was discovered during stress testing.

After adding tens of millions of elements, when I inserted another value into the Set, I found that the delay reached tens of thousands of nanoseconds, which is significantly different from the usual single-digit nanoseconds.

The type is haxmap.Newint, int

Missed func LoadAndDelete

LoadAndDelete func deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present

Seems not thread safe

I update the vendor with the latest main branch and wrote this test code to simulate the situation.

func TestDebug(t *testing.T) {
	var wg sync.WaitGroup
	m := haxmap.New[string, struct{}]()

	acquire := func(key string) (free func(), acquired bool) {
		if _, loaded := m.GetOrSet(key, struct{}{}); loaded {
			return nil, false
		}

		free = func() {
			m.Del(key)
		}

		return free, true
	}

	n := 1000
	key := "key"
	var sum int32
	wg.Add(n)

	for i := 0; i < n; i++ {
		go func(idx int) {
			defer wg.Done()

			_, acq := acquire(fmt.Sprintf("%d", idx))
			require.True(t, acq)

			free, acquired := acquire(key)
			t.Log(acquired)
			if !acquired {
				return
			}

			// makes sure that there're only one thread has been acquired.
			require.True(t, atomic.CompareAndSwapInt32(&sum, 0, 1), atomic.LoadInt32(&sum))
			// marks there's no thread is acquired in advance.
			require.True(t, atomic.CompareAndSwapInt32(&sum, 1, 0))

			free()
		}(i)
	}

	wg.Wait()
}

When run go test without -race it shows fine, no errors. But if enable race detection, it will fail like

    sync_test.go:94: false
    sync_test.go:100:
        	Error Trace:	/Users/cmgs/.go/src/github/projecteru2/agent/utils/sync_test.go:100
        	            				/Users/cmgs/.go/src/github/projecteru2/agent/utils/asm_arm64.s:1172
        	Error:      	Should be true
        	Test:       	TestDebug
        	Messages:   	1
    sync_test.go:100:
        	Error Trace:	/Users/cmgs/.go/src/github/projecteru2/agent/utils/sync_test.go:100
        	            				/Users/cmgs/.go/src/github/projecteru2/agent/utils/asm_arm64.s:1172
        	Error:      	Should be true
        	Test:       	TestDebug
        	Messages:   	1
FAIL
FAIL	github.com/projecteru2/agent/utils	0.208s
FAIL

The test command is (I put this code under the utils pkg)

GOOS=darwin GOARCH=arm64 go test -race -count=1 -timeout 120s -run TestDebug ./utils/...

Not sure what happen, because the this error only shows under GOOS=darwin and GOARCH=arm64 (I use M1 macbook). can pass in linux env（https://github.com/projecteru2/agent/actions/runs/3359505108/jobs/5567595644）.

Any ideas?

Set after Delete seems to delete key

The following test fails with h.Get(1) returning that the key:value entry does not exist:

func TestHaxmap(t *testing.T) {
	h := haxmap.New[int, string]()
	for i := 1; i <= 10; i++ {
		h.Set(i, strconv.Itoa(i))
	}
	for i := 1; i <= 10; i++ {
		h.Del(i)
	}
	for i := 1; i <= 10; i++ {
		h.Set(i, strconv.Itoa(i))
	}
	for i := 1; i <= 10; i++ {
		id, ok := h.Get(i)
		assert.Equal(t, strconv.Itoa(i), id)
		assert.True(t, ok)
	}
}

I'm assuming it has to do with the lazy delete, where the h.Del(i) only flags it and h.Set(i) deletes the entry rather than setting it, but I haven't looked too deeply into it. My local environment is an M1 Macbook with Go version 1.19.

GetOrSet and map key types

Hello! Thank you for your awesome package and for the recent (important) GetOrSet functionality.

I want to ask if you can allow (and implement) the usage of function (as the value constructor) which will be called just once (to avoid unnecessary value construction logic everytime using GetOrSet).

The second thing is to ask to allow the usage of types which underlying type is among of those which your hashable supports. For example, type SeqId uint64.

Random crashes during grow

I am not sure what is wrong, but migrating to haxmap introduced a lots of crashing in tests (random crashes).
https://github.com/quickfixgo/quickfix/pull/685/files

goroutine 130 gp=0x14000102700 m=5 mp=0x1400022a808 [running]:
runtime.throw({0x105053623?, 0x14000194570?})
	/opt/homebrew/opt/go/libexec/src/runtime/panic.go:1067 +0x38 fp=0x1400021d270 sp=0x1400021d240 pc=0x104b0f648
runtime.sigpanic()
	/opt/homebrew/opt/go/libexec/src/runtime/signal_unix.go:931 +0x224 fp=0x1400021d2d0 sp=0x1400021d270 pc=0x104b11364
github.com/alphadose/haxmap.(*element[...]).isDeleted(...)
	/Users/matej.spiller-muys/go/pkg/mod/github.com/alphadose/[email protected]/list.go:110
github.com/alphadose/haxmap.(*element[...]).next(0x105239fc0?)
	/Users/matej.spiller-muys/go/pkg/mod/github.com/alphadose/[email protected]/list.go:38 +0x74 fp=0x1400021d320 sp=0x1400021d2e0 pc=0x104f14a84
github.com/alphadose/haxmap.(*element[...]).search(0x105239fc0?, 0xe664a19d58b3cdf5, 0x62)
	/Users/matej.spiller-muys/go/pkg/mod/github.com/alphadose/[email protected]/list.go:87 +0x68 fp=0x1400021d350 sp=0x1400021d320 pc=0x104f147a8
github.com/alphadose/haxmap.(*element[...]).inject(0x105239fc0?, 0xe664a19d58b3cdf5, 0x62, 0x14000194570)
	/Users/matej.spiller-muys/go/pkg/mod/github.com/alphadose/[email protected]/list.go:61 +0x34 fp=0x1400021d3a0 sp=0x1400021d350 pc=0x104f14874
github.com/alphadose/haxmap.(*Map[...]).Set(0x10523e440, 0x62, {0x140000faa90, 0x1, 0x3})
	/Users/matej.spiller-muys/go/pkg/mod/github.com/alphadose/[email protected]/map.go:167 +0x144 fp=0x1400021d400 sp=0x1400021d3a0 pc=0x104f135d4

Any idea how to debug this since ti is very random.

I tried:

m.tagLookup = haxmap.New[Tag, field]() -> works
m.tagLookup = haxmap.New[Tag, field](1) -> works
m.tagLookup = haxmap.New[Tag, field](10) -> crashes
m.tagLookup = haxmap.New[Tag, field](100) -> crashes

Copyright violation

This repository uses code from other libraries without respecting their copyright.

For example, the file hash64.go contains code that is copied from https://github.com/cespare/xxhash/

The license clearly states:

Copyright (c) 2016 Caleb Spare

MIT License

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

Unnecessary resizing

Map is resizing unnecessarily after same operations although the map length is always same.

m := New[int, any]()
fmt.Printf("len: %d, indexCount: %d\n", m.Len(), len(m.metadata.Load().index))
for i := 0; i < 10000; i++ {
	m.Set(i, nil)
	m.Del(i)
}
fmt.Printf("len: %d, indexCount: %d\n", m.Len(), len(m.metadata.Load().index))

the output:

len: 0, indexCount: 8
len: 0, indexCount: 16384

[BUG] The test below may hang indefinitely

func BenchmarkDelete_alphadose_haxmap(b *testing.B) {
	b.ReportAllocs()
	var m = haxmap.New[int, int]()
	for i := 0; i < 1000000; i++ {
		m.Set(i, i)
	}
	runtime.GC()

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			m.Del(i)
			i++
			if i >= 1000000{
				i = 0
			}
		}
	})
}

GetOrSet race?

As I understand it golang's preemption model is that a goroutine may be interrupted either at "wait" boundaries (such as locks, sleeps) & when making system calls, or at function call boundaries where the stack may increase. In other words, the preemption model does allow for preemption between golang statements involving a function call.

Therefore, this code in GetOrSet() contains a race, no?

		if elem.key == key && !elem.isDeleted() {
			actual, loaded = *elem.value.Load(), true

Is your thinking that the race is of no consequence in a concurrent map because it would be no worse, in that case, than in the alternative, having scheduled the Set prior to the delete implicated in the race?

建议添加几个函数

我感觉这个库跟另外一个库很类似，但是那个库已经很久没维护了，而且那个库和这个库一样，有好几个函数没有实现，导致我用起来不是很顺手，我看您好像还在维护这个库，所以希望您能实现
1、Keys() 返回所有的key
2、Vals() 返回所有的val
3、Clone() 生成一个当前map的所有元素的克隆
4、支持自定义marshal函数，因为golang自带的json确实很占资源。并且在UnmarshalJSON函数中支持自我初始化
4、Has 或 Contains 和 HasBy(func) 或 ContainsBy(func) 判断某个元素或某个元素的属性是否在map中

如果您能支持，我将非常感谢，并在所有函数支持之后迁移到这个库上来

Save to file, load from file

Pls, help

Will it cause new keys can't been set when deleting keys in ForEach iteration?

Code：

package main

import (
	"context"
	"fmt"
	"math/rand"
	"time"

	"github.com/alphadose/haxmap"
)

type data struct {
	id  int
	exp time.Time
}

func main() {
	c := haxmap.New[int, *data](256)
	ctx, cancel := context.WithCancel(context.Background())
	defer cancel()

	go func() {
		t := time.NewTicker(time.Second * 2)
		defer t.Stop()
		var count int
		for {
			select {
			case <-t.C:
				count = 0
				c.ForEach(func(s int, b *data) bool {
					if time.Now().After(b.exp) {
						c.Del(s)
						count++
					}
					return true
				})
				fmt.Println("Del", count)
			case <-ctx.Done():
				return
			}
		}
	}()

	for i := 0; i < 20000; i++ {
		c.Set(i, &data{id: i, exp: time.Now().Add(time.Millisecond * time.Duration((1000 + rand.Intn(800))))})
		time.Sleep(time.Microsecond * time.Duration(rand.Intn(200)+10))
		if i%100 == 0 {
			fmt.Println(i)
		}
	}

	time.Sleep(time.Second * 3)
	fmt.Println("LEN", c.Len())
}

Running the above code, setting the new Key will stop.

New() initializer panics if the given size is uintptr(0)

I wanted to initialize a haxmap B with the same size as haxmap A with the following code:

B := haxmap.New[string, struct{}](A.Len())

which worked for most cases except when A.Len() is 0. When A has 0 key-values, the initializer would panic.

Would be awesome if this is handled 🙏

UUID for Key?

Hi, thank you for your excellent map. How can I use google/UUID for the key? or can you add this feature to the map?

Can't get data after multiple sets

test code:

hmap := haxmap.New[int64, interface{}](32)
go func() {
	var idx int64
	for i := 1; i <= 300; i++ {
		time.Sleep(time.Millisecond * 250)
		idx++
		hmap.Set(idx, idx)
		idx++    // Accelerated progress
		hmap.Set(idx, idx)
		fmt.Println("new..........", idx-1, idx)
	}
}()
go func() {
	var idx int64 = 1
	for {
		if _, ok := hmap.Get(idx); ok {
			fmt.Println("get_del...........", idx)
			hmap.Del(idx)
			idx++
		}
		time.Sleep(time.Millisecond * 10)
	}
}()
time.Sleep(time.Hour)

After looping for a while, no more data is obtained

Development Environment: Windows10(x64), go1.19.1

How Do I actually delete a key?

mep := haxmap.New[int, string]()
    
mep.Set(1, "one")
println(mep.Len()) // 1

mep.Del(1) // delegate key 1
println(mep.Len()) // 0

// Still can traverse the key/value pair ？
mep.ForEach(func(key int, value string) bool {
    fmt.Printf("Key -> %d | Value -> %s\n", key, value)
    return true
})

// Print: Key -> 1 | Value -> one

I mean, I have deleted key 1, mep.len() is already 0, why ForEach still iterates over the deleted key-value pair? How to actually remove them from mep?

Support for Go 1.23 Iterators

We could add support for the range-over-function feature introduced in Go 1.23.
https://go.dev/wiki/RangefuncExperiment

The ForEach method we already have indeed matches the iter.Seq2 function type, allowing us to use it directly as an iterator function.

type Seq2[K, V any] func(yield func(K, V) bool)

func (m *Map[K, V]) ForEach(lambda func(K, V) bool) {...}

for k, v := range m.ForEach {...}

However, this is not the recommended approach.
https://go.dev/blog/range-functions

As a matter of convention, we encourage all container types to provide an All method that returns an iterator, so that programmers don’t have to remember whether to range over All directly or whether to call All to get a value they can range over. They can always do the latter.

The point I’m suggesting is to specifically support iterators and document them. We need to define a new function called Iterator, which will return a function that operates exactly the same as the ForEach method. Additionally, we can define a Keys function to iterate only over keys, avoiding the overhead of atomic loading for values.

for k, v := range m.Iterator() {...}

for k := range m.Keys() {...}

We can separate the iterators into a new file and use build tags to control when it is built, allowing us to keep the module version (1.18) unchanged.

Keep the older language version for the module as a whole, but use a //go:build go1.23 build tag to permit using range over function types in a specific file.

improve haxmap performance

I test some different map use cases. in every case(read 100%、99%、90%、75%、 50%) test code
xsync.mapof > concurrent-map(shard rwlock) > haxmap
the ConcurrentMap shard map with rwlock:

//goos: windows
//goarch: amd64
//pkg: benchmap
//cpu: 12th Gen Intel(R) Core(TM) i9-12900K
//BenchmarkConcurrentMap_WarmUp
//BenchmarkConcurrentMap_WarmUp/reads=100%
//BenchmarkConcurrentMap_WarmUp/reads=100%-24         	19311262	        59.97 ns/op	  16674108 ops/s
//BenchmarkConcurrentMap_WarmUp/reads=99%
//BenchmarkConcurrentMap_WarmUp/reads=99%-24          	19390272	        57.46 ns/op	  17403041 ops/s
//BenchmarkConcurrentMap_WarmUp/reads=90%
//BenchmarkConcurrentMap_WarmUp/reads=90%-24          	20722754	        58.18 ns/op	  17188562 ops/s
//BenchmarkConcurrentMap_WarmUp/reads=75%
//BenchmarkConcurrentMap_WarmUp/reads=75%-24          	19096568	        61.73 ns/op	  16198394 ops/s
//BenchmarkConcurrentMap_WarmUp/reads=50%
//BenchmarkConcurrentMap_WarmUp/reads=50%-24          	15739459	        69.01 ns/op	  14491307 ops/s

the xsync map result:

// goos: windows
// goarch: amd64
// pkg: benchmap
// cpu: 12th Gen Intel(R) Core(TM) i9-12900K
// BenchmarkXSyncMap_WarmUp
// BenchmarkXSyncMap_WarmUp/reads=100%
// BenchmarkXSyncMap_WarmUp/reads=100%-24         	24926673	        47.70 ns/op	  20964357 ops/s
// BenchmarkXSyncMap_WarmUp/reads=99%
// BenchmarkXSyncMap_WarmUp/reads=99%-24          	24938018	        47.36 ns/op	  21114211 ops/s
// BenchmarkXSyncMap_WarmUp/reads=90%
// BenchmarkXSyncMap_WarmUp/reads=90%-24          	24128313	        46.64 ns/op	  21440622 ops/s
// BenchmarkXSyncMap_WarmUp/reads=75%
// BenchmarkXSyncMap_WarmUp/reads=75%-24          	23475463	        54.89 ns/op	  18219448 ops/s
// BenchmarkXSyncMap_WarmUp/reads=50%
// BenchmarkXSyncMap_WarmUp/reads=50%-24          	20382096	        58.53 ns/op	  17084646 ops/s
// PASS

the haxmap result:

//goos: windows
//goarch: amd64
//pkg: benchmap
//cpu: 12th Gen Intel(R) Core(TM) i9-12900K
//BenchmarkHaxLockFreeMap_WarmUp
//BenchmarkHaxLockFreeMap_WarmUp/reads=100%
//BenchmarkHaxLockFreeMap_WarmUp/reads=100%-24         	17538038	        63.97 ns/op	  15631949 ops/s
//BenchmarkHaxLockFreeMap_WarmUp/reads=99%
//BenchmarkHaxLockFreeMap_WarmUp/reads=99%-24          	17473504	        63.95 ns/op	  15638035 ops/s
//BenchmarkHaxLockFreeMap_WarmUp/reads=90%
//BenchmarkHaxLockFreeMap_WarmUp/reads=90%-24          	16729821	        66.61 ns/op	  15012730 ops/s
//BenchmarkHaxLockFreeMap_WarmUp/reads=75%
//BenchmarkHaxLockFreeMap_WarmUp/reads=75%-24          	17592495	        69.28 ns/op	  14433428 ops/s
//BenchmarkHaxLockFreeMap_WarmUp/reads=50%
//BenchmarkHaxLockFreeMap_WarmUp/reads=50%-24          	15320367	        78.30 ns/op	  12770672 ops/s
//PASS

It's amazing. Maybe there cound be more performance for the lockfree map.

CompareAndStore would be nice

For concurrent programs a compare and swap value would be really neat, as you might have a race if multiple threads are doing:

value, _ := map.Load(key)
value.Modify()
map.Store(key, value)

The pattern could be changed to

for {
  oldvalue, _ := map.Load(key)
  newvalue := oldvalue
  newvalue.Modify()
  success := map.CompareAndStore(key, oldvalue, newvalue)
  if success {
    break
  }
}

If there were any considering support LRU?

Plan for new release

Thank you for excellent map library.

It looks that several fixes and new APIs are added after v1.2.0.
Do you have any plan to release them ?

Infinite loop test case

Go 1.19, ubuntu 22.04

Run with -test.cpu 4

func TestInfiniteLoop(t *testing.T) {
	t.Run("infinite loop", func(b *testing.T) {
		m := haxmap.New[int, int](512)
		for i := 0; i < 112050; i++ {
			if i > 112024 {
				fmt.Printf("%d\n", i)
				m.Set(i, i) // set debug point here and step into until .inject
			} else {
				m.Set(i, i)
			}
		}
	})
}