Skip to content

dew.data.tokens

Document chunk tables, packed windows, first-fit plans and a row’s shares of its room.

NameSummary
share_tokensHow many of its own tokens each segment of a row keeps of the row’s room: the one allocation segments that share a row read, as a decision row’s copies of its state do.
chunk_tableThe document each chunk is cut from and where in it the chunk starts, both int64 and one entry per chunk, for documents of lengths cut into pieces of at most chunk_len tokens, each starting chunk_len - overlap after the last (dew.data.text.Chunks).
chunk_lengthsThe token count of each chunk chunk_table cuts documents of lengths into.
entriesHow many entries of a window a document’s field takes: its length, or one for a scalar, as grain’s packer counts it (PackedBatch._get_element_lengths_flat).
PackedWindowsbins windows documents are laid into end to end, as grain’s packer lays them (grain/_src/python/dataset/transformations/packing_packed_batch.py, PackedBatch): each field in a zero-padded window of its own length (lengths), allocated at the dtype and trailing shape template, the first document of the set, holds (a token’s row of an aligned auxiliary field), and each document copied in as it is added, so nothing it reads from is held.
packed_windowchunks, each holding the same per-token fields, laid end to end in a zero-padded window of window tokens as grain’s packer lays them (PackedWindows), with one pair of segment ids and positions named after the first field.
FirstFitGrain’s first-fit placement (FirstFitPackedBatch.try_add_to_batch): bins open windows, each with room for rooms entries of each field, a document going to the first window with room for every field of it and fewer than segments documents.
first_fitThe plan grain’s first-fit packer would follow over chunks of sizes (FirstFit).

function source

def share_tokens(
lengths: Sequence[int],
room: int,
*,
caps: Sequence[int | None] | None = None,
whole: Sequence[bool] | None = None,
) -> list[int]

How many of its own tokens each segment of a row keeps of the row’s room: the one allocation segments that share a row read, as a decision row’s copies of its state do.

A segment kept whole (whole) takes all of its lengths, past the room too, which the row’s own check then judges. The others share what that leaves, never below zero, each wanting its length up to its cap (caps, None for none). Where their wants exceed it, the share is max-min within one token: in a stable ascending order of want, each takes the least of its want and an equal split of what is left, floored, so a floor’s remainder goes to the later segments in that order ([10, 10] into 7 keeps [3, 4], [100, 10, 10] into 4 keeps [2, 1, 1]). No share is below zero, the cut ones sum to at most what they share, and none of it is left while a segment wants more.

function source

def chunk_table(lengths, chunk_len: int, overlap: int) -> tuple[np.ndarray, np.ndarray]

The document each chunk is cut from and where in it the chunk starts, both int64 and one entry per chunk, for documents of lengths cut into pieces of at most chunk_len tokens, each starting chunk_len - overlap after the last (dew.data.text.Chunks).

A window holds nothing longer than itself, so a document that outgrows it is cut first, and each chunk becomes its own segment of the window, which keeps attention inside the chunk and RoPE running from the chunk’s own 0. A document of chunk_len tokens or fewer is one chunk; a document of no tokens is no chunks.

function source

def chunk_lengths(lengths, chunk_len: int, overlap: int) -> np.ndarray

The token count of each chunk chunk_table cuts documents of lengths into.

function source

def entries(value) -> int

How many entries of a window a document’s field takes: its length, or one for a scalar, as grain’s packer counts it (PackedBatch._get_element_lengths_flat).

class source

class PackedWindows(
template: Batch,
lengths: Mapping[str, int],
paired: Sequence[str],
bins: int,
)

bins windows documents are laid into end to end, as grain’s packer lays them (grain/_src/python/dataset/transformations/packing_packed_batch.py, PackedBatch): each field in a zero-padded window of its own length (lengths), allocated at the dtype and trailing shape template, the first document of the set, holds (a token’s row of an aligned auxiliary field), and each document copied in as it is added, so nothing it reads from is held.

<field>_segment_ids says which document of the window each entry came from, counted from 1, and 0 for the padding at the end, and <field>_positions the entry’s place inside its document, for each of the paired fields: the first token field, whose pair describes every token field, as documents are cut the same way in each, and each field along an axis of its own, as grain writes one for each field it does not take for a meta feature. A block-diagonal mask and per-document RoPE read the token pair.

def add(window: int, document: Batch) -> None

document laid after what window window holds.

def windows() -> list[Batch]

Every window that holds a document, in order: the first ones, since an empty window takes any document a window has room for.

function source

def packed_window(chunks: Sequence[Batch], window: int) -> Batch

chunks, each holding the same per-token fields, laid end to end in a zero-padded window of window tokens as grain’s packer lays them (PackedWindows), with one pair of segment ids and positions named after the first field.

It is grain’s assembly, held to it field for field (tests/test_grain_packing.py), and not grain’s own packer, whose public form lays a twelve-chunk window in 3.6 ms on armada’s CPUs where this takes 35 us, and an indexed read assembles a window a read (rows 1873, 1064).

class source

class FirstFit(rooms: Sequence[int], bins: int, segments: int | None = None)

Grain’s first-fit placement (FirstFitPackedBatch.try_add_to_batch): bins open windows, each with room for rooms entries of each field, a document going to the first window with room for every field of it and fewer than segments documents. Where none has, the packer emits every window that holds a document, in order, and starts afresh (grain/_src/python/dataset/transformations/packing.py:250-266).

The one placement both of Dew’s first-fit packers follow: a plan over documents’ lengths alone (first_fit), and the packer of a stream of them (dew.data.packing.FirstFitPacked).

def restart() -> None

Every window open and empty, as after the packer emits them.

def place(sizes: Sequence[int]) -> int | None

The window a document of sizes entries in each field goes to, which takes them, or None where no open window has room for it. One longer than a window is refused, as grain refuses it: no window ever has room for it.

def holding() -> int

How many windows hold a document: the first ones, since an empty window takes any document a window has room for.

function source

def first_fit(
sizes: np.ndarray,
window: int,
bins: int,
segments: int | None = None,
) -> tuple[np.ndarray, np.ndarray]

The plan grain’s first-fit packer would follow over chunks of sizes (FirstFit).

Run over the lengths alone it is a plan rather than a pass: which window every chunk belongs to, without reading a token. That plan is what lets the packing run ahead of the shard, so a window holds the same chunks at any process count.

It is grain’s placement, held to it window for window (tests/test_grain_packing.py), and not grain’s packer run over the lengths: over 200,000 chunks on armada’s CPUs this plans in 0.15 to 0.22 s (windows of 2048 and 4096 tokens, 1 to 16 bins) and grain’s packer, fed zero-strided stand-ins of each length, in 88 s, the same plan (rows 1873, 1064).

Returns the chunk indices grouped by window, in the order the packer added them, and where each window starts in that grouping. A window the packer never added anything to is dropped, since it would be a batch row of pure padding. Only the last set of bins can hold one, because a record goes to the first window with room and an empty window has room for anything.