如影随形

影子是一个会撒谎的精灵,它在虚空中流浪和等待被发现之间;在存在与不存在之间....

您现在的位置是:首页>技术文章>详情

使用SSE2指令高效实现strtolower

发布时间:2020-07-27文章类型:转载浏览(6975)




原文地址:https://www.laruence.com/2020/06/16/5916.html

    PHP的类名,函数,方法名是不区分大小写的,也就是说无论你怎么定义函数名,实际上在引擎层面查找的时候都是会统一转换成小写形式来做的。 也就是说strtolower的应用是非常普遍的。

    当然,PHP也做了很多的设计来避免对字符串做过多的字符串小写操作,比如如果我们在PHP代码中写下:

    1. CamelFunc();

    这样的函数调用的时候, PHP会在编译时刻就把CamelFunc全部小写,然后存储在原始字面量之后(PHP-5.4 literals)。

    但不管怎么说,还是不能完全避免对strtolower的调用,比如动态名字的时候。

    所以如果能提升strtolower的性能的话,还是会很有益处的。

    之前我分享过如何用SSE2指令来做字符替换,今天来分享下PHP8中使用SSE2指令来做locale无关的strtolower的较高效实现,strtoupper相对来说也会类似。

    当然,有同学可能会疑问为啥不是SSE4,或者AVX,最根本的原因是SSE2的支持度更广泛,基本上可以说现在的x86架构的CPU没有不支持的。相对来说,不需要考虑太多runtime switch,否则会导致代码变的很复杂,这块大家可以参考我之前给PHP7做的base64 encode/decocde的SIMD优化

    回到正题,我们首先来看看ASCII码表,很容易的能发现:
    a-z和A-Z都是分别连续编码的,a和A的编码值相差32(十进制), 所以其实strtolower如果不考虑locale的话,基本就是:

    • 确定一个字符是大写字母, 因为如果不是大写字母,你给它加32的话,它的意义就变了.
    • 给这个字符加上32, 这个字符就变成了小写形式

    传统的做法是一个字符个字符来判断它是否是大写字母,然后做变换,而在PHP8之前,我们是采用码表实现的,也就是给256 Range的字符都给定一个对应的’lower’编码值,直接查表即可,但不管怎么说,这些都需要一个字符一个字符的处理。

    现在来看看我在PHP8中的SSE2实现:

    1. const __m128i _A = _mm_set1_epi8('A' - 1);
    2. const __m128i Z_ = _mm_set1_epi8('Z' + 1);
    3. const __m128i delta = _mm_set1_epi8('a' - 'A');
    4. do {
    5.      __m128i op = _mm_loadu_si128((__m128i*)p);
    6.      __m128i gt = _mm_cmpgt_epi8(op, _A);
    7.      __m128i lt = _mm_cmplt_epi8(op, Z_);
    8.      __m128i mingle = _mm_and_si128(gt, lt);
    9.      __m128i add = _mm_and_si128(mingle, delta);
    10.      __m128i lower = _mm_add_epi8(op, add);
    11.      _mm_storeu_si128((__m128i *)q, lower);
    12.      p += 16;
    13.      q += 16;
    14. } while (p + 16 <= end);

    结合上面的步骤我们来看看这段代码中几个关键步骤:

    • _mm_loadu_si128: 一次性读取16个字符进入mmx寄存器
    • _mm_cmpgt_epi8: 一条指令检查16个字符串那些的字符值是大于’A’-1的
    • _mm_cmplt_epi8: 一条指令检查16个字符串哪些字符的值是小于’Z’+1的
    • _mm_and_si128: 结合上面俩条的结果,最后的结果中0xff的值的位置就是大写字符
    • _mm_add_epi8: 给所有的0xff位置的字符加上32(0x20), 完成小写转换

    它一次能批量处理16个字符,相比原来要做16次单个字符比较,tolower的处理,性能提升会非常明显。

    不过有一点要注意的,在PHP8中,我们只是针对locale为默认的情况下才会使用这个加速,也就是如果你使用了setlocale设置LC_TYPE为非默认的”C”, 就不会应用这个优化。

    好了,现在看起来我讲完了,文章是不是也应该结束了呢?

    并不是!

    考虑上面的代码,我们有没有办法进一步优化呢?

    我在Yaf框架中,其实使用了一个稍微更巧妙的改进, 核心的变化在:

    1. const __m128i upper_guard = _mm_set1_epi8('A' + 128);
    2. __m128i in = _mm_loadu_si128((__m128i*)str);
    3. rot = _mm_sub_epi8(in, upper_guard);
    4. upper = _mm_cmpgt_epi8(rot, _mm_set1_epi8(-128 + 'Z' - 'A'));

    如上面的代码所示,首先我们把所有读进来的字符,统一减去(减去)’A' + 128,此时如果对于’A’来说,它的值是-128,也就是8位bits最小的值-128.

    此时只要是小于等于-128 + ‘Z’ - ‘A’的字符,就都是大写字符了。

    这段代码取代了原来的需要两次比较合并结果的方法,只需要一次比较,就可以确定哪些字符是大写字符了,后续的逻辑都一样了,给大写字母加上32即可,是不是就比较巧妙了?
    不过,我并没有把这个版本的实现merge到PHP8中,只是在Yaf中应用了,PHP8中还是保留了原来俩次比较的方法,主要的原因还是因为这个方法相对来说理解起来有点困难,性能提升也不明显,为了代码逻辑清晰易懂。

    好了,到这里,本篇文章就真的结束了, byebye 🙂

关键字词:strtolower