Maximizing Algorithm Performance in .NET: Levenshtein Distance
summary
Levenshtein implementation in C# moves from a baseline that takes ~0.5s and allocates ~381MB for 10,000‑char inputs to a chain of concrete wins: replacing the full matrix with a single row cuts allocations and gives ~57% speedup and removes 99.9% of allocations; renting with ArrayPool makes it allocation‑free; small pointer tweaks add ~9%; SIMD with AVX2 plus a diagonal vector algorithm and optional multi‑threading reaches roughly 7–9× faster and scales to 100k chars (benchmarks and Quickenshtein code on GitHub with BenchmarkDotNet).
AI-written summary · about
chapters (24)
- 0:00Start
- 2:13Calculating the distance
- 3:35The 3 essential elements of Levenshtein Distance
- 3:55Our baseline implementation
- 4:58Time/Space Complexity Hurts!
- 7:41Understanding the algorithm (Part 2)
- 8:59Span-ing Memory
- 9:35The performance of trimming
- 10:20Let's talk branch prediction
- 10:54The performance impact of branches
- 11:17Understanding the algorithm (Part 3)
- 13:56Source character optimization
- 15:30Pointers on all data access
- 16:28Current performance progress
- 16:46Hardware Intrinsics
- 17:16Single Instruction, Multiple Data (SIMD)
- 17:33SIMD: Improving trimming logic
- 19:46SIMD: Data Initialization
- 22:57For even larger strings: Multi-threading
- 24:41Understanding the algorithm (Part 4)
- 26:06SIMD: Main Calculation (Revisited)
- 28:35Having a performance goal
- 28:55Measuring performance changes
- 29:12How you approach the problem
related talks
01h 14mTurbocharged: Writing High-performance C# and .NET code
01h 01mTurbocharged: Writing High-Performance C# and .NET Code
59mWriting (in)efficient C#
56mState of the .NET Performance
47mUnlocking Performance Improvements in .NET
59mHigh-performance code design patterns in C#
01h 04mTurbocharged: Writing High-Performance C# and .NET Code
37mRock Your Code Code and App Performance for Microsoft .Net