brentp/intintmap

fast int64-int64 map for go

Fast int64 -> int64 hash in golang.

intintmap

import "github.com/brentp/intintmap"

Package intintmap is a fast int64 key -> int64 value map.

It is copied nearly verbatim from http://java-performance.info/implementing-world-fastest-java-int-to-int-hash-map/ .

It interleaves keys and values in the same underlying array to improve locality.

It is 2-5X faster than the builtin map:

BenchmarkIntIntMapFill                 	      10	 158436598 ns/op
BenchmarkStdMapFill                    	       5	 312135474 ns/op
BenchmarkIntIntMapGet10PercentHitRate  	    5000	    243108 ns/op
BenchmarkStdMapGet10PercentHitRate     	    5000	    268927 ns/op
BenchmarkIntIntMapGet100PercentHitRate 	     500	   2249349 ns/op
BenchmarkStdMapGet100PercentHitRate    	     100	  10258929 ns/op

Usage

m := intintmap.New(32768, 0.6)
m.Put(int64(1234), int64(-222))
m.Put(int64(123), int64(33))

v, ok := m.Get(int64(222))
v, ok := m.Get(int64(333))

m.Del(int64(222))
m.Del(int64(333))

fmt.Println(m.Size())

for k := range m.Keys() {
    fmt.Printf("key: %d\n", k)
}

for kv := range m.Items() {
    fmt.Printf("key: %d, value: %d\n", kv[0], kv[1])
}

type Map

type Map struct {
}

Map is a map-like data-structure for int64s

func New

func New(size int, fillFactor float64) *Map

New returns a map initialized with n spaces and uses the stated fillFactor. The map will grow as needed.

func (*Map) Get

func (m *Map) Get(key int64) (int64, bool)

Get returns the value if the key is found.

func (*Map) Put

func (m *Map) Put(key int64, val int64)

Put adds or updates key with value val.

func (*Map) Del

func (m *Map) Del(key int64)

Del deletes a key and its value.

func (*Map) Keys

func (m *Map) Keys() chan int64

Keys returns a channel for iterating all keys.

func (*Map) Items

func (m *Map) Items() chan [2]int64

Items returns a channel for iterating all key-value pairs.

func (*Map) Size

func (m *Map) Size() int

Size returns size of the map.

intintmap's Issues

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

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
}

Is there a way to do a PutIfNotExists

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

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

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 👍

How can the source...

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