Crate lite_strtab

Source

Expand description

§lite-strtab

lite-strtab is a crate for storing many immutable strings in one buffer with minimal resource usage.

It is a simple, in-memory, build-once data structure:

Push strings into a builder
Finalize into an immutable table
Look strings up by StringId

As simple as that.

§Design overview

Memory: one UTF-8 byte buffer plus one compact offset table; optional NUL-termination
CPU: cheap ID-based lookups (bounds check + two offset reads)
Binary size: no panics on insertion, avoiding backtrace overhead

Offset and ID types are configurable to match your workload. The common choice is O = u32 and I = u16.

§Why this exists

[Note: Numbers are for 64-bit machines.]

For a companion blog post with additional design insights and real-world context, see Sometimes I Need to Store a Lot of Strings Efficiently, So I Built lite-strtab.

Types like [Box<[String]>] and [Box<[Box<str>]>] keep one handle per element:

[Box<[String]>]: 24 bytes (ptr + len + capacity)
[Box<[Box<str>]>]: 16 bytes (ptr + len)

This is in addition to allocator overhead per string allocation (metadata + alignment).

In contrast, lite-strtab aims to remove these overheads by storing all strings in a single buffer, with an offset table to define string boundaries.

One raw alloc containing all UTF-8 bytes
One offset table (len + 1 entries, with a final sentinel)

This removes per-string allocation overhead. Rather than storing 16/24 bytes per string (+ allocation overhead), we just store 4 bytes per string (for u32 offsets) + one final sentinel offset.

§Installation

[dependencies]
lite-strtab = "0.1.0"

§Feature flags

Feature	Description
`std`	Enabled by default. The crate still uses `#![no_std]` + `alloc` internally.
`nightly`	Uses Rust’s unstable allocator API instead of `allocator-api2` and requires a nightly compiler (`allocator_api`).

§Basic usage

use lite_strtab::StringTableBuilder;

let mut builder = StringTableBuilder::new();
let hello = builder.try_push("hello").unwrap();
let world = builder.try_push("world").unwrap();

let table = builder.build();
assert_eq!(table.get(hello), Some("hello"));
assert_eq!(table.get(world), Some("world"));

§Choosing `O` and `I`

StringTableBuilder<O, I> has two size/capacity knobs:

O (Offset) stores byte offsets into the shared UTF-8 buffer.
- It limits total stored bytes.
- It costs size_of::<O>() per string inside the StringTable.
I (StringIndex, used by StringId) stores string IDs.
- It limits string count.
- It costs size_of::<I>() per stored ID field (table index) in your own structs.

Most users should start with O = u32, I = u16:

Meaning about 4 GiB of UTF-8 data and 64Ki entries per table
Meaning: 2 bytes per StringId (index into table) in your own structs
- Comparison (64-bit): Box<str> handle is 16 bytes, String is 24 bytes

Capacity quick-reference:

Setting	Bytes	Max value	Practical meaning in this crate
`I = u8`	1	`255`	Up to `256` strings per table
`I = u16`	2	`65,535`	Up to `65,536` strings per table
`I = u32`	4	`4,294,967,295`	Up to `4,294,967,296` strings per table
`O = u16`	2	`65,535`	Up to `65,535` UTF-8 bytes total
`O = u32`	4	`4,294,967,295`	Up to about `4 GiB` UTF-8 bytes total

§Custom allocator

use lite_strtab::{Global, StringTableBuilder};

let mut builder = StringTableBuilder::<u32>::new_in(Global);
let id = builder.try_push("example").unwrap();
let table = builder.build();

assert_eq!(table.get(id), Some("example"));

§Custom `O` and `I` types

use lite_strtab::{Global, StringTableBuilder};

let mut builder = StringTableBuilder::<u16, u8>::new_in(Global);
let id = builder.try_push("tiny-id").unwrap();
let table = builder.build();

assert_eq!(id.into_raw(), 0u8);
assert_eq!(table.get(id), Some("tiny-id"));

If you only want to change O, use StringTableBuilder::<u16>::new_in(Global) and I keeps its default (u16).

§Null-padded mode

Set NULL_PADDED = true to store strings with a trailing NUL byte:

use lite_strtab::StringTableBuilder;

let mut builder = StringTableBuilder::new_null_padded();
let id = builder.try_push("hello").unwrap();
let table = builder.build();

assert_eq!(table.get(id), Some("hello"));   // NUL trimmed
assert_eq!(table.as_bytes(), b"hello\0");   // raw bytes include NUL

§Scope

This crate focuses on in-memory string storage only.

It does not do:

serialization/deserialization
compression/decompression
sorting/deduplication policies

If you need those, build them in a wrapper around this crate.

§Benchmarks

Memory usage was measured on Linux with glibc malloc using malloc_usable_size to capture actual allocator block sizes including alignment and metadata overhead.

They can be captured with cargo run -p lite-strtab --features memory-report --bin memory_report.

How to read these tables:

Total = Heap allocations + Distributed fields + One-time metadata
Distributed fields = string references distributed across fields/structs (e.g. String, Box<str>, StringId<u16>)
in these results, lite-strtab uses StringId<u16>

§Datasets

Three representative datasets were used:

YakuzaKiwami: 4,650 game file paths (238,109 bytes), for example sound/ja/some_file.awb.
EnvKeys: 109 environment variable names from an API specification (1,795 bytes).
ApiUrls: 90 REST API endpoint URLs (3,970 bytes).

§YakuzaKiwami (4650 entries, 238,109 bytes)

Summary

Representation	Total	Heap allocations	Distributed fields	vs lite-strtab
`lite-strtab`	266068 (259.83 KiB)	256736 (250.72 KiB)	9300 (9.08 KiB)	1.00x
`lite-strtab (null-padded)`	270708 (264.36 KiB)	261376 (255.25 KiB)	9300 (9.08 KiB)	1.02x
`Vec<String>`	384240 (375.23 KiB)	272640 (266.25 KiB)	111600 (108.98 KiB)	1.44x
`Box<[Box<str>]>`	346928 (338.80 KiB)	272528 (266.14 KiB)	74400 (72.66 KiB)	1.30x

Heap allocations (tree)

lite-strtab: 256736 (250.72 KiB) (96.49%)
- StringTable<u32, u16> byte buffer: 238120 (232.54 KiB) (92.75% of heap) - concatenated UTF-8 string payload data
- StringTable<u32, u16> offsets buffer: 18616 (18.18 KiB) (7.25% of heap) - u32 offsets into the shared byte buffer
lite-strtab (null-padded): 261376 (255.25 KiB) (96.55%)
- StringTable<u32, u16, true> byte buffer: 242760 (237.07 KiB) (92.88% of heap) - concatenated UTF-8 string payload data with NUL terminators
- StringTable<u32, u16, true> offsets buffer: 18616 (18.18 KiB) (7.12% of heap) - u32 offsets into the shared byte buffer
Vec<String>: 272640 (266.25 KiB) (70.96%)
- String payload allocations: 272640 (266.25 KiB) (100.00% of heap) - one UTF-8 allocation per string
Box<[Box<str>]>: 272528 (266.14 KiB) (78.55%)
- Box<str> payload allocations: 272528 (266.14 KiB) (100.00% of heap) - one UTF-8 allocation per string

Distributed fields (per-string handles)

lite-strtab: 9300 (9.08 KiB) (3.50%) - StringId<u16>: field per string (2 B each x 4650)
Vec<String>: 111600 (108.98 KiB) (29.04%) - String: field per string (24 B each x 4650)
Box<[Box<str>]>: 74400 (72.66 KiB) (21.45%) - Box<str>: field per string (16 B each x 4650)

One-time metadata (table object itself)

lite-strtab: 32 B (StringTable<u32, u16> struct itself; one per table, not per string)

§EnvKeys (109 entries, 1,795 bytes)

Summary

Representation	Total	Heap allocations	Distributed fields	vs lite-strtab
`lite-strtab`	2490 (2.43 KiB)	2240 (2.19 KiB)	218 B	1.00x
`lite-strtab (null-padded)`	2602 (2.54 KiB)	2352 (2.30 KiB)	218 B	1.04x
`Vec<String>`	5504 (5.38 KiB)	2888 (2.82 KiB)	2616 (2.55 KiB)	2.21x
`Box<[Box<str>]>`	4472 (4.37 KiB)	2728 (2.66 KiB)	1744 (1.70 KiB)	1.80x

Heap allocations (tree)

lite-strtab: 2240 (2.19 KiB) (89.96%)
- StringTable<u32, u16> byte buffer: 1800 (1.76 KiB) (80.36% of heap) - concatenated UTF-8 string payload data
- StringTable<u32, u16> offsets buffer: 440 B (19.64% of heap) - u32 offsets into the shared byte buffer
lite-strtab (null-padded): 2352 (2.30 KiB) (90.39%)
- StringTable<u32, u16, true> byte buffer: 1912 (1.87 KiB) (81.29% of heap) - concatenated UTF-8 string payload data with NUL terminators
- StringTable<u32, u16, true> offsets buffer: 440 B (18.71% of heap) - u32 offsets into the shared byte buffer
Vec<String>: 2888 (2.82 KiB) (52.47%)
- String payload allocations: 2888 (2.82 KiB) (100.00% of heap) - one UTF-8 allocation per string
Box<[Box<str>]>: 2728 (2.66 KiB) (61.00%)
- Box<str> payload allocations: 2728 (2.66 KiB) (100.00% of heap) - one UTF-8 allocation per string

Distributed fields (per-string handles)

lite-strtab: 218 B (8.76%) - StringId<u16>: field per string (2 B each x 109)
Vec<String>: 2616 (2.55 KiB) (47.53%) - String: field per string (24 B each x 109)
Box<[Box<str>]>: 1744 (1.70 KiB) (39.00%) - Box<str>: field per string (16 B each x 109)

One-time metadata (table object itself)

lite-strtab: 32 B (StringTable<u32, u16> struct itself; one per table, not per string)

§ApiUrls (90 entries, 3,970 bytes)

Summary

Representation	Total	Heap allocations	Distributed fields	vs lite-strtab
`lite-strtab`	4564 (4.46 KiB)	4352 (4.25 KiB)	180 B	1.00x
`lite-strtab (null-padded)`	4660 (4.55 KiB)	4448 (4.34 KiB)	180 B	1.02x
`Vec<String>`	6896 (6.73 KiB)	4736 (4.62 KiB)	2160 (2.11 KiB)	1.51x
`Box<[Box<str>]>`	6112 (5.97 KiB)	4672 (4.56 KiB)	1440 (1.41 KiB)	1.34x

Heap allocations (tree)

lite-strtab: 4352 (4.25 KiB) (95.35%)
- StringTable<u32, u16> byte buffer: 3976 (3.88 KiB) (91.36% of heap) - concatenated UTF-8 string payload data
- StringTable<u32, u16> offsets buffer: 376 B (8.64% of heap) - u32 offsets into the shared byte buffer
lite-strtab (null-padded): 4448 (4.34 KiB) (95.45%)
- StringTable<u32, u16, true> byte buffer: 4072 (3.98 KiB) (91.55% of heap) - concatenated UTF-8 string payload data with NUL terminators
- StringTable<u32, u16, true> offsets buffer: 376 B (8.45% of heap) - u32 offsets into the shared byte buffer
Vec<String>: 4736 (4.62 KiB) (68.68%)
- String payload allocations: 4736 (4.62 KiB) (100.00% of heap) - one UTF-8 allocation per string
Box<[Box<str>]>: 4672 (4.56 KiB) (76.44%)
- Box<str> payload allocations: 4672 (4.56 KiB) (100.00% of heap) - one UTF-8 allocation per string

Distributed fields (per-string handles)

lite-strtab: 180 B (3.94%) - StringId<u16>: field per string (2 B each x 90)
Vec<String>: 2160 (2.11 KiB) (31.32%) - String: field per string (24 B each x 90)
Box<[Box<str>]>: 1440 (1.41 KiB) (23.56%) - Box<str>: field per string (16 B each x 90)

One-time metadata (table object itself)

lite-strtab: 32 B (StringTable<u32, u16> struct itself; one per table, not per string)

§Read performance (YakuzaKiwami)

In this benchmark we sequentially read all of the 4,650 strings (238,109 bytes).

By:

Getting the &str with get / get_unchecked
Reading the &str data to compute a value (i.e. hashing).
- This factors the other hidden costs such as memory alignment, etc.

§AHash payload read (`get` / `get_unchecked`)

Hashing the data with AHash, a realistic real world workload.

Access	Representation	avg time (µs)	avg thrpt (GiB/s)
`get`	`Vec<String>`	13.561	16.352
`get`	`Box<[Box<str>]>`	13.002	17.056
`get`	`lite-strtab`	13.368	16.589
`get`	`lite-strtab (null-padded)`	13.714	16.171
`get_unchecked`	`Vec<String>`	13.448	16.490
`get_unchecked`	`Box<[Box<str>]>`	12.812	17.308
`get_unchecked`	`lite-strtab`	13.207	16.790
`get_unchecked`	`lite-strtab (null-padded)`	13.828	16.037

§Byte-by-byte read (`get_u8` / `get_u8_unchecked`)

Summing bytes one at a time.

Access	Representation	avg time (µs)	avg thrpt (GiB/s)
`get_u8`	`Vec<String>`	18.979	11.684
`get_u8`	`Box<[Box<str>]>`	18.778	11.809
`get_u8`	`lite-strtab`	23.245	9.540
`get_u8_unchecked`	`Vec<String>`	18.928	11.716
`get_u8_unchecked`	`Box<[Box<str>]>`	18.861	11.758
`get_u8_unchecked`	`lite-strtab`	19.008	11.666

§Chunked read (`get_usize` / `get_usize_unchecked`)

Reading data in usize chunks; then u8 for the remainder.

Access	Representation	avg time (µs)	avg thrpt (GiB/s)
`get_usize`	`Vec<String>`	8.219	26.982
`get_usize`	`Box<[Box<str>]>`	8.234	26.932
`get_usize`	`lite-strtab`	8.038	27.590
`get_usize_unchecked`	`Vec<String>`	8.167	27.154
`get_usize_unchecked`	`Box<[Box<str>]>`	8.402	26.393
`get_usize_unchecked`	`lite-strtab`	8.042	27.575

§Iterator (`iter` / `iter_u8` / `iter_usize`)

Using native iterators where available.

Style	Representation	avg time (µs)	avg thrpt (GiB/s)
`ahash`	`Vec<String>`	12.387	17.902
`ahash`	`Box<[Box<str>]>`	12.145	18.259
`ahash`	`lite-strtab`	12.897	17.195
`ahash`	`lite-strtab (null-padded)`	14.774	15.010
`u8`	`Vec<String>`	17.998	12.321
`u8`	`Box<[Box<str>]>`	17.916	12.378
`u8`	`lite-strtab`	17.617	12.588
`usize`	`Vec<String>`	7.751	28.610
`usize`	`Box<[Box<str>]>`	7.845	28.268
`usize`	`lite-strtab`	7.588	29.226

Reproduce with cargo bench --bench my_benchmark. Linux glibc. cargo 1.95.0-nightly (fe2f314ae 2026-01-30).

In summary, actual read performance on real data is within margin of error.

The overhead of looking up a string by ID is negligible. Any difference you see is mostly due to run to run variation.

I’ve experimented with data alignment too, but saw no notable difference in practice after aligning to usize boundaries to avoid reads across word boundaries. There may be some in random access patterns; I’ve only benched sequential here.

§Assembly comparison

Instruction count to get &str, x86_64, release mode:

Method	Instructions	Access Pattern
`lite-strtab::get`	~12	bounds check → load 2 offsets → compute range → add base
`lite-strtab::get_unchecked`	~7	load 2 offsets → compute range → add base
`Vec<String>::get`	~8	bounds check → load ptr from heap → deref for (ptr, len)
`Vec<String>::get_unchecked`	~5	load ptr from heap → deref for (ptr, len)
`Box<[Box<str>]>::get`	~7	bounds check → load ptr → deref for (ptr, len)
`Box<[Box<str>]>::get_unchecked`	~4	load ptr → deref for (ptr, len)

Overhead of processing the data largely dominates; so the difference here is negligible.

§License

MIT

[Box<[Box<str>]>]: alloc::boxed::Box [Box<[String]>]: alloc::boxed::Box Offset: crate::Offset StringId: crate::StringId StringIndex: crate::StringIndex StringTable: crate::StringTable u16: prim@u16 u32: prim@u32

RUSTFLAGS="-C target-cpu=native" cargo bench is ~80% faster on 9950X3D; relative differences unchanged. ↩

Re-exports§

pub use builder::StringPoolBuilder;
pub use builder::StringTableBuilder;
pub use error::Error;
pub use error::Result;
pub use table::StringPool;
pub use table::StringPoolIter;
pub use table::StringTable;
pub use table::StringTableIter;
pub use types::Offset;
pub use types::StringId;
pub use types::StringIndex;

Modules§

builder: Builder for creating immutable pools. Builder for creating an immutable crate::StringTable.
error: Error types. Error types for string pool construction and internal validation.
table: Immutable pool storage and iteration. Immutable string storage backed by one byte buffer and one offset table.
types: Data and type definitions. Public data and type definitions used by the crate.

Structs§

Global: The global memory allocator.

Traits§

Allocator: An implementation of Allocator can allocate, grow, shrink, and deallocate arbitrary blocks of data described via Layout.