An Efficient strtolower with SSE2中文EN

Class, function and method names in PHP are case-insensitive: however you spell a function name, the engine lowercases it before every lookup. That makes strtolower extremely common.

PHP does a lot of design work to avoid lowercasing strings over and over — for instance, when you write:

CamelFunc();

the compiler lowercases CamelFunc once at compile time and stores it alongside the original literal (PHP 5.4 literals).

Still, calls to strtolower can't be avoided entirely — dynamic names, for one.

So making strtolower faster pays off broadly.

I previously shared how to do character replacement with SSE2; today it's PHP 8's efficient, locale-independent strtolower built on SSE2. strtoupper works much the same way.

You might wonder why not SSE4 or AVX. The fundamental reason is reach: SSE2 is supported by essentially every x86 CPU in existence. That means little to no runtime dispatch — otherwise the code gets messy fast. For what runtime switching does look like, see the SIMD base64 encode/decode I did for PHP 7.

Back to the point. Look at the ASCII table and you'll quickly notice:
a–z and A–Z are each encoded contiguously, and 'a' sits exactly 32 (decimal) above 'A'. So, ignoring locale, strtolower is basically:

• Decide whether a character is an uppercase letter — because adding 32 to anything else changes its meaning entirely.
• Add 32 to it, and it becomes lowercase.

The traditional approach checks and converts one character at a time. Before PHP 8 we used a lookup table: all 256 byte values mapped to their 'lower' equivalents, one table lookup per character (see the definition of zend_strlower_ascii below). Either way, it's strictly one character at a time.

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)])

Now my SSE2 implementation in PHP 8:

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);

The key steps, following the logic above:

• _mm_loadu_si128: load 16 characters into an XMM register in one go
• _mm_cmpgt_epi8: one instruction checks which of the 16 bytes are greater than 'A'-1
• _mm_cmplt_epi8: one instruction checks which are less than 'Z'+1
• _mm_and_si128: AND the two results — positions holding 0xff are exactly the uppercase letters
• _mm_add_epi8: add 32 (0x20) at every 0xff position, completing the conversion

It processes 16 characters per batch. Compare that with 16 rounds of single-character comparison and table lookup, and the speedup is substantial.

One caveat: in PHP 8 this fast path only applies under the default locale. If you call setlocale to change LC_CTYPE away from "C", the optimization is not used.

All right, that sounds like a wrap — should the post end here?

Nope!

Look at the code above again: can we squeeze it further?

In the Yaf framework I actually used a cleverer twist. The core change:

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'));

As shown above: first subtract 'A' + 128 from every loaded byte (with wrapping). For 'A' itself the result is -128 — the minimum value of a signed 8-bit integer.

Now any byte that compares ≤ -128 + 'Z' - 'A' must be an uppercase letter.

This replaces the two-compare-then-AND sequence with a single comparison to identify uppercase characters; the rest is unchanged — add 32 to the uppercase ones. Rather neat, isn't it?

I never merged this version into PHP 8, though; it only lives in Yaf. PHP 8 keeps the two-comparison form, mainly because the rotate trick is harder to grasp and the extra speedup is marginal — clarity of logic won.

Now the post really is over. Bye-bye 🙂

Appendix: for the SSE2 instruction set, see the Intel intrinsics guide