Skip to content

perf: replace arr_build_full ht_head memset with versioned bucket heads #806

Description

@justinjoy

Background

Issue #740 recorded a negative finding from PR #731: the CRDT perf rep stos bar is not caused by the per-row timestamp memset in col_join_append_pair. That memset compiles inline and should not be retried as the target.

The likely hot site remains the full arrangement rebuild path:

  • wirelog/columnar/arrangement.c: arr_build_full() clears arr->ht_head with memset(arr->ht_head, 0xFF, nbuckets * sizeof(uint32_t)) before rebuilding chains.
  • CRDT recursive strata can trigger repeated full arrangement rebuilds as the right-side IDB grows.

Proposed direction

Investigate replacing the full ht_head clear with versioned bucket heads, for example:

  • Add a generation/version side array or tagged bucket-head representation to col_arrangement_t.
  • Increment the arrangement build generation on full rebuild instead of clearing every bucket.
  • Treat a bucket as empty when its stored generation differs from the current build generation.
  • Preserve existing UINT32_MAX/chain semantics or migrate them carefully.

This likely changes col_arrangement_t layout, so update the layout sentinel in tests/test_arrangement.c intentionally if the design lands.

Acceptance criteria

  • Do not touch or retry lazy timestamp memset in col_join_append_pair; do-not-retry: lazy timestamp memset in col_join_append_pair (wrong target) #740 established that as the wrong target.
  • Correctness preserved for existing arrangement tests, including incremental update, cache reuse, LRU eviction, K-fusion isolation, and join arrangement tests.
  • Add targeted tests for version wrap/clear fallback if generation counters can wrap.
  • Benchmark CRDT W=1/W=8 before and after; show whether the libc memset bar moves or disappears.
  • If the design regresses memory, document the tradeoff and gate it behind a measured win.

References

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions