roslyn: EnC: OutOfMemoryException thrown by LongestCommonSubsequence.ComputeCostMatrix
When editing large methods (1000s of statements).
The algorithm is currently allocating N^2 matrix. It can be optimized to N D or O(N).
Repro:
using System;
class Program
{
static void Main(string[] args)
{
int i = 1;
if (i == 0)
{
Console.WriteLine(0);
Console.WriteLine(1);
...
Console.WriteLine(10000);
}
else
{
Console.WriteLine(0);
Console.WriteLine(1);
...
Console.WriteLine(10000);
}
}
}
About this issue
- Original URL
- State: closed
- Created 8 years ago
- Comments: 17 (9 by maintainers)
Commits related to this issue
- Reduce memory consumption of LongestCommonSubsequence Changed implementation of LongestCommonSubsequence to use a less memory-intensive algorithm. The old algorithm allocated O(oldSequence.Length * n... — committed to hekota/roslyn by hekota 7 years ago
- Reduce memory consumption of LongestCommonSubsequence Changed implementation of LongestCommonSubsequence to use a less memory-intensive algorithm. The old algorithm allocated O(oldSequence.Length * n... — committed to tmat/roslyn by hekota 7 years ago
- Reduce memory consumption of LongestCommonSubsequence (#23808) * Add tests for LongestCommonSubsequence class * Add more tests for LongestCommonSubsequence * Reduce memory consumption of Longes... — committed to dotnet/roslyn by tmat 7 years ago
- Reduce memory consumption of LongestCommonSubsequence Changed implementation of LongestCommonSubsequence to use a less memory-intensive algorithm. The old algorithm allocated O(oldSequence.Length * n... — committed to tmat/roslyn by hekota 7 years ago
- Port https://github.com/dotnet/roslyn/pull/16677 to Dev14 (#23812) * Reduce memory consumption of LongestCommonSubsequence Changed implementation of LongestCommonSubsequence to use a less memory-i... — committed to dotnet/roslyn by tmat 7 years ago
Fixed by https://github.com/dotnet/roslyn/pull/16677