dockyard_rl.data.packing.algorithms

Sequence-packing algorithms.

Each algorithm takes a list of (index, length) pairs and a maximum pack size, and returns a list of packs. Each pack is a list of indices from the input, ordered so that the sum of their lengths does not exceed max_pack_size.

All algorithms preserve the invariant: for every pack p: sum(lengths[i] for i in p) <= max_pack_size

Module Contents

Functions

first_fit_decreasing	Classic First-Fit Decreasing bin-packing heuristic.
shuffle_packing	Greedy packing after randomly shuffling sequences.
dp_packing	Near-optimal bin-packing via a DP subset-sum over each pack.
online_packing	Online greedy packing in arrival order (no reordering).
available_algorithms	Names pack_sequences accepts, sorted.
validate_packing_algorithm	Return algorithm if pack_sequences accepts it, else raise.
pack_sequences	Pack sequences using the named algorithm.

Data

Pack
PackList

API

dockyard_rl.data.packing.algorithms.Pack

None

dockyard_rl.data.packing.algorithms.PackList

None

dockyard_rl.data.packing.algorithms.first_fit_decreasing(lengths: list[int], max_pack_size: int, *, seed: Optional[int] = None) → dockyard_rl.data.packing.algorithms.PackList

Classic First-Fit Decreasing bin-packing heuristic.

Sequences are sorted longest-first, then each sequence is placed into the first existing pack that still has enough room. A new pack is opened if none fits.

Args: lengths: Token lengths of all sequences. max_pack_size: Maximum tokens per pack (e.g. max_seq_len). seed: Unused; kept for API compatibility with other algorithms.

Returns: List of packs; each pack is a list of indices into lengths.

dockyard_rl.data.packing.algorithms.shuffle_packing(lengths: list[int], max_pack_size: int, *, seed: Optional[int] = 42) → dockyard_rl.data.packing.algorithms.PackList

Greedy packing after randomly shuffling sequences.

Provides diversity across training steps: each call with a different seed yields a different packing, preventing the model from memorising pack co-occurrences.

Args: lengths: Token lengths of all sequences. max_pack_size: Maximum tokens per pack. seed: RNG seed for the shuffle (default: 42).

Returns: List of packs.

dockyard_rl.data.packing.algorithms.dp_packing(lengths: list[int], max_pack_size: int, *, seed: Optional[int] = None, max_sequences_per_pack: int = 32) → dockyard_rl.data.packing.algorithms.PackList

Near-optimal bin-packing via a DP subset-sum over each pack.

For each pack, we greedily grow a subset of remaining sequences that maximises utilisation without exceeding max_pack_size. The DP runs over the unplaced sequences, so worst-case complexity is O(N * max_pack_size) per pack. Practical performance is much better because sequences are pre-sorted and pruned aggressively.

Args: lengths: Token lengths of all sequences. max_pack_size: Maximum tokens per pack. seed: Unused; for API compatibility. max_sequences_per_pack: Hard cap on sequences per pack to bound DP cost.

Returns: List of packs.

dockyard_rl.data.packing.algorithms.online_packing(lengths: list[int], max_pack_size: int, *, seed: Optional[int] = None) → dockyard_rl.data.packing.algorithms.PackList

Online greedy packing in arrival order (no reordering).

Each sequence is appended to the current open pack if it fits; otherwise the current pack is closed and a new one is started. This mirrors the behaviour of a streaming dataloader where sequences arrive in a fixed order and cannot be reordered.

Args: lengths: Token lengths in arrival order. max_pack_size: Maximum tokens per pack. seed: Unused; for API compatibility.

Returns: List of packs.

dockyard_rl.data.packing.algorithms.available_algorithms() → list[str]

Names pack_sequences accepts, sorted.

Public so a config can be validated where it is read, rather than at the first packed micro-batch – which is after cluster spin-up, model load and a full rollout.

dockyard_rl.data.packing.algorithms.validate_packing_algorithm(algorithm: str) → str

Return algorithm if pack_sequences accepts it, else raise.

Callers validate at config-resolution time so an unknown name is refused when the policy is constructed, not at the first packed micro-batch.

dockyard_rl.data.packing.algorithms.pack_sequences(lengths: list[int], max_pack_size: int, algorithm: str = 'first_fit_decreasing', seed: Optional[int] = None) → dockyard_rl.data.packing.algorithms.PackList

Pack sequences using the named algorithm.

Args: lengths: Token lengths of all sequences. max_pack_size: Maximum tokens allowed per pack. algorithm: One of “first_fit_decreasing” / “ffd”, “shuffle” / “shuffle_packing”, “dp” / “dp_packing”, “online” / “online_packing”. seed: RNG seed forwarded to algorithms that support it.

Returns: List of packs (each a list of indices into lengths).

Raises: KeyError: If algorithm is not in the registry. ValueError: If any sequence exceeds max_pack_size.