perf: table width fitting is linear in total column width and recomputes display widths

[codeforester]

Problem

Two hot paths in terminal table rendering scale badly with cell width.

1. _fit_table_width() shrinks one display column per iteration
(lib/python/base_cli/output.py:344-356):

while sum(result) > available:
    index = max(range(len(result)), key=result.__getitem__)
    if result[index] <= 1:
        break
    result[index] -= 1

Each iteration is O(ncols) and removes exactly one unit of width, so the loop runs
sum(widths) - available times. max_cell_width defaults to 80, which bounds it in normal use —
but max_cell_width=None is a documented public option on render_records(), and with it a single
long cell makes rendering effectively quadratic.

2. _display_width() is recomputed about four times per cell. _write_table() computes it for
column sizing, then _truncate() calls it again on the whole value and once per character, then
_pad_cell() calls it a third time (lib/python/base_cli/output.py:293-331, 364-396). Each call
does up to three unicodedata lookups per character.

Verified evidence

Reviewed 2026-09-30 at a58ec109349fa3f3d03eae5b0de078b39ea361a2 (macOS, Python 3.14.6).

_fit_table_width([w, w], 80):

Column width	Time
10,000	3.49 ms
100,000	35.77 ms
1,000,000	352.54 ms

Linear in total width, as expected from the algorithm — 352 ms of pure arithmetic to lay out one row.

Proposal

1. Replace the decrement loop with a direct proportional allocation: compute the target widths
   arithmetically (largest-remainder or water-filling against available), then apply the
   >= 1 floor. Same result, O(ncols log ncols).
2. Compute each cell's display width once. _truncate() and _pad_cell() should accept the
   already-known width, or the table builder should carry (text, width) pairs.
3. Consider clamping cell text to available before width computation when max_cell_width is
   None, so an enormous cell never drives the layout arithmetic at all.

Acceptance criteria

• _fit_table_width() is not linear in total column width; the 1,000,000-width case completes in
  well under a millisecond.
• Rendered output is byte-for-byte identical to today's for the existing table tests, including the
  East Asian width, combining-character, and ellipsis cases.
• A regression test covers max_cell_width=None with a very wide cell and asserts a time or
  operation bound.

Non-goals

• Do not change the visual table format or the ellipsis character.
• Do not change minimum_widths or terminal_width semantics.