Improve performance of UriIdentityService (#273108) by yavanosta · Pull Request #273111 · microsoft/vscode

yavanosta · 2025-10-24T13:14:24Z

This CL improves perfrormance of UriIdentityService:

Migrates to string keys and native Map for cache to reduce amount of URI objects creation/conversion to string.
Improves cache cleanup algorithm by using quickSelect to pick median value instead of sorting the entire cache.

Changes measured on my local machine (MacBook Air M4):

Case 1: inserting 1000 URIs on almost full cache (has 64000 items): 153ms -> 18ms
Case 2: reading 50000 URIs from cache on almost full cache (has 65000 items): 297ms -> 81ms
Case 3: cache trim 297ms -> 17ms

Fixes #273108

…rosoft#273108)

Copilot

Pull Request Overview

This PR improves the performance of the UriIdentityService by optimizing its internal caching mechanism. The changes reduce object creation overhead and improve cache cleanup efficiency.

Key changes:

Migrated from SkipList to native Map with string keys to reduce URI object creation
Refactored path casing logic into a separate PathCasingCache class
Replaced full-sort cache cleanup with quickSelect algorithm to find median value

Reviewed Changes

Copilot reviewed 2 out of 2 changed files in this pull request and generated 2 comments.

File	Description
src/vs/platform/uriIdentity/common/uriIdentityService.ts	Refactored UriIdentityService to use Map with string keys, extracted PathCasingCache class, and optimized cache cleanup with quickSelect
src/vs/platform/uriIdentity/test/common/uriIdentityService.test.ts	Added test to verify cache eviction respects access time when cache overflows

src/vs/platform/uriIdentity/test/common/uriIdentityService.test.ts

src/vs/platform/uriIdentity/common/uriIdentityService.ts

…microsoft#273108)

…crosoft#273108)

jrieken

Can we leave cosmetic changes (formatting, extracting code) out of this PR. It makes reviewer harder and only serves personal preferences. Thanks

jrieken · 2025-11-10T14:40:23Z

src/vs/platform/uriIdentity/common/uriIdentityService.ts

+	scheme: string;
+}
+
+class PathCasingCache extends Disposable {


Extracting PathCasingCache is just cosmetic and to your personal preference or am I missing some "real" change here?

Hi Johannes. Thanks for the thoughtful review!

This is mixture of cosmetic and real change. Let me try to clarify this and the next comment.

The current behavior works in the following way:

We create a new ExtUri(ignorePathCasing) passing there ignorePathCasing callback as a parameter

On the UriIdentityService side we maintain a map that keeps track of case sensitivity for each file system

Since SkipList uses this.extUri for each comparison it automatically uses the latest version of case-sensitivity state

However with the new pre-generated string keys situation is different:

We generate keys on insertion using the current state of case-sensitivity

On read we do NOT read the state of case-sensitivity, so we can read wrong URI if case-sensitivity for a certain file system has changed

To fix this, there are two options: regenerate keys or simply clean them up from cache and let them to be regenerated on the next read

Since in comparison to just updating boolean (what happens today), both of that options is relatively expensive we don't want to do that on each onDidChangeFileSystemProviderCapabilities event, since it may be related to some other capability. So we only do that when case sensitivity changes.

Overall this logic became slightly more complicated. Today: update boolean on every event. Now: maintain case-sensitivity state and clean up the main cache if it changes. So I decided that it would make sense to extract all case-sensitivity tracking logic into a separate class to keep each class focused on they primary purpose. Case sensitivity cache - track case sensitivity state and inform the main class when it changes. The main class maintain URI cache and (partially) clear it when needed.

Does this split make sense from your perspective?

Reverted split.

jrieken · 2025-11-10T14:41:23Z

src/vs/platform/uriIdentity/common/uriIdentityService.ts

+			if (entry.uri.scheme !== e.scheme) {
+				continue;
+			}
+			this._canonicalUris.delete(key);


This is new behaviour, right? So when the FS casing has changes old canonical uris are dropped

See response here. I tried to cover both comments in a single response.

src/vs/platform/uriIdentity/common/uriIdentityService.ts

yavanosta · 2025-11-11T09:41:59Z

Can we leave cosmetic changes (formatting, extracting code) out of this PR. It makes reviewer harder and only serves personal preferences. Thanks

~~Hi Johannes!~~

~~Thanks for the review. Can I ask you to clarify what specifically you suggest to revert in this PR? My understanding is that you recommend to:~~

~~Revert PathCasingCache extraction. Is this still valid after my explanation?~~
~~Do you also recommend to revert refactoring to Disposable?~~
~~Not sure if I understand what you mean by formatting. I have not reformatted code I have not touched, can you share an example of what you mean here?~~

I reverted every change possible to minimize diff.

jrieken · 2025-11-12T14:08:01Z

I reverted every change possible to minimize diff.

Thanks for doing that and for this high quality PR. It's the details that make a great product. You can pick up a thank you here: https://swag.code.visualstudio.com

yavanosta added 3 commits October 24, 2025 10:37

UriIdentityService: Extend disposable to manage child disposables

9aebfc7

UriIdentityService: Extract PathCasingCache in a separate class

2a1e508

UriIdentityService: use strings as keys for _canonicalUris cache (mic…

4af82e4

…rosoft#273108)

Copilot AI review requested due to automatic review settings October 24, 2025 13:14

Copilot AI reviewed Oct 24, 2025

View reviewed changes

src/vs/platform/uriIdentity/test/common/uriIdentityService.test.ts Outdated Show resolved Hide resolved

src/vs/platform/uriIdentity/common/uriIdentityService.ts Outdated Show resolved Hide resolved

yavanosta force-pushed the UriIdentityService-perf branch from 42f61f3 to 528a459 Compare October 24, 2025 13:19

vs-code-engineering bot added the triage-needed label Oct 24, 2025

vs-code-engineering bot assigned dbaeumer Oct 24, 2025

yavanosta added 3 commits October 24, 2025 15:49

UriIdentityService: use quickSelect for cache trim instead of sorting (…

5fe7a3f

…microsoft#273108)

UriIdentityService: use native Map instead of skip list for cache (mi…

00a48da

…crosoft#273108)

UriIdentityService: add test for cache cleanup order

01f4c01

yavanosta force-pushed the UriIdentityService-perf branch from 528a459 to 01f4c01 Compare October 24, 2025 13:49

bpasero assigned jrieken and unassigned dbaeumer Oct 24, 2025

bpasero removed the triage-needed label Oct 24, 2025

jrieken self-requested a review November 10, 2025 14:20

jrieken added 2 commits November 10, 2025 15:23

Merge branch 'main' into UriIdentityService-perf

5ed07e9

fix tests

e73bbd5

jrieken requested changes Nov 10, 2025

View reviewed changes

UriIdentityService: minimize diff size as requested on review

781f319

yavanosta force-pushed the UriIdentityService-perf branch from 6e5b4c6 to 781f319 Compare November 11, 2025 10:35

UriIdentityService: set time=1 for the first item after trim

add8ec5

yavanosta requested a review from jrieken November 11, 2025 10:38

jrieken approved these changes Nov 12, 2025

View reviewed changes

vs-code-engineering bot added this to the November 2025 milestone Nov 12, 2025

jrieken enabled auto-merge November 12, 2025 14:08

bpasero approved these changes Nov 12, 2025

View reviewed changes

jrieken merged commit b6555e9 into microsoft:main Nov 12, 2025
17 checks passed

vs-code-engineering bot locked and limited conversation to collaborators Dec 28, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Improve performance of UriIdentityService (#273108)#273111

Improve performance of UriIdentityService (#273108)#273111
jrieken merged 10 commits intomicrosoft:mainfrom
yavanosta:UriIdentityService-perf

yavanosta commented Oct 24, 2025 •

edited

Loading

Uh oh!

Copilot AI left a comment

Uh oh!

Uh oh!

Uh oh!

jrieken left a comment

Uh oh!

jrieken Nov 10, 2025

Uh oh!

yavanosta Nov 11, 2025

Uh oh!

yavanosta Nov 11, 2025

Uh oh!

jrieken Nov 10, 2025

Uh oh!

yavanosta Nov 11, 2025

Uh oh!

Uh oh!

yavanosta commented Nov 11, 2025 •

edited

Loading

Uh oh!

jrieken commented Nov 12, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

Conversation

yavanosta commented Oct 24, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull Request Overview

Reviewed Changes

Uh oh!

Uh oh!

Uh oh!

jrieken left a comment

Choose a reason for hiding this comment

Uh oh!

jrieken Nov 10, 2025

Choose a reason for hiding this comment

Uh oh!

yavanosta Nov 11, 2025

Choose a reason for hiding this comment

Uh oh!

yavanosta Nov 11, 2025

Choose a reason for hiding this comment

Uh oh!

jrieken Nov 10, 2025

Choose a reason for hiding this comment

Uh oh!

yavanosta Nov 11, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

yavanosta commented Nov 11, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jrieken commented Nov 12, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

yavanosta commented Oct 24, 2025 •

edited

Loading

yavanosta commented Nov 11, 2025 •

edited

Loading