[✨ Triage] dotnet/runtime#117777 by MihaZupan - Uri path compression is O(n^2)

[MihuBot]

Triage for dotnet/runtime#117777.
Repo filter: All networking issues.
MihuBot version: 79b6fb.
Ping MihaZupan for any issues.

This is a test triage report generated by AI, aimed at helping the triage team quickly identify past issues/PRs that may be related.
Take any conclusions with a large grain of salt.

dotnet/runtime#117777: Uri path compression is O(n^2) by MihaZupan
[Tool] Searching for Uri path compression performance, Uri O(n^2), Uri path normalization performance, Uri.cs path compression, Uri ../ performance, Uri path algorithm (IncludeOpen=True, IncludeClosed=True, IncludeIssues=True, IncludePullRequests=True, Repository=dotnet/runtime)
[Tool] Found 80 issues, 116 comments, 80 returned results (15133 ms)

Here are the most relevant related issues and discussions for issue #117777 ("Uri path compression is O(n^2)"):

---

1. PR #117287 (July 2025) - Remove Uri length limits

• Summary: This PR, authored by MihaZupan, removed the explicit 64k length limit for URIs. In the discussion, MihaZupan explicitly points out that the path compression algorithm (removing /../ etc.) is currently O(n^2), and that this could become problematic now that the length limit is gone. He suggests that the algorithm should be rewritten to be linear before .NET 10 ships.
• Key Comment:

  "One issue I see with this is our path compression (e.g. removing /../) algorithm being O(n^2) right now. We should rewrite that into something linear before .NET 10 ships (or we could choose to block this PR until we do so)."
  (link)

• Relevance: Directly acknowledges the O(n^2) issue and its new importance after removing the length limit.

---

2. PR #46751 (January 2021) - Spanify Uri Compress helper

• Summary: This PR extracted and refactored part of the path compression logic to use spans, but did not change the algorithmic complexity. The stated goal was to simplify future changes and improve code clarity, not to improve performance or complexity.
• Discussion: No major discussion about algorithmic complexity, but this PR is a precursor to making the code easier to optimize in the future.

---

3. PR #32692 (February 2020) - Remove more allocations across Uri

• Summary: This PR included a "spanification" of the Compress method (used for path compression), reducing allocations but not changing the O(n^2) nature of the algorithm. There is some discussion about performance regressions in specific cases, but not about the overall complexity.
• Key Comment:

  "Spanified the Compress method to allow for other changes ... there might be a perf regression in specific cases here, I will run some tests"

• Relevance: Shows ongoing work to make the code more efficient and ready for further optimization, but does not address the O(n^2) issue directly.

---

4. Issue #1857 (January 2020) - System.Uri rejects otherwise valid strings with length >= 65520

• Summary: This issue discusses the previous 64k length limit and the engineering trade-offs involved. MihaZupan comments that removing the length restriction would require addressing "sub-optimal algorithmical approaches in Uri that could 'explode' should the length limit be relaxed (in which case they should be fixed ofc)."
• Key Comment:

  "There are likely some sub-optimal algorithmical approaches in Uri that could 'explode' should the length limit be relaxed (in which case they should be fixed ofc)."

• Relevance: Anticipates the exact problem now being raised in #117777.

---

5. PR #32552 (February 2020) - Optimize percent-encoded UTF8 processing in Uri

• Summary: This PR improved the performance of percent-decoding in URIs, making it linear and allocation-friendly. While not directly about path compression, it shows a precedent for optimizing similar algorithms in the Uri class.

---

6. Issue #31300 (October 2019) - [Uri] System.Uri does not compact empty path segments

• Summary: This issue discusses the canonicalization and normalization of URI paths, including the removal of empty segments and dot-segments. The discussion is more about correctness and standards compliance than performance, but it is related to the path normalization logic.

---

7. Issue #34618 (April 2020) - [Uri] Consider caching PathAndQuery

• Summary: Discusses caching computed properties for performance, but not specifically about the O(n^2) path compression.

---

Summary

• The O(n^2) complexity of the path compression algorithm in System.Uri has been known for some time, but was not a practical issue until the 64k length limit was removed in PR #117287.
• MihaZupan, the author of both the length-removal PR and the new issue, has explicitly called out the need to rewrite the path compression logic to be linear before .NET 10 ships.
• Several PRs (notably #46751 and #32692) have refactored the relevant code to use spans and reduce allocations, making it easier to optimize in the future, but have not changed the algorithmic complexity.
• There is precedent for optimizing similar algorithms in the Uri class (e.g., percent-decoding).
• The need to address this is now urgent due to the removal of the length limit.

No existing issue or PR has yet implemented a linear path compression algorithm. The current issue (#117777) is the first to explicitly call for this as a requirement for .NET 10.

---

If you need more details on any of the above issues or PRs, let me know!