logo标签列表

C#中SIMD字符串转无符号整数解析的性能优化

c#ssesimdavxsystem.numerics
7

我已经使用.NET中可用的SIMD指令实现了一种解析长度<=8的无符号整数字符串的方法，具体如下：

public unsafe static uint ParseUint(string text)
{
  fixed (char* c = text)
  {
    var parsed = Sse3.LoadDquVector128((byte*) c);
    var shift = (8 - text.Length) * 2;
    var shifted = Sse2.ShiftLeftLogical128BitLane(parsed, 
      (byte) (shift));

    Vector128<byte> digit0 = Vector128.Create((byte) '0');
    var reduced = Sse2.SubtractSaturate(shifted, digit0);

    var shortMult = Vector128.Create(10, 1, 10, 1, 10, 1, 10, 1);
    var collapsed2 = Sse2.MultiplyAddAdjacent(reduced.As<byte, short>(), shortMult);

    var repack = Sse41.PackUnsignedSaturate(collapsed2, collapsed2);
    var intMult = Vector128.Create((short)0, 0, 0, 0, 100, 1, 100, 1);
    var collapsed3 = Sse2.MultiplyAddAdjacent(repack.As<ushort,short>(), intMult);

    var e1 = collapsed3.GetElement(2);
    var e2 = collapsed3.GetElement(3);
    return (uint) (e1 * 10000 + e2);
  }
}

遗憾的是，与基准uint.Parse()进行比较后，以下结果相当不理想：

方法 平均值 误差 标准偏差
基准 15.157 纳秒 0.0325 纳秒 0.0304 纳秒
ParseSimd 3.269 纳秒 0.0115 纳秒 0.0102 纳秒

有哪些方法可以改进上述代码？ 我特别关注的领域包括：

  • 使用涉及text.Length的计算进行SIMD寄存器的位移操作的方式
  • ~~使用涉及矢量0s和1的MultiplyAddAdjacent来解压UTF-16数据~~
  • 使用GetElement()提取元素的方式--也许有一些可以在某处进行ToScalar()调用的地方？
5
你是在说将近五倍的改进结果“相当令人失望”吗？ :-) - Soonts
@500-服务器内部错误，抱歉，已修复。 - Dmitri Nesteruk
基准是 int.Parse() 吗？ - JAlex
@JAlex，这有什么区别吗？ - Dmitri Nesteruk
1
你应该能够使用SSSE3 pmaddubsw 将字节相乘并水平加入到单词（shorts）中。https://www.felixcloutier.com/x86/pmaddubsw。但我认为你的数据是以UTF-16开头的，所以不用考虑了。相关（针对UTF-8 / ASCII）：如何使用SIMD实现atoi？ 检测数字的结尾并相应地进行洗牌，因此与仅有几个数字的标量相比，速度可能会慢得多。 - Peter Cordes
显示剩余6条评论
3个回答
7

我进行了一些优化。

public unsafe uint ParseUint2(string text)
{
    fixed (char* c = text)
    {
        Vector128<ushort> raw = Sse3.LoadDquVector128((ushort*)c);
        raw = Sse2.ShiftLeftLogical128BitLane(raw, (byte)(8 - text.Length << 1));
        Vector128<ushort> digit0 = Vector128.Create('0');
        raw = Sse2.SubtractSaturate(raw, digit0);
        Vector128<short> mul0 = Vector128.Create(10, 1, 10, 1, 10, 1, 10, 1);
        Vector128<int> res = Sse2.MultiplyAddAdjacent(raw.AsInt16(), mul0);
        Vector128<int> mul1 = Vector128.Create(1000000, 10000, 100, 1);
        res = Sse41.MultiplyLow(res, mul1);
        res = Ssse3.HorizontalAdd(res, res);
        res = Ssse3.HorizontalAdd(res, res);
        return (uint)res.GetElement(0);
    }
}

使用vphaddd可以减少类型转换和最终计算的数量，因此速度提高了约10%。

但是...imm8必须是编译时常量。这意味着您不能在imm8作为参数的地方使用变量。否则，JIT编译器不会为该操作生成内部指令。它将在此处进行外部方法调用（也许有一些解决方法）。感谢@PeterCordes的帮助。

与上面的代码相比，无论text.Length如何，这个怪兽都没有显著提高速度。

public unsafe uint ParseUint3(string text)
{
    fixed (char* c = text)
    {
        Vector128<ushort> raw = Sse3.LoadDquVector128((ushort*)c);
        switch (text.Length)
        {
            case 0: raw = Vector128<ushort>.Zero; break;
            case 1: raw = Sse2.ShiftLeftLogical128BitLane(raw, 14); break;
            case 2: raw = Sse2.ShiftLeftLogical128BitLane(raw, 12); break;
            case 3: raw = Sse2.ShiftLeftLogical128BitLane(raw, 10); break;
            case 4: raw = Sse2.ShiftLeftLogical128BitLane(raw, 8); break;
            case 5: raw = Sse2.ShiftLeftLogical128BitLane(raw, 6); break;
            case 6: raw = Sse2.ShiftLeftLogical128BitLane(raw, 4); break;
            case 7: raw = Sse2.ShiftLeftLogical128BitLane(raw, 2); break;
        };
        Vector128<ushort> digit0 = Vector128.Create('0');
        raw = Sse2.SubtractSaturate(raw, digit0);
        Vector128<short> mul0 = Vector128.Create(10, 1, 10, 1, 10, 1, 10, 1);
        Vector128<int> res = Sse2.MultiplyAddAdjacent(raw.AsInt16(), mul0);
        Vector128<int> mul1 = Vector128.Create(1000000, 10000, 100, 1);
        res = Sse41.MultiplyLow(res, mul1);
        res = Ssse3.HorizontalAdd(res, res);
        res = Ssse3.HorizontalAdd(res, res);
        return (uint)res.GetElement(0);
    }
}

再次提到，@PeterCordes不让我写慢代码。下面的版本有两个改进。现在字符串已经加载并移位，然后通过相同的偏移减去移位掩码。这避免了使用变量计数时ShiftLeftLogical128BitLane的缓慢回退。
第二个改进是用pshufd + paddd替换vphaddd。
// Note that this loads up to 14 bytes before the data part of the string.  (Or 16 for an empty string)
// This might or might not make it possible to read from an unmapped page and fault, beware.
public unsafe uint ParseUint4(string text)
{
    const string mask = "\xffff\xffff\xffff\xffff\xffff\xffff\xffff\xffff00000000";
    fixed (char* c = text, m = mask)
    {
        Vector128<ushort> raw = Sse3.LoadDquVector128((ushort*)c - 8 + text.Length);
        Vector128<ushort> mask0 = Sse3.LoadDquVector128((ushort*)m + text.Length);
        raw = Sse2.SubtractSaturate(raw, mask0);
        Vector128<short> mul0 = Vector128.Create(10, 1, 10, 1, 10, 1, 10, 1);
        Vector128<int> res = Sse2.MultiplyAddAdjacent(raw.AsInt16(), mul0);
        Vector128<int> mul1 = Vector128.Create(1000000, 10000, 100, 1);
        res = Sse41.MultiplyLow(res, mul1);
        Vector128<int> shuf = Sse2.Shuffle(res, 0x1b); // 0 1 2 3 => 3 2 1 0
        res = Sse2.Add(shuf, res);
        shuf = Sse2.Shuffle(res, 0x41); // 0 1 2 3 => 1 0 3 2
        res = Sse2.Add(shuf, res);
        return (uint)res.GetElement(0);
    }
}

比初始方案快两倍，至少在我的Haswell i7上是这样。

1
使用vphaddd的方式意味着有更大的优化空间，可以减少2个洗牌操作! [水平SSE向量求和（或其他缩减）的最快方法] (https://dev59.com/g2w05IYBdhLWcg3w11Qk#35270026) - Peter Cordes
1
@PeterCordes “除非C#做了一些奇怪的事情” - 它确实做了。JIT输出中没有内置函数，而是使用了方法“call”。我很惊讶。谢谢你澄清这个对我来说可疑的东西。 :) 我会深入研究并稍后更新答案，谢谢。 - aepot
2
不要使用固定的“digit0”常量，而是从一个大小为0xffff和'0'字节的滑动窗口中加载它。 （我之前写的是0x20，但那是一个错误）。就像在使用未对齐缓冲区进行矢量化：使用VMASKMOVPS：从不对齐计数生成掩码？还是根本不使用该指令中一样，但是您加载了一个用于psubusw的常量，它将使您想要的元素归零（因为当您减去0xffff时，饱和无符号子可以做到这一点） - Peter Cordes
1
@PeterCordes 已经实现了，现在真的很快。非常感谢！ - aepot
1
另一个微小的优化：在饱和减法之后，使用packuswb将数字打包到较低的半部分，然后执行pmaddubsw，接着是pmaddwd，最后进行一次洗牌和加法以进行最终的缩减。当然，如果您想要转换一系列字符串，则可以融合多达四个缩减步骤。 - chtz
显示剩余7条评论
6

C# (thanks @aepot)

public unsafe uint ParseUint(string text)
{
    fixed (char* c = text)
    {
        Vector128<byte> mul1 = Vector128.Create(0x14C814C8, 0x010A0A64, 0, 0).AsByte();
        Vector128<short> mul2 = Vector128.Create(0x00FA61A8, 0x0001000A, 0, 0).AsInt16();
        Vector128<long> shift_amount = Sse2.ConvertScalarToVector128Int32(8 - text.Length << 3).AsInt64();

        Vector128<short> vs = Sse2.LoadVector128((short*)c);
        Vector128<byte> vb = Sse2.PackUnsignedSaturate(vs, vs);
        vb = Sse2.SubtractSaturate(vb, Vector128.Create((byte)'0'));
        vb = Sse2.ShiftLeftLogical(vb.AsInt64(), shift_amount).AsByte();

        Vector128<int> v = Sse2.MultiplyAddAdjacent(Ssse3.MultiplyAddAdjacent(mul1, vb.AsSByte()), mul2);
        v = Sse2.Add(Sse2.Add(v, v), Sse2.Shuffle(v, 1));
        return (uint)v.GetElement(0);
    }
}

使用SSSE3的C语言解决方案：

#include <uchar.h> // char16_t
#include <tmmintrin.h> // pmaddubsw

unsigned ParseUint(char16_t* ptr, size_t len) {
    const __m128i mul1 = _mm_set_epi32(0, 0, 0x010A0A64, 0x14C814C8);
    const __m128i mul2 = _mm_set_epi32(0, 0, 0x0001000A, 0x00FA61A8);
    const __m128i shift_amount = _mm_cvtsi32_si128((8 - len) * 8);

    __m128i v = _mm_loadu_si128((__m128i*)ptr); // unsafe chunking
    v = _mm_packus_epi16(v,v); // convert digits from UTF16-LE to ASCII
    v = _mm_subs_epu8(v, _mm_set1_epi8('0'));
    v = _mm_sll_epi64(v, shift_amount); // shift off non-digit trash

    // convert
    v = _mm_madd_epi16(_mm_maddubs_epi16(mul1, v), mul2);
    v = _mm_add_epi32(_mm_add_epi32(v,v), _mm_shuffle_epi32(v, 1));
    
    return (unsigned)_mm_cvtsi128_si32(v);
}

无论如何调整字符串的位置（参见aepot's anwser），我们都要远离使用pmulld。SSE基本上只支持16位整数乘法，而32位乘法的延迟和操作单元是原来的两倍。然而，需要注意pmaddubsw和pmaddwd的符号扩展行为。

使用标量x64：

// untested && I don't know C#
public unsafe static uint ParseUint(string text)
{
  fixed (char* c = text)
  {
    var xmm = Sse2.LoadVector128((ushort*)c); // unsafe chunking
    var packed = Sse2.PackSignedSaturate(xmm,xmm); // convert digits from UTF16-LE to ASCII
    ulong val = Sse2.X64.ConvertToUInt64(packed); // extract to scalar

    val -= 0x3030303030303030; // subtract '0' from each digit
    val <<= ((8 - text.Length) * 8); // shift off non-digit trash

    // convert
    const ulong mask = 0x000000FF000000FF;
    const ulong mul1 = 0x000F424000000064; // 100 + (1000000ULL << 32)
    const ulong mul2 = 0x0000271000000001; // 1 + (10000ULL << 32)
    val = (val * 10) + (val >> 8);
    val = (((val & mask) * mul1) + (((val >> 16) & mask) * mul2)) >> 32;
    return (uint)val;
  }
}

如果我们事先不知道数字的长度怎么办？

// C pseudocode & assumes ascii text
uint64_t v, m, len;
v = unaligned_load_little_endian_u64(p);
m = v + 0x4646464646464646; // roll '9' to 0x7F
v -= 0x3030303030303030; // unpacked binary coded decimal
m = (m | v) & 0x8080808080808080; // detect first non-digit
m = _tzcnt_u64(m >> 7); // count run of digits
if (((uint8_t)v) > 9) return error_not_a_number;
v <<= 64 - m; // shift off any "trailing" chars that are not digits
p += m >> 3; // consume bytes
v = parse_8_chars(v);

或者，如果我们有一个字符串列表需要处理：

// assumes ascii text
__m256i parse_uint_x4(void* base_addr, __m256i offsets_64x4)
{
    const __m256i x00 = _mm256_setzero_si256();
    const __m256i x0A = _mm256_set1_epi8(0x0A);
    const __m256i x30 = _mm256_set1_epi8(0x30);
    const __m256i x08 = _mm256_and_si256(_mm256_srli_epi32(x30, 1), x0A);
    const __m256i mul1 = _mm256_set1_epi64x(0x010A0A6414C814C8);
    const __m256i mul2 = _mm256_set1_epi64x(0x0001000A00FA61A8);
    __m256i v, m;

    // process 4 strings at once, up to 8 digits in each string...
    // (the 64-bit chunks could be manually loaded using 3 shuffles)
    v = _mm256_i64gather_epi64((long long*)base_addr, offsets_64x4, 1);

    // rebase digits from 0x30..0x39 to 0x00..0x09
    v = _mm256_xor_si256(v, x30);

    // range check
    // (unsigned gte compare)
    v = _mm256_min_epu8(v, x0A);
    m = _mm256_cmpeq_epi8(x0A, v);

    // mask of lowest non-digit and above
    m = _mm256_or_si256(m, _mm256_sub_epi64(x00, m));

    // align the end of the digit-string to the top of the u64 lane
    // (shift off masked bytes and insert leading zeros)
    m = _mm256_sad_epu8(_mm256_and_si256(m, x08), x00);
    v = _mm256_sllv_epi64(v, m);
    
    // convert to binary
    // (the `add(v,v)` allow us to keep `mul2` unsigned)
    v = _mm256_madd_epi16(_mm256_maddubs_epi16(mul1, v), mul2);
    v = _mm256_add_epi32(_mm256_shuffle_epi32(v, 0x31), _mm256_add_epi32(v,v)); 

    // zero the hi-dwords of each qword
    v = _mm256_blend_epi32(v, x00, 0xAA);

    return v;
}
我已经添加了针对SSSE3的C#翻译。最快的解决方案。 - aepot
1
我认为你不需要将这个社区变成维基页面；在低流量的汇编/SIMD标签中获得声望已经很困难了，你应该因为自己撰写和编辑答案而获得荣誉。虽然现在已经无法撤销，但是在未来，除非你想放弃回答并且不对其未来内容负责，否则不要觉得有必要这样做。 - Peter Cordes
有趣的事实：在Haswell（例如Sandybridge）之前，pmulld曾经是单uop，在Intel上使用。对于AVX2，Intel改为仅共享一个（或在SKL中共享两个）FMA单元的尾数乘法器（每个32位元素仅宽24位），因为拥有特殊的32位整数乘法硬件对于更宽的向量来说变得昂贵。（16位整数在DSP方面更常见且更便宜。） - Peter Cordes
这里有非常有趣的想法。如果我想检查一个字符串是否包含8个连续数字，然后计算结果（或返回false），该怎么办？ - Carl Verret
@CarlVerret，我在答案中添加了一些提示。 - aqrit
显示剩余7条评论
3

首先，五倍的提升并不是“相当令人失望”的。

我不会使用标量代码完成最后一步，这里有一个替代方案：

// _mm_shuffle_epi32( x, _MM_SHUFFLE( 3, 3, 2, 2 ) )
collapsed3 = Sse2.Shuffle( collapsed3, 0xFA );
// _mm_mul_epu32
var collapsed4 = Sse2.Multiply( collapsed3.As<int, uint>(), Vector128.Create( 10000u, 0, 1, 0 ) ).As<ulong, uint>();
// _mm_add_epi32( x, _mm_srli_si128( x, 8 ) )
collapsed4 = Sse2.Add( collapsed4, Sse2.ShiftRightLogical128BitLane( collapsed4, 8 ) );
return collapsed4.GetElement( 0 );

C++ 版本会比我的 PC 上的 .NET Core 3.1 更快。生成的代码不够优秀，它们像这样初始化常量：
00007FFAD10B11B6  xor         ecx,ecx  
00007FFAD10B11B8  mov         dword ptr [rsp+20h],ecx  
00007FFAD10B11BC  mov         dword ptr [rsp+28h],64h  
00007FFAD10B11C4  mov         dword ptr [rsp+30h],1  
00007FFAD10B11CC  mov         dword ptr [rsp+38h],64h  
00007FFAD10B11D4  mov         dword ptr [rsp+40h],1

他们使用栈内存代替另一个向量寄存器。看起来JIT开发人员忘记了那里有16个向量寄存器，完整的函数只使用xmm0。

00007FFAD10B1230  vmovapd     xmmword ptr [rbp-0C0h],xmm0  
00007FFAD10B1238  vmovapd     xmm0,xmmword ptr [rbp-0C0h]  
00007FFAD10B1240  vpsrldq     xmm0,xmm0,8  
00007FFAD10B1245  vpaddd      xmm0,xmm0,xmmword ptr [rbp-0C0h]
这并没有提升性能。 - Dmitri Nesteruk
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接