Press "Enter" to skip to content

使用SSE2指令高效实现strtolower

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

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

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实现:

const __m128i _A = _mm_set1_epi8('A' - 1);
const __m128i Z_ = _mm_set1_epi8('Z' + 1);
const __m128i delta = _mm_set1_epi8('a' - 'A');
do {
	__m128i op = _mm_loadu_si128((__m128i*)p);
	__m128i gt = _mm_cmpgt_epi8(op, _A);
	__m128i lt = _mm_cmplt_epi8(op, Z_);
	__m128i mingle = _mm_and_si128(gt, lt);
	__m128i add = _mm_and_si128(mingle, delta);
	__m128i lower = _mm_add_epi8(op, add);
	_mm_storeu_si128((__m128i *)q, lower);
	p += 16;
	q += 16;
} 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框架中,其实使用了一个稍微更巧妙的改进, 核心的变化在:

const __m128i upper_guard = _mm_set1_epi8('A' + 128);
__m128i in = _mm_loadu_si128((__m128i*)str);
rot = _mm_sub_epi8(in, upper_guard);
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 🙂

附录,关于SSE2的指令集,可以参看Intel intrinsics guide

4 Comments

  1. Junmin Yang
    Junmin Yang June 22, 2020

    有没有Benchmark的结果可以展示一下。

  2. liligo
    liligo June 19, 2020

    我打算直接拓展glic

Leave a Reply

Your email address will not be published. Required fields are marked *