Эффективное повторение меньшего целочисленного/битового шаблона в C
Предположим, у меня есть объект, содержащий множество небольших целочисленных типов. Например, ветвь октодерева, содержащая 8 uint16_t:
uint16_t values[8];
Я хотел бы присвоить им всем одно значение. Очевидным решением является использование цикла:
for (int i = 0; i < 8; ++i)
values[i] = new_value;
Однако есть ли способ написать это без зацикливания или иного назначения их один за другим? Есть ли SWAR или подобные трюки, позволяющие выполнить эту задачу менее чем за 8 шагов?
Мне разрешено упаковывать values[8] в union вместе с другими более крупными типами.
Я пробовал скомпилировать цикл и присваивая каждому значению индивидуально в предположении, что компилятор с включенной оптимизацией распознает шаблон, но я все равно получаю неоптимальный «линейный» алгоритм присвоения каждого значения по одному .
На вопрос «Однако есть ли способ написать это без цикла?» Нет. Повторное выполнение чего-либо требует какого-то цикла по определению.
@ikegami Вы можете назначать их по одному без цикла, values[0] = new_value; values[1] = new_value; values[2] = new_value; // ...
Можно использовать достаточно простой макрос, включающий сдвиг битов. uint64_t t[2] = { MACRO( n ) }; Не стоит заморачиваться с его написанием. Извини...
Включите оптимизацию. Если полностью развернутый цикл будет быстрее, оптимизатор, скорее всего, сделает это. Если векторизация поможет, ее тоже обычно будут использовать.
Ответы 1
Если рассматриваемый меньший тип — это unsigned char или тип с тем же представлением, один из вариантов — просто использовать memset():
uint8_t values[8];
memset(values, new_value, 8);
Производительность будет зависеть от компилятора и реализации. Любой разумный компилятор должен распознавать вызовы библиотек, такие как memset(), и генерировать для них оптимальный код.
Если рассматриваемый тип больше unsigned char, это исключает memset(), но на ум приходит пара других способов.
Вы можете использовать каламбур, чтобы вместо того, чтобы каждый раз присваивать значение, назначать первые 2 по отдельности, затем переинтерпретировать первые 2 как более крупный тип, чтобы присвоить первые 2 вторым 2 за один шаг и так далее:
union Components {
uint16_t u16[8];
uint32_t u32[4];
uint64_t u64[2];
} values;
values.u16[1] = values.u16[0] = new_value;
values.u32[1] = values.u32[0];
values.u64[1] = values.u64[0];
Аналогичный эффект можно использовать с побитовыми операторами:
uint64_t value = new_value;
value |= value << 16;
value |= value << 32;
В некотором смысле, приведенное выше имеет логарифмическое количество шагов, если количество сделанных копий умещается в одном регистре.
Последний способ — просто использовать умножение на магическое число. Двоичное умножение эквивалентно добавлению к результату для каждого бита числа либо 0, если бит равен 0, либо другого числа, сдвинутого на позицию бита. Таким образом, мы можем использовать это, создавая маски, которые содержат 0 бит для всех битов, кроме начала того места, где нам нужна копия нашего исходного числа.
uint8_t new_value;
uint64_t values = 0x0101010101010101U * new_value; // 8 copies of new_value concatenated together
uint16_t new_value;
uint64_t values = 0x0001000100010001U * new_value; // 4 copies of new_value concatenated together
К фактическим 16-битным значениям можно получить индивидуальный доступ в форме массива, используя union, аналогичный второму примеру:
union Components values;
values.u64[1] = values.u64[0] = 0x0001000100010001U * new_value; // This can be made even better if you have a futuristic machine with 128-bit registers
Если вам разрешено использовать встроенные функции SSE2, вы можете использовать _mm_set1_epi16(new_value) или _mm_set1_epi8(new_value) для 16 или 8-битных new_values соответственно. Вы можете обернуть его #ifdef _SSE2__ для переносимости (за исключением Visual Studio).
Примечание. Техника умножения немного лучше , чем метод копирования в два раза больше при использовании в памяти, но значительно превосходит вариант при использовании в регистре. Оба значительно превосходят индивидуальный метод.
Это вопросы и ответы, предназначенные для документирования известных мне решений, но если у кого-то есть еще одно или есть что добавить, не стесняйтесь добавлять свой собственный ответ.