4
\$\begingroup\$

I want to optimize the following code:

#ifdef USE_SSE
#define STRING_PREFETCH_TBL(ptr)            \
        _mm_prefetch(ptr, _MM_HINT_T0);     \
        _mm_prefetch(ptr+64, _MM_HINT_T0);  \
        _mm_prefetch(ptr+128, _MM_HINT_T0); \
        _mm_prefetch(ptr+192, _MM_HINT_T0)
#else

#define STRING_PREFETCH_TBL(ptr)
#endif


__declspec(align(128)) const char TblToLower[] = 
{
    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,
    35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,97,98,
    99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,91,
    92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,
    119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
    144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,
    170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,
    197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,
    225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,

};

void StrToLowerCase( const char* src, char* dst )
{
    STRING_PREFETCH_TBL(TblToLower);

    while(*src)
    {
        *dst = TblToLower[*src];
        dst++;
        src++;
    }
    *dst = '\0';
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Note that your StrToLowerCase function is not Unicode-enabled, and it only handles English letters. \$\endgroup\$ – Frerich Raabe Sep 10 '13 at 9:59
  • \$\begingroup\$ Have you measured this against the standard C provided ::tolower()? \$\endgroup\$ – Martin York Sep 10 '13 at 17:24
  • 2
    \$\begingroup\$ PS. This is a C question. Nothing about this kind of code is C++ like. \$\endgroup\$ – Martin York Sep 10 '13 at 17:26
  • 1
    \$\begingroup\$ For ASCII you only need 0 .. 127. \$\endgroup\$ – MrSmith42 Oct 10 '13 at 10:39
  • 4
    \$\begingroup\$ Have you tried profiling it against an implementation like char c=*src++; *dst++ = (92>c && 64<c)? c|32 :c which is more complicated, but fits in any cpu-cache and does not need to load an array from the ram or access it there? \$\endgroup\$ – MrSmith42 Oct 10 '13 at 10:48
7
\$\begingroup\$

As far as optimizing the tolower logic itself for a single ASCII character, your table is about as fast as it gets.

Alternatives would be:
A) the standard tolower function
B) this bit trick if you have only ASCII alpha characters

(unsigned char)((c) | (unsigned char)0x20) 

C) this bit trick for all ASCII characters

// set the most significant bit in value X if greater than or equal to 'A'
// set the most significant bit in value Y if less than or equal to 'Z'
// bitwise AND X and Y to determine if both are true and mask out all other bits
// shift the set bit into the 0x20 place and bitwise OR in the bit
(unsigned char)(((((unsigned char)0x40 - (c)) & ((c) - (unsigned char)0x5b) & (unsigned char)0x80) >> 2) | (c))

I ran 300 iterations on a pre-generated random string of one-billion bytes (including the null terminator) of some x64 code under full optimization and no debugger attached from Visual Studio 2013.

  • your table lookup took about 22.4 seconds
  • alternative A took about 106.0 seconds (the call was not inlined)
  • alternative B took about 15.1 seconds (but it only works for strings only containing letters)
  • alternative C took about 31.9 seconds (so the table beats the bit tricks)

For whatever it's worth, replacing the tolower logic with a NOP and simply copying the source string took 15.0 seconds, so that's what's being spent in loop overhead.

But no matter, your real opportunity for optimization here is in vectorization and parallelization.

However this cannot happen as the signature and contract to the StrToLowerCase function exists now. This is for two reasons:

  1. Any vectorized instructions will need to access data in larger chunks than one byte, and reading (and writing) past the null is bad if you don't know the arrays are padded out the appropriate amount.
  2. You don't know the length of the string without doing a byte-by-byte scan for the null terminator. So you can't break the string into chunks easily and spin off threads to process separate chunks, and you're going to have to check for the null terminator in the middle of vectorized code (if you go that route), and you will lose much of if not all of what you gain.

So, for the sake of moving forward. Let's assume our signature now looks like this:
void StrToLowerCase(const char *src, char *dst, unsigned len)
where for the sake simplicity, len is however many chunks of data the function must process whatever its size may be for the given implementation.

Lets explore vectorized approaches:

If you have a processor that supports AVX2 instructions, then you can use the VGATHERDPS instruction which performs 8 vectorized lookups. However I don't have this instruction so I couldn't try it out. In fact few CPUs will since it first showed up in 2013. So moving on...

Almost everyone has SSE2 now days, and luckily the above bit trick can be vectorized with SSE2. Here is an implementation that operates on 128-bit chunks:

__forceinline void StrToLowerCaseSSE2(const char *src, char *dst, unsigned len)
{
   __m128i const *src128 = (__m128i const*)src;
   __m128i       *dst128 = (__m128i*)dst;
   while (len--)
   {
      __m128i const c16  = _mm_load_si128(src128++);
      __m128i const abv  = _mm_sub_epi8(_mm_set_epi32(0x40404040, 0x40404040, 0x40404040, 0x40404040), c16);
      __m128i const blw  = _mm_sub_epi8(c16, _mm_set_epi32(0x5B5B5B5B, 0x5B5B5B5B, 0x5B5B5B5B, 0x5B5B5B5B));
      __m128i       msk  = _mm_and_si128(abv, blw);
      msk                = _mm_and_si128(msk, _mm_set_epi32(0x80808080, 0x80808080, 0x80808080, 0x80808080));
      msk                = _mm_srli_epi16(msk, 2);
      msk                = _mm_or_si128(msk, c16);
      _mm_store_si128(dst128++, msk);
   }
}

The above SSE2 implementation finishes the test in just 5.3 seconds, roughly 4.5 times faster than the table lookup code that was previously that fastest. However, keep in mind some of this is in the loop overhead we eliminated by effectively unrolling the loop 16 times (each iteration of the SSE2 loop lower-cases 16 ASCII chars). If we unroll the loop 16 times for the lookup code, it finishes in 15.3 seconds. So loop overhead aside, the SSE2 implementation is about 3 times faster. Furthermore, if we employee the alpha-character only tolower in the unrolled loop it finishes in 8.9 seconds, and the SSE2 code that handles non-alpha ASCII characters as well as extended ASCII (codes greater than 127) is still faster.

The SSE2 implementation will be the fastest presented here, but lets say you don't want to use SSE2, you have 64-bit support, and you only have standard ASCII in the range [0, 127] and not extended ASCII in the range [0, 255] (the most significant bit is always zero). In that case you can use a 64-bit vectorized approach that hijacks the 64-valued bit in the same way the above bit trick operations hijack the 128-valued bit. The subtractions can be done on 8 characters shoved into a 64-bit integer, but the trick will be ensuring carries and borrows don't escape the byte you're working in. This can be done by keeping in mind the 128-valued bit in every byte will be zero. Here is the 64-bit implementation where len is the number of 64-bit chunks:

 __forceinline void StrToLowerCase64(const char *src, char *dst, unsigned len)
{
   unsigned const __int64 *src64 = (unsigned const __int64 *)src;
   unsigned       __int64 *dst64 = (unsigned __int64 *)dst;
   while (len--)
   {
      unsigned const __int64 x = *src64++;
      *dst64++ = (((0xC0C0C0C0C0C0C0C0 - x) & (x + 0x2525252525252525) & 0x4040404040404040) >> 1) | x;
   }
}

The above 64-bit implementation finishes the test in 6.3 seconds, and is almost as fast as the 128-bit SSE2 implementation that finished in 5.3 seconds.

Whats next?

From here one can adapt these tricks to higher bit-width vectorization instructions so long as one can be confident the target platform has them available.

There are two other places to go with this that will certainly give even better performance if the strings or number of string to process are large enough. One, is breaking this up into threads either within the function or in the functions that call this function. The other is to resort to offloading the task to the GPU or other more drastic hardware solutions.

EDIT Here is an SSE2 approach adapted to work with the null terminator. The input still needs to be 128-bit aligned, but special logic could easily be added to the function to handle that. It finishes in 5.8 seconds, so it's only marginally slower than the version that does not perform a null check which finished in 5.3 seconds.

__forceinline void StrToLowerCaseSSE(const char* src, char* dst)
{
    __m128i const *src128  = (__m128i const*)src;
    __m128i       *dst128  = (__m128i*)dst;
    for (;;)
    {
        __m128i const c16  = _mm_load_si128(src128);
        __m128i const null = _mm_cmpeq_epi8(c16, _mm_set_epi32(0, 0, 0, 0));
        if (_mm_movemask_epi8(null))
            break;
        ++src128;
        __m128i const abv  = _mm_sub_epi8(_mm_set_epi32(0x40404040, 0x40404040, 0x40404040, 0x40404040), c16);
        __m128i const blw  = _mm_sub_epi8(c16, _mm_set_epi32(0x5B5B5B5B, 0x5B5B5B5B, 0x5B5B5B5B, 0x5B5B5B5B));
        __m128i       msk  = _mm_and_si128(abv, blw);
        msk                = _mm_and_si128(msk, _mm_set_epi32(0x80808080, 0x80808080, 0x80808080, 0x80808080));
        msk                = _mm_srli_epi16(msk, 2);
        msk                = _mm_or_si128(msk, c16);
        _mm_store_si128(dst128++, msk);
    }
    src = (const char*)src128;
    dst = (char*)dst128;
    while (*src)
    {
        const unsigned char c = *src++;
        *dst++ = (unsigned char)(((((unsigned char)0x40 - (c)) & ((c)-(unsigned char)0x5b) & (unsigned char)0x80) >> 2) | (c));
    }
    *dst = '\0';
}

And here is similar null check adaptation of the 64-bit code. It finishes in 6.4 seconds where the original 64-bit version took 6.3.

__forceinline void StrToLowerCase64(const char* src, char* dst)
{
    unsigned const __int64 *src64 = (unsigned const __int64 *)src;
    unsigned       __int64 *dst64 = (unsigned __int64 *)dst;
    for (;;)
    {
        const unsigned __int64 x  = *src64;
        if ((x - 0x0101010101010101) & 0x8080808080808080)
            break;
        ++src64;
        *dst64++ = (((0xC0C0C0C0C0C0C0C0 - x) & (x + 0x2525252525252525) & 0x4040404040404040) >> 1) | x;
    }
    src = (const char*)src64;
    dst = (char*)dst64;
    while (*src) {
        const unsigned char x = *src++;
        *dst++ = (unsigned char)(((((unsigned char)0x40 - (x)) & ((x)-(unsigned char)0x5b) & (unsigned char)0x80) >> 2) | (x));
    }
    *dst = '\0';
}
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

This is what Visual Studio 2012 with /O2 generated for me without SSE support:

_StrToLowerCase:
  00000000: 8B 54 24 04        mov         edx,dword ptr [esp+4]
  00000004: 8B 44 24 08        mov         eax,dword ptr [esp+8]
  00000008: 8A 0A              mov         cl,byte ptr [edx]
  0000000A: 84 C9              test        cl,cl
  0000000C: 74 19              je          00000027
  0000000E: 2B D0              sub         edx,eax
  00000010: 0F BE C9           movsx       ecx,cl
  00000013: 8D 40 01           lea         eax,[eax+1]
  00000016: 0F B6 89 00 00 00  movzx       ecx,byte ptr _TblToLower[ecx]
            00
  0000001D: 88 48 FF           mov         byte ptr [eax-1],cl
  00000020: 8A 0C 02           mov         cl,byte ptr [edx+eax]
  00000023: 84 C9              test        cl,cl
  00000025: 75 E9              jne         00000010
  00000027: C6 00 00           mov         byte ptr [eax],0
  0000002A: C3                 ret

...and this is with SSE:

_StrToLowerCase:
  00000000: 8B 54 24 04        mov         edx,dword ptr [esp+4]
  00000004: B8 00 00 00 00     mov         eax,offset _TblToLower
  00000009: 8A 0A              mov         cl,byte ptr [edx]
  0000000B: 0F 18 08           prefetcht0  [eax]
  0000000E: B8 40 00 00 00     mov         eax,offset _TblToLower+40h
  00000013: 0F 18 08           prefetcht0  [eax]
  00000016: B8 80 00 00 00     mov         eax,offset _TblToLower+80h
  0000001B: 0F 18 08           prefetcht0  [eax]
  0000001E: B8 C0 00 00 00     mov         eax,offset _TblToLower+0C0h
  00000023: 0F 18 08           prefetcht0  [eax]
  00000026: 8B 44 24 08        mov         eax,dword ptr [esp+8]
  0000002A: 84 C9              test        cl,cl
  0000002C: 74 19              je          00000047
  0000002E: 2B D0              sub         edx,eax
  00000030: 0F BE C9           movsx       ecx,cl
  00000033: 8D 40 01           lea         eax,[eax+1]
  00000036: 0F B6 89 00 00 00  movzx       ecx,byte ptr _TblToLower[ecx]
            00
  0000003D: 88 48 FF           mov         byte ptr [eax-1],cl
  00000040: 8A 0C 02           mov         cl,byte ptr [edx+eax]
  00000043: 84 C9              test        cl,cl
  00000045: 75 E9              jne         00000030
  00000047: C6 00 00           mov         byte ptr [eax],0
  0000004A: C3                 ret

It looks pretty much optimal to me already. So I'd try:

  1. Inlining the function to avoid the overhead of the function call
  2. Study the input strings given to the function; if you find that you have many reoccurring strings (and long ones), you may want to consider caching the results.

As a bottom note, I'd probably write the main loop of the function as

while ( *src ) *dst++ = TblToLower[*src++];

..and declare the TblToLower table as a static inside of the function to improve (read: reduce) the scope of visibility. Maybe this even improves cache locality?

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ If you are going to optimize into a single line why not just: while(*dst++ = TblToLower[*src++]){} \$\endgroup\$ – Martin York Sep 10 '13 at 21:52
  • \$\begingroup\$ @LokiAstari: Because I don't like assignments in conditionals. \$\endgroup\$ – Frerich Raabe Sep 11 '13 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.