Skip to content

FSST: codes buffer keeps up to ~2x spare capacity after compression, not counted in nbytes() #11420

Open

Description

@anoop-narang

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:

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: develop at 824c922e8e16f541572ef3da669166380c4ee1c1
  • 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

  1. shu-chen-dot-ca commented on Nov 12, 2026

    @shu-chen-dot-ca

    I'll take this one.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

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