constmap

The constmap formats are shared with rsconstmap (Rust) and fastconstmap (C/Python). You can load files generated by these implementations on little-endian hosts (x86-64, ARM64, etc.).

• VerifiedConstMap and PairedVerifiedConstMap are identical across implementations.
• ConstMap files from fastconstmap use the magic CMAP0003 (which includes an extra 4-byte key count); this package's ReadFrom accepts these and ignores the extra count.

Note: Files written by fastconstmap version 0.9 and earlier use the XXH3 hash and are not compatible with this package.

// Load a verified map built by Python
vm, err := constmap.LoadVerifiedFromFile("built-by-python.vmap")

// Load a standard map built by Rust
cm, err := constmap.LoadFromFile("built-by-rust.cmap")

To run the standard benchmark suite (comparing against Go's built-in map), use:

go test -bench=. -benchmem

For stable, reproducible results with multiple iterations and longer execution times, use:

go test -bench=. -benchmem -count=5 -benchtime=3s

To run the memory usage comparison test:

go test -run TestMemoryUsage -v

To install the constmap package in your Go project, use the following command:

go get github.com/lemire/constmap

Execute all tests using the standard Go test command.

go test -v

Use constmap.New(keys, values) to create an immutable map from string keys to uint64 values.

Requirements:

• keys and values slices must have equal length.
• keys must be unique.

Warning: After construction, the map is immutable. If you look up a key that was not in the original set, it returns an undefined value. Use VerifiedConstMap if you need to detect missing keys.

package main

import (
	"fmt"
	"log"

	"github.com/lemire/constmap"
)

func main() {
	keys := []string{"apple", "banana", "cherry"}
	values := []uint64{100, 200, 300}

	cm, err := constmap.New(keys, values)
	if err != nil {
		log.Fatal(err)
	}

	fmt.Println(cm.Map("banana")) // 200
}

The MapMany and MapManyInto methods are designed to be faster than a standard loop over Map by overlapping memory accesses (memory-level parallelism).

• Mechanism: The implementation processes keys in blocks (defined by batchBlock = 8). It hashes a block of keys before gathering values, allowing multiple array accesses to be in flight simultaneously.
• Performance Gains: The benefit depends on memory latency and cache size. For example, with a million keys, batching was observed to be ~18% faster on an Apple M4 Max and ~8% faster on an Intel Xeon Gold 6548N for ConstMap. For VerifiedConstMap, which touches more arrays, the gains were ~11% on Apple M4 Max and ~24% on Intel Xeon Gold 6548N.
• Limitations: If a key is 32 bytes or longer, it may drop the block back to per-key hashing, reducing the batching advantage.

A PairedVerifiedConstMap is a specialized memory layout of a VerifiedConstMap. Instead of keeping values and fingerprints in separate arrays, it stores each value next to its fingerprint in a single slots array.

When to use it:

• Pros: On a cache-miss (present key), it is approximately 20% faster on Intel Xeon Gold 6548N and 10% faster on Apple M4 Max because it touches fewer cache lines (3 lines instead of 6).
• Cons: On an absent key, it is slower than a standard VerifiedConstMap because it always brings the value into the cache alongside the fingerprint, whereas a standard map only reads the fingerprint array.

Note: The serialized format is unique to the paired layout and is not interchangeable with the standard VerifiedConstMap format.

If you need to distinguish between a valid value and a missing key, use VerifiedConstMap. It stores a verification fingerprint for each key, allowing it to detect (with high probability) lookups of keys that were not in the original set.

• Construction: Use NewVerified(keys []string, values []uint64).
• Lookup: Use Map(key string) uint64. If the key was not in the original set, it returns the sentinel value constmap.NotFound (0xFFFFFFFFFFFFFFFF).
• Trade-off: It uses approximately double the memory (~18 bytes/key instead of ~9).

keys := []string{"apple", "banana"}
values := []uint64{1, 2}

vm, err := constmap.NewVerified(keys, values)
if err != nil {
    log.Fatal(err)
}

val := vm.Map("missing_key")
if val == constmap.NotFound {
    fmt.Println("Key not found!")
}

You can persist a ConstMap or VerifiedConstMap to disk using the following methods:

For ConstMap

• cm.SaveToFile(path string): Serializes the map to the specified path.
• constmap.LoadFromFile(path string): Deserializes a map from the specified path.

For VerifiedConstMap

• vm.SaveToFile(path string): Serializes the verified map to the specified path.
• constmap.LoadVerifiedFromFile(path string): Deserializes a verified map from the specified path.

Format Details:

• The format is little-endian and includes an FNV-1a 64-bit checksum for integrity verification.
• The formats are compatible with rsconstmap (Rust) and fastconstmap (C/Python) on little-endian hosts.

// Saving
cm.SaveToFile("map.bin")

// Loading
newCm, err := constmap.LoadFromFile("map.bin")

For streaming operations, use WriteTo and ReadFrom which accept any implementation of io.Writer or io.Reader.

// Write to any io.Writer.
n, err := cm.WriteTo(w)

// Read from any io.Reader.
var cm constmap.ConstMap
n, err := cm.ReadFrom(r)