Introduction
Optimizing C# algorithms involves identifying bottlenecks and applying targeted improvements: choosing better data structures, reducing allocations, eliminating redundant computation, and leveraging language-specific features like Span<T> and LINQ. This article walks through common optimization techniques with practical examples.
Profiling Before Optimizing
Always measure before optimizing. Use Stopwatch for quick benchmarks and BenchmarkDotNet for rigorous comparisons:
1using System.Diagnostics;
2
3var sw = Stopwatch.StartNew();
4int result = SlowAlgorithm(data);
5sw.Stop();
6Console.WriteLine($"Elapsed: {sw.ElapsedMilliseconds}ms");
For production profiling, use BenchmarkDotNet:
1using BenchmarkDotNet.Attributes;
2using BenchmarkDotNet.Running;
3
4[MemoryDiagnoser]
5public class AlgorithmBenchmarks
6{
7 private int[] data;
8
9 [GlobalSetup]
10 public void Setup() => data = Enumerable.Range(0, 100_000).ToArray();
11
12 [Benchmark(Baseline = true)]
13 public int Original() => SlowSum(data);
14
15 [Benchmark]
16 public int Optimized() => FastSum(data);
17}
18
19BenchmarkRunner.Run<AlgorithmBenchmarks>();
Optimization 1: Replace O(n²) with O(n)
The most impactful optimization is reducing algorithmic complexity:
1// O(n²) — checking all pairs for duplicates
2public static bool HasDuplicatesSlow(int[] arr)
3{
4 for (int i = 0; i < arr.Length; i++)
5 for (int j = i + 1; j < arr.Length; j++)
6 if (arr[i] == arr[j])
7 return true;
8 return false;
9}
10
11// O(n) — using a HashSet
12public static bool HasDuplicatesFast(int[] arr)
13{
14 var seen = new HashSet<int>(arr.Length);
15 foreach (int x in arr)
16 if (!seen.Add(x))
17 return true;
18 return false;
19}
Optimization 2: Choose the Right Data Structure
1// Slow: searching a List<T> is O(n)
2List<string> list = GetLargeList();
3bool found = list.Contains("target"); // O(n)
4
5// Fast: HashSet<T> lookup is O(1)
6HashSet<string> set = new HashSet<string>(list);
7bool found = set.Contains("target"); // O(1)
| Operation | List<T> | HashSet<T> | Dictionary<K,V> | SortedSet<T> |
| Search | O(n) | O(1) | O(1) | O(log n) |
| Insert | O(1)* | O(1) | O(1) | O(log n) |
| Delete | O(n) | O(1) | O(1) | O(log n) |
| Ordered | Yes | No | No | Yes |
Optimization 3: Reduce Allocations
Excessive object allocation increases GC pressure. Use value types, Span<T>, and pooling:
1// Bad: allocates a new string for every substring check
2public static int CountSubstrings(string text, string target)
3{
4 int count = 0;
5 for (int i = 0; i <= text.Length - target.Length; i++)
6 {
7 if (text.Substring(i, target.Length) == target) // Allocates!
8 count++;
9 }
10 return count;
11}
12
13// Good: use Span<T> to avoid allocations
14public static int CountSubstringsOptimized(string text, string target)
15{
16 int count = 0;
17 ReadOnlySpan<char> textSpan = text.AsSpan();
18 ReadOnlySpan<char> targetSpan = target.AsSpan();
19
20 for (int i = 0; i <= textSpan.Length - targetSpan.Length; i++)
21 {
22 if (textSpan.Slice(i, targetSpan.Length).SequenceEqual(targetSpan))
23 count++;
24 }
25 return count;
26}
Optimization 4: Cache Computed Values
1// Bad: recomputes expensive operation every iteration
2for (int i = 0; i < items.Length; i++)
3{
4 double threshold = Math.Sqrt(items.Length) * ComputeFactor(); // Constant!
5 if (items[i] > threshold) Process(items[i]);
6}
7
8// Good: compute once outside the loop
9double threshold = Math.Sqrt(items.Length) * ComputeFactor();
10for (int i = 0; i < items.Length; i++)
11{
12 if (items[i] > threshold) Process(items[i]);
13}
Optimization 5: Use Array/Span over LINQ for Hot Paths
LINQ is readable but adds overhead from delegates and allocations:
1// LINQ — readable but allocates iterators and delegates
2int sum = numbers.Where(n => n > 0).Sum();
3
4// Manual loop — no allocations, faster in tight loops
5int sum = 0;
6foreach (int n in numbers)
7{
8 if (n > 0) sum += n;
9}
10
11// Span + for loop — fastest for arrays
12int sum = 0;
13Span<int> span = numbers.AsSpan();
14for (int i = 0; i < span.Length; i++)
15{
16 if (span[i] > 0) sum += span[i];
17}
Optimization 6: StringBuilder for String Concatenation
1// Bad: O(n²) — creates a new string on each concatenation
2string result = "";
3for (int i = 0; i < 10000; i++)
4 result += i.ToString() + ",";
5
6// Good: O(n) — StringBuilder mutates in place
7var sb = new StringBuilder(10000 * 5); // Pre-allocate capacity
8for (int i = 0; i < 10000; i++)
9{
10 sb.Append(i);
11 sb.Append(',');
12}
13string result = sb.ToString();
Optimization 7: Parallel Processing
For CPU-bound work on large datasets, use Parallel.For or PLINQ:
1// Sequential
2double[] results = new double[data.Length];
3for (int i = 0; i < data.Length; i++)
4 results[i] = ExpensiveComputation(data[i]);
5
6// Parallel
7Parallel.For(0, data.Length, i =>
8{
9 results[i] = ExpensiveComputation(data[i]);
10});
Common Pitfalls
Premature optimization: Optimize only after profiling identifies the actual bottleneck. Most code runs infrequently enough that readability matters more than micro-performance.
Micro-benchmarking mistakes: JIT compilation, CPU caching, and GC pauses skew naive benchmarks. Use BenchmarkDotNet with warmup iterations for reliable measurements.
LINQ in hot loops: LINQ is fine for cold paths. In tight loops called millions of times, the delegate invocation and iterator allocation cost adds up. Switch to for loops in hot paths.
Boxing with generics: Using object or non-generic interfaces with value types causes boxing. Prefer generic methods and interfaces (IComparable<T> over IComparable).
Over-parallelizing: Parallel processing has thread management overhead. For small datasets or cheap operations, the overhead exceeds the benefit. Only parallelize CPU-bound work on large inputs.
Summary
Profile first with Stopwatch or BenchmarkDotNet — never guess the bottleneck
Reduce algorithmic complexity (O(n²) → O(n)) before micro-optimizing
Choose appropriate data structures: HashSet for lookups, Dictionary for key-value, Span<T> for slicing without allocation
Minimize allocations in hot paths using Span<T>, StringBuilder, and value types
Use Parallel.For for CPU-bound work on large datasets, but avoid over-parallelizing
