Сегодня очень плохо спал — всё время просыпался, потом долго ворочался, не мог уснуть. Утром оказалось мозг никак не мог успокоиться после вчерашней заметки про разбор быстрого алгоритма для подсчёта длины строки в UTF-8 при помощи векторизации для процессоров ARM.

Вчера я остановился на том, что у разбираемого способа есть две очевидные недоработки — ненужное вычисление, которое решается инвертированием условия и подсчёт «хвоста», который всегда вычисляется «классическим» способом — без векторизации, хотя если строка у нас кратна вектору, можно было бы этого избежать.

Первый недостаток исправлялся очень просто, а хорошая реализация второй проверки мне вчера в голову не пришла.

Зато, когда я проснулся, она уже была у меня в голове. Всего три операции — первой получаем вектор, где на позициях с ненулевым байтом записывается 255, потом делается операция «И» с номерами позиций и весь вектор суммируется.

В итоге, если ноль стоит в векторе только на крайней правой позиции, у нас получается сумма арифметической прогрессии без последнего элемента.

По замерам такой вариант чуть быстрее.

size_t strlen_utf8(unsigned char * p) {
    size_t len = 0;

    const int8x16_t threshold = vdupq_n_s8(-63);
    const uint8x16_t delta = vdupq_n_u8(1);

    for(;;) {
        int8x16_t operand = vld1q_s8((const int8_t * ) p);
        if (vminvq_u8(operand) == 0) {
            uint8x16_t pos = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
            uint8_t sum = vaddvq_u8(vandq_u8(vtstq_u8(operand, operand), pos));

            // арифметическая прогрессия без последнего члена
            if (sum == 16*(16+1) / 2 - 16) {
                uint8x16_t gt = vcgtq_s8(operand, threshold);
                return len + vaddvq_u8(vandq_u8(gt, delta)) - 1;
            } else {
                break;
            }
        }

        uint8x16_t gt = vcgtq_s8(operand, threshold);
        len += vaddvq_u8(vandq_u8(gt, delta));
        p += sizeof(uint8x16_t);
    }

    for (signed char c; (c = *p); p++) {
        if (c >= -64) {
            len++;
        }
    }

    return len;
}