Does this issue occur when all extensions are disabled?: Yes

• VS Code Version: 1.105.1
• OS Version: MacOS 15.7.1

UriIdentityService is heavily used to normalize URIs. While this code is not very heavy it sits on a critical path in many situation and already caused significant performance problems before. See this issue as an example when a user had more then 1 million items in cache.

Currently [UriIdentityService] has some room for improvement:

1. For caching it uses SkipList with extUri.compare as a comparator. Compare method currently creates comparison key for each URI before comparison. It leads to creation of 2 new URIs and stringifying them which is also non-trivial. While each individual operation is not very heavy they can build up due to huge amount of them. With (almost) full cache get/set operation will require around 35 comparisons (see SkipList source and paper). Which means around 70 URI creations and toString calls in getComparisonKey. All together this leads to high costs of reading/writing many items from the list.

2. It is important to mention that huge amount of getComparisonKey is needed not only for insertion but also for reads, making reading from the cache almost as expensive operation as insertion.

3. While one can notice problems (1) and (2) only when reading/writing huge amounts of items in cache (thousands of items) which should not happen very often, such a situation actually happens when cache overflows. The current implementation sorts all existing items in cache in chronological order, clears the cache and reinsert items back to cache one by one. With the current limit it is 32768 insertions. It can take up to 200-300 ms

4. Last tiny problem is that current implementation of UriIdentityService reverses cache age on cleanup. First it sorts items in descending order (max time === newest first), then resets cache timer, and then reinserts first half of the resulting array into new cache starting from the head of the list. So the most recent item in the old cache gets 0 time in a new cache, so it becomes the oldest. But in fact this is not important because we are not specifically interested in relative timing for items left in cache. Since this is exactly half of the cache, and after cleanup this is by definition the oldest half all of them. If none of them are touched they all together will be removed anyway. And if some of them are touched they will get updated time.