Performance: Table column width calculation is O(rows × cells × depth)
Nobody has claimed this yet.
- Dominant language
- Go
- Stars
- 1
- Forks
- 2
- PR merge metrics
- No merged PRs in 30d
Description
## Description
Table layout performs expensive recursive content width estimation for every cell, resulting in O(rows × cells × tree_depth) complexity.
## Location
- `layout/layout.go:870-947` - `calculateColumnWidths()`, `estimateCellMinWidth()`
- `layout/layout.go:950+` - `estimateContentWidth()` (recursive)
## Problem
```go
func (box *LayoutBox) calculateColumnWidths(numColumns int, tableWidth float64) []float64 {
for _, row := range box.Children { // O(rows)
for _, cell := range row.Children { // O(cells)
minWidth := box.estimateCellMinWidth(cell) // Recursive!
}
}
}
func (box *LayoutBox) estimateCellMinWidth(cell *LayoutBox) float64 {
contentWidth := box.estimateContentWidth(cell) // Walks entire subtree
}
```
For a table with 100 rows and 5 columns, this performs 500 recursive tree walks.
## Suggested Improvements
1. **Cache content width during layout pass** - Store `contentWidth` on LayoutBox after first computation
2. **Single-pass accumulation** - Calculate widths while building the layout tree
3. **Limit recursion depth** - For deep nesting, use an estimate instead of exact measurement
4. **Use font metrics for text-only cells** - Skip subtree walk for simple text content
## Impact
Tables are common on web pages. Large tables (like Hacker News) will benefit significantly from this optimization.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading layout/layout.go:870-947, especially calculateColumnWidths() and estimateCellMinWidth(), then inspect estimateContentWidth() around line 950. Compare the suggested caching, single-pass, recursion-limit, and font-metrics approaches; done should reduce repeated recursive walks for large tables while preserving column-width behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100