faststringmap

README

faststringmap

faststringmap is a fast read-only string keyed map for Go (golang). It also has the following advantages:

• look up strings and byte slices without use of the unsafe package
• minimal impact on GC due to lack of pointers in the data structure
• data structure can be trivially serialized to disk or network
• supports any type as the value type (via generics)

The module provided a generic Map[T] type that implements a map string from string (or []byte) to a generic type T.

faststringmap is a variant of a data structure called a Trie. At each level we use a slice to hold the next possible byte values. This slice is of length one plus the difference between the lowest and highest possible next bytes of strings in the map. Not all the entries in the slice are valid next bytes. faststringmap is thus more space efficient for keys using a small set of nearby runes, for example those using a lot of digits.

Example

Example usage can be found in faststringmap_example_test.go.

Motivation

Duncan Harris first created faststringmap in order to improve the speed of parsing CSV where the fields were category codes from survey data. The majority of these were numeric ("1", "2", "3"...) plus a distinct code for "not applicable". I was struck that in the simplest possible cases (e.g. "1" ... "5") the map should be a single slice lookup.

I then forked the origin repo, and improved on Duncan's implementation:

• Added generic value type support
• Simplified overall implementation

Benchmarks

$ go test . -bench ^Benchmark   
goos: darwin
goarch: arm64
pkg: alon.kr/x/faststringmap
cpu: Apple M2 Pro
BenchmarkFastStringMap-10         201025              5935 ns/op
BenchmarkGoStringMap-10           117952             11465 ns/op
PASS
ok      alon.kr/x/faststringmap 3.829s

Documentation

Overview

Example

package main

import (
	"fmt"
	"sort"

	"alon.kr/x/faststringmap"
)

func main() {
	m := []faststringmap.MapEntry[uint32]{
		{"key1", 42},
		{"key2", 27644437},
		{"l", 2},
	}

	fm := faststringmap.NewMap[uint32](m)

	// add an entry that is not in the fast map
	m = append(m, faststringmap.MapEntry[uint32]{"m", 4})

	// sort the keys so output is the same for each test run
	keys := make([]string, 0, len(m))
	for _, e := range m {
		keys = append(keys, e.Key)
	}
	sort.Strings(keys)

	// lookup every key in the fast map and print the corresponding value
	for _, k := range keys {
		v, ok := fm.LookupString(k)
		fmt.Printf("%q: %d, %v\n", k, v, ok)
	}

}

Output:

"key1": 42, true
"key2": 27644437, true
"l": 2, true
"m": 0, false

Index

• type Map
  • func FromMap[T any](m map[string]T) Map[T]
  • func NewMap[T any](entries []MapEntry[T]) Map[T]
  • func (m *Map[T]) AtIndex(index Uint) (t T, ok bool)
  • func (m *Map[T]) IndexBytes(s []byte) Uint
  • func (m *Map[T]) IndexString(s string) Uint
  • func (m *Map[T]) LookupBytes(s []byte) (t T, ok bool)
  • func (m *Map[T]) LookupString(s string) (t T, ok bool)
• type MapEntry
• type Uint

Examples

• Package

Types

type Map

type Map[T any] struct {
	// contains filtered or unexported fields
}

Map[T] is a fast read only map from string to generic type T Lookups are about 5x faster than the built-in Go map type

func FromMap

func FromMap[T any](m map[string]T) Map[T]

FromMap[T] constructs a new Map from a builtin Go map

func NewMap

func NewMap[T any](entries []MapEntry[T]) Map[T]

NewMap[T] constructs a new Map from the provided map entries

func (*Map[T]) AtIndex

func (m *Map[T]) AtIndex(index Uint) (t T, ok bool)

AtIndex returns the value in the map at the supplied internal index

func (*Map[T]) IndexBytes

func (m *Map[T]) IndexBytes(s []byte) Uint

IndexBytes returns the index of the value in the map for the supplied byte slice, or 0 if the value is not present in the map. Use AtIndex() to get the value using the resulting index.

func (*Map[T]) IndexString

func (m *Map[T]) IndexString(s string) Uint

IndexString returns the index of the value in the map for the supplied string, or 0 if the value is not present in the map. Use AtIndex() to get the value using the resulting index.

func (*Map[T]) LookupBytes

func (m *Map[T]) LookupBytes(s []byte) (t T, ok bool)

LookupBytes looks up the supplied byte slice in the map

func (*Map[T]) LookupString

func (m *Map[T]) LookupString(s string) (t T, ok bool)

LookupString looks up the supplied string in the map

type MapEntry

type MapEntry[T any] struct {
	Key   string
	Value T
}

MapEntry[T] is for supplying data to initialize a new map

type Uint

type Uint = uint32