Skip to content

Instantly share code, notes, and snippets.

@Turnerj
Created February 5, 2020 14:40
Show Gist options
  • Save Turnerj/92ef8b18437042c9f15a6b7e932058b7 to your computer and use it in GitHub Desktop.
Save Turnerj/92ef8b18437042c9f15a6b7e932058b7 to your computer and use it in GitHub Desktop.
A really really terrible (but worth while keeping around) version of an AVX Levenshtein calculator
#if NETCOREAPP3_0
using System;
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
namespace Quickenshtein
{
public static partial class Levenshtein
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static unsafe void CalculateDistance_Avx2(char sourcePrevChar, ushort* targetPtr, int targetLength, ref int lastInsertionCost, ref int lastSubstitutionCost, int* previousRowPtr, ref int columnIndex)
{
var sourcePrevCharVector = Vector128.Create(sourcePrevChar);
var negationVector = Vector128.Create((ushort)1);
var allOnesVector128 = Vector128.Create(1);
var allOnesVector256 = Vector256.Create(1);
while (targetLength >= 8)
{
targetLength -= 8;
var targetCharVector = Sse3.LoadDquVector128(targetPtr + columnIndex);
var notEqualVector = Sse2.AndNot(Sse2.CompareEqual(sourcePrevCharVector, targetCharVector), negationVector);
var deletionCostsVector = Avx.LoadDquVector256(previousRowPtr + columnIndex);
var substitutionCostsVector = Avx2.Subtract(deletionCostsVector, allOnesVector256);
substitutionCostsVector = Avx2.Add(Avx2.ConvertToVector256Int32(notEqualVector), substitutionCostsVector);
lastInsertionCost = Sse41.Min(
Sse2.Add(
Sse41.Min(
Vector128.Create(lastInsertionCost, 0, 0, 0),
Vector128.Create(deletionCostsVector.GetElement(0), 0, 0, 0)
),
allOnesVector128
),
Vector128.Create(substitutionCostsVector.GetElement(0), 0, 0, 0)
).GetElement(0);
previousRowPtr[columnIndex++] = lastInsertionCost;
lastInsertionCost = Sse41.Min(
Sse2.Add(
Sse41.Min(
Vector128.Create(lastInsertionCost, 0, 0, 0),
Vector128.Create(deletionCostsVector.GetElement(1), 0, 0, 0)
),
allOnesVector128
),
Vector128.Create(substitutionCostsVector.GetElement(1), 0, 0, 0)
).GetElement(0);
previousRowPtr[columnIndex++] = lastInsertionCost;
lastInsertionCost = Sse41.Min(
Sse2.Add(
Sse41.Min(
Vector128.Create(lastInsertionCost, 0, 0, 0),
Vector128.Create(deletionCostsVector.GetElement(2), 0, 0, 0)
),
allOnesVector128
),
Vector128.Create(substitutionCostsVector.GetElement(2), 0, 0, 0)
).GetElement(0);
previousRowPtr[columnIndex++] = lastInsertionCost;
lastInsertionCost = Sse41.Min(
Sse2.Add(
Sse41.Min(
Vector128.Create(lastInsertionCost, 0, 0, 0),
Vector128.Create(deletionCostsVector.GetElement(3), 0, 0, 0)
),
allOnesVector128
),
Vector128.Create(substitutionCostsVector.GetElement(3), 0, 0, 0)
).GetElement(0);
previousRowPtr[columnIndex++] = lastInsertionCost;
lastInsertionCost = Sse41.Min(
Sse2.Add(
Sse41.Min(
Vector128.Create(lastInsertionCost, 0, 0, 0),
Vector128.Create(deletionCostsVector.GetElement(4), 0, 0, 0)
),
allOnesVector128
),
Vector128.Create(substitutionCostsVector.GetElement(4), 0, 0, 0)
).GetElement(0);
previousRowPtr[columnIndex++] = lastInsertionCost;
lastInsertionCost = Sse41.Min(
Sse2.Add(
Sse41.Min(
Vector128.Create(lastInsertionCost, 0, 0, 0),
Vector128.Create(deletionCostsVector.GetElement(5), 0, 0, 0)
),
allOnesVector128
),
Vector128.Create(substitutionCostsVector.GetElement(5), 0, 0, 0)
).GetElement(0);
previousRowPtr[columnIndex++] = lastInsertionCost;
lastInsertionCost = Sse41.Min(
Sse2.Add(
Sse41.Min(
Vector128.Create(lastInsertionCost, 0, 0, 0),
Vector128.Create(deletionCostsVector.GetElement(6), 0, 0, 0)
),
allOnesVector128
),
Vector128.Create(substitutionCostsVector.GetElement(6), 0, 0, 0)
).GetElement(0);
previousRowPtr[columnIndex++] = lastInsertionCost;
lastInsertionCost = Sse41.Min(
Sse2.Add(
Sse41.Min(
Vector128.Create(lastInsertionCost, 0, 0, 0),
Vector128.Create(deletionCostsVector.GetElement(7), 0, 0, 0)
),
allOnesVector128
),
Vector128.Create(substitutionCostsVector.GetElement(7), 0, 0, 0)
).GetElement(0);
previousRowPtr[columnIndex++] = lastInsertionCost;
lastSubstitutionCost = deletionCostsVector.GetElement(7);
}
}
}
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment