FindStructSizeByField is O(n²) inside instruction loop

[jonathanpeppers]

Problem

FindStructSizeByField in Transpiler.StructAnalysis.cs performs an O(structs x fields) search on every call:

static int FindStructSizeByField(
    string fieldName,
    Dictionary<string, List<(string Name, int Size)>> structLayouts)
{
    foreach (var kvp in structLayouts)
    {
        foreach (var f in kvp.Value)
        {
            if (f.Name == fieldName)
            {
                int size = 0;
                foreach (var field in kvp.Value) size += field.Size;
                return size;
            }
        }
    }
    return 0;
}

This is called inside Pass 3 of EstimateMethodLocalBytes (Transpiler.LocalFrameAllocation.cs:115-152), which iterates all IL instructions. The combined complexity is O(instructions x structs x fields).

Impact

For a 2000-instruction method with 10 struct types x 5 fields each, this is up to 100,000 string comparisons per method. Not a correctness bug today, but transpilation time degrades quadratically as programs grow more complex.

Proposed Fix

Pre-build a reverse-lookup dictionary before the loop:

// Build once before Pass 3
var fieldToStructSize = new Dictionary<string, int>(StringComparer.Ordinal);
foreach (var (_, fields) in structLayouts)
{
    int structSize = fields.Sum(f => f.Size);
    foreach (var (fieldName, _) in fields)
        fieldToStructSize[fieldName] = structSize;
}

// Pass 3: O(1) lookup per instruction
if (fieldToStructSize.TryGetValue(fieldName, out int structSize) && structSize > 0)
{
    totalBytes += structSize;
    structLocalsCounted.Add(ldlocaIdx);
}

Files

• src/dotnes.tasks/Utilities/Transpiler.StructAnalysis.cs (lines 263-280)
• src/dotnes.tasks/Utilities/Transpiler.LocalFrameAllocation.cs (lines 115-152)

[jonathanpeppers]

The algorithmic analysis looks correct (moving from O(I x S x F) to O(S x F + I)), but we should prove it with numbers before merging.

Can we add a BenchmarkDotNet project that benchmarks EstimateMethodLocalBytes (or FindStructSizeByField directly) with varying instruction counts and struct layouts? That way we can see the actual before/after timings and confirm the improvement is measurable in practice.