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’编码值,直接查表即可(如下代码所示, zend_strlower_ascii的定义),但不管怎么说,这些都需要一个字符一个字符的处理。

static const unsigned char tolower_map[256] = {
0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17, ………………, 0xff
};

#define zend_tolower_ascii(c) (tolower_map[(unsigned char)(c)])

现在来看看我在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

15 Comments

  1. dordle
    dordle May 9, 2023

    I bookmarked your webpage because the articles are superior to those on other similar blogs. Thank you for your wonderful blog!

  2. Bitlife
    Bitlife March 13, 2023

    Are you prepared to play the game BitLife – Life Simulator and experience an interesting virtual life? Before your life is over, start your life over and make the right choices little by little, year by year, until you eventually become a model citizen.

  3. Site
    Site September 9, 2021

    惊人的

  4. impostor
    impostor May 10, 2021

    This code is fast and smart, it can be applied in conjunction with a few more branches when needed.

  5. play solitaire
    play solitaire December 7, 2020

    Thanks for sharing your precious time to create this post, It so informative and the content makes the post more interesting. really appreciated.

  6. David Schmitt
    David Schmitt July 10, 2020

    It’s really a very short and useful code.

  7. Junmin Yang
    Junmin Yang June 22, 2020

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

  8. liligo
    liligo June 19, 2020

    我打算直接拓展glic

Comments are closed.