Super-linear (~O(n²)) render time for large tables with `page-break-inside: avoid`

I asked Claude Opus 4.8 (Anthropic's coding agent) to open this issue after we together found and root-caused a performance bug while profiling a large-table PDF in dompdf. The investigation below (profiling, scaling measurements, and the root-cause trace through the source) was done by Claude; I have reviewed it.

Summary

Rendering a large table whose rows carry page-break-inside: avoid scales super-linearly (roughly O(n²)) with the number of rows. A ~500-row report table that should take well under a second takes ~30s. The per-row cost grows as the table gets taller, which points at repeated work per page break rather than a high constant factor.

Minimal reproduction

<?php
require 'vendor/autoload.php';

use Dompdf\Dompdf;

function table(int $rows): string
{
    $row = '<tr>' . str_repeat('<td>value</td>', 8) . '</tr>';
    return '<style>'
         . 'table { border-collapse: collapse; }'
         . 'tr    { page-break-inside: avoid; }'   // <-- the trigger
         . 'td    { border: 1px solid #000; padding: 2px; font-size: 9px; }'
         . '</style>'
         . '<table>' . str_repeat($row, $rows) . '</table>';
}

foreach ([100, 200, 400, 800] as $rows) {
    $t = microtime(true);
    $dompdf = new Dompdf();
    $dompdf->loadHtml(table($rows));
    $dompdf->render();
    $dompdf->output();
    printf("rows=%4d  %6.2fs  (%.1f ms/row)\n", $rows, $s = microtime(true) - $t, 1000 * $s / $rows);
}

Measured results (dompdf 3.1.5, PHP 8.3)

With tr { page-break-inside: avoid; } (super-linear: 2× rows ⇒ ~2.7× time):

rows= 100    1.54s  (15.4 ms/row)
rows= 200    3.46s  (17.3 ms/row)
rows= 400    7.92s  (19.8 ms/row)
rows= 800   21.63s  (27.0 ms/row)   <- ms/row keeps climbing

Without that rule (linear baseline, ms/row stays flat):

rows= 100    2.39s  (23.9 ms/row)
rows= 200    4.16s  (20.8 ms/row)
rows= 400    9.18s  (22.9 ms/row)
rows= 800   19.58s  (24.5 ms/row)

The tell is the ms/row column: flat without the rule, steadily rising with it. (The real-world document that started this had 11 wider columns and some multi-line cells, where the same effect is stronger: ~33 ms/row at 50 rows rising to ~63 ms/row at ~490 rows / 20 pages.)

Where the time goes (sampling profile)

We sampled the render of the real ~490-row table (1300 samples via a SIGALRM sampler). Self-time hot spots:

Inclusive stack: render 96% → reflow 79% → FrameReflower\Table::reflow 70% → TableRowGroup::reflow 44% → FrameDecorator\Page::check_page_break 32%.

So roughly ~37% of the time is CSS style re-computation and ~22% is frame-tree walking, all hanging off table reflow + page-break handling.

Root cause analysis

The cost is driven by how pagination splits the table. When a row crosses a page boundary, FrameDecorator\AbstractFrameDecorator::split() moves the breaking row and every following sibling into a new frame and calls reset() on each one:

// AbstractFrameDecorator::split()
$iter = $child;
while ($iter) {
    $frame = $iter;
    $iter = $iter->get_next_sibling();
    $frame->reset();              // recursive reset of the whole tail
    $split->append_child($frame);
}

AbstractFrameDecorator::reset() recurses into all descendants, and Style::reset() clears the per-frame used-value cache:

// Css\Style::reset()
foreach (array_keys($this->non_final_used) as $prop) {
    unset($this->_props_used[$prop]);   // cached used values dropped
}

The split-off remainder is then re-reflowed from scratch, which recomputes every cleared property through the Style::__get → computed() path. With page-break-inside: avoid on every row, more rows get pushed whole to the next page, so more page breaks occur and a larger tail is reset+re-reflowed each time. A row near the end is reset and re-reflowed roughly once per page break, giving ~O(rows × pages) ≈ O(n²) total work. That matches both the rising ms/row and the profile (Style::reset / __get / apply_styles dominating, under check_page_break).

Suggested direction

Incremental table pagination, so already-laid-out rows are not reset and re-reflowed when a later row triggers a page break, would remove the quadratic term. Short of that, even avoiding the full Style used-value cache invalidation for properties that cannot change across a page break (position-independent properties: borders, font, colors, intrinsic widths) on split-induced resets should cut the re-computation cost substantially. We are happy to help test a patch against the reproduction above.

Environment

• dompdf/dompdf 3.1.5
• PHP 8.3.29 (NTS)
• Default options (issue is independent of the HTML5 parser setting; we also reproduced with the legacy parser)