colinmarc / colinmarc/cdb

Make sure that the `key` argument on `Get` doesn't need to be allocated on heap

Open
#12 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
69
Forks
13
PR merge metrics
No merged PRs in 30d

Description

Currently, when one calls `cdb.Get(key)`, if the caller has the key on stack, like `key := [4]byte {0,1,2,3}`, the Go compiler decides that the value "escapes" and thus it must be allocated on the heap. (The reason being that `cdb.hash` uses that `key` value, and an arbitrary implementation might decide to keep a slice of the key.)

This can be spotted with the following simple test:
~~~~
func BenchmarkStackEscapeYes(b *testing.B) {
db, err := cdb.OpenMmap("./test/test.cdb")
require.NoError(b, err)
require.NotNil(b, db)

for i := 0; i < b.N; i++ {
keyOnStack := [2]byte {'X', byte (i)}
keySlice := keyOnStack[:]
db.Get(keySlice)
}
}
~~~~

If comipilled as `go test -gcflags -m` one can see the message `./noescape_test.go:32:3: moved to heap: keyOnStack`.

The following two patches solve this issue:
* https://github.com/cipriancraciun/go-cdb-lib/commit/5b54da10043798cb8ed6c4c99ab6ada9362c4413 -- adds the `NoEscapeBytes` function based on what Go's `runtime` does internally -- https://github.com/golang/go/blob/ecb2f231fa41b581319505139f8d5ac779763bee/src/runtime/stubs.go#L172-L181
* https://github.com/cipriancraciun/go-cdb-lib/commit/e860a79836f2daefeea77602feb9b3d3c99f2ebe -- a simple patch of the `Get` function that uses the `NoEscapeBytes`, which tricks the Go compiler into not requiring the key to be heap allocated;

The performance improvements are about ~10ns per call, which if also using the `mmap` patch sent earlier represents 50% of the total runtime.

~~~~
BenchmarkStackEscapeNo-4 1000000000 9.368 ns/op 0 B/op 0 allocs/op
BenchmarkStackEscapeYes-4 1000000000 23.12 ns/op 2 B/op 1 allocs/op
~~~~

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the Get entry point and cdb.hash, then inspect the benchmark in noescape_test.go using go test -gcflags -m and test/test.cdb. Compare the two linked patches and verify that stack keys no longer escape, with the benchmark showing 0 B/op and 0 allocs/op.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
database
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.