Potential performance issue: linear template parameter lookup in reliesOnTemplateParameters

[arnavsharma990]

Hi,

While exploring template instantiation logic in DMD, I noticed a potential performance bottleneck in templatesem.d, specifically in the reliesOnTemplateParameters function.

Issue

In multiple visitor cases (e.g., TypeIdentifier), the code performs a linear scan over all template parameters:

foreach (tp; tparams)
{
    if (tp.ident.equals(t.ident))
        return true;
}

This check appears to be executed frequently during template deduction and semantic analysis, and is also used recursively when traversing complex types.

Why it might matter

• This introduces O(n) lookup per check, where n = number of template parameters
• For templates with many parameters or deeply nested types, this can multiply quickly
• The function is called repeatedly during template matching and deduction

Possible direction

One possible improvement could be:

• Precomputing a hash-based lookup (e.g., identifier → parameter set)
• Or using a more efficient structure to avoid repeated linear scans

Question

Is this something that has already been considered or optimized elsewhere?

I’d be happy to explore this further and try benchmarking potential improvements if this direction makes sense.

Thanks!

[dkorpel]

Is this something that has already been considered or optimized elsewhere?

Parameters use linear scans in various places. In practice this is often okay since most functions don't have more than 5 parameters. That means the constant factor might be more important than the time complexity, so an investigation of real code bases is in order.

I recall plotting the distribution of parameter lengths in all public dub packages years ago, the median was somewhere below 5 and the max was somewhere below 40. This was only regular parameters instead of template parameters, but those are more common and likely to cause performance trouble. I would particularly investigate the O(n) Parameter.getNth function often used in loops, that's more likely to be a bottleneck but again - it's better to measure than guess!