cuckoo

README

cuckoo

Package cuckoo implements d-ary bucketized cuckoo hashing with stash (bucketized cuckoo hashing is also known as splash tables). This implementation uses configurable number of hash functions and cells per bucket. Greedy algorithm for collision resolution is a random walk.

Purpose

Cuckoo is a memory-efficient alternative to the built-in map[Key]Value type (where Key is an integer type and Value can be any type) with zero per-item overhead. Hence, the memory-efficiency is equal to the load factor (which can be as high as 99%).

Performance

Benchmark results on linux/amd64 with i7-4770S (2M uint32 Key/Value insertion) with gc compiler (version 1.7):

go test -bench=. -v -cpu 1
=== RUN   TestZero
--- PASS: TestZero (0.00s)
=== RUN   TestSimple
--- PASS: TestSimple (1.28s)
=== RUN   TestMem
--- PASS: TestMem (0.41s)
		cuckoo_test.go:148: LoadFactor: 0.9534401893615723
		cuckoo_test.go:149: Built-in map memory usage (MiB): 65.57434844970703
		cuckoo_test.go:150: Cuckoo hash  memory usage (MiB): 16.000137329101562
BenchmarkCuckooInsert   10000000               121 ns/op               0 B/op          0 allocs/op
BenchmarkCuckooSearch   20000000                83.8 ns/op             0 B/op          0 allocs/op
BenchmarkCuckooDelete   20000000               132 ns/op               0 B/op          0 allocs/op
BenchmarkMapInsert      10000000               130 ns/op               9 B/op          0 allocs/op
BenchmarkMapSearch      20000000                81.6 ns/op             0 B/op          0 allocs/op
BenchmarkMapDelete      100000000               11.7 ns/op             0 B/op          0 allocs/op
PASS
ok      github.com/salviati/cuckoo      12.941s

Arch-specific optimizations

Cuckoo is SIMD-friendly by design, and there are plans for fast-path SIMD functions.

Usage

After cloning the repository, modify the definitions of Key and Value types to fit your needs. For optimal performance, you should also experiment with the fine-grade parameters of the algorithm listed in config.go.

Documentation

godoc

License

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Documentation

Overview

Package cuckoo implements d-ary bucketized cuckoo hashing with stash (bucketized cuckoo hashing is also known as splash tables). This implementation uses configurable number of hash functions and cells per bucket. Greedy algorithm for collision resolution is a random walk.

Index

• Constants
• type Cuckoo
  • func NewCuckoo(logsize int) *Cuckoo
  • func (c *Cuckoo) Delete(k Key)
  • func (c *Cuckoo) ForRange(f func(Key, Value))
  • func (c *Cuckoo) Insert(k Key, v Value)
  • func (c *Cuckoo) Len() int
  • func (c *Cuckoo) LoadFactor() float64
  • func (c *Cuckoo) Search(k Key) (v Value, ok bool)
• type Key
• type Value

Constants

const (
	DefaultLogSize = 8 + bshift // A reasonable logsize value for NewCuckoo for use when the number of items to be inserted is not known ahead.
)

other configurable variables

Types

type Cuckoo

type Cuckoo struct {
	// contains filtered or unexported fields
}

Cuckoo implements a memory-efficient map[Key]Value equivalent where Key is an integer and Value can be anything. Similar to built-in maps Cuckoo is not thread-safe. In a parallel environment you may need to wrap access with mutexes.

func NewCuckoo

func NewCuckoo(logsize int) *Cuckoo

Logsize mustn't exceed hashBits, defined in hash.go.

func (*Cuckoo) Delete

func (c *Cuckoo) Delete(k Key)

Delete removes the item corresponding to the given key (if exists).

func (*Cuckoo) ForRange

func (c *Cuckoo) ForRange(f func(Key, Value))

ForRange loops over all (key,value) pairs in the hash map and calls f for each.

func (*Cuckoo) Insert

func (c *Cuckoo) Insert(k Key, v Value)

Insert adds given key/value item into the hash map. If an item with key k already exists, it will be replaced.

func (*Cuckoo) Len

func (c *Cuckoo) Len() int

Len returns the number of items in the hash map.

func (*Cuckoo) LoadFactor

func (c *Cuckoo) LoadFactor() float64

LoadFactor returns the load factor of the hash table, which is the ratio of the used cells to the allocated cells.

func (*Cuckoo) Search

func (c *Cuckoo) Search(k Key) (v Value, ok bool)

Search tries to retrieve the value associated with the given key. If no such item is found, ok is set to false.

type Key

type Key uint32

Key must be an integer-type.

type Value

type Value uint32

Value can be anything, replace this to match your needs (not using unsafe.Pointer to avoid the overhead to store additional pointer or interface{} which comes with a worse overhead).