Rely on a compiler

We may auto-generate a huge switch statement and let the compiler do all the hard job. It's not naive approach, as compilers are getting better and better. Refer to a great presentation Hans Wennborg: C++ switch statements under the hood in LLVM.

Perfect hashing function

Perfect hashing functions are really great (see Modern perfect hashing for strings), although they do not fit well to this particular problem. Lookup in a hash table requires two steps:

• Calculate the value of our perfect hash function — this yields the index to the hash table,
• Fetch the entry from the table — the entry contains the key (a character code) and a value (an upper- or lowercase code). We need to check if the input value equals to the key and only then there's a hit.

const uint32_t src_code = input[i];

const size_t h = perfect_hash_function(src_code);
if (hash_table[h].src_code == src_code) {
    output[j++] = hash_table[h].dst_code;
} else {
    output[j++] = src_code; // no changes to the character
}

The first problem is finding a cheap perfect hash function, as we have to evaluate it for every character. We tried to find something like ((character code * M) >> N) & mask, where M, N and mask are compile time constants. The best hash function returned value ~8100. This means hash table size would be approx 126kB, while we can reduce auxiliary table sizes to ~26kB using simpler techniques.

The second problem is related to vectorization — fetching table entries require using VPGATHERDD. Our input are vectors of 4-byte character codes, but the size of hash table entry is 8 bytes. Thus we would need to issue gather instruction twice: either to fetch separately two halves of entries, or fetch 8-byte entries for characters at odd/even indices of the input.

Use lookup tables

Lookup tables addressed directly by the character code seems to be the best option.

1. An obvious solution is to have tables of size 0x1ffff, that is 131'072 entries. Than the lookup costs us only check the range and a single memory fetch.

   const uint32_t src_code = input[i];
   if (src_code < 0x1'ffff) {
       output[j++] = lookup[src_code];
   } else {
       output[j++] = src_code;
   }
   

   The drawback is size of a single table: 131'072 * 4 bytes = 524'288 bytes. 512kB exceeds usual sizes of L1 cache and cache misses may kill performance. Of course, we can come up with scenarios where this is not a problem. For example, if we're dealing with texts written in one language, we effectively will use only a small portion of the tables. But when we cannot assume anything about the text source, having 1MB of auxiliary tables does not seem to be a right solution. Also, when case changing is only a part of bigger system, huge lookup tables might be a problem.

2. It is possible to compress lookup tables. We know that only a small fraction of codes are being altered during case changing, thus we can rule out a huge number of character codes. We split a character code into higher and lower parts. The higher order bits are used to distinguish between ranges of codes having none or some characters to change. If the characters from the given range are not changed, we simply do not save that range.

   The lower part of character code is used as a local offset within the selected range.

   A simplified algorithm is shown below.

   const uint32_t src_code = input[i];
   if (src_code < 0x1'ffff) {
       constexpr int N = some_predefined_const;
       const uint32_t hi = src_code >> N;
       const uint32_t lo = src_code & ((1 << N) - 1);
   
       const uint32_t group_id = first_level_lookup[hi];
       if (group_id != 0) {
           // `group_id + lo` may be a bit different expression, but generally
           // we combine somehow the lower bits with the `group_id`.
           const uint32_t dst_code = second_level_lookup[group_id + lo];
           output[j++] = dst_code;
       } else {
           output[j++] = src_code;
       }
   } else {
       output[j++] = src_code;
   }
   

   This solution also requires two lookups, so we are having exactly the same problem as in the case of perfect hashing function — two gathers. Not ideally, but compression allows us to shave significant portions of lookup tables when compared to the naive solution.

3. We said that a lookup table (single or compressed) is addressed by character codes, but what is stored in the table?

   We may store there UTF-32 uppercase or lowercase codes directly. However, we may also store there already encoded UTF-8 characters, when the UTF-8 is desired encoding.

   Another option is storing symmetrical differences (xor) between the source and destination codes. For uppercase we have 139 distinct differences, for lowercase 124. That is significantly fewer than the actual number of codes (1525 and 1433, respectively).

   The conversion that uses differences requires just additional xor operation. And as we learn later on, this allows some nice tricks, including replacing one of memory gathers with an in-register shuffle (yes, PSHUFB!).

   const uint32_t src_code = input[i];
   if (src_code < 0x1'ffff) {
       output[j++] = src_code ^ lookup[src_code];
   } else {
       output[j++] = src_code;
   }
   

Possible improvement?

When we hit the slow path, we might want to check whether any of the characters from SIMD registers would change. When nothing would change, we simply could copy the register contents to the output.

As the pictures in Appendix B and C suggest, there are many ranges of characters that are not altered during case changing. We may use higher order bits of code points to identify these ranges and avoid the slow path. Unfortunately, it doesn't work well in real world scenarios.

We used exactly the same datasets as the simdutf project: the Wikipedia article about the Mars in various languages. The languages are: Arabic, Chinese, Czech, English, Esperanto, French, German, Greek, Hebrew, Hindi, Japanese, Korean, Persian, Portuguese, Russian, Thai, Turkish and Vietnamese.

In our evaluation we process 8-character blocks of the input (eight UTF-32 characters fit in an AVX2 register). A block is first checked for ASCII characters. If there are some non-ASCII characters, we perform either uppercase of lowercase transformation on the block.

The following table summarizes the experiment. The column "ASCII" says what fraction of the input blocks went through the fast path. The last two columns: "changed case" and "not changed" show the slow path outcome — the fraction of blocks that were changed or not. As we can observe, in the case of European languages the majority of blocks is getting changed, while in Asian languages almost nothing got modified.

This results make the discussed optimization pointless.

Solution 1 — huge lookup tables

This is the first approach — use single, 512kB tables. To handle multi-character strings we used auxiliary lookup table, as discussed in the previous section.

The scalar code performing lookup is shown below. The input is UTF-32-encoded string, n is its length. The output should be big enough (n*3 is the safest & simplest to obtain size).

size_t utf32_uppercase_plain(const uint32_t* input, size_t n, uint32_t* output) {
    size_t j=0;
    for (size_t i=0; i < n; i++) {
        const uint32_t src = input[i];
        if (likely(src <= 0x1'ffff)) {
            const uint32_t dst = UTF32_UPPERCASE_PLAIN[src];
            if (unlikely(int32_t(dst) < 0)) {
                const size_t ofs = dst & 0x1ff;
                switch (dst >> 30) {
                    case 2:
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 0];
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 1];
                        break;
                    case 3:
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 0];
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 1];
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 2];
                        break;
                    default:
                        assert(false);
                }
            } else {
                output[j++] = dst;
            }
        } else {
            output[j++] = src;
        }
    }

    return j;
}

The code is rather straightforward, the only unusual thing is marking branches with likely/unlikely (wrappers for __builtin_expect). This moved the handling of multi-character replacements out of the main loop.

In the case of lowercase operation, there is only one multi-character replacement, it can be handled directly. But it might not be a good solution, and better use table-based one. In the introduction we showed that the characters having different cases are added to the Unicode standard.

size_t utf32_lowercase_plain(const uint32_t* input, size_t n, uint32_t* output) {
    size_t j=0;
    for (size_t i=0; i < n; i++) {
        const uint32_t src = input[i];
        if (likely(src <= 0x1'ffff)) {
            const uint32_t dst = UTF32_LOWERCASE_PLAIN[src];
            if (unlikely(int32_t(dst) < 0)) {
                // there's exactly one replacement pair for lowercase
                // 'İ' => 'i̇' (2)
                output[j++] = 0x0069;
                output[j++] = 0x0307;
            } else {
                output[j++] = dst;
            }
        } else {
            output[j++] = src;
        }
    }

    return j;
}

Solution 2 — compressed lookup table (variant #1)

This section describes the solution we used at Sneller. We purposely omitted the mutli-character replacements as too complex for our needs at the moment of creating the product.

The values in range 0 .. 0x1_ffff can be saved on 17 bits. We split the 17-bit character code into two parts: higher 9-bit (row), and lower 8-bit (column). For each of 512 possible higher order bit combinations, we collect all 256 lower- or uppercase character codes; we are collecting codes for range 0x000_00 .. 0x000_ff, then 0x001_00 .. 0x001_ff, up to the range 0x1ff_00 .. 0x1ff_ff.

Then, for each group of 256 character codes (rows), we find the first and the last column where character codes got changed. We save only this range of characters, alongside the first and last index. Note that not all characters within a range are subject of case change — this is an additional storage cost we pay for simplicity.

Thus, the first level lookup contains 512 records with:

• offset to the second-level lookup table,
• 8 bits for first index,
• 8 bits for last index,

These three fields fit in a single 4-byte word. For unused entries we set an invalid range, having last < first; this saves us one extra check for invalid entries. For detailed info about the first level lookup, see appendix D.

The second level lookup contains arrays of 4-byte elements. At Sneller we stored UTF-8 encoded strings, as internally we used that encoding. In the experiments for this article, we store UTF-32 characters.

 character 'ą'
┌─────────────┐
│    00105    │ ╶───────────────────────────┐
└─────────────┘                             │
      |                                     │
      │     1st level lookup                │           2nd level lookup
      │  ┌─────┬─────┬────────┐             │           ┌──────────────┐
      │  │ min │ max │ offset │             │           ┆              ┆
      │  ├─────┼─────┼────────┤             │           ┆              ┆
      │  │  61 │  ff │     0  │             │ +5        ┆              ┆
      │  ├─────┼─────┼────────┤             ▼           ├──────────────┤
      └─▶│  01 │  ff │   159  │ ╶──╴159╶───▶◯╶──╴163╶──▶│  00104 = 'Ą' │ #163
         ├─────┴─────┴────────┤             ▲           ├──────────────┤
         ┆  │                 ┆             │ -1        ┆              ┆
         ┆  └───────────────╴ ┆ ╶───────────┘           ┆              ┆
         ┆    01 <= 05 <= ff  ┆                         ┆              ┆
         ┆                    ┆                         ┆              ┆
         └────────────────────┘                         ┆              ┆
                                                        └──────────────┘

Below is shown the implementation.

size_t utf32_uppercase_compressed_v2(const uint32_t* input, size_t n, uint32_t* output) {
    size_t j=0;
    for (size_t i=0; i < n; i++) {
        const uint32_t src = input[i];
        const uint32_t key = src >> 8; // use higher 9 bits
        if (unlikely(key >= UTF32_UPPERCASE_V2_MAX_HI_BITS)) {
            output[j++] = src;
            continue;
        }

        const uint32_t entry  = UTF32_UPPERCASE_V2_OFFSET[key];
        const uint32_t min    = entry & 0xff;
        const uint32_t max    = (entry >> 8) & 0xff;
        const uint32_t offset = entry >> 16;

        const uint32_t lo = src & 0xff;
        if (lo >= min && lo <= max) {
            const uint32_t dst = UTF32_UPPERCASE_V2_DATA[offset + lo - min];
            if (likely(int32_t(dst) >= 0)) {
                output[j++] = dst;
            } else {
                const size_t ofs = dst & 0x1ff;
                switch (dst >> 30) {
                    case 2:
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 0];
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 1];
                        break;
                    case 3:
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 0];
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 1];
                        output[j++] = UTF32_UPPERCASE_PLAIN_LONG_REPL[ofs + 2];
                        break;
                    default:
                        assert(false);
                    }
            }
        } else {
            output[j++] = src;
        }
    }

    return j;
}

Solution 3 — compressed lookup tables (variant #2)

A simplification to the above method is storing the whole row, without dealing with the first & last index and logic required to handle them: a condition and more complex offset calculation.

The following table shows the analysis of lookup table size depending on high/low bits split. We will get the smallest tables for 11 higher/6 lower bits, or 10 higher/7 lower bits. They are approx ~50kB, which is ~2 times more than in the compressed table.

We may store the first level lookup on 16-bit values, that would save 2-3kB, but it's negligible amount of memory.

Solution 4 — compressed lookup tables with diffs (variant #3)

Another variant of compressed table, but stores character differences (xor) rather than raw code points. As we have already seen, the number of distinct difference values is significantly lower than character codes. And it appeared that many rows repeat, they allows even better compression.

The table below also shows that we never get more than 255 distinct rows, thus the 1st level lookup table can be an array of bytes.

And for the best character code split we are getting comparable table sizes to the first, more sophisticated variant #1.

Below is shown the actual implementation of AVX2 procedure, using 10 higher and 7 lower bits of character code. There's also shown the fast path for ASCII conversion, which is basically the same in all vectorized procedures.

size_t avx2_utf32_uppercase_compressed_v3(const uint32_t* input, size_t n, uint32_t* output) {
    size_t j=0;
    size_t i=0;

    const __m256i fallback_key = _mm256_set1_epi32(UTF32_UPPERCASE_V3_MAX_HI_BITS);
    const __m256i mask_00ff    = _mm256_set1_epi32(0x00ff);
    const __m256i mask_000f    = _mm256_set1_epi32(0x000f);

    for (i=0; i < 8*(n / 8); i += 8) {
        const __m256i src = _mm256_loadu_si256((const __m256i*)(&input[i]));

        if (_mm256_testz_si256(src, _mm256_set1_epi32(0xffffff80))) {
            const __m256i ge_a = _mm256_cmpgt_epi32(src, _mm256_set1_epi32('a' - 1)); // char >= 'a'
            const __m256i le_z = _mm256_cmpgt_epi32(_mm256_set1_epi32('z' + 1), src); // char <= 'z'

            const __m256i v0 = _mm256_and_si256(ge_a, le_z);
            const __m256i v1 = _mm256_and_si256(v0, _mm256_set1_epi32(0x20));
            const __m256i v2 = _mm256_xor_si256(src, v1);

            _mm256_storeu_si256((__m256i*)(&output[j]), v2);
            j += 8;
            continue;
        }

        // key = min((src >> 4), UTF32_LOWERCASE_V3_MAX_HI_BITS)
        const __m256i key_0       = _mm256_srli_epi32(src, 4);
        const __m256i key         = _mm256_min_epi32(key_0, fallback_key);

        // group_id = lookup[key] & 0xff
        const __m256i group_id_0  = _mm256_i32gather_epi32((const int*)UTF32_UPPERCASE_V3_LOOKUP, key, 1);
        const __m256i group_id    = _mm256_and_si256(group_id_0, mask_00ff);

        // ofs = src & 0xf
        const __m256i ofs         = _mm256_and_si256(src, mask_000f);

        // const uint32_t diff = UTF32_UPPERCASE_V3_DATA[group_id * 16 + ofs];
        const __m256i indices     = _mm256_add_epi32(_mm256_slli_epi32(group_id, 4), ofs);
        const __m256i diff        = _mm256_i32gather_epi32((const int*)UTF32_UPPERCASE_V3_DATA, indices, 4);
        const __m256i out         = _mm256_xor_si256(diff, src);

        _mm256_storeu_si256((__m256i*)(&output[j]), out);
        if (_mm256_movemask_ps(_mm256_castsi256_ps(diff))) {
            const size_t d = utf32_uppercase_compressed_v3(input + i, 8, output + j);
            j += d;
        } else {
            j += 8;
        }
    }

    const size_t d = utf32_uppercase_compressed_v3(input + i, n - i, output + j);

    return d + j;
}

Vectorization of variant #3

All compressed variants have to use two memory gather instructions. But in the variant #3 we limited the range of offsets to bytes. Thus we can use VPSHUFB (AVX2) or VPERMI2B (AVX-512) to implement the first level lookup.

AVX2 variant #4

Use 5 higher bits (row #12 in the above table): this requires two VPSHUFB invocations plus some merging. Auxiliary tables size is 320kB.

The lookup code is shown below.

// key = min((src >> 12), UTF32_LOWERCASE_V4_MAX_HI_BITS)
const __m256i key_0       = _mm256_srli_epi32(src, 12);
const __m256i key         = _mm256_min_epi32(key_0, _mm256_set1_epi32(UTF32_LOWERCASE_V4_MAX_HI_BITS));

// lo = lookup for bits 15:12, where bit #16 is 0
const __m256i lo          = _mm256_shuffle_epi8(lo_lookup, key);

// hi = lookup for bits 15:12, where bit #16 is 1
const __m256i hi          = _mm256_shuffle_epi8(hi_lookup, key);

// mask: bit #16 to mask
const __m256i mask        = _mm256_cmpgt_epi32(key, mask_000f);

// group_id = lookup[key] & 0xff
const __m256i ofs_0       = select(mask, hi, lo);
const __m256i ofs_1       = _mm256_and_si256(ofs_0, mask_00ff);
const __m256i ofs_2       = _mm256_slli_epi32(ofs_1, 12);
const __m256i ofs_3       = _mm256_and_si256(src, mask_0fff);

// indices = (group_id << 12) + (src_code & 0xfff)
const __m256i indices     = _mm256_add_epi32(ofs_3, ofs_2);

// const uint32_t diff = UTF32_UPPERCASE_V4_DATA[indices];
const __m256i diff        = _mm256_i32gather_epi32((const int*)UTF32_UPPERCASE_V4_DATA, indices, 4);
const __m256i out         = _mm256_xor_si256(diff, src);

_mm256_storeu_si256((__m256i*)(&output[j]), out);

AVX2 variant #5

Use 6 higher bits (row #11 in the above table): this requires four VPSHUFB invocations plus merging. Auxiliary tables size is 216kB.

The lookup code is shown below. These four VPSHUFB are not that expansive, but the whole merging and masking make the whole procedure complex.

const __m256i key_0       = _mm256_srli_epi32(src, 11);
const __m256i key         = _mm256_and_si256(key_0, mask_000f);
const __m256i selector    = _mm256_srli_epi32(src, 15);

const __m256i res0_a      = _mm256_shuffle_epi8(lookup_0, key);
const __m256i selector_0  = _mm256_cmpeq_epi32(selector, _mm256_set1_epi32(0));
const __m256i res0        = _mm256_and_si256(res0_a, selector_0);

const __m256i res1_a      = _mm256_shuffle_epi8(lookup_1, key);
const __m256i selector_1  = _mm256_cmpeq_epi32(selector, _mm256_set1_epi32(1));
const __m256i res1        = _mm256_and_si256(res1_a, selector_1);

const __m256i res2_a      = _mm256_shuffle_epi8(lookup_2, key);
const __m256i selector_2  = _mm256_cmpeq_epi32(selector, _mm256_set1_epi32(2));
const __m256i res2        = _mm256_and_si256(res2_a, selector_2);

const __m256i res3_a      = _mm256_shuffle_epi8(lookup_3, key);
const __m256i selector_3  = _mm256_cmpeq_epi32(selector, _mm256_set1_epi32(3));
const __m256i res3        = _mm256_and_si256(res3_a, selector_3);

const __m256i group_0     = _mm256_or4_si256(res0, res1, res2, res3);
const __m256i group_1     = _mm256_and_si256(group_0, mask_00ff);
const __m256i group       = _mm256_slli_epi32(group_1, 11);

const __m256i ofs         = _mm256_and_si256(src, mask_07ff);
const __m256i indices     = _mm256_add_epi32(ofs, group);

// const uint32_t diff = UTF32_UPPERCASE_V4_DATA[indices];
const __m256i diff        = _mm256_i32gather_epi32((const int*)UTF32_UPPERCASE_V5_DATA, indices, 4);
const __m256i out         = _mm256_xor_si256(diff, src);

AVX-512 variant #6

Use 7 higher bits (row #10 in the above table): this requires a single invocation of VPERMI2B. Auxiliary tables size is 128kB.

// key = min((src >> 4), UTF32_LOWERCASE_V6_MAX_HI_BITS)
const __m512i key         = _mm512_srli_epi32(src, 10);
const __m512i group_0     = _mm512_permutex2var_epi8(lo_lookup, key, hi_lookup);
const __m512i group       = _mm512_and_si512(group_0, mask_00ff);

const __m512i ofs_0       = _mm512_slli_epi32(group, 10);
const __m512i ofs_1       = _mm512_and_si512(src, mask_03ff);
const __m512i indices     = _mm512_add_epi32(ofs_1, ofs_0);

// const uint32_t diff = UTF32_UPPERCASE_V6_DATA[indices];
const __m512i diff        = _mm512_i32gather_epi32(indices, (const uint32_t*)UTF32_UPPERCASE_V6_DATA, 4);
const __m512i out         = _mm512_xor_si512(diff, src);

Ryzen 7

• Compiler: gcc (Debian 14.1.0-5) 14.1.0
• CPU: AMD Ryzen 7 7730U with Radeon Graphics

Ice Lake

• Compiler: gcc (GCC) 13.3.1 20240611 (Red Hat 13.3.1-2)
• CPU: Intel(R) Xeon(R) Gold 6338 CPU @ 2.00GHz

A — Codepoints of letters having different cases

B — Lowercase letters placement

The picture shows which characters in range 0..0x1ffff have lowercase variants: they are marked with blue, green or red. In gray are shown characters without lowercase variants.

There are 512 rows (addressed by bits [16:8]) of 256 characters (addressed by bits [7:0] of character code).

C — Uppercase letters placement

The picture shows which characters in range 0..0x1ffff have uppercase variants: they are marked with blue, green or red. In gray are shown characters without lowercase variants.

There are 512 rows (addressed by bits [16:8]) of 256 characters (addressed by bits [7:0] of character code).

D — Compressed tables — variant 1

The exact sizes of the 1st level lookup tables in variant #1.