Это довольно сложно, но оставайся со мной.Я не могу привести ни одного конкретного места, откуда я получил это, кроме «27 лет опыта кодирования».
В исходной задаче числовая строка установлена в натуральные целые числа 0,1,2,3,4,5,6 ... Однако мы заботимся только о числах, которые делятся на 3, поэтому давайте переопределим нашу числовую строку, чтобы в ней было только три значения: {2,3,4} и переназначим числовую строку так, чтобы:
0 => 4
1 => 2
2 => 3
3 => 4
4 => 2
5 => 3
6 => 4
.. и т. д.
Вы заметите, что числа, которые делятся на 3, отображаются в 4 в нашей последовательности.Зачем использовать {2,3,4}?Значение 4 равно 100 в двоичном виде, что означает, что любой элемент с его третьим установленным битом будет делиться на 3. Это легко проверить с помощью битовых операций.
Поскольку мы используем 2,3,4 в качестве триной последовательностимы можем уменьшить размер нашего элемента массива до 4 бит.Мы определим массив как 8-битные значения, но вдвое меньше необходимого нам размера в байтах (плюс 1 в случае, если это массив нечетного размера), и сохраним в массиве по два элемента.Операции добавления и сравнения можно выполнять как операции SIMD (одиночная инструкция, несколько данных), увеличивая или проверяя до 16 элементов на одну итерацию цикла, используя некоторые умные битовые операции.
В этом и заключается концепция.Теперь перейдем к коду.
Сначала нам нужно выделить и инициализировать наш массив.
unsigned char *arr = malloc(n/2 + 1);
// Init all element values to 4:
memset(&arr, 0x44, n/2 + 1);
Мы собираемся увеличивать 16 элементов за один раз, приведя блок из 8 массивов.байтов к uint_64, добавьте 0x1111111111111111 и затем перейдите к следующему блоку.Повторите с 32-битной, 16-битной, 8-битной и 4-битной математикой, чтобы до 8, 4, 2 или 1 осталось до конца операции.
Перед каждым шагом все, что имеетзначение 4 должно быть уменьшено на 3 перед приращением, чтобы числа оставались в правильном положении.
Вот код (не проверенный) для команды приращения:
/**
@param p
p is the address of the byte with the first aligned element to be incremented, &arr[A/2] when A is even, &arr[A/2]+1 when A is odd.
@param j
j is the number of elements to increment. (B-A) when A is even, (B-A-1) when A is odd.
*/
void increment_aligned_block(unsigned char *p, int j)
uint64_t fours;
while (j>16) {
// Find the ones that are value 4
fours = *p & 0x4444444444444444;
// Decrement each that matches by 3
*p -= (fours >> 1 | fours >> 2);
// Add 1 to each of the 16 array elements in the block.
(uint64_t)(*p) += 0x1111111111111111;
p += 8; j -= 16;
}
if (j >= 8) {
// repeat the above for 32-bits (8 elements)
// left as an exercise for the reader.
p += 4; j -= 8;
}
if (j >= 4) {
// repeat the above for 16-bits (4 elements)
// left as an exercise for the reader.
p += 2; j -= 4;
}
if (j >= 2) {
// repeat the above for 8-bits (2 elements)
// left as an exercise for the reader.
p += 1; j -= 2;
}
if (j == 1) {
// repeat the above for 8-bits (1 elements)
// left as an exercise for the reader.
}
}
Для сравненияuse:
/**
@param p
p is the address of the byte with the first aligned element to be counted, &arr[A/2] when A is even, &arr[A/2]+1 when A is odd.
@param j
j is the number of elements to count. (B-A) when A is even, (B-A-1) when A is odd.
*/
int count_aligned_block(unsigned char *p, int j)
int count = 0;
uint64_t divisible_map;
while (j > 16) {
// Find the values of 4 in the block
divisible_map = (uint64_t)(*p) & 0x4444444444444444;
// Count the number of 4s in the block,
// 8-bits at a time
while (divisible_map) {
switch (divisible_map & 0x44) {
case 0x04:
case 0x40:
count++;
break;
case 0x44:
count += 2;
break;
default:
break;
}
divisible_map >>= 8;
}
}
// Repeat as above with 32, 16, 8 and 4-bit math.
// Left as an exercise to the reader
return count;
}
Возможно, вы заметили, что функции называются foo_aligned_block, а p должен быть байтом первого выровненного элемента.Что это такое?Поскольку мы упаковываем два элемента на байт, индекс начального элемента должен быть выровнен по четному числу.Если команда в файле 0 0 30, то мы можем вызвать increment_algined_block(&arr[A/2], 30), без проблем.Однако, если команда в файле - 0 1 30, нам нужен дополнительный код для обработки первого элемента без выравнивания по индексу 1, а затем вызов increment_aligned_block(&arr[A/2 + 1], 29).Опять же, оставлено в качестве упражнения для читателя.
Хочу отметить, что это не самый оптимальный вариант.
Нераспределенный доступ обычно довольно дорогой.То есть чтение 8-байтового значения из 8-байтового выровненного адреса происходит быстрее, чем из не выровненного адреса.Мы можем добавить дополнительные оптимизации только к вызову foo_aligned_block(), так что все обращения будут гарантированно выровнены.