用SIMD实现整数序列的解析

2020-05-29 14:50:35

虽然使用SIMD指令将字符串转换为整数值是可行的,但此应用程序是不切实际的。对于典型情况,当解析单个值时,标量过程-如标准的atoi或strtol-比任何花哨的SSE代码都要快。

然而,SIMD程序可以非常快速地并行转换几个数字。只有一个";但";:输入数据必须是规则和有效的,即输入字符串必须只包含ASCII数字。最近,我更新了一篇关于使用基准测试结果进行SSE解析的文章。这些速度确实令人印象深刻,例如,SSSE3解析器比单纯的标量代码快7到9倍。

显而易见的问题是,如何使用这些功能强大的SIMD程序来转换真实数据?我所说的实数是指可能损坏的输入,这些输入包含一系列不同长度的数字,由预定义集合中的字符分隔。

使用SSE指令高效分析和验证此类字符串的方法。有一个特殊的变体,它只处理无符号数字,还有一个功能齐全的有符号数字变体。

本文从无签名转换开始,因为它比签名转换更容易。签名的转换分享了核心思想,只是增加了一些额外的步骤。

正文伴随着BSD许可的软件,其中包括与验证和基准程序一起的全功能实现。

它是一个任意长度的字符串;但它应该很大,比如几千字节或兆字节。

输入包含整数。数字是可选的符号字符';+';或';-';后跟非空的数字序列';0';..';9';。

数字由用户定义的集合中的字符分隔;例如,它可能是逗号和空白字符(空格、换行符等)。

解析器必须能够检查输入的有效性,即缺少无效字符和正确的输入格式(数字至少用一个字符分隔,符号字符只出现在数字的开头)。

对于输入字符串";123;-52,+432424-999;1234568,+879";以及三个分隔符';,';';和';';,预计算法将提取六个整数:[123,-52,432424,-999,1234568,879]。转换数字的顺序必须与输入字符串中的顺序完全相同。

还测试了一个简化的解析器。此解析器仅将所有非数字和非符号字符视为分隔符。

转换算法在循环中工作,在每次迭代中,恰好从内存加载并处理一个输入向量。

根据数字的布局,输入将标准化为SIMD程序所需的格式。在这一步,我们选择:从输入中转换多少个数字,以及哪个SIMD程序适合转换。

由于SIMD程序在矢量中强加了特定的数字布局,因此任意输入必须正确对齐。为此,我们需要识别输入中的数字跨度,并将每个跨度移动到向量的某些子数组上。让我们假设此时输入包含数字或分隔符(用_表示)。

例如,一个数字为1_2_3_4_5_6_的向量必须转换为123456_。然后,SSE过程将所有数字并行转换为数组[1,2,3,4,5,6]。同样,带有两位数的矢量_12__34_必须转换为12345678_,然后结果将是[12,34,56,78]。

让我们考虑一个更复杂的情况,当一个字符串含有不同位数的数字时。有几种方法可以转换INPUT_1_2_34_567_89__:

如果我们选择转换一位数,则只能转换前两个范围-因为我们需要保持输入数字的顺序。标准化后,输入为12_。输入端的Tail_34_567_89__保持不变。

如果我们选择两位数的转换,那么前三个跨度就可以转换。较短的数字用零完成,然后归一化输入为010234_。结果是[1,2,34];此时间位较短的输入的Tail_567_89__保持不变。

最后,如果我们选择四位数的转换,那么四个第一个跨度就可以转换。同样,较短的数字用零完成,标准化输入为0001000200340567。结果是[1,2,34,567],但仍未处理块的尾部,即_89__。

我们可以看到,为了转换给定的跨度组合,我们需要知道:

获取此信息似乎相当复杂,特别是当我们查看最后一个示例时。幸运的是,所有参数都可以预先计算。跨距组合可以保存为位模式,其中1表示数字。例如,从Vector_1_2_34_567_89__,我们得到范围模式0b0101011011101100=0x56ec.范围模式用于从预计算阵列获取记录。记录包含以下字段:

Shuffle_digits-16字节数组,它是指令_mm_Shuffle_ep8(PShufb)的参数;指令在某些位置移动字节;

CONVERSION_ROUTINE-选择SSE转换过程的枚举;例如,它告诉您置乱的输入是一个由两位数组成的数组;

ELEMENT_COUNT-SSE转换过程中必须存储在输出集合中的元素数。

具有预计算阵列的解决方案仅适用于SSE,因为跨度模式具有16位。在向量较宽的AVX2和AVX512的情况下,这样的表会简单地太大,分别为232个或264个条目。此外,AVX2版本的pshfb指令适用于通道,即矢量的128位半部分,因此不可能对所有输入进行混洗。

但是AVX2和AVX512指令仍然可以用于算法的某些部分,特别是在输入验证中。

要构建整个预计算表,必须处理所有65536个跨度模式。处理图案包括以下步骤:

确定数字跨度。对于Pattern_ddd_d__ddd_dd_we,有四个跨度[(1,3),(6,6),(9,11),(14,15)]。但是对于模式_dddd_ddd,只有一个跨度[(4,7)]。矢量末端的跨度可能会在下一块中继续,我们不知道如何转换它。然而,我们可以假设从向量开始的跨度是一个新的数字,并且包括在跨度的列表中。

找到跨度的最佳转换方案。我们系统地检查哪些SSE转换是可能的,即一位/两位/四位/八位,以及每个转换可以处理多少个跨度-选择处理项目最多的程序。此步骤的输出是以下记录字段的值:TOTAL_SKIP-处理了多少个输入字节;对于Pattern_dddd_,我们知道处理了整个输入(Total_Skip=16);对于Pattern_d_ddd_d,我们只处理索引5处的第一个跨度,但是我们知道跨度之后的四个非数字字符也可以跳过,因此Total_Skip是9。

构建洗牌模式。有了元素大小和跨度位置后,就构建了向量Shuffle_digits。跨距中的字符映射到向量中的适当子数组上。在该步骤中还完成了零补全,因为指令pshfb或者从输入向量复制给定的字节,或者如果索引已经设置了最高有效位,则将其置零。

让我们考虑span pattern_ddd__d__ddd_dd_。可以使用四位转换进行转换,因此归一化向量的布局应为:

[a0|a1|a2|a3|b0|b1|b2|b3|c0|c1|c2|c3|d0|d1|d2|d3]。

向量中有四个数字a、b、c和d;请注意,第0索引处的字节保存最高有效数字。

模式中的第一个数字有三位数,分别位于索引1、2和3,表示a1=1、a2=2、a3=3;a0的值应为零,因此a0=0x80。

第二个数字在索引6处只有一个数字,因此b3=6,由于其余数字必须为零,因此b0=b1=b2=0x80。

第三个数字的索引为9、10、11,因此c1=9,c2=10,c3=11,c0=0x80。

最后一个数字,即第四个数字,在索引14和15处有两位数,因此d2=14,d3=15,其余必须为零,所以d0=d1=0x80。

[80|1|2|3|80|80|80|6|80|9|10|11|80|80|14|15]。

//t0=[';0';..';9]中的input[i]?0xff:0x00 const__m128i t0=decimal_digits_ask(Input);const uint16_t span_ask=_mm_movemask_ep8(T0);

然后,将混洗后的向量发布到适当的转换例程。block kinfo结构保存转换类型(CONVERSION_ROUTINE)和从SSE结果中获得的项目数(ELEMENT_COUNT)。使用SSE转换程序并不总是可行的,因此需要一个标量代码来处理奇怪的情况。

如果(b.。CONVERSION_ROUTINE==CONVERSION::SSE1 Digit){CONVERT_1 Digit(无序排列,b.。ELEMENT_COUNT,OUTPUT);}ELSE IF(b.。CONVERSION_ROUTINE==CONVERSION::SSE2 Digits){CONVERT_2 Digits(无序排列,b.。ELEMENT_COUNT,OUTPUT);}ELSE IF(b.。CONVERSION_ROUTE==CONVERSION::SSE4 Digits){CONVERT_4 Digits(无序排列,b.。ELEMENT_COUNT,OUTPUT);}ELSE IF(b.。CONVERSION_ROUTE==CONVERSION::SSE8 Digits){CONVERT_8 Digits(无序排列,b.。ELEMENT_COUNT,OUTPUT);}ELSE{//不支持大小写,此处调用标量代码}。

在实践中,我们需要两个掩码:一个是数字位置,另一个是分隔符位置。如果Or&#ed掩码包含一些零元素,则表示存在无效字符。以下是一个架构:

const__m128i bytemask_digit=DECIMAL_DIGITS_MASK(输入);const__m128i bytemask_Sep=匹配器。get_ask(输入);const__m128i bytemask_valid=_mm_or_si128(bytemask_digit,bytemask_Sep);const uint16_t Valid_Mask=_mm_movemask_ep8(Bytemask_Valid);IF(Valid_Mask!=0xffff){Throw std::logic_error(";error input";);}。

最通用的SSE实现在时间上与分隔符集合的大小成正比。将集合中的每个字符广播到矢量中,然后与输入矢量进行比较。得到的字节掩码与前一个结果相同。

__m128i get_ask(const__m128i&;input,const__m128i&;initial)const{__m128i result=initial;for(size_t i=0;i<;n+1;i++){const__m128i ask=_mm_cmpeq_ep8(字母[i],input);result=_mm_or_si128(result,ask);}返回结果;

如果分隔符集合在编译时是已知的,则编译器可以展开循环。

SSE4.2中的SNTI指令pcmpestrm(_Mm_Cmpestrm)也可用于相同的情况。该指令有两个参数。一个是输入向量,另一个解释为一组单独的字符(最多16个)或字符范围(最多8个)。结果是与集合(或范围)匹配的输入字符的掩码。在下面的示例中,使用了集合变量。

__m128i get_ask(const__m128i&;input,const__m128i&;initial){const uint8_t mode=_SIDD_UBYTE_OPS|_SID_CMP_EQUAL_ANY|_SID_UNIT_MASK;return_mm_or_si128(Initial,_mm_cmpestrm(set,set_size,input,16,mode));}。

处理输入向量中的所有数字是不可能的,有时甚至是不可能的。在单个迭代中,转换1到16个字节。下表显示了详细信息--一个重要的结论是,几乎95%的模式处理至少一半的输入向量。

但是,输入验证总是针对整个向量进行的,全部为16个字节。这个问题可能会被克服,请参见处理更大的输入。

上交所的单位没有得到充分利用。最长的一位数字序列是";1;2;3;4;5;6;7;8;";。它包含8个数字,而SSE过程能够处理16个数字。同样,最长的两位数字序列是";12;34;56;78;98;;";。它有5个数字,但是SSE过程能够转换8个数字。同样,最长的四位数字序列是";1234;5678;9123;;";-它有三个四位数字,SSE过程可以转换四个数字。

与无符号转换类似,有符号转换也需要Aspan模式。但在这种情况下,图案中还包括符号字符';+';和';-';。对于此示例字符串:

混洗跨越到正确的向量元素上-这与无符号转换中的情况完全相同。

输入=[';_';|';-';|';1';|';2';|';3';|';_';|';+';|';4';|';5';|';_';|';-';|';6&##。_';|';7';|';8';|';_';]。

随机洗牌=[';-';';1';';2';';3';|0x00';+';';4';';5';|0x00 0x00';-';';';6';|0x00 0x00';7';';8&#

随机标记=[';-';';-';';|';+';';+';';+';';+';|';-';';-';';-';';-';|&##。7';';7';';7';';7';]。

Shuffled_Signs向量不一定只包含';+';或';-';,它可能还包含数字,但这不是错误。

从混洗后的矢量中删除符号字符,并将ASCII字符转换为值:

[0 1 2 3|0 0 4 5|0 0 0 6|0 0 7 8]。

因此,我们最终得到一个无符号数字向量,这样的输入可以通过已经定义的SSE过程进行转换:

最后,取消适当的元素;我们使用一个众所周知的等式(~x+1),它在SSE代码中表示为(xxor(-1)-(-1))。值-1是通过将SHUFFLED_SIGNES与';-';进行比较而获得的:

Negated_MASK=(Shuffled_Signs==PACKED_BYTE(';-';))[ff|00 00 00|ff|00 00 00]。

由于指令_mm_subs_epu8(Psubusb)用于从ASCII色调数值进行转换,因此对混洗矢量中的符号字符进行掩蔽是免费的,因为指令_mm_subs_epu8(Psubusb)用于从ASCII色调数值转换:

该指令执行饱和减法,即计算max(0,a-b)。由于';-';和';+';的ASCII代码分别为43和45,而';0';的ASCII代码为48,因此对于两个符号字符,该表达式的结果均为零。

字符';+';和';-';只能出现在数字范围的开头,即我们想要拒绝像";++12";或";1234-,";这样的输入。

第一阶段类似于无符号转换,即将所有掩码“或”编辑在一起,然后将零个元素指向无效字符。

第二阶段检查符号字符是否放置正确。对于每个跨度组合,我们需要预先计算有效符号位置的掩码。然后,在或盖上面具之后,我们只需验证它们是否放置在有效位置即可。(#39;-#39;-#39;-#39;-#39;-#39;-#39;-#39;我们只需验证它们是否放置在有效位置即可。

在实践中,由于验证只需要简单AND,所以预计算数据具有用于无效符号位置的位掩码。下面的代码片段显示了第二步的架构。

const__m128i ascii_minus=_mm_set1_ep8(';-';);const__m128i ascii_plus=_mm_set1_ep8(';+';);//.。const__m128i bytemask_plus=_mm_cmpeq_ep8(input,ascii_plus);const__m128i bytemask_minus=_mm_cmpeq_ep8(input,ascii_minus);const_m128i bytemask_sign=_mm_or_si128(bytemask_plus,bytemask_minus);//.。const uint16_t sign_ask=_mm_movemask_ep8(Bytemask_Sign);const uint16_t span_ask=_mm_movemask_ep8(Bytemask_Span);const块信息&;bi=块[span_ask];if(sign_ask&;bi。INVALID_SIGN_MASK){在无效位置抛出std::run_error(";';+';或';-';);}。

AVX512VBMI定义了功能强大的指令_mm512_permutex2var_ep8(Vperm2b),它使用ZMM寄存器每个字节的最低7位作为索引,在128字节表中进行查找。内部函数的调用很奇怪:

const__m512i lookup_lo=.//元素0..63const__m512i lookup_hi=.//和64..127转换的查找const__m512i=_mm512_permutex2var_ep8(lookup_lo,input,lookup_hi);

如果有效字符集适合标准ASCII字符集,即仅设置了最低7位,则验证步骤可能会快速拒绝扩展ASCII(第7位集),然后使用_mm512_permutex2var_ep8的单个调用转换输入。当允许完整的8位输入时,则必须使用256字节查找的两个部分调用指令两次。

此指令的一次(或两次)调用允许将所有64个输入字节一次分类为所需的类别:

类别编码为某个位置的位,在示例实现中使用以下模式:

范围模式由指令_mm512_movep8_ask(Vpmovb2m)从最高有效位获得;其工作方式与SSE中的pmovmaskb完全相同。符号模式由指令_mm512_test_ep8_ask(Vptestmb)通过测试位7(掩码0x40)获得。

const__m512i class=_mm512_permutex2var_ep8(class_lo,input,class_hi);if(_mm512_test_ep8_ask(class,class)!=uint64_t(-1)){掷出std::logic_error(";无效字符";);}uint64_t span_mask64=_mm512_movep8_ask(Class);uint64_t sign_mask64=_mm512_test_ep8_ask(class,_mm512_set1_ep8(int8_t(0x40);

const__m128i ascii_minus=_mm_set1_ep8(';-';);const__m128i ascii_plus=_mm_set1_ep8(';+';);//.。const__m128i bytemask_plus=_mm_cmpeq_ep8(input,ascii_plus);const__m128i bytemask_minus=_mm_cmpeq_ep8(input,ascii_minus);const_m128i bytemask_sign=_mm_or_si128(bytemask_plus,bytemask_minus);const__m128i bytemask_digit=。const uint16_t span_ask=_mm_movemask_ep8(Bytemask_Span);const块信息&;bi=块信息[span_ask];

const uint16_t sign_ask=_mm_movemask_ep8(Bytemask_Sign);if(sign_ask&;bi.。INVALID_SIGN_MASK){在无效位置抛出std::run_error(";';+';或';-';);}。

const__m128i ascii_minus=_mm_set1_ep8(';-';);const__m128i随机数字=_mm_loadu_si128((const__m128i*)bi。洗牌数字);const__m128i Shuffle_Signs=_mm_loadu_si128((const__m128i*)bi.。Shuffle_Signs);const__m128i Shuffled=_mm_Shuffle_EP8(输入,Shuffle_digits);const__m128i Shuffled_Signs=_mm_Shuffle_EP8(输入,Shuffle_Signs);const__m128i Negate_MASK=_mm_cmpeq_ep8(Shuffled_Signs,ascii_minus);

如果(bi.。CONVERSION_ROUTE==CONVERSION::SSE1Digit){CONVERT_1digit(无序排列,双。ELEMENT_COUNT,OUTPUT);}ELSE IF(bi.。CONVERSION_ROUTINE==CONVERSION::SSE2 Digits){CONVERT_2 DIGNITS_SIGNED(无序排列,否定掩码,双。ELEMENT_COUNT,OUTPUT);}ELSE IF(bi.。CONVERSION_ROUTE==CONVERSION::SSE4 Digits){CONVERT_4 DIGNITS_SIGNED(Shuffled,Negate_MASK,bi.。ELEMENT_COUNT,OUTPUT);}ELSE IF(bi.。CONVERSION_ROUTE==CONVERSION::SSE8 Digits){CONVERT_8 DIGNITS_SIGNED(无序排列,否定掩码,双。ELEMENT_COUNT,OUTPUT);}Else{//标量转换}。

正如警告部分所述,算法的单个步骤验证整个输入向量,但很少转换来自输入的所有字节。尽管检测数字和符号字符可能被认为是很便宜的,但我们看到针对任意一组分隔符进行验证可能真的很耗时。

..