`UnrechableBlocksOptimizer` has bad performance

[Youssef1313]

Description

It looks like there are repeated called to FoldedInstructions.IndexOf where CPU spends most of its time in?

runtime/src/tools/illink/src/linker/Linker.Steps/UnreachableBlocksOptimizer.cs

Line 1173 in ce54acd

idx = FoldedInstructions.IndexOf (instruction);

It might be more efficient to build a dictionary that maps instruction to index and use that instead of IndexOf?

Reproduction Steps

Expected behavior

Actual behavior

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

[Youssef1313]

I randomly paused the debugger while running the linker, and it was on this line. This is also where it spends most of its time per the performance trace.

Here, FoldedInstructions has 22542 elements. So a dictionary should be a lot better than linear search.

One more note that a dictionary could even be avoided. The instruction index is only calculated to check whether it's in a specific range, and this range is always VERY small. We could just loop through this small range. Note that this small range is either single instruction, two instructions, or maximum three instructions (IsJumpTargetRange (i - 2, i)).

[Youssef1313]

@vitek-karas @sbomer Can you please take a look at this? This should hopefully improve the performance a lot

Tagging subscribers to this area: @agocke, @sbomer, @vitek-karas
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

It looks like there are repeated called to FoldedInstructions.IndexOf where CPU spends most of its time in?

runtime/src/tools/illink/src/linker/Linker.Steps/UnreachableBlocksOptimizer.cs

Line 1173 in ce54acd

idx = FoldedInstructions.IndexOf (instruction);

It might be more efficient to build a dictionary that maps instruction to index and use that instead of IndexOf?

Reproduction Steps

Expected behavior

Actual behavior

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

Author:	Youssef1313
Assignees:	-
Labels:	untriaged, in-pr, area-Tools-ILLink
Milestone:	-