8000 Tags · achille-roussel/kway-go · GitHub
[go: up one dir, main page]

Skip to content

Tags

Tags

v1.0.2

Toggle v1.0.2's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
Do not refill sources while unyielded values reference their batches (#4

)

## The bug

`tree.next` and `merge2` pulled the next batch from a source as soon as
its current batch was exhausted, while values copied from that batch
were still sitting in the *unyielded* output buffer. Pulling resumes the
producer, which may recycle the memory holding the values it yielded
before.

For value types (`int`, `string`) this is harmless because the copy into
the output buffer is a full copy. For element types with interior
pointers (`T = []byte`, structs containing slices) the copy shares
backing memory, and a source that reuses its buffers across pulls
corrupts output that was already merged but not yet yielded. This blocks
using kway-go from parquet-go, where `T = parquet.Row = []Value` and the
values point into page buffers that are recycled on the next read.

## The fix: flush before refill

Never pull from a source while the output buffer holds values copied
from that source's current batch: when the batch is exhausted and the
buffer is non-empty, yield the buffer first and refill on the next
iteration, by which time the caller is done with the values.

- `tree.go`: the tree already had a `pending` flag for the batches it
passes through to the caller without copying them ("do not refill this
cursor until the caller is done with the batch"). The copy path in
`nextScalar` and `nextRuns` now reuses it: when the winner's cursor runs
out of values and `n > 0`, the tree returns `buf[:n]` and refills,
replays and continues on the next call. With `n == 0` nothing is at
risk, so the refill happens in place and the tree never returns a
spurious empty batch, which `merge` reads as end of stream.
- `merge.go`: `merge2` yields `buffer[:offset]` before calling
`next0`/`next1`. The tail fast paths that pass a source's own slice
through are safe as-is: the consumer is done with the slice by the time
`yield` returns, and the next pull happens after that.

The flush only happens when a refill is actually needed, keeping the
yielded batches as large as the sources allow.

## Regression test

`TestMergeSliceRecycledBuffers` merges k sources of `[]byte` where every
value of a source is backed by a single buffer that the source poisons
with `'#'` on each pull. 24 subtests cover k = 2 (the `merge2` path), 3
and 8 (the tree path), batch sizes 1, 5, 32 and 128 (the larger ones
also drive the zero-copy passthrough), and both distinct and duplicate
values across sources. The test fails on the current code (output comes
back full of `########` and repeated values) and passes with the fix.

## Verification

- No public API changes; the memory contract for the input sequences is
now documented on `MergeSlice`.
- `go test`, `go test -race -count 2` and `go vet` all pass.
- Benchmarks (`-count 6`, benchstat) are a wash: geomean -0.16% on
sec/op. Worst cases are `MergeSlice3` (+3.7%) and `MergeSlice2` (+2.6%),
which refill most often relative to their buffer size, offset by
`Merge2` (-3.1%), `MergeBlocks8` (-1.6%) and `MergeSliceBlocks2`
(-1.3%).

🤖 Generated with [Claude Code](https://claude.com/claude-code)

v1.0.1

Toggle v1.0.1's commit message
fix out of range slice index

Signed-off-by: Achille Roussel <achille.roussel@gmail.com>

v1.0.0

Toggle v1.0.0's commit message
upgrade to require Go 1.23

Signed-off-by: Achille Roussel <achille.roussel@gmail.com>

v0.3.1

Toggle v0.3.1's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
Fix merge2 bug (#2)

v0.3.0

Toggle v0.3.0's commit message
add example showing how to create asynchronous input sequences

Signed-off-by: Achille Roussel <achille.roussel@gmail.com>

v0.2.3

Toggle v0.2.3's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
README: add graph

Signed-off-by: Achille <achille.roussel@gmail.com>

v0.2.2

Toggle v0.2.2's commit message
README: fix typos

Signed-off-by: Achille Roussel <achille.roussel@gmail.com>

v0.2.1

Toggle v0.2.1's commit message
README: update examples

Signed-off-by: Achille Roussel <achille.roussel@gmail.com>

v0.2.0

Toggle v0.2.0's commit message
README: fix formatting

Signed-off-by: Achille Roussel <achille.roussel@gmail.com>

v0.1.0

Toggle v0.1.0's commit message
update README

Signed-off-by: Achille Roussel <achille.roussel@gmail.com>
0