Optimize access to our ISearchableReadOnlyList / ImmutableList

[smedilol]

What is the current problem

If you look at CodeElementTokenizer with a Profiler, you'll see that iteration of ImmutableList is slow. This is the same if you use direct index access to an element ot the ImmutableList. The ImmutableList is iterated multiple times by the paser. Most parser step and the diagnostics can iterate it.

The parser should use ISearchableReadOnlyList interface which wraps our ImmutableList class. But there are several cast of ISearchableReadOnlyList to ImmutableList.

Describe the solution you'd like

As we need to update our list of CodeElementLine : insert, update or remove at a specified index, the ImmutableList is the better choice. A LinkedList is not accessible directly with a index. At least not in a fast way.

After a simple test, it's faster to copy the ImmutableList to another list and then iterate over this list. The solution is to copy the ImmutableList to a simple implementation of ISearchableReadOnlyList backed by a simple List. Of course this implementation should prevent any modification to the list.

Technical

• Replace all usage of ImmutableList by ISearchableReadOnlyList if only the interface is needed.
• Restrict the usage of ImmutableList to CompilationDocument to manage text update step.
• Create a simple implementation of ISearchableReadOnlyList backed by a simple List and use it in all step of the parser after text update step.

How to test automatically We can use the same tests made for #2235 and checks the previous version of the Document Snapshot to be sure that each version is immutable.

[fm-117]

The .NET framework has its own implementation for ImmutableList, unfortunately it is available starting with .NET 5...

[smedilol]

Depending on the result of #2442, this issue might not be necessary.

[fm-117]

The PR #2575 contains small changes to help migrate to .NET implementation of ImmutableList, se wtill have to track and adpat all usages of our ISearchableReadOnlyList<T>. After migration check performance gain between original code and MS code.