Quickenshtein

Quickenshtein's performance characteristics vary based on the string content and length. The library includes specific benchmarks to evaluate how different scenarios affect calculation speed:

• Edge Difference: Tests the fastest internal path by using strings of equal length that match at the edges but contain only matching characters elsewhere, minimizing operations.
• Text Length: Evaluates the impact of string length (e.g., 5, 20, or 40 characters) in worst-case scenarios where no characters match.
• Huge Text: Tests the limits of the calculator using extremely long strings (e.g., 8,192 or 32,768 characters) in worst-case scenarios.
• Edge Match/Empty Text: (Details in subsequent segments) Scenarios involving matching edges or empty strings.

When processing extremely large strings (e.g., 32,768 characters), Quickenshtein provides two primary modes that impact performance and resource usage:

• Quickenshtein_NoThreading: Executes the calculation on a single thread. This is useful for minimizing overhead in environments where multi-threading is not beneficial or available.
• Quickenshtein_WithThreading: Utilizes multi-threading to accelerate calculations for large inputs. For very large strings (32,768 chars), the threaded version significantly outperforms the non-threaded version in terms of execution time (e.g., ~286ms vs ~295ms on .NET Core 5.0, and ~436ms vs ~1,293ms on .NET 4.7.2).

Note that Quickenshtein_WithThreading may involve different allocation patterns compared to the non-threaded version.

Quickenshtein's performance is heavily dependent on the availability of hardware intrinsics (SIMD instructions like AVX2 and SSE41).

Based on benchmarks, using the version of the library that utilizes 'All Intrinsics' on .NET Core provides significantly higher throughput and lower latency compared to environments where these features are disabled or unavailable:

• With All Intrinsics: ~17.31 ms (Fastest)
• Without AVX2: ~28.94 ms
• Without SSE41 or Hardware Intrinsics: ~100 ms (Slowest)
• Standard .NET Framework: ~100.77 ms

To ensure maximum performance, ensure your runtime environment supports and has enabled AVX2 and SSE41.

Quickenshtein achieves high performance using hardware intrinsics. To get the best results, use .NET Core 3 or higher.

On modern x86 systems, the library leverages:

• SSE2
• SSE4.1
• AVX2

If these intrinsics are unavailable, the library will fall back to a slower implementation that still functions correctly.

For very large strings (typically 8,000 characters or more), you can enable multi-threading to distribute the calculation across multiple CPU cores.

Note: Unlike single-threaded mode, multi-threading is not allocation-free and will allocate a small amount of memory depending on the number of threads used. Multi-threading is particularly beneficial on .NET Framework or systems without hardware intrinsics (SSE2, SSE4.1, AVX2).

using Quickenshtein;

// Enable threading using the default threaded options
var distance2 = Levenshtein.GetDistance("Saturday", "Sunday", CalculationOptions.DefaultWithThreading);

Use the Levenshtein.GetDistance method to calculate the edit distance between two strings. By default, the library uses single-threaded mode, which is allocation-free and optimal for small to medium-sized strings.

To use the library, ensure you have the Quickenshtein namespace imported.

using Quickenshtein;

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

You can fine-tune performance by providing a custom CalculationOptions object to Levenshtein.GetDistance. This allows you to control when threading kicks in and how much work is assigned to each thread. It is recommended to benchmark these settings on your specific hardware and workload.

Available properties in CalculationOptions:

• EnableThreadingAfterXCharacters: The threshold of string length at which threading is enabled.
• MinimumCharactersPerThread: The minimum number of characters required to justify spawning/using a thread.

using Quickenshtein;

// Custom calculation options for tuning
var distance3 = Levenshtein.GetDistance("Saturday", "Sunday", new CalculationOptions {
    EnableThreadingAfterXCharacters = 10000,
    MinimumCharactersPerThread = 25000
});