Skip to content

kll-percall (lib) reports a nominal 4·k footprint, not asap_sketchlib's allocation #191

Closed

Description

@zzylol

kll-percall on the lib library reports a nominal footprint, kll_footprint = 4 · k · sizeof(T) (sketch-bench/src/wrappers/kll/mod.rs:19): 1600 B at k = 50, 6400 B at k = 200, 25600 B at k = 800. It is the same at every item count (approxbench reports 1600 B at 1e3, 1e6 and 1e8 items for k = 50).

It is not what asap_sketchlib::KLL allocates. init_internal (asap_sketchlib 0.3.0, kll.rs:300-326) boxes compute_max_capacity(k, m) item slots once and never grows them, plus a level index of MAX_LEVELS + 1 usizes and a merge buffer of capacity k:

k reported (4·k·8) allocated (slots + levels + merge buffer) allocated / reported
50 1600 B 4640 + 496 + 400 = 5536 B 3.46×
200 6400 B 8032 + 496 + 1600 = 10128 B 1.58×
800 25600 B 22240 + 496 + 6400 = 29136 B 1.14×

aqpbm-planeval (handle.rs:40-59, 995-1006) and the hydra-kll wrapper (hydra_kll/mod.rs:33) already replicate the library's capacity; the kll-percall lib rows don't.

Impact. The optimizer's cost table takes KLL's mem_bytes_per_instance from these rows (study_saturation.py --phase optimizer-cost), so KLL memory is understated about 3.5× at k = 50. Memory-weighted results that chose KLL (the Fargate weight setting of the AutoSketch-vs-ASAP eval merged in #138) need a new cost table and a rerun. The CPU-only results are unaffected.

Fix. Report the allocation for the lib rows, sharing the replica with hydra-kll. The oxide rows keep a nominal size: sketch_oxide's KLL grows its buffers as it fills.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions