Ускорение производительности цикла, выполняющего беззнаковую операцию long long по модулю.

Question

Мне нужно выполнить множество операций по нахождению остатков деления unsigned long long число по 16-битному модулю:

unsigned long long largeNumber;
long residues[100];
unsigned long modules[100];
intiModules(modules); //set different 16-bit values

for(int i = 0; i < 100; i++){
     residues[i] = largeNumber % modules[i];
}

Как я могу ускорить этот цикл?

Число итераций невелико (32–128), но этот цикл выполняется очень часто, поэтому его скорость имеет решающее значение.

Answer 1

Деление на константу (а их всего 65536) можно выполнить путем умножения обратной величины, за которой/предшествует некоторая тонкая настройка.Поскольку этот метод точен для ограниченного диапазона, можно использовать некоторые методы, чтобы уменьшить 64-битный операнд до гораздо меньшего значения (которое по-прежнему соответствует исходному значению):

// pseudo code -- not c
a = 0x1234567890abcdefULL;
a = 0x1234 << 48 + 0x5678 << 32 + 0x90ab << 16 + 0xcdef;

a % N === ((0x1234 * (2^48 % N) +     // === means 'is congruent'
           (0x5678 * (2^32 % N)) +    // ^ means exponentation
           (0x90ab * (2^16 % N)) + 
           (0xcdef * 1)) % N;

Промежуточное значение можно вычислить только с помощью (небольших) умножений, а окончательный остаток (%N) можно вычислить с помощью обратного умножения.

Answer 2

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

Прирост (или его отсутствие, некоторые компиляторы выполняют эту оптимизацию за вас) зависит от архитектуры/компилятора.

На моей машине изменение цикла при сохранении количества операций от

for(int i = 0; i < 500000000; i++){
    residues[i % 100] = largeNumber % modules[i % 100];
}

к

for(int i = 0; i < 500000000; i+=5){
    residues[(i+0) % 100] = largeNumber % modules[(i+0) % 100];
    residues[(i+1) % 100] = largeNumber % modules[(i+1) % 100];
    residues[(i+2) % 100] = largeNumber % modules[(i+2) % 100];
    residues[(i+3) % 100] = largeNumber % modules[(i+3) % 100];
    residues[(i+4) % 100] = largeNumber % modules[(i+4) % 100];
}

с gcc -O2 выигрыш составляет ~15%.(500000000 вместо 100, чтобы увидеть более значительную разницу во времени)