Repository navigation
Description
What happened?
After fsst_compress, the FSST codes buffer can hold up to about 2x its length in spare capacity. nbytes() counts the buffer's length, not its allocation, so an FSST array can keep up to about 1.9x its nbytes() allocated.
The codes buffer starts empty, grows by extend_from_slice once per batch, and is frozen without being shrunk:
compress.rs#L334:codes: ByteBufferMut::empty_aligned_in(..)compress.rs#L374:self.codes.extend_from_slice(&self.batch_codes)compress.rs#L401:self.codes.freeze()buffer_mut.rs#L536: growth at least doubles the capacity, andfreezekeeps the allocation.
Array::nbytes() is documented as returning "the estimated physical bytes owned or referenced by this array tree" (typed.rs#L458). It sums buffer lengths, though, and once the buffer is frozen, nothing exposes the allocation's size. I expected the frozen codes buffer to be close to its length, so that the memory an FSST array holds is close to its nbytes().
Steps to reproduce
Cargo.toml:
[package]
name = "fsst-repro"
version = "0.1.0"
edition = "2024"
[dependencies]
vortex-array = { git = "https://github.com/vortex-data/vortex", rev = "824c922e8e16f541572ef3da669166380c4ee1c1" }
vortex-fsst = { git = "https://github.com/vortex-data/vortex", rev = "824c922e8e16f541572ef3da669166380c4ee1c1" }
vortex-session = { git = "https://github.com/vortex-data/vortex", rev = "824c922e8e16f541572ef3da669166380c4ee1c1" }src/main.rs, which counts live heap bytes around fsst_compress:
use std::alloc::{GlobalAlloc, Layout, System};
use std::sync::atomic::{AtomicUsize, Ordering::Relaxed};
use vortex_array::arrays::VarBinArray;
use vortex_array::dtype::{DType, Nullability};
use vortex_array::{IntoArray, VortexSessionExecute};
use vortex_fsst::{fsst_compress, fsst_train_compressor};
use vortex_session::VortexSession;
struct Counting;
static LIVE: AtomicUsize = AtomicUsize::new(0);
unsafe impl GlobalAlloc for Counting {
unsafe fn alloc(&self, l: Layout) -> *mut u8 {
LIVE.fetch_add(l.size(), Relaxed);
unsafe { System.alloc(l) }
}
unsafe fn dealloc(&self, p: *mut u8, l: Layout) {
LIVE.fetch_sub(l.size(), Relaxed);
unsafe { System.dealloc(p, l) }
}
unsafe fn realloc(&self, p: *mut u8, l: Layout, n: usize) -> *mut u8 {
LIVE.fetch_add(n, Relaxed);
LIVE.fetch_sub(l.size(), Relaxed);
unsafe { System.realloc(p, l, n) }
}
}
#[global_allocator]
static A: Counting = Counting;
fn main() {
for str_len in [32, 64, 80, 128, 160] {
let session = VortexSession::empty();
vortex_fsst::initialize(&session);
let mut ctx = session.create_execution_ctx();
// 8192 random hex strings of `str_len` characters.
let mut x: u64 = 1;
let strings: Vec<String> = (0..8192)
.map(|_| {
(0..str_len / 16)
.map(|_| {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
format!("{x:016x}")
})
.collect()
})
.collect();
let input = VarBinArray::from_iter(
strings.iter().map(|s| Some(s.as_str())),
DType::Utf8(Nullability::NonNullable),
)
.into_array();
let compressor = fsst_train_compressor(&input, &mut ctx).unwrap();
let before = LIVE.load(Relaxed);
let fsst = fsst_compress(&input, &compressor, &mut ctx).unwrap();
let held = LIVE.load(Relaxed) - before;
let codes = fsst.codes_bytes().len();
let nbytes = fsst.into_array().nbytes();
println!(
"str_len={str_len:<4} codes_len={codes:<8} nbytes={nbytes:<8} held={held:<8} held/nbytes={:.2}",
held as f64 / nbytes as f64
);
}
}cargo run --release prints:
str_len=32 codes_len=137243 nbytes=205078 held=209963 held/nbytes=1.02
str_len=64 codes_len=273106 nbytes=340941 held=345826 held/nbytes=1.01
str_len=80 codes_len=341076 nbytes=408911 held=618584 held/nbytes=1.51
str_len=128 codes_len=544274 nbytes=612109 held=1161236 held/nbytes=1.90
str_len=160 codes_len=679795 nbytes=747630 held=1160848 held/nbytes=1.55
held is the live heap that fsst_compress leaves behind: the returned array plus whatever it keeps alive. The excess over nbytes matches the codes buffer's spare capacity. It depends only on where the final batch lands relative to the last doubling, so it varies from about 1.0x to 1.9x as the input size changes.
Environment
- Vortex:
developat824c922e8e16f541572ef3da669166380c4ee1c1 - Rust 1.99.1
- macOS 26.2 (arm64)
Additional context
This matters wherever FSST arrays are kept in memory and sized by nbytes(), for example an in-memory cache with a byte budget. There, the cache can hold up to about 2x what it counts.
A possible fix: at the end of finish, copy the codes into an exactly sized buffer when the spare capacity is large (for example, more than 25% of the length). That costs one copy of the compressed bytes. Another option is to reserve the codes capacity up front from an estimate.
#10599 / #11382 fixed a similar nbytes() versus retained-memory gap for constant string scalars.
This issue was investigated and written with AI assistance (Claude Code). The output above is pasted unedited from running the reproducer as shown.
Activity
fix(cache): own exactly the bytes a liquid array holds (#61)
shu-chen-dot-ca commentedon Nov 12, 2026
I'll take this one.