Part 3 · 5 chapters · ~45 min

Layout Algorithms

Block layout is one pass, inline layout is line breaking, flex is a clamp loop over free space, grid is a fixpoint over track sizes, and tables measure everything twice. This part is each of those as an algorithm with its passes, its iteration bound, its incrementality, and its pathology, with greedy versus optimal line breaking drawn side by side.

Block and inline: one pass, then line breaking

the question

"Why does a paragraph reflow when I change a word, and why does a block not?"

Because block layout is a single downward pass with no dependencies between siblings except the running y, and inline layout is line breaking, where every break depends on the words before it. Block layout is O(children); a change to one block affects only the blocks below it (their y shifts). Inline layout is O(runs) per paragraph with greedy breaking, and a change anywhere in the paragraph can change every line after it.

code

// block layout, the whole algorithm (the tiny browser's layoutBlock is this in 60 lines)
// for a block container with block children, top to bottom:
//   width:  containing block width − margins − padding − borders   (auto margins absorb free space: centring)
//   x:      containing block x + left margin + border + padding
//   y:      running cursor + top margin, collapsed with the previous sibling's bottom margin (max, not sum)
//   height: sum of children's used heights (or the explicit height)
// one pass, O(children), no iteration. the only subtlety is margin collapsing (adjacent, parent-child when no border/padding, empty blocks)
// and the interaction with floats: a float is laid out at the current line, shifted to the edge, and subsequent line boxes
// are shortened where they overlap its margin box (an interval query per line: "what floats intersect y..y+h")

// inline formatting (the tiny browser's layoutInline): flatten inline content into runs; measure each run (shaping);
// fill line boxes greedily; a run that does not fit starts a new line; vertical-align positions runs within the line's
// height. O(runs) per paragraph. floats, text-indent, and ::first-line make it O(runs × floats) in the worst case.

block formatting, as an algorithm

Width first, top down: a block's width comes from its containing block (the auto-width equation), so widths are known before any child is laid out.
Height bottom up: a block's height is the sum of its children's, so heights are known only after children are laid out. One recursive pass: widths going down, heights coming up.
Margin collapsing: adjacent vertical margins become one (the larger); parent and first child collapse when nothing separates them (no border, padding, or BFC boundary). A few conditional rules, all local.
Floats: the one non-local feature. A float is positioned at the current line and removed from flow; later line boxes in the same BFC shrink around it. Engines keep a float list per BFC and query it per line: O(floats) per line, so a thousand floats make inline layout slow, which is why layouts moved to flex and grid.
Incrementality: a changed block is relaid; siblings below shift by the height delta; siblings above and ancestors whose size did not change are untouched. This is why block layout scales: most changes are local.

inline formatting

Runs: inline content is flattened into a sequence of text runs (one per font, direction, and style change) and atomic inlines (images, inline-blocks).
Measurement: each run is shaped (the browser course part 11): characters to glyphs with advances. The cost is per run, cached per word in Blink.
Line breaking: break opportunities from the Unicode line breaking algorithm (UAX #14) plus hyphenation; then greedy filling (next chapter).
Vertical layout of a line: the line box height from the tallest run (line-height and vertical-align), baselines aligned.
Incrementality: LayoutNG can restart from the line containing the change if nothing before it moved; an edit at the end of a paragraph relays only the last line. An edit at the start relays the paragraph.

Line breaking: greedy, and the optimal one it is not

Breaking a paragraph into lines is a choice of which spaces become line ends. The greedy algorithm takes the last space that fits on each line and moves on: O(n), stable under edits, and what browsers do. The optimal algorithm (Knuth and Plass, 1981) minimises a badness over the whole paragraph with dynamic programming, producing the evenly filled lines of a typeset book. Browsers now approximate the optimal one for the last few lines (text-wrap: pretty) and for short blocks (text-wrap: balance).

the model

Boxes: unbreakable content with a width (a word, or a syllable when hyphenation is on).
Glue: breakable space with a natural width, a stretch and a shrink (how far it can be pulled or pushed to justify a line).
Penalties: places where a break is allowed at a cost (a hyphen: a penalty for the ugliness and the inserted hyphen width) or forbidden (a non-breaking space: infinite penalty) or forced (a line break: negative infinity).
A line's badness: a function of how much its glue had to stretch or shrink: (adjustment ratio)³ × 100 in TeX, where the ratio is slack divided by available stretch. A line that fits exactly has badness 0; one stretched to the limit, 100; beyond the limit, infeasible.

the two algorithms

Greedy (first fit): for each line, add items until the next would overflow; break at the last legal opportunity. One pass. The line being built never looks at what comes after. Produces loose lines before a long word and orphans on the last line.
Knuth-Plass (total fit): best[j] = the minimum total badness of all lines ending at break point j = min over feasible i < j of best[i] + badness(line i..j). Fill the table left to right; the last break's best is the paragraph's; backtrack for the breaks. O(n × w) where w is the number of feasible predecessors (words that could start a line ending at j: the line width divided by the average word width, ~10 to 20). With "looseness" and demerits for consecutive hyphens or tight-then-loose lines, the full algorithm is a few hundred lines.
Why browsers stayed greedy: relayout frequency (every resize, every font swap, every content change), the cost of running it on every paragraph on a page, and stability: greedy guarantees that an edit changes only the lines after it; optimal can reflow the whole paragraph from a change at its end.

what browsers do now

text-wrap: pretty: a bounded optimisation over the last few lines (Chrome evaluates a small number of alternative break positions for the last four lines) to avoid orphans and very short last lines. Near-greedy cost.
text-wrap: balance: for blocks of up to about six lines (headings): find, by bisection on the available width, the narrowest width that yields the same line count, so lines are roughly equal. Each bisection step is a full greedy layout of the block; the line cap bounds the cost.
hyphens: auto: adds break opportunities from a language dictionary (part 9), which helps both algorithms produce tighter lines.

GREEDY VERSUS OPTIMAL LINE BREAKING

the same paragraph, two algorithms

swipe the figure sideways, or tap expand for full screen

1/6

the words

The words with their widths (in units; spaces are 1 unit, stretchable). The line width is 30 units. Each word is a box; each space is glue; each possible break is at a space. The question: which spaces become line ends?

The flex algorithm

Flexbox resolves one dimension, the main axis, by distributing free space according to flex factors, with a loop that handles minimum and maximum constraints, then sizes the cross axis from the results. Two to three layouts per item; one loop per line; a nested container repeats the whole thing per measurement of its parent.

the steps (CSS Flexbox §9)

Determine the available space in the main and cross axes from the container.
Hypothetical main size per item: flex-basis if definite; otherwise the item's content size in the main axis (max-content for a row), which requires laying the item out. Clamp by min and max.
Collect items into lines (if wrapping): greedy, in order, breaking when the sum of hypothetical sizes exceeds the container. Single-line containers have one line.
Resolve flexible lengths per line: compute free space = container − Σ hypothetical. If positive, grow by flex-grow shares; if negative, shrink by flex-shrink × basis shares. Clamp each item by its min and max; freeze clamped items; recompute free space over the unfrozen; repeat until nothing clamps. At most n iterations per line.
Cross size per item: lay each item out at its resolved main size to get its cross size (height for a row). The line's cross size is the max (or the container's, if single-line with a definite cross size).
Align: align-items within the line (stretch makes cross sizes equal), align-content across lines, justify-content for leftover main space.

what the algorithm explains

flex: 1 equalises items because it sets basis to 0%, so all space is "free" and distributed by equal grow factors; flex: auto keeps content sizes and shares only the leftover.
Items overflow instead of shrinking because min-width: auto resolves to the item's min-content size and the clamp freezes them there. min-width: 0 (or overflow: hidden) lets step 4 shrink them.
Flex items are laid out twice (hypothetical and final) in the common case; text-heavy items pay shaping twice unless the engine caches it. Deeply nested flex is the usual cause of a slow layout: each level's measurement runs the children's full algorithm.
Percentages in the cross axis resolve late (after the line's cross size is known), which is why a percentage height inside a flex row sometimes needs a third pass or resolves to auto.

THE FLEX ALGORITHM

three passes over one row

swipe the figure sideways, or tap expand for full screen

1/6

hypothetical sizes

Four items. flex-basis: auto for all, so the hypothetical main sizes are the content sizes: 120, 80, 200, 100 (from a max-content measurement of each). Sum: 500. Container: 600. Free space: +100. flex-grow: 1, 2, 0, 1 (sum 4). flex-shrink: 1 each (not needed here).

Grid track sizing

Grid sizes its tracks, not its items: the track sizing algorithm runs over columns, then over rows, each as a sequence of passes that grow track sizes from their minimums toward their maximums under the items' contributions, finishing with a fixpoint for fr units. Items are then placed into the resolved tracks and laid out once more at their final sizes.

the four steps (CSS Grid §12.3 to 12.7)

Initialise: each track gets a base size (its min sizing function if fixed, else 0) and a growth limit (its max if fixed, else infinity).
Resolve intrinsic sizes: for items spanning one track, raise the track's base to the items' min-content contributions and its limit to their max-content contributions (for auto and content-sized tracks). Then for items spanning two tracks, three, and so on: distribute each item's extra contribution across its spanned tracks that can still grow. Spanning fr tracks is handled last.
Maximise tracks: if free space remains, grow tracks toward their growth limits (equally, until each hits its limit).
Expand flexible tracks: compute the fr unit as free space over Σfr; any fr track whose share is below its base (its minmax floor or content minimum) is set to that base and removed from the flexible set; recompute. Converges in at most as many iterations as fr tracks. Then stretch auto tracks with any remaining space if there are no fr tracks and justify-content: normal.

before and after

Placement comes first: explicit positions, then auto-placement with a cursor that walks cells in order and skips occupied ones (grid-auto-flow: dense restarts the cursor from the beginning for each item, filling holes at O(cells) per item in the worst case).
Rows after columns: an item's height depends on its width, so rows cannot be sized until column widths are known. For a grid whose height drives its width (writing-mode or aspect constraints), the spec allows a second pass over columns.
Final layout: each item is laid out at its cell's size. Items with align-self: stretch get the cell's size; others their content size within it.

cost and the patterns that raise it

Two measurements per item (min-content and max-content) for content-sized tracks; none for fixed tracks. A grid of repeat(12, 1fr) with fixed-size items is cheap; repeat(auto-fit, minmax(200px, 1fr)) over text cards measures every card twice.
Spanning items add a distribution pass per distinct span count; many different spans, many passes.
Nested grids re-run the algorithm per parent measurement; subgrid lets a child's tracks be the parent's and avoids that.
Large auto-placed grids: the placement cursor is linear, but dense packing with many holes can approach quadratic.

GRID TRACK SIZING

a fixpoint over columns, then rows

swipe the figure sideways, or tap expand for full screen

1/6

the tracks

Four column tracks: 100px (fixed), auto (content-sized), minmax(150px, 1fr) (at least 150, grows with free space), 2fr (flexible). Container 900px, gap 0 for simplicity. Items: A in column 2 with min-content 80 and max-content 220; B spanning columns 2 and 3 with max-content 400; C in column 4 with 120.

Table layout, and measuring all of it

table auto layout (the legacy algorithm, CSS 2.1 §17.5.2.2)

Measure every cell twice: min-content width (the longest unbreakable word) and max-content width (the content on one line). O(cells) layouts, each potentially shaping text.
Column minimums and maximums: per column, the max of its cells' min widths and the max of their max widths; cells spanning columns distribute their widths across the spanned columns.
Resolve the table width: if the sum of column maxes fits, use them; if only the mins fit, use mins and distribute the rest proportionally; percentage columns are resolved against the table width with their own rules.
Then rows: cells laid out at their column widths give row heights; rowspans distribute.
The cost: every cell measured twice before any column width is known, and the whole table re-measured on any content change, because one long word in row 999 can change every column. A 1,000 × 50 table is 100,000 measurements per relayout. This is why big tables are slow and why table-layout: fixed exists.

table-layout: fixed

Column widths from the first row (and <col> widths) only; later rows never affect columns. One pass over the first row, then O(rows) for heights. Content that does not fit overflows or wraps within its cell.
Incremental: a change in row 999 relays row 999. The right choice for any table over a few hundred rows, and the only choice for virtualised tables (whose rendered rows change constantly).

code

// measuring layout
// Performance → "Layout" events: nodes that need layout, the root of the relayout, and the duration
// Layout thrash: the browser course part 4; "Forced reflow" warnings in the trace with the stack that read layout
// the experiments:
//   1. a flex row with 1,000 items vs a grid row with 1,000 items vs 1,000 inline-blocks: time Layout for each on a width change
//   2. nested flex 5 deep with 10 children per level vs the same with contain: layout on each level
//   3. a paragraph of 2,000 words with text-wrap: wrap vs pretty vs balance (balance is capped; try a 6-line block)
//   4. a table with 50 columns and table-layout: auto vs fixed on a 1,000-row body
// what to watch: Layout duration and the "nodes needing layout" count; whether a change in one item relaid the whole container

Layout mode	Measurements per item	Iteration	Incremental on change	Pathology
Block	1	None	Siblings below shift; ancestors if height changed	Floats: O(floats) per line
Inline (greedy)	1 shaping per run (cached per word)	None	From the changed line, if earlier lines are unaffected	Very long paragraphs; many floats; per-element custom fonts
Inline (balance / pretty)	Several greedy passes	Bisection (balance), bounded search (pretty)	Whole block	Capped by line count, by design
Flex	2 to 3	Clamp loop, ≤ n per line	Whole container (one item changes free space for all)	Deep nesting; content-sized items; min-width: auto confusion
Grid	2 (content tracks), 0 (fixed)	fr fixpoint, ≤ fr tracks; span passes	Whole grid (track sizes shared)	auto-fit over content; many spans; dense packing with holes
Table (auto)	2 per cell	Width resolution	Whole table	Any large table
Table (fixed)	First row only	None	Changed row	None; content may overflow
Absolute / fixed positioning	1	None	The element alone	None (but no flow interaction)

the pointer

Part 4 is what happens to the geometry: paint order as a tree walk with stacking contexts, display list culling, tiling and damage rectangles. Layout decides where; paint decides what to draw and in what order; the compositor decides what to redraw.