Awesome

Quickenshtein

A quick and memory efficient Levenshtein Distance calculator for .NET

Performance

Quickenshtein gets its speed and memory efficiency from a number of different optimizations. To get the most performance out of the library, you will need .NET Core 3 or higher as this has support for hardware intrinsics.

Quickenshtein takes advantage of the following hardware intrinsics. On any recent x86 system, you will likely have these available.

• SSE2
• SSE4.1
• AVX2

If your computer doesn't have one of the hardware intrinsics available, Quickenshtein will still work - just slower than optimal.

Multi-Threading

By default, Quickenshtein performs in single-threaded mode as this mode performs best for small to medium size strings while having no memory allocations. When dealing with huge strings of 8000 characters or more, it may be useful to switch to multi-threaded mode. In this mode, the calculation is broken up and shared between multiple cores in a system.

Multi-threading is especially useful for systems without hardware intrinsics or for .NET Framework as shown in the table below where it provided a 3x performance improvement.

To enable threading, you can pass in CalculationOptions.DefaultWithThreading to Levenshtein.GetDistance() or configure your own CalculationOptions with settings that work best for you.

Note: Multi-threading is not allocation free (unlike single-threading mode) and will allocate a small amount depending on the number of threads used.

Benchmarking

There are a number of benchmarks in the repository that you can run on your system to see how well Quickenshtein performs.

Most of these benchmarks...

• Run .NET Framework and .NET Core so you can see how the performance changes between them
• Compare against a simple baseline Levenshtein Distance implementation with no specific optimizations
• Compare against Fastenshtein, one of the other fast .NET Levenshtein Distance implementations

You can view results to these benchmarks at the links below:

• Benchmarking against Fastenshtein
• Isolated Benchmarks
• Intrinsics Performance

Example Usage

using Quickenshtein;

// Common usage (uses default CalculationOptions with threading disabled)
var distance1 = Levenshtein.GetDistance("Saturday", "Sunday");

// Enable threading
var distance2 = Levenshtein.GetDistance("Saturday", "Sunday", CalculationOptions.DefaultWithThreading);

// Custom calculation options (helps with tuning for your specific workload and environment - you should benchmark your configurations on your system)
var distance3 = Levenshtein.GetDistance("Saturday", "Sunday", new CalculationOptions {
    EnableThreadingAfterXCharacters = 10000,
    MinimumCharactersPerThread = 25000
});

Learning Resources

I've written quite a bit about Levenshtein Distance and various ways you can extract performance from it:

• Levenshtein Distance Part 1: What is it?
• Levenshtein Distance Part 2: Gotta Go Fast
• Levenshtein Distance Part 3: Optimize Everything!
• Levenshtein Distance with SIMD

If you prefer video:

• Maximising Algorithm Performance in .NET: Levenshtein Distance at .NET Conf 2020