Created
February 5, 2020 14:40
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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