Деление на константы, подобные этому, должно быть выполнено с умножением на мультипликативное обратное .Как вы можете видеть, компиляторы оптимизируют x/12 до x*43691 >> 19
bool h(uint16_t x)
{
return x % 12 == 1;
}
h(unsigned short):
movzx eax, di
imul eax, eax, 43691 ; = 0xFFFF*8/12 + 1
shr eax, 19
lea eax, [rax+rax*2]
sal eax, 2
sub edi, eax
cmp di, 1
sete al
ret
Поскольку в SSE / AVX есть команды умножения, это можно легко векторизовать.Кроме того, x = (x % 12 == 1) ? 1 : 0; можно упростить до x = (x % 12 == 1) и затем преобразовать в x = (x - 1) % 12 == 0, что позволяет избежать таблицы констант для сравнения значения 1.Вы можете использовать векторное расширение , чтобы gcc автоматически генерировал для вас код
typedef uint16_t ymm __attribute__((vector_size(32)));
ymm mod12(ymm x)
{
return !!((x - 1) % 12);
}
Ниже приведен вывод из gcc
mod12(unsigned short __vector(16)):
vpcmpeqd ymm3, ymm3, ymm3 ; ymm3 = -1
vpaddw ymm0, ymm0, ymm3
vpmulhuw ymm1, ymm0, YMMWORD PTR .LC0[rip] ; multiply with 43691
vpsrlw ymm2, ymm1, 3
vpsllw ymm1, ymm2, 1
vpaddw ymm1, ymm1, ymm2
vpsllw ymm1, ymm1, 2
vpcmpeqw ymm0, ymm0, ymm1
vpandn ymm0, ymm0, ymm3
ret
Clang и ICC не поддерживают !! для векторных типов, поэтому вам нужно изменить на (x - 1) % 12 == 0.К сожалению, похоже, что компиляторы не поддерживают __attribute__((vector_size(8)) для выдачи инструкций MMX.Но в настоящее время вы все равно должны использовать SSE или AVX
Вывод для x % 12 == 1 короче, как вы можете видеть в той же ссылке Godbolt выше, но вам нужна таблица, содержащая 1 для сравнения, которая может быть лучше или нет,Проверьте, какой из них работает быстрее в вашем случае
В качестве альтернативы для небольшого входного диапазона, как этот, вы можете использовать справочную таблицу.Базовая версия нуждается в массиве из 65536 элементов
#define S1(x) ((x) + 0) % 12 == 1, ((x) + 1) % 12 == 1, ((x) + 2) % 12 == 1, ((x) + 3) % 12 == 1, \
((x) + 4) % 12 == 1, ((x) + 4) % 12 == 1, ((x) + 6) % 12 == 1, ((x) + 7) % 12 == 1
#define S2(x) S1((x + 0)*8), S1((x + 1)*8), S1((x + 2)*8), S1((x + 3)*8), \
S1((x + 4)*8), S1((x + 4)*8), S1((x + 6)*8), S1((x + 7)*8)
#define S3(x) S2((x + 0)*8), S2((x + 1)*8), S2((x + 2)*8), S2((x + 3)*8), \
S2((x + 4)*8), S2((x + 4)*8), S2((x + 6)*8), S2((x + 7)*8)
#define S4(x) S3((x + 0)*8), S3((x + 1)*8), S3((x + 2)*8), S3((x + 3)*8), \
S3((x + 4)*8), S3((x + 4)*8), S3((x + 6)*8), S3((x + 7)*8)
bool mod12e1[65536] = {
S4(0U), S4(8U), S4(16U), S4(24U), S4(32U), S4(40U), S4(48U), S4(56U)
}
. Для использования просто замените x % 12 == 1 на mod12e1[x].Это, конечно, может быть векторизовано
Но поскольку результат равен только 1 или 0, вы также можете использовать 65536-битный массив , чтобы уменьшить размер только до 8 КБ
Вы также можете проверить делимость на 12 делением на 4 и 3. Делимость на 4 очевидно тривиальна.Делимость на 3 можно рассчитать несколькими способами:
- . Вычисляется разница между суммой нечетных цифр и суммой четные цифры как в ответе גלעד ברקן и проверьте, делится ли оно на 3 или нет
Или вы можете проверить, равна ли сумма цифр в базе 2 2k (например, основание 4, 16, 64 ...), чтобы увидеть, делится ли оно на 3 или нет.
Это работает, потому что в базе b проверяется делимостьлюбые делители n из b - 1, просто проверьте, делится ли сумма цифр на n или нет.Вот его реализация
void modulo12equals1(uint16_t d[], uint32_t size) {
for (uint32_t i = 0; i < size; i++)
{
uint16_t x = d[i] - 1;
bool divisibleBy4 = x % 4 == 0;
x = (x >> 8) + (x & 0x00ff); // max 1FE
x = (x >> 4) + (x & 0x000f); // max 2D
bool divisibleBy3 = !!((01111111111111111111111ULL >> x) & 1);
d[i] = divisibleBy3 && divisibleBy4;
}
}
Кредиты на делимость на 3 - Роланд Иллиг
Поскольку вывод автовекторизованной сборки слишком длинный,Вы можете проверить это по ссылке Godbolt
См. также