Clear() is not working as intended. g is a copy of the group, not the group itself. The tests pass because ctrl is cleared, which tricks the test into thinking that clear has worked because the keys can no longer be found. I also noticed that Clear() does not use newEmptyMetadata() so there is an optimisation to cache an empty meta and then just assign it control. The same optimisation could be applied to the groups by creating a zero group and the applying it to each group.

This is evidently a very small issue, but the "Go Playground" hyperlink in the readme redirects to https://github.com/dolthub/swiss/blob/main, which is a 404 page.

Hi, I was trying to reproduce map benchmark using swiss
https://github.com/kokizzu/kokizzu-benchmark/blob/master/assoc/go-swiss/swiss.go
https://github.com/kokizzu/kokizzu-benchmark/blob/master/assoc/map.go

https://pastebin.com/diff/SBZXSPFb
but I got different result when using swiss

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

CPU: 14.36s     Real: 12.60s    RAM: 2269936KB

time go run go-swiss/swiss.go  
6009354 6009348 611297
1 6 1 --> should be the same as above

CPU: 13.06s     Real: 12.14s    RAM: 1837384KB

1. see:

   swiss/bits_amd64.go

   Line 34 in c0064a0

   b := simd.MatchMetadata((*[16]int8)(m), int8(h))

   
   The group size is 8, but when use simd, it convert to 16.
   If the locate is the last one, programe might be coredump, or result not correct.

2. compare with https://github.com/rust-lang/hashbrown, group size should be 16.

3. group count should be one more.
   when the locate is ths last one, and use unalign load, the last one more group can avoid out of range.

Sorry, I think this library still has a lot of bugs and is far from reaching a level that can be actually used.

Like this

m := swiss.NewMap[int, string](1000)
m.Put(11, `11)
m.Clear()

how's the memory in bytes allocation? how much garbage does it generate?

Now that maps is on the way to go 1.21, I wonder is it good time to add Keys(), Values() and various maps functions into Map methods?

TIA

I used Swiss to test out a utility I had written. Initially, it used native maps but employed a lot of memory. I can confirm that the switch to Swiss memory usage (and the graph from the blog) is correct.

I had to make a change, however. I had more items that the uint32 could hold a reference to. I changed the types within the library to uint64. I should have chosen a different data structure, a separate issue.

Would you accept a PR that allows two swiss versions of uint32 and uint64? I was thinking of being through generics.

Give some advice about this lib:

1. ctrl byte is everything, so no need to set kv when delete.
   those lines are not need:
   

   swiss/map.go

   Line 141 in c0064a0

   m.groups[g].keys[s] = key

2.when init ctrl bytes, we can use simd or unsafe code, not one by one.
see:

3.If the group's ctrl bytes are all empty, Iter() can be faster.
see:

4.Let ctrl bytes slice address is align to 32, so we can use _mm_load_128() to replace __mm_loadu_128():
see:

5. If group count is power of 2, not need to use if to check range.
   see:

   swiss/map.go

   Line 96 in c0064a0

   if g >= uint32(len(m.groups)) {

   
   g = g & 0xffff // if group count is 65536

6.try groupSize=32, and use avx2 to match 32 bytes each time.

7. XXHash might be better than golang map hasher.

see:

We always need to use both key and value, so if we put key and value togother, it might be improve cpu cache hit.

So struct group define like this might be better:

type group[K comparable, V any] struct {
	items [groupSize]struct {
		key   K
		value V
	}
}

Hi,

Currently, I'm developing the concurrent version of swiss-map https://github.com/mhmtszr/concurrent-swiss-map

While implementing Range functions https://github.com/mhmtszr/concurrent-swiss-map/blob/master/concurrent_swiss_map.go#L119 I couldn't stop the other shard because I didn't know the result of the callback functions thus I couldn't stop other shard iterations.

If the Iter function returns a boolean would be great for here what do you think?

Also, I'm open to your feedback about my concurrent-swiss-map implementation too.

It is hoped that the entire hash table can be theoretically traversed in the unmutated case by an interface that randomly fetches key-value pairs.

I compiled the quickstart program and the compiler issued the error message m.Clear()
"m.Clear undefined (type *swiss.Map[string, int] has no field or method Clear)"

In the github code, Clear() is a method.

I don't really understand: the downloaded version must be different from the github current code.

as the title said.

I have a long running process that uses swissmaps to store values before they're committed to a datastore. In the event that the process is stopped, I would like to write a gob file with the swissmaps, and upon restart decode the gob file in to the swissmaps.

Currently, this is not possible because swiss.Map doesn't have any exported fields. To remedy this, I have to convert the swissmap to a regular map and then save it to the gob file, and on restart read the gob file maps and put the values into a swissmap.

Here is the benchmark.

I found the performance of Get() method is worse than go map get when the capacity is 1~500.

And in my project, call times of Get() method is much more than Put(). And the capacity of map is often less than 500.

So the performance of swiss is not good enough. Wish to improve it.

goos: windows
goarch: amd64
pkg: web/util/listutil
cpu: Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz
BenchmarkCreateSwissMap
BenchmarkCreateSwissMap-8         499999              3184 ns/op           10128
 B/op          3 allocs/op
BenchmarkCreateGoMap
BenchmarkCreateGoMap-8            249999              5692 ns/op           20504
 B/op          2 allocs/op
BenchmarkSwissMapPut
BenchmarkSwissMapPut-8             35820             37102 ns/op           34624
 B/op         15 allocs/op
BenchmarkGoMapPut
BenchmarkGoMapPut-8                28435             44501 ns/op           43173
 B/op         42 allocs/op
BenchmarkSwissMapGet
BenchmarkSwissMapGet-8            226414              5092 ns/op               0
 B/op          0 allocs/op
BenchmarkGoMapGet
BenchmarkGoMapGet-8               292682              4278 ns/op               0
 B/op          0 allocs/op
BenchmarkSwissMapIterate
BenchmarkSwissMapIterate-8        750000              1616 ns/op               0
 B/op          0 allocs/op
BenchmarkGoMapIterate
BenchmarkGoMapIterate-8           249999              4900 ns/op               0
 B/op          0 allocs/op
PASS

package listutil_test

import (
	"github.com/dolthub/swiss"
	"testing"
)

const capacity = 500

func CreateSwissMap() *swiss.Map[int, int] {
	m := swiss.NewMap[int, int](0)

	for i := 1; i <= capacity; i++ {
		m.Put(i, i)
	}

	return m
}

func CreateMap() map[int]int {
	m := map[int]int{}

	for i := 1; i <= capacity; i++ {
		m[i] = i
	}

	return m
}

func BenchmarkCreateSwissMap(b *testing.B) {
	b.ReportAllocs()
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		m := swiss.NewMap[int, int](capacity)
		if m != nil {

		}
	}
}

func BenchmarkCreateGoMap(b *testing.B) {
	b.ReportAllocs()
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		m := make(map[int]int, capacity)
		if m != nil {

		}
	}
}

func BenchmarkSwissMapPut(b *testing.B) {
	b.ReportAllocs()
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		CreateSwissMap()
	}
}

func BenchmarkGoMapPut(b *testing.B) {
	b.ReportAllocs()
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		CreateMap()
	}
}

func BenchmarkSwissMapGet(b *testing.B) {
	m := CreateSwissMap()
	size := m.Count()

	b.ReportAllocs()
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		for i := 1; i <= size; i++ {
			v, ok := m.Get(i)
			if !ok || v == 0 {
				panic(`not found`)
			}
		}
	}
}

func BenchmarkGoMapGet(b *testing.B) {
	m := CreateMap()
	size := len(m)

	b.ReportAllocs()
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		for i := 1; i <= size; i++ {
			v, ok := m[i]
			if !ok || v == 0 {
				panic(`not found`)
			}
		}
	}
}

func BenchmarkSwissMapIterate(b *testing.B) {
	m := CreateSwissMap()

	b.ReportAllocs()
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		m.Iter(func(k int, v int) (stop bool) {
			if k <= 0 {
				panic(1)
			}

			if v == 0 {
				panic(1)
			}

			return false
		})
	}
}

func BenchmarkGoMapIterate(b *testing.B) {
	m := CreateMap()

	b.ReportAllocs()
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		for k, v := range m {
			if k <= 0 {
				panic(1)
			}

			if v == 0 {
				panic(1)
			}
		}
	}
}

I'm getting the following error:

../../go/pkg/mod/github.com/thepudds/[email protected]/match_stub.go:5:6: missing function body

Whenever I try to run the tests.

I took a peek at the package "thepudds/swisstable" and I noticed this file:

match_amd64.s

which looks like it should be providing the stub for AMD64 - but doesn't seem to be. I am running on a Mac with AMD64.

In regards to what I've tried - before I tried running the tests - I ran the following:

go mod tidy

which did install the following:

go: downloading github.com/thepudds/fzgen v0.4.2
go: downloading gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405
go: downloading github.com/sanity-io/litter v1.5.1

Then when I tried to run the tests and I got the same error - I also ran the following:

go install

I did check out the README.md here:
https://github.com/thepudds/swisstable

But, didn't see anything with regards to special instructions for AMD64.

Thanks!

If you look at the Rust api for std::collections::HashMap it is generic over the hashing function.
This is very useful for people to be able to choose, based on whether they care more about speed than security in the particular functionality they are using the map in.

I think, this would be a good feature to have here.

Hi,

While developing concurrent-swiss-map, I already calculate the hash of the key, after calling the Put function that hash calculation will be made again.

If we have a method that get hash value as a parameter and a value, would be great.