You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The FSE decode table uses 8-byte `Entry` structs (`{base_line: u32, num_bits: u8, symbol: u8}` + padding). The C reference packs entries into 4 bytes (`{newState: u16, symbol: u8, nbBits: u8}`), enabling:
2× cache density — 4-byte entries vs 8-byte doubles the number of entries per cache line
Bulk table spreading — `MEM_write64()` can write 2 packed entries (or 8 symbols) at once during `build_decoding_table`, vs one-at-a-time with current layout
```c
typedef struct {
unsigned short newState; // 2 bytes — next state index
unsigned char symbol; // 1 byte
unsigned char nbBits; // 1 byte
} FSE_decode_t; // 4 bytes total, no padding
```
The key difference: C uses `newState` (direct index) instead of `base_line` (offset that gets added to read bits). This allows `u16` instead of `u32` because max table size is `1 << max_accuracy_log` = `1 << 9` = 512, fitting in `u16`.
Refactor Entry to use `new_state: u16` instead of `base_line: u32`
`#[repr(C)]` to guarantee 4-byte packed layout
All callers of `entry.base_line` need updating
Decode logic: currently `new_state = base_line + bits_read`, becomes direct index
2. Bulk table spreading
First pass: spread symbols into packed entries using u64 writes (2 entries per write)
Second pass: fill `new_state` and `nbBits` fields
3. Update decode hot path
`update_state` / `update_state_fast` to use new decode logic
4. Cache-line alignment for decode tables
Align FSE decode tables to 64-byte boundaries (x86 cache line) using `#[repr(align(64))]` on the table array wrapper
On Apple M-series (128-byte prefetch block), consider 128-byte alignment for AArch64 builds via `#[cfg_attr(target_arch = "aarch64", repr(align(128)))]`
Partition LL/ML/OF tables into separate cache-line-aligned allocations to avoid false sharing when three FSE decoders run interleaved in sequence decode loop
`fse/fse_encoder.rs` — encoder-side table if it references Entry
`decoding/sequence_section_decoder.rs` — callers
`huff0/huff0_decoder.rs` — FSE used for Huffman weight decoding
All tests using Entry or FSETable
Context
Discovered during #55 (PR for #11). The dual-state decode optimization showed ~3% improvement from batched refill checks, but the bulk table spreading item from #11 was blocked by the 8-byte Entry layout.
Performance impact estimate
Cache density: ~5-10% on sequence-heavy data (FSE tables stay in L1)
Summary
The FSE decode table uses 8-byte `Entry` structs (`{base_line: u32, num_bits: u8, symbol: u8}` + padding). The C reference packs entries into 4 bytes (`{newState: u16, symbol: u8, nbBits: u8}`), enabling:
C reference layout (fse_decompress.c)
```c
typedef struct {
unsigned short newState; // 2 bytes — next state index
unsigned char symbol; // 1 byte
unsigned char nbBits; // 1 byte
} FSE_decode_t; // 4 bytes total, no padding
```
The key difference: C uses `newState` (direct index) instead of `base_line` (offset that gets added to read bits). This allows `u16` instead of `u32` because max table size is `1 << max_accuracy_log` = `1 << 9` = 512, fitting in `u16`.
Current Rust layout
```rust
pub struct Entry {
pub base_line: u32, // offset added to bits read
pub num_bits: u8,
pub symbol: u8,
}
// 8 bytes with padding
```
What needs to change
1. Packed Entry layout
2. Bulk table spreading
3. Update decode hot path
4. Cache-line alignment for decode tables
Scope
This is a significant refactor touching:
Context
Discovered during #55 (PR for #11). The dual-state decode optimization showed ~3% improvement from batched refill checks, but the bulk table spreading item from #11 was blocked by the 8-byte Entry layout.
Performance impact estimate
Estimate
2d 4h