3.1   Range checking

The maximum possible value from SSE conversion procedure is ± 99999999. This value is smaller than the maximum that can hold a 32-bit number (2³¹ − 1 = 2147483647) and also absolute value of the minimum (2³¹ = 2147483648). It means that if an output collection uses at least 32-bit numbers, then SSE procedures never cause overflow (signed nor unsigned).

Obviously, for 16-bit outputs, overflow is possible. For such case an extra step would be required, but I do not discuss it in this text.

3.2   Sample implementation

Below is a sample SSE implementation which shows all described steps.

// 1. convert from ASCII '0' .. '9' to numbers 0 .. 9
const __m128i ascii0 = _mm_set1_epi8('0');
const __m128i t0 = _mm_subs_epu8(input, ascii0);

// 2. convert to 2-digit numbers
const __m128i mul_1_10 = _mm_setr_epi8(10, 1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1);
const __m128i t1 = _mm_maddubs_epi16(t0, mul_1_10);

// 3. convert to 4-digit numbers
const __m128i mul_1_100   = _mm_setr_epi16(100, 1, 100, 1, 100, 1, 100, 1);
const __m128i t2 = _mm_madd_epi16(t1, mul_1_100);

// 4a. convert form 32-bit into 16-bit element vector
const __m128i t3 = _mm_packus_epi32(t2, t2);

// 4. convert to 8-digit numbers
const __m128i mul_1_10000 = _mm_setr_epi16(10000, 1, 10000, 1, 10000, 1, 10000, 1);
const __m128i t4 = _mm_madd_epi16(t3, mul_1_10000);

4.1   Algorithm overview

The conversion algorithm works in a loop, in each iteration exactly one input vector is loaded from memory and processed.

• The vector is validated.
• Depending on the layout of the digits, the input is normalized to the format required by the SIMD procedures. At this step we choose: how many numbers from the input are converted and which SIMD procedure is suitable for conversion.
• After conversion, the input pointer is advanced and the loop continues.

4.2   Normalizing input

Since SIMD procedures impose specific layout of digits within a vector, an arbitrary input has to be properly aligned. In order to do this, we need to identify spans of digits in the input and move each span onto certain subarrays of a vector. Let's assume at this point that the input contains either digits or separators (denoted with _).

For instance, the vector with one-digit numbers 1___2_3__4__5_6_ must be transformed into 123456__________. Then an SSE procedure will convert in parallel all the numbers into the array [1, 2, 3, 4, 5, 6]. Likewise, the vector with two-digit numbers _12__34___56_78_ must be transformed into 12345678________ and then the result will be [12, 34, 56, 78].

Let's consider a more complicated case, when a string has numbers with different count of digits. There are a few ways to convert the input _1_2_34_567_89__:

• If we choose conversion of one-digit numbers, then just the two first spans can be converted — because we need to keep the order of numbers from the input. After normalization the input into 12______________ just two values [1, 2] will be produced. The input's tail _34_567_89__ remain untouched.
• If we choose conversion of two-digit numbers, then the three first spans can be converted. Shorter numbers are completed with zeros, then normalized input is 010234__________. The result is [1, 2, 34]; this time a bit shorter input's tail _567_89__ remain untouched.
• Finally, if we choose conversion of four-digit numbers, then the four first spans can be converted. Again, shorter numbers are completed with zeros, and normalized input is 0001000200340567. The result is [1, 2, 34, 567], but still the chunk's tail, i.e. _89__, is unprocessed.

We can see that in order to convert given span combination we need to know:

1. How to shuffle bytes in the input vector?
2. Which SIMD procedure can be used then?
3. How many numbers converted by the SIMD procedure must be stored?

Obtaining this information seems to be quite complicated, especially when we look at the last example. Fortunately, all parameters can be precalculated. A span combination can be saved as a bit-pattern, where ones represent digits. For example, from vector _1_2_34_567_89__ we get the span pattern 0b0101011011101100 = 0x56ec. A span pattern is used to fetch a record from the precalculated array. The record contains following fields:

• shuffle_digits — an array of 16 bytes, which is the argument for the instruction _mm_shuffle_epi8 (pshufb); the instruction moves bytes at certain positions;
• conversion_routine — an enumeration that selects an SSE conversion procedure; for instance, it tells that shuffled input is an array of two-digit numbers;
• element_count — the number of elements from the SSE conversion procedure that must be stored in the output collection.

The solution with a precalculated array is suitable only for SSE, as span patterns have 16 bits. In cases of AVX2 and AVX512, where vectors are wider, such a table would be simply too large, respectively 2³² or 2⁶⁴ entries. Additionally, the AVX2 version of pshufb instruction works on lanes, i.e. 128-bit halves of a vector, thus it is impossible to shuffle all inputs.

But AVX2 and AVX512 instructions still might be used in some parts of algorithms, especially in input validation.

4.3   Precalculating data

To build the whole precalculated table all 65536 span patterns have to be processed. Processing a pattern consists following steps:

1. Determine digit spans. For pattern _ddd__d__ddd_dd_ we have four spans [(1,3), (6,6), (9,11), (14,15)]. But for pattern ____dddd___ddddd there is only one span [(4,7)]. The span at the vector's end might be continued in the next chunk, and we don't know how to convert it. However, we may assume that a span which starts at the vector's beginning is a new number and thus it is included into the span's list.
2. Find the best conversion scheme for the spans. We systematically check which SSE conversion is possible, i.e. one-/two-/four-/eight-digit and how many spans each conversion can process — the procedure which processes the most items is selected. The output from this step are values for the following record fields:
   • element_size — 1, 2, 4, 8 or 0 if SSE conversion is not possible;
   • element_count — the numbers of converted spans;
   • total_skip — how many input bytes are processed; for pattern ____dddd________ we know that the whole input is processed (total_skip=16); for pattern ____d____ddddd_d we process only the first span at index 5, but we know that four non-digit characters after the span can be also skipped, thus total_skip is 9.
3. Construct the shuffle pattern. Having the element size and spans positions the vector shuffle_digits is built. The characters from a span are mapped on the appropriate subarrays in the vector. Also zero completion is done in this step, as the instruction pshufb either copy given byte from the input vector or put zero if the index has got the most significant bit set.

[ a0 | a1 | a2 | a3 | b0 | b1 | b2 | b3 | c0 | c1 | c2 | c3 | d0 | d1 | d2 | d3 ]

[ 80 |  1 |  2 |  3 | 80 | 80 | 80 |  6 | 80 |  9 | 10 | 11 | 80 | 80 | 14 | 15 ]

4.4   SSE algorithm outline

Below are major steps of the algorithm's loop, with snippets from the actual implementation.

1. Load 16 characters into the input vector.

const __m128i input = _mm_loadu_si128((const __m128i*)data);

2. Check for invalid characters (will be discussed later).

3. Build the span pattern:

// t0 = input[i] in ['0'..'9] ? 0xff : 0x00
const __m128i  t0 = decimal_digits_mask(input);
const uint16_t span_mask = _mm_movemask_epi8(t0);

5. Fetch the block info with the precalculate parameters.

const BlockInfo& bi = blocks[span_mask];

6. From the block info get the shuffle pattern for _mm_shuffle_epi8.

const __m128i shuffle_digits = _mm_loadu_si128((const __m128i*)b.shuffle_digits);
const __m128i shuffled = _mm_shuffle_epi8(input, shuffle_digits);

7. The shuffled vector is then issued to the proper conversion routine. The block info structure keeps the conversion kind (conversion_routine) and also the number of items to get from the SSE result (element_count). It is not always possible to use any SSE conversion procedure, thus a scalar code is needed to handle odd cases.

if (b.conversion_routine == Conversion::SSE1Digit) {

    convert_1digit(shuffled, b.element_count, output);

} else if (b.conversion_routine == Conversion::SSE2Digits) {

    convert_2digits(shuffled, b.element_count, output);

} else if (b.conversion_routine == Conversion::SSE4Digits) {

    convert_4digits(shuffled, b.element_count, output);

} else if (b.conversion_routine == Conversion::SSE8Digits) {

    convert_8digits(shuffled, b.element_count, output);

} else {

    // case unsupported, a scalar code is called here
}

8. Advance the input pointer. The block info structure keeps how many bytes were actually covered.

data += b.total_skip;

4.5   Detecting invalid inputs

In case of unsigned inputs we need to classify input characters into three categories:

• digits, i.e. chars '0' .. '9';
• user-defined set of separators;
• invalid numbers.

In practise we need two masks: one with positions of digits, another with positions of separators. If the or'ed mask has some zero elements, it means that there are invalid characters. Below is a schema:

const __m128i bytemask_digit = decimal_digits_mask(input);
const __m128i bytemask_sep   = matcher.get_mask(input);
const __m128i bytemask_valid = _mm_or_si128(bytemask_digit, bytemask_sep);

const uint16_t valid_mask = _mm_movemask_epi8(bytemask_valid);

if (valid_mask != 0xffff) {
    throw std::logic_error("wrong input");
}

__m128i decimal_digits_mask(const __m128i input) {
    const __m128i ascii0 = _mm_set1_epi8('0');
    const __m128i after_ascii9 = _mm_set1_epi8('9' + 1);

    const __m128i t0 = _mm_cmplt_epi8(input, ascii0); // t1 = (x < '0')
    const __m128i t1 = _mm_cmplt_epi8(input, after_ascii9); // t0 = (x <= '9')

    return _mm_andnot_si128(t0, t1); // x <= '9' and x >= '0'
}

bool is_digit(char c) {

    const uint8_t x = c;
    return (x - '0') <= 9;
}

uint64_t decimal_digits_mask(const __m128i input) {

    const __m512i ascii0 = _mm512_set1_epi8('0');
    const __m512i ascii9 = _mm512_set1_epi8('9');

    const __m512i t0 = _mm512_sub_epi8(input, ascii0);

    return __mm256_cmple_epu8_mask(t0, ascii9);
}

__m128i decimal_digits_mask_version2(const __m128i input) {

    const __m512i t0 = _mm_sub_epi8(input, _mm_set1_epi8(80));

    return _mm_cmplt_epi8(t0, _mm_set1_epi8(-118));
}

__m128i get_mask(const __m128i& input, const __m128i& initial) const {
    __m128i result = initial;
    for (size_t i=0; i < n + 1; i++) {

        const __m128i mask = _mm_cmpeq_epi8(letters[i], input);
        result = _mm_or_si128(result, mask);
    }

    return result;
}

__m128i get_mask(const __m128i& input, const __m128i& initial) {

    const uint8_t mode = _SIDD_UBYTE_OPS
                       | _SIDD_CMP_EQUAL_ANY
                       | _SIDD_UNIT_MASK;

    return _mm_or_si128(initial, _mm_cmpestrm(set, set_size, input, 16, mode));
}

4.6   Caveats

1. It is unlikely, and sometimes impossible, to process all digits from the input vector. In a single iteration one to 16 bytes are converted. The table below shows details — an important conclusion is that almost 95% of patterns process at least half of an input vector.

2. However, the input validation is always done for the whole vector, all 16 bytes. This problem might be overcome, see Processing larger inputs.
3. SSE units are underutilized. The longest one-digit number sequence is "1;2;3;4;5;6;7;8;". It contains eight numbers, while the SSE procedure is able to process 16 numbers. Likewise, the longest two-digit number sequence is "12;34;56;78;98;;". It has five numbers, but the SSE procedure is able to convert eight numbers. Similarly, the longest four-digit numbers sequence is "1234;5678;9123;;" — it has three four-digit numbers, the SSE procedure is able to convert four numbers.

5.1   Algorithm

Similarly to the unsigned conversion, the signed conversion also requires a span pattern. But in this case also the sign characters '+' and '-' are included in the pattern. For this sample string:

input     = "_+123_-45_78_-9_"

the span pattern is:

span_mask = _dddd_ddd_dd_dd_

The conversion unfortunately requires two shuffles:

1. Shuffle spans onto proper vector elements — this is exactly the same as in unsigned conversion.
2. Populate the first span characters, i.e. possibly sign character, on the proper vector elements.

For input:

input =

[ '_' | '-' | '1' | '2' | '3' | '_' | '+' | '4' | '5' | '_' | '-' | '6' | '_' | '7' | '8' | '_' ]

The conversion processes four four-digit numbers. After shuffling the digit spans we have:

shuffled =

[ '-'   '1'   '2'   '3' | 0x00  '+'   '4'   '5' | 0x00  0x00  '-'   '6' | 0x00  0x00  '7'   '8' ]

and the vector of sign characters is:

shuffled_signs =

[ '-'   '-'   '-'   '-' | '+'   '+'   '+'   '+' | '-'   '-'   '-'   '-' | '7'   '7'   '7'   '7' ]

The shuffled_signs vector does not necessarily contain only '+' or '-', it might contain also digits, but this is not an error.

Then the conversion works as follows:

• From the shuffled vector the sign characters are removed and ASCII characters are converted into values:

  [  0     1     2     3  |  0     0     4     5  |  0     0     0     6  |  0     0     7     8  ]
  

• Thus we end up with a vector of unsigned numbers, and such an input can be converted by the already defined SSE procedures:

  [          123          |           45          |           6           |           78          ]
  

• Finally, negate appropriate elements; we use a well known equation (~x + 1), which is expressed in the SSE code as (x xor (-1) - (-1)). The value -1 is obtained from comparing shuffled_signs with the '-':

  negated_mask = (shuffled_signs == packed_byte('-'))
  
  [ ff    ff    ff    ff  | 00    00    00    00  | ff    ff    ff    ff  | 00    00    00    00  ]
  

  or as vector of int32_t:

  [          -1           |           0           |          -1           |           0           ]
  

5.2   Implementation note

Masking of the sign characters in shuffled vector is done at no cost, as the instruction _mm_subs_epu8 (psubusb) is used to convert from ASCII to numeric values:

const __m128i ascii0 = _mm_set1_epi8('0');
const __m128i t0 = _mm_subs_epu8(input, ascii0);

The instruction performs subtract with saturation, i.e. calculates max(0, a-b). Since the ASCII codes of '-' and '+' are respectively 43 and 45 and the ASCII code of '0' is 48, then the result of such expression is zero for both sign characters.

5.3   Detecting invalid inputs

The characters '+' and '-' can be present only at the beginning of a digit span, i.e. we want to reject inputs like "++12" or "1234-,".

To properly validate the input we need four masks for:

1. separators,
2. digits,
3. the character '-',
4. the character '+'.

The first phase is similar to the unsigned conversion, i.e. all masks are or'ed together, then zero elements point at invalid characters.

The second phase checks if sign characters are placed properly. For each span combination we need to precalculate the mask of valid sign positions. Then, after or'ing the masks for the '+' and '-' we simply verify if they are placed on valid positions.

In practise the precalculated data has a bit-mask for invalid sign positions, thanks to that validation require just a simple and. The snippet below shows the schema of the second step.

const __m128i ascii_minus = _mm_set1_epi8('-');
const __m128i ascii_plus  = _mm_set1_epi8('+');

// ...

const __m128i bytemask_plus  = _mm_cmpeq_epi8(input, ascii_plus);
const __m128i bytemask_minus = _mm_cmpeq_epi8(input, ascii_minus);
const __m128i bytemask_sign  = _mm_or_si128(bytemask_plus, bytemask_minus);

// ...

const uint16_t sign_mask = _mm_movemask_epi8(bytemask_sign);
const uint16_t span_mask = _mm_movemask_epi8(bytemask_span);
const BlockInfo& bi = blocks[span_mask];
if (sign_mask & bi.invalid_sign_mask) {
    throw std::runtime_error("'+' or '-' at invalid position");
}

const __m512i lookup_lo = ... // elements 0..63
const __m512i lookup_hi = ... // and 64..127 of the lookup
const __m512i transformed = _mm512_permutex2var_epi8(lookup_lo, input, lookup_hi);

const __m512i classes = _mm512_permutex2var_epi8(class_lo, input, class_hi);

if (_mm512_test_epi8_mask(classes, classes) != uint64_t(-1)) {
    throw std::logic_error("invalid character");
}

uint64_t span_mask64 = _mm512_movepi8_mask(classes);
uint64_t sign_mask64 = _mm512_test_epi8_mask(classes, _mm512_set1_epi8(int8_t(0x40)));

5.4   SSE algorithm outline

Below are major steps of the algorithm's loop, with snippets from the actual implementation.

1. Load 16 characters into the input vector.

const __m128i input = _mm_loadu_si128((const __m128i*)data);

2. Check for invalid characters (as described above).
3. Build the span pattern and fetch the conversion parameters.

const __m128i ascii_minus    = _mm_set1_epi8('-');
const __m128i ascii_plus     = _mm_set1_epi8('+');

// ...
const __m128i bytemask_plus  = _mm_cmpeq_epi8(input, ascii_plus);
const __m128i bytemask_minus = _mm_cmpeq_epi8(input, ascii_minus);
const __m128i bytemask_sign  = _mm_or_si128(bytemask_plus, bytemask_minus);

const __m128i bytemask_digit = decimal_digits_mask(input);
const __m128i bytemask_span  = _mm_or_si128(bytemask_digit, bytemask_sign);

const uint16_t span_mask = _mm_movemask_epi8(bytemask_span);
const BlockInfo& bi = block_info[span_mask];

4. Validate if the sign characters are properly placed.

const uint16_t sign_mask = _mm_movemask_epi8(bytemask_sign);
if (sign_mask & bi.invalid_sign_mask) {
    throw std::runtime_error("'+' or '-' at invalid position");
}

5. If sign_mask is zero, choose faster unsigned conversion path.
6. Otherwise prepare data for signed conversion.

const __m128i ascii_minus = _mm_set1_epi8('-');

const __m128i shuffle_digits = _mm_loadu_si128((const __m128i*)bi.shuffle_digits);
const __m128i shuffle_signs  = _mm_loadu_si128((const __m128i*)bi.shuffle_signs);

const __m128i shuffled       = _mm_shuffle_epi8(input, shuffle_digits);
const __m128i shuffled_signs = _mm_shuffle_epi8(input, shuffle_signs);
const __m128i negate_mask    = _mm_cmpeq_epi8(shuffled_signs, ascii_minus);

7. And finally invoke proper conversion routine.

if (bi.conversion_routine == Conversion::SSE1Digit) {

    convert_1digit(shuffled, bi.element_count, output);

} else if (bi.conversion_routine == Conversion::SSE2Digits) {

    convert_2digits_signed(shuffled, negate_mask, bi.element_count, output);

} else if (bi.conversion_routine == Conversion::SSE4Digits) {

    convert_4digits_signed(shuffled, negate_mask, bi.element_count, output);

} else if (bi.conversion_routine == Conversion::SSE8Digits) {

    convert_8digits_signed(shuffled, negate_mask, bi.element_count, output);

} else {

    // scalar conversion
}

7.1   Example

Let's convert following input 24-byte input (the space separates 8-byte chunks):

_12_3_45 6_7890_1 ___99___

The first chunk of input is _12_3_45, i.e. the span_pattern = 0b01101011 = 0x6b. The digit spans are [(1,2), (4,4), (6,7)], following code handles them:

*output++ = convert<2>(data + 1);
*output++ = convert<1>(data + 4);
val       = convert<2>(data + 6);
has_val   = true;

The template convert is parametrized by the number of digits to convert and gets a pointer to the first character. The important fact is such code doesn't need to validate pointers, sizes etc. All is known in the compile-time.

The next input's chunk is 6_7890_1, the digit spans are [(0,0), (2,5), (7,7)]. A variant of template convert that accepts two parameters simple starts conversion from the saved state (val).

if (has_val) {
    *output++ = continue<1>(data + 0, val);
} else {
    *output++ = convert<1>(data + 0);
}

*output++ = convert<4>(data + 2);
val       = convert<1>(data + 7);
has_val   = true;

The last, third chunk, is ___99___, and there is just one digit span [(3,4)]:

if (has_val) {
    *output++ = val;
    has_val = false;
}

*output++ = convert<2>(data + 3);
has_val   = false;

11.1   SSE conversion — execution statistics

Caveats shows statistics of 1) average processed bytes and 2) SSE utilization. This section presents real numbers gathered during conversion of 1000000 bytes containing 1-8 digit signed numbers.

11.2   SSE conversion — runtime analysis

The lookup table is quite large: in the sample implementation single record occupies 38 bytes, it gives almost 2,5 MiB. This section presents analysis of span_pattern usage during conversion of various inputs. Following parameters are collated:

1. The number of different span patterns that appear during conversion. This is explained in details below.
2. The number of CPU clocks per input byte (on Skylake); the results were directly get from Performance comparison.
3. Both cache miss and branch miss ratios (the same Skylake); these results were obtained by running separate bin/benchmark-hwevents tool. The ratios should give a hint about real-workload penalties.

During a conversion a histogram is build. The histogram contains span_pattern and the number of its occurrences; the histogram is sorted by the frequency. Having such a sorted histogram it is easy to estimate how many distinct patterns appear in most iterations.

Let's analyse sample, made up, histogram:

There are 10 different patterns that were used in 43 loops. We can read from the table that in 1/4 of iterations (11 of 43) were used even seven patterns. Most of processing uses just three patterns. It means that only a small portion of the large lookup is actually touched.

The tables in following sections have got data processed in this way. Each column contains number of distinct patterns that take part in given percentage of the iterations (25%, 50%, 75%, 95% and all, 100%).

The results for various input sizes are available in the repository, below are shown only 4kB and 64kB inputs.

11.3   Performance comparison