brentp/intintmap

fast int64-int64 map for go

intintmap's Issues

Port to type parameters (code included)

Hi, I wasn't sure exactly how to go about this, so just jumping in

First of all, thanks for an amazing project <3 We have used it a lot at work and the results have been great.

I took a stab at porting everything to type parameters / aka generics, since we have want to use this data structure for uint16s and other integer types as well. I uploaded the result here https://github.com/kamstrup/intmap

I am not sure if it makes sense to create a PR for this project since I broke API and changed prettymuch everything in the effort -- also the intintmap package name no longer applies since only the keys are required to be of int sub-type in the new project, values can be anything. So I renamed to just "intmap" :-)

If you want to update this repo to hold the new project I can def figure something out, just let me know what you think 👍

Is there a way to do a PutIfNotExists

I'd like to insert in case something does not exist to reduce the roundtrip

Unexpected results with Map.Items()

Hi,

m.Items() gives some unexpected results when you add a key with value 0.

This can be fixed by something like this:

// Items returns a channel for iterating all key-value pairs.
func (m *Map) Items() chan [2]int64 {
	c := make(chan [2]int64, 10)
	go func() {
		data := m.data
		var k int64

		if m.hasFreeKey {
			c <- [2]int64{FREE_KEY, m.freeVal}
		}

		for i := 0; i < len(data); i += 2 {
			k = data[i]
			if k == FREE_KEY {
				continue
			}
			c <- [2]int64{k, data[i+1]}
		}
		close(c)
	}()
	return c
}

iterating over map is 10x slower

func BenchmarkIntIntMapIterKeys(b *testing.B) {
	var j, v, sum int64
	var ok bool
	m := New(2048, 0.60)
	fillIntIntMap(m)
	for i := 0; i < b.N; i++ {
		sum = int64(0)
		for j = range m.Keys() {
			if v, ok = m.Get(j); ok {
				sum += j
				sum += v
			}
		}
		//log.Println("int int sum:", sum)
	}
}

func BenchmarkIntIntMapIterItems(b *testing.B) {
	var j, v, sum int64
	var kv [2]int64
	m := New(2048, 0.60)
	fillIntIntMap(m)
	for i := 0; i < b.N; i++ {
		sum = int64(0)
		for kv = range m.Items() {
			j = kv[0]
			v = kv[1]
			sum += j
			sum += v
		}
		//log.Println("int int sum:", sum)
	}
}

func BenchmarkIntIntMapIterNoChan(b *testing.B) {
	var sum int64
	m := New(2048, 0.60)
	fillIntIntMap(m)
	for i := 0; i < b.N; i++ {
		sum = int64(0)
		m.Items2(func(k, v int64) {
			sum += k
			sum += v
		})

		//log.Println("int int sum:", sum)
	}
}

func BenchmarkStdMapIter(b *testing.B) {
	var j, v, sum int64
	m := make(map[int64]int64, 2048)
	fillStdMap(m)
	for i := 0; i < b.N; i++ {
		sum = int64(0)
		for j, v = range m {
			sum += j
			sum += v
		}
		//log.Println("map sum:", sum)
	}
}

cpu: AMD Ryzen 9 5950X 16-Core Processor            
BenchmarkIntIntMapIterKeys
BenchmarkIntIntMapIterKeys-32      	       9	 119676935 ns/op
BenchmarkIntIntMapIterItems
BenchmarkIntIntMapIterItems-32     	       8	 127800299 ns/op
BenchmarkIntIntMapIterNoChan
BenchmarkIntIntMapIterNoChan-32    	      76	  14489078 ns/op
BenchmarkStdMapIter
BenchmarkStdMapIter-32             	      69	  15238876 ns/op

Some bounds checking can be eliminated for extra speed

I have been looking at the performance of this package, specifically at bounds check elimination that was introduced since Go 1.7.

Using go build -gcflags="-d=ssa/check_bce/debug=1" it seems there is a lot of bounds checking going on. Eliminating might in some cases increase performance so I took a quick look if there is some low hanging fruit to be found. There is 1 minor change that can be implemented that impacts performance quit a lot in the 10 Percent hitrate benchmark on my machine:

Before:

goarch: amd64
pkg: github.com/Marreck/intintmap
BenchmarkIntIntMapFill-4                   	      10	 158195310 ns/op
BenchmarkStdMapFill-4                      	       5	 281591720 ns/op
BenchmarkIntIntMapGet10PercentHitRate-4    	   20000	     70048 ns/op
BenchmarkStdMapGet10PercentHitRate-4       	   20000	     65797 ns/op
BenchmarkIntIntMapGet100PercentHitRate-4   	     500	   3021940 ns/op
BenchmarkStdMapGet100PercentHitRate-4      	     100	  10399684 ns/op
PASS

After:

goarch: amd64
pkg: github.com/Marreck/intintmap
BenchmarkIntIntMapFill-4                   	      10	 159295270 ns/op
BenchmarkStdMapFill-4                      	       5	 282393180 ns/op
BenchmarkIntIntMapGet10PercentHitRate-4    	   20000	     58797 ns/op
BenchmarkStdMapGet10PercentHitRate-4       	   20000	     67847 ns/op
BenchmarkIntIntMapGet100PercentHitRate-4   	     500	   2955890 ns/op
BenchmarkStdMapGet100PercentHitRate-4      	     100	  10299620 ns/op
PASS

How can the source...

... be changed for int32 -> int32? , thanks.