go-playground / form

100%

Build Type

push

github

Committed by web-flow

Commit Message

Improve issue #71: Optimize nested structure decoding performance (#73)

## Problem
When decoding structs with data nested inside two or more layers of
slices or maps, the decoder exhibited exponential performance
degradation based on the number of values.

### Example Structure
```go
type FormRequest struct {
Foos []*NestedFoo `form:"foos"`
}

type NestedFoo struct {
Bars []*NestedBar `form:"bars"`
}

type NestedBar struct {
Bazs   []string          `form:"bazs"`
Lookup map[string]string `form:"lookup"`
}
```

### Performance Before Fix
- 50 values: ~1 second
- 100 values: ~4 seconds  
- 200 values: ~16 seconds

The performance degradation was exponential, making the decoder unusable
for real-world nested data.

## Root Cause
The `findAlias()` function performed a **linear O(n) search** through
the `dataMap` slice for every alias lookup. With deeply nested
structures, this function was called thousands or millions of times,
resulting in O(n²) or worse complexity.

For example, with 1000 nested elements, the parser would:
1. Create ~1002 unique aliases (1 for `foos`, 1 for `foos[0].bars`, 1000
for `foos[0].bars[N].lookup`)
2. Call `findAlias()` many times during parsing and decoding
3. Each `findAlias()` call would iterate through the entire dataMap
linearly

## Solution
Replaced the linear search with a **hash map lookup (O(1))**:

1. Added `aliasMap map[string]*recursiveData` field to the `decoder`
struct
2. Modified `parseMapData()` to populate the map as aliases are created
3. Changed `findAlias()` to use the map instead of iterating through the
slice

### Code Changes
**decoder.go:**
- Added `aliasMap` field to `decoder` struct for O(1) lookups
- Initialized/cleared the map in `parseMapData()`  
- Populated the map when creating new `recursiveData` entries
- Modified `findAlias()` to use map lookup instead of linear search

**decoder_test.go:**
- Added comprehensive test with 10, 50, and 200 nested values
- Uses race-detector-aware thresholds (st... (continued)

Run Details

9 of 9 new or added lines in 1 file covered. (100.0%)

1 existing line in 1 file now uncovered.

1080 of 1083 relevant lines covered (99.72%)

43077.28 hits per line