dew.data.tokens
Document chunk tables, packed windows, first-fit plans and a row’s shares of its room.
| Name | Summary |
|---|---|
share_tokens | 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. |
chunk_table | 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). |
chunk_lengths | The token count of each chunk chunk_table cuts documents of lengths into. |
entries | 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). |
PackedWindows | 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. |
packed_window | 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. |
FirstFit | 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. |
first_fit | The plan grain’s first-fit packer would follow over chunks of sizes (FirstFit). |
share_tokens
Section titled “share_tokens”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.
chunk_table
Section titled “chunk_table”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.
chunk_lengths
Section titled “chunk_lengths”def chunk_lengths(lengths, chunk_len: int, overlap: int) -> np.ndarrayThe token count of each chunk chunk_table cuts documents of lengths into.
entries
Section titled “entries”def entries(value) -> intHow 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).
PackedWindows
Section titled “PackedWindows”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.
PackedWindows.add
Section titled “PackedWindows.add”def add(window: int, document: Batch) -> Nonedocument laid after what window window holds.
PackedWindows.windows
Section titled “PackedWindows.windows”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.
packed_window
Section titled “packed_window”def packed_window(chunks: Sequence[Batch], window: int) -> Batchchunks, 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).
FirstFit
Section titled “FirstFit”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).
FirstFit.restart
Section titled “FirstFit.restart”def restart() -> NoneEvery window open and empty, as after the packer emits them.
FirstFit.place
Section titled “FirstFit.place”def place(sizes: Sequence[int]) -> int | NoneThe 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.
FirstFit.holding
Section titled “FirstFit.holding”def holding() -> intHow many windows hold a document: the first ones, since an empty window takes any document a window has room for.
first_fit
Section titled “first_fit”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.