dotnet / dotnet/winforms

TableLayoutPanel layout has quadratic reservation-row advancement for deep row spans

Open
#15,066 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C#
Stars
4.9k
Forks
1.1k
Avg merge
1d 13m
Merged PRs (30d)
85

Description

### .NET version

Investigated against `dotnet/winforms` commit `f0cd8e488e17c03994589d835fb0c1c1269b4491` (the unmodified main baseline used for the measurements).

- .NET SDK 11.0.100-rc.1.26420.103
- Runtime 11.0.0-rc.1.26453.118
- Windows x64, OS version 10.0.26200
- AMD Ryzen 9 9950X3D 16-Core Processor
- Release builds; `DOTNET_TieredCompilation=0`

### Did it work in .NET Framework?

Not tested/verified.

### Did it work in any of the earlier releases of .NET Core or .NET 5+?

Not tested/verified. This reports an algorithmic performance limitation, not a confirmed regression from a particular release.

### Issue description

`TableLayoutPanel` layouts with a deep row span and many subsequently placed controls repeatedly advance through a large reservation grid.

The private [TableLayout.ReservationGrid implementation at the measured baseline](https://github.com/dotnet/winforms/blob/f0cd8e488e17c03994589d835fb0c1c1269b4491/src/System.Windows.Forms/System/Windows/Forms/Layout/TableLayout.ReservationGrid.cs) stores future rows in a `List`. `AdvanceRow()` calls `RemoveAt(0)`, shifting every remaining row reference. Draining R reserved rows therefore shifts R(R-1)/2 references: O(R²) work.

**Actual:** repeated advancement has a quadratic scaling curve and adds measurable layout cost in the public workload below.

**Expected:** consuming reservations should take amortized O(1) per row, or O(R) for R advances, while preserving control placement, overlap detection, row/column spans, grow-style behavior, and exceptions. This expectation concerns reservation advancement, not the complexity of every other part of layout.

#### Measurements

Median microseconds for draining the actual private production grid through bound delegates; reservation setup and reflection/delegate creation are outside timing:

| Reserved rows | Unmodified baseline (µs) | Proposed fix (µs) |
| ---: | ---: | ---: |
| 256 | 5.376 | 0.564 |
| 512 | 13.871 | 1.019 |
| 1,024 | 66.495 | 1.913 |
| 2,048 | 173.713 | 3.675 |
| 4,096 | 792.331 | 7.191 |
| 8,192 | 3,072.369 | 14.400 |
| 16,384 | 12,754.237 | 28.925 |
| 32,768 | 52,194.950 | 57.275 |

At the larger sizes, doubling the row count approaches fourfold baseline time versus twofold time with the proposed fix. Timed isolated advancement allocated 0 bytes in both versions.

Median microseconds for the public `ResumeLayout(true)` workload:

| Rows | Unmodified baseline (µs) | Proposed fix (µs) |
| ---: | ---: | ---: |
| 128 | 50.538 | 51.666 |
| 256 | 106.412 | 105.000 |
| 512 | 225.738 | 215.287 |
| 1,024 | 534.200 | 439.025 |
| 2,048 | 1,727.400 | 917.300 |
| 4,096 | 3,484.400 | 1,904.200 |

The 4,096-row layout was about 45% faster in this sweep. These are diagnostic Stopwatch measurements on one host; separate sweeps varied, and the isolated speedup must not be interpreted as a general application speedup.

A separate A/B/B/A check of 0, 1, 2, 4, and 8 rows (31 batches per size per process) showed changes between -2.32% and +0.14% when averaging the two process medians for each version. This did not show a consistent small-layout slowdown. Timed public allocations were unchanged at each measured size.

### Steps to reproduce

1. Build the baseline checkout in Release using the repository build instructions.
2. On an STA thread, create a two-column `TableLayoutPanel` with layout suspended.
3. Add one control at (0, 0) spanning R rows, followed by R flow controls.
4. Time only `ResumeLayout(performLayout: true)`. Keep control creation, GC, validation, and disposal outside the timed interval.
5. Repeat for increasing R, including 128, 256, 512, 1,024, 2,048, and 4,096. Warm up and measure multiple batches rather than relying on a single call.

The public setup used in the benchmark is:

```csharp
private static TableLayoutPanel CreatePanel(int rows)
{
TableLayoutPanel panel = new()
{
ColumnCount = 2,
RowCount = 0,
GrowStyle = TableLayoutPanelGrowStyle.AddRows,
AutoSize = true,
};

panel.SuspendLayout();

Control spanningControl = new()
{
Name = "SpanningControl",
Size = new Size(1, 1),
Margin = Padding.Empty,
};

panel.Controls.Add(spanningControl, 0, 0);
panel.SetRowSpan(spanningControl, rows);

for (int row = 0; row < rows; row++)
{
panel.Controls.Add(new Control
{
Name = $"Flow{row}",
Size = new Size(1, 1),
Margin = Padding.Empty,
});
}

return panel;
}
```

Call this with positive R, then call `ResumeLayout(true)` inside the timed section. The final flow control should be at column 1, row R-1. Dispose each panel after measurement.

[PR #15065](https://github.com/dotnet/winforms/pull/15065) contains the complete runnable benchmark source, project file, SDK pin, build/run commands, full scaling tables, and small-layout checks in the expandable **Benchmark source and reproduction** section. It also contains the isolated production-grid benchmark, which separates row advancement from the rest of layout.

### Proposed resolution

An implementation is available in #15065: retain the existing list, maintain a logical head, clear/reset on exhaustion, and compact when discarded rows are at least as numerous as live rows. This amortizes compaction over preceding advances without introducing a new public API or custom collection.

The proposal has a memory tradeoff: discarded `BitArray` references are retained until compaction/reset, and some sliding-window workloads can grow the backing list capacity. The PR documents these limits and the correctness checks; unchanged allocation counts above apply only to the measured workloads.

Suggested issue classification for maintainer triage: `area-Layout`, `tenet-performance`, `enhancement`.

Contributor guide

Open the contributing guide

Research direction

Start with src/System.Windows.Forms/System/Windows/Forms/Layout/TableLayout.ReservationGrid.cs and review PR #15065, including its benchmark source and correctness checks. Run the documented benchmark on an STA thread, then verify that deep row spans, control placement, overlap detection, grow-style behavior, and exceptions remain unchanged while reservation advancement scales linearly.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
desktop, performance
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.