src/lib/collections/packed/README.md

# Packed Collections

A Rust library providing memory-efficient collections optimized for dynamically
sized types (specifically `[u8]` and `str`) stored in a single contiguous
buffer.

## Overview

In Rust, storing dynamically sized types (DSTs) like strings or slices in
standard collections typically requires indirection, such as `Vec<String>` or
`Vec<Box<[u8]>>`. This introduces:

1. **Memory Overhead**: Each item requires a pointer and allocator metadata.
2. **Memory Fragmentation**: Items are scattered in the heap, hurting cache
   locality.

The `packed` library solves this by storing all elements sequentially in a
single contiguous `Vec<u8>` buffer and maintaining a separate `Vec<usize>` of
offsets. This eliminates the per-element allocator overhead and ensures all data
is local in memory.

## Collections

### `PackedVec<T>`

A vector-like structure that stores elements of type `T` (where `T` is `[u8]` or
`str`) contiguously.

- **O(1)** random access by index.
- **O(log N)** binary search support when items are sorted.
- **Append-only**: Supports `push` but not insertion or deletion in the middle.

### `PackedMap<K, V>`

A map with keys stored in a sorted `PackedVec<K>` and values in a standard
`Vec<V>`.
- **O(log N)** lookups via binary search.
- **Immutable Keys**: The map structure is rigid after creation. You can update
  values of existing keys, but you cannot insert new keys that are out of order.

### `PackedMapBuilder<K, V>`

A builder for `PackedMap` that allows incrementally appending potentially
out-of-order key-value pairs. It optimizes for mostly-sorted inputs while
supporting full out-of-order insertion.

- **O(log N)** inserts and lookups via binary search.

## When to Use

- **Memory-Constrained Environments**: When you need to store millions of small
  strings or byte slices and cannot afford the overhead of `Box` or `String` for
  each.

- **Read-Heavy Workloads**: When the collection is built once or rarely and read
  frequently. Contiguous storage provides excellent cache locality compared to
  pointer-based map structures like `BTreeMap`.

- **Hot Loops / Cache Locality**: When performing frequent lookups in a
  performance-critical loop. Since all keys are stored contiguously, it provides
  much better cache locality than pointer-based map structures like `BTreeMap`.

- **Streaming Data**: When you are streaming data (e.g., from a file or network)
  and want to avoid allocation overhead during construction. You can read data
  into a single reusable buffer and push references to it into `PackedVec` or
  `PackedMapBuilder`. The collection copies the data into its internal
  contiguous buffer, avoiding the need to allocate a new `String` or `Box` for
  every item processed.

- **Long-Lived Structures**: When the data structure is kept around for a while,
  allowing you to amortize the initial construction cost and benefit from
  reduced memory usage over time.

- **Ordered Data**: When you need a map that maintains key order or supports
  range queries (via `range` and `range_mut`).

- **Mostly Sorted Input**: If you are building a map from data that is already
  sorted or mostly sorted, `PackedMapBuilder` will be very fast.

## When NOT to Use

- **Arbitrary Types**: The `PackedItem` trait is sealed and limited to `[u8]`
  and `str`. You cannot use this for custom types without modifying the library.

- **Frequent Mutations**: If you need a map that supports frequent insertions
  and deletions across the entire key range, use `std::collections::HashMap` or
  `BTreeMap`. `PackedMap` does not support arbitrary insertions.

- **Already Allocated Data**: If your data is already stored in a collection of
  heap-allocated objects (e.g., `BTreeMap<String, V>`), the memory savings of
  converting to a packed structure may not justify the conversion cost unless
  the structure is long-lived or cache locality in hot loops is critical. The
  conversion will also temporarily require double memory.

- **Unsorted Bulk Inserts without Builder**: If you try to use
  `PackedMap::insert` directly with unsorted data, it will fail if the key is
  out of order. You must use `PackedMapBuilder`.