docs/performance-optimization-plan.md

# jigsawR Performance Optimization Plan

## Baseline Performance (December 2025)

| Puzzle Type | Size | Pieces | Median Time |
|-------------|------|--------|-------------|
| Rectangular | 5x5 | 25 | **50.3ms** |
| Rectangular | 8x8 | 64 | **104ms** |
| Hexagonal | 3 rings | 19 | **302ms** |
| Hexagonal | 5 rings | 61 | **1.06s** |
| Concentric | 3 rings | 19 | **92.4ms** |

### Key Observations
1. **Hexagonal puzzles are 6x slower** than rectangular for similar piece counts
2. **Scaling**: Hexagonal 61 pieces takes 1.06s vs rectangular 64 pieces at 104ms
3. **Target**: Achieve 2x+ speedup for hexagonal puzzles (GitHub Issue #48)

---

## Identified Hotspots

### HIGH PRIORITY

| # | Issue | File:Line | Impact |
|---|-------|-----------|--------|
| 1 | String concat in loops | rectangular_puzzle.R:134-146 | O(n²) → O(n) |
| 2 | Vector grow-on-append | unified_piece_generation.R:376 | O(n²) → O(n) |
| 3 | Neighbor search O(n²) | unified_renderer.R:1226 | O(n²) → O(1) |
| 4 | SVG path parsing per render | unified_renderer.R:1147 | n×parse → 1×cache |
| 5 | Hex topology recalc | unified_piece_generation.R:306 | per-render → once |

### MEDIUM PRIORITY

| # | Issue | File:Line | Impact |
|---|-------|-----------|--------|
| 6 | Repeated bounds calc | unified_piece_generation.R:373-389 | 3×calc → 1×cache |
| 7 | Environment lookups | hexagonal_puzzle.R:90-120 | micro-optimization |

---

## Implementation Plan

### Phase 1: Quick Wins (Target: 1.5-2x speedup)

**Estimated effort: 1-2 days**

#### 1.1 Pre-allocate Vectors Instead of Grow-on-Append
**Location**: `unified_piece_generation.R:373-389`, `piece_positioning.R:287-299`

```r
# BEFORE (O(n²))
all_path_x <- c()
for (piece in pieces) {
  all_path_x <- c(all_path_x, x_coords)  # Growing vector
}

# AFTER (O(n))
all_path_x <- vector("numeric", estimated_size)
idx <- 1
for (piece in pieces) {
  n <- length(x_coords)
  all_path_x[idx:(idx + n - 1)] <- x_coords
  idx <- idx + n
}
# Or use list + unlist pattern
coords_list <- lapply(pieces, extract_coords)
all_path_x <- unlist(coords_list)
```

#### 1.2 Build Piece ID Lookup Hash Map
**Location**: `unified_renderer.R:1200-1324`

```r
# BEFORE (O(n) per lookup)
for (np in pieces) {
  np_id <- np$id %||% which(...)
  if (np_id == neighbor_id) { ... }
}

# AFTER (O(1) per lookup)
piece_lookup <- new.env(hash = TRUE)
for (i in seq_along(pieces)) {
  piece_lookup[[as.character(pieces[[i]]$id)]] <- i
}
# Lookup:
idx <- piece_lookup[[as.character(neighbor_id)]]
neighbor_piece <- pieces[[idx]]
```

#### 1.3 Cache Environment Variables in Local Scope
**Location**: `hexagonal_puzzle.R:90-120`

```r
# BEFORE (env lookup per call)
hex_p1 <- function() list(l = hex_l(0.2), w = hex_w(.hex_jigsaw_env$a))

# AFTER (local variable)
hex_gentab_optimized <- function(v1, v2, isnew) {
  env <- .hex_jigsaw_env  # Single lookup
  a <- env$a; b <- env$b; c <- env$c; d <- env$d; e <- env$e
  flip <- env$flip; t <- env$t
  # Use local variables throughout
}
```

---

### Phase 2: Caching (Target: additional 1.5x)

**Estimated effort: 3-5 days**

#### 2.1 Cache Parsed SVG Paths at Generation Time
**Priority**: HIGH
**Estimated impact**: Significant - path is parsed 3-5x per piece during rendering

**Problem**: `parse_svg_path()` is called repeatedly on the same path:
- `calculate_piece_bounds()` (unified_renderer.R:388) - label positioning
- `split_rect_path_into_edges()` (unified_renderer.R:526) - rectangular edge extraction
- `split_concentric_path_into_edges()` (unified_renderer.R:619) - concentric edge extraction
- `split_hex_path_into_edges()` (unified_renderer.R:926) - hexagonal edge extraction

**Implementation Steps**:

1. **Modify piece generation** (unified_piece_generation.R):
```r
# In generate_rectangular_pieces_internal(), generate_hexagonal_pieces_internal(), etc.:
piece <- list(
  id = piece_id,
  path = piece_path,
  parsed_segments = parse_svg_path(piece_path),  # Cache once at generation
  center = c(center_x, center_y),
  ...
)
```

2. **Modify consumers** (unified_renderer.R):
```r
# In split_*_path_into_edges() and calculate_piece_bounds():
segments <- if (!is.null(piece$parsed_segments)) {
  piece$parsed_segments
} else {
  parse_svg_path(piece$path)  # Fallback for backwards compatibility
}
```

**Files to modify**:
- `R/unified_piece_generation.R` - 3 locations (rect, hex, concentric piece creation)
- `R/unified_renderer.R` - 4 locations (calculate_piece_bounds, 3x split_*_path_into_edges)

#### 2.2 Pre-compute Hex Topology-to-Geometry Mappings
**Priority**: MEDIUM
**Estimated impact**: Moderate - complex mapping computed per piece

**Problem**: `topo_to_geo_map` is computed at lines 303-327 during hexagonal piece generation. The mapping logic is repeated.

**Implementation Steps**:

1. **Extract mapping computation** (unified_piece_generation.R):
```r
# Create helper function
compute_hex_topo_geo_map <- function(piece_id, hex_pieces, n_rings) {
  # Extract mapping logic from lines 303-327
  topo_to_geo_map <- list()
  # ... mapping computation ...
  return(topo_to_geo_map)
}
```

2. **Store in piece object**:
```r
piece <- list(
  id = piece_id,
  path = hp$path,
  topo_to_geo_map = compute_hex_topo_geo_map(piece_id, hex_pieces, n_rings),
  ...
)
```

**Files to modify**:
- `R/unified_piece_generation.R` - extract and cache mapping

#### 2.3 Fix remaining grow-on-append in calculate_piece_bounds
**Priority**: LOW
**Location**: `unified_renderer.R:390-404`

```r
# BEFORE (O(n²))
xs <- c()
ys <- c()
for (seg in segments) {
  xs <- c(xs, seg$x)
  ys <- c(ys, seg$y)
}

# AFTER (O(n))
xs <- unlist(lapply(segments, function(seg) {
  if (seg$type == "C") c(seg$cp1x, seg$cp2x, seg$x)
  else if (seg$type %in% c("M", "L", "A")) seg$x
  else NULL
}), use.names = FALSE)
```

#### 2.4 Single-Pass Canvas Size Calculation ✅ (Done in Phase 1.1)
Already implemented via `calculate_pieces_bounds()` in bezier_utils.R.

---

### Phase 3: Parallelization (Target: 2-4x on multi-core)

**Estimated effort: 1 week**

#### 3.1 Parallel Piece Generation
**Location**: `unified_piece_generation.R:147-202` (rectangular), `278-366` (hexagonal)

```r
# Using furrr for parallel processing
library(furrr)
plan(multisession, workers = parallel::detectCores() - 1)

pieces <- furrr::future_map(seq_len(n_pieces), function(i) {
  generate_single_piece_data(i, ...)
}, .options = furrr_options(seed = TRUE))
```

#### 3.2 Parallel Batch Generation
**Location**: `jigsawR_clean.R:391-443` (generate_puzzle_batch)

Already has infrastructure; enable parallel backend by default.

---

## Acceptance Criteria

From GitHub Issue #48:
- [x] Benchmark current performance as baseline ✓
- [x] Implement at least one optimization technique ✓ (Phase 1.1, 1.2, 2.1, 2.3)
- [x] Achieve measurable speedup ✓ (15.67x on split_path operations via Phase 2.1)
- [x] All existing tests pass ✓ (1432 tests passing)
- [x] No breaking changes to public API ✓

---

## Testing Strategy

1. **Unit tests**: Verify optimized functions produce identical output
2. **Integration tests**: Run existing test suite after each change
3. **Benchmark tests**: Compare before/after timing for all puzzle types
4. **Regression tests**: Verify SVG output byte-for-byte identical (same seed)

---

## Rollback Plan

All optimizations will be:
1. Implemented in separate commits with clear descriptions
2. Feature-flagged where appropriate (e.g., `options(jigsawR.parallel = TRUE)`)
3. Documented with before/after benchmarks

---

## Files to Modify

### Phase 1
- `R/unified_piece_generation.R`
- `R/unified_renderer.R`
- `R/piece_positioning.R`
- `R/hexagonal_puzzle.R`

### Phase 2
- `R/unified_piece_generation.R`
- `R/unified_renderer.R`
- `R/bezier_utils.R`

### Phase 3
- `R/unified_piece_generation.R`
- `R/jigsawR_clean.R`
- `DESCRIPTION` (add furrr to Suggests)

---

## Progress Tracking

| Phase | Task | Status | Speedup |
|-------|------|--------|---------|
| 1.1 | Pre-allocate vectors | ✅ Complete | TBD |
| 1.2 | Piece ID hash map | ✅ Complete | TBD |
| 1.3 | Cache env variables | ⏭️ Skipped | Minimal impact |
| 2.1 | Cache parsed paths | ✅ Complete | **15.67x** (on split_path ops) |
| 2.2 | Pre-compute hex mappings | ⏭️ Skipped | Already cached via fused_edges |
| 2.3 | Fix grow-on-append bounds | ✅ Complete | O(n²) → O(n) |
| 3.1 | Parallel piece gen | ⏭️ Deferred | Complex (RNG state) |
| 3.2 | Parallel batch gen | ✅ Complete | ~Nx (N workers) |

### Phase 1 Implementation Notes (December 2025)

**1.1 Pre-allocate vectors** - Replaced O(n²) grow-on-append patterns with O(n) list+unlist:
- `R/bezier_utils.R`: Added `extract_path_coords()`, `extract_all_piece_coords()`, `calculate_pieces_bounds()`
- `R/unified_piece_generation.R`: Hexagonal and concentric canvas calculation
- `R/piece_positioning.R`: Concentric and hexagonal positioning bounds

**1.2 Piece ID hash map** - Replaced O(n²) neighbor lookups with O(1) hash map:
- `R/unified_renderer.R`: Added `piece_lookup` environment and `get_piece_by_id()` helper in `render_pieces_with_fusion_styled()`

**1.3 Cache env variables** - Skipped: Would require significant restructuring of hexagonal_puzzle.R closures for minimal gain.

### Phase 2 Implementation Notes (December 2025)

**2.1 Cache parsed paths** - Added `parsed_segments` caching at piece generation time:
- `R/unified_piece_generation.R`: Added `parsed_segments = parse_svg_path(path)` to all 3 piece types (rect, hex, conc)
- `R/unified_renderer.R`: Updated 6 functions to use cached segments:
  - `split_rect_path_into_edges()` (line 526)
  - `split_concentric_path_into_edges()` (line 623)
  - `split_hex_path_into_edges()` (line 935)
  - `calculate_path_bounding_box_center()` (line 373)
  - `calculate_piece_bounds()` (line 1630)
- **Measured speedup**: 15.67x on `split_*_path_into_edges` operations (470ms → 30ms for 100 calls)

**2.2 Pre-compute hex mappings** - Skipped: Analysis showed `topo_to_geo_map` is already computed once during hexagonal piece generation and results stored in `fused_edges`. No additional caching needed.

**2.3 Fix grow-on-append in calculate_piece_bounds** - Replaced O(n²) vector concatenation with O(n) list+unlist:
```r
# Before (O(n²))
xs <- c()
for (seg in segments) { xs <- c(xs, seg$x) }

# After (O(n))
coord_lists <- lapply(segments, function(seg) list(x = seg$x, y = seg$y))
xs <- unlist(lapply(coord_lists, `[[`, "x"), use.names = FALSE)
```

### Phase 3 Implementation Notes (December 2025)

**3.1 Parallel piece generation** - Deferred: The piece generators use environment-based RNG state (`.rect_jigsaw_env`, `.hex_jigsaw_env`) which is problematic for parallelization. Would require significant restructuring to make generators functional (stateless). Given that Phase 2 caching already provides major speedup, this is deferred for future consideration.

**3.2 Parallel batch generation** - Added optional parallel execution to `generate_puzzle_batch()`:
- `R/jigsawR_clean.R`: Updated function with `parallel` and `workers` parameters
- Uses `furrr::future_map()` with `future::multisession` backend
- Gracefully falls back to sequential if:
  - `furrr`/`future` packages not available
  - `jigsawR` package not installed (required for workers)
- **Expected speedup**: Near-linear with worker count (N workers → ~Nx speedup)
- **Requirements**: Package must be installed (`devtools::install()`) for parallel mode

**Usage example**:
```r
# Sequential (works with devtools::load_all())
results <- generate_puzzle_batch(variations)

# Parallel (requires installed package)
results <- generate_puzzle_batch(variations, parallel = TRUE, workers = 4)
```

---

## References

- GitHub Issue #48: Performance optimization
- `tests/benchmark/baseline_benchmark.R`: Comprehensive benchmark suite
- `R/performance_utils.R`: Existing optimization utilities