В моей программе я использую много целочисленного деления на 10 ^ х и целочисленную модульную функцию мощности 10.
Например:
unsigned __int64 a = 12345;
a = a / 100;
....
или
unsigned __int64 a = 12345;
a = a % 1000;
....
Если я собираюсь использовать правый сдвиг бит >>, тогда я получу режим 2^x, чего я не хочу.
Можно ли ускорить мою программу в функциях с целым делением и модулем?
Короткий ответ: НЕТ
Длинный ответ: НЕТ.
Объяснение:
Компилятор уже оптимизирует для вас подобные утверждения.
Если есть способ реализовать это быстрее, чем целочисленное деление, то компилятор уже знает об этом и будет применять его (при условии, что вы включите оптимизацию).
Если вы предоставите соответствующие флаги архитектуры, тогда компилятор может даже знать о конкретных сборках с быстрой архитектурой, которые обеспечат хороший трюк для выполнения операции, иначе он применит лучший трюк для общей архитектуры, для которой он был скомпилирован.
Короче говоря, компилятор будет бить человека 99.9999999% времени в любом трюке оптимизации (попробуйте не забудьте добавить флаг оптимизации и флаги архитектуры). Таким образом, лучшее, что вы обычно можете сделать, это равный компилятору.
Если каким-то чудом вы обнаружите метод, который еще не был обнаружен сборщиками, которые тесно сотрудничают с командой компилятора бэкэнд. Тогда, пожалуйста, сообщите им об этом, и следующая версия популярных компиляторов будет обновлена с помощью твика "Неизвестный (google)" деление на 10.
От http://www.hackersdelight.org/divcMore.pdf
unsigned divu10(unsigned n) {
unsigned q, r;
q = (n >> 1) + (n >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 3;
r = n - q*10;
return q + ((r + 6) >> 4);
}
Это отлично подходит для сред, в которых отсутствует какая-либо операция div, и ее только ~ 2x медленнее, чем собственное деление на моем i7 (оптимизация выключена, естественно).
Здесь немного более быстрая версия алгоритма, хотя есть и некоторые неприятные ошибки округления с отрицательными числами.
static signed Div10(signed n)
{
n = (n >> 1) + (n >> 2);
n += n < 0 ? 9 : 2;
n = n + (n >> 4);
n = n + (n >> 8);
n = n + (n >> 16);
n = n >> 3;
return n;
}
Поскольку этот метод предназначен для 32-разрядной целочисленной точности, вы можете оптимизировать большинство этих сдвигов, если вы работаете в 8-битной или 16-разрядной среде.
Вместо другой заметки, возможно, имеет смысл просто написать правильную версию Div # n # в ассемблере. Компиляторы не всегда могут предсказать конечный результат так же эффективно (хотя в большинстве случаев они делают это довольно хорошо). Поэтому, если вы работаете в среде микрочипов на низком уровне, рассмотрите ручную процедуру asm.
#define BitWise_Div10(result, n) { \
/*;n = (n >> 1) + (n >> 2);*/ \
__asm mov ecx,eax \
__asm mov ecx, dword ptr[n] \
__asm sar eax,1 \
__asm sar ecx,2 \
__asm add ecx,eax \
/*;n += n < 0 ? 9 : 2;*/ \
__asm xor eax,eax \
__asm setns al \
__asm dec eax \
__asm and eax,7 \
__asm add eax,2 \
__asm add ecx,eax \
/*;n = n + (n >> 4);*/ \
__asm mov eax,ecx \
__asm sar eax,4 \
__asm add ecx,eax \
/*;n = n + (n >> 8);*/ \
__asm mov eax,ecx \
__asm sar eax,8 \
__asm add ecx,eax \
/*;n = n + (n >> 16);*/ \
__asm mov eax,ecx \
__asm sar eax,10h \
__asm add eax,ecx \
/*;return n >> 3;}*/ \
__asm sar eax,3 \
__asm mov dword ptr[result], eax \
}
Использование:
int x = 12399;
int r;
BitWise_Div10(r, x); // r = x / 10
// r == 1239
Опять же, просто заметка. Это лучше использовать на чипах, которые действительно имеют действительно плохое разделение. На современных процессорах и современных компиляторах разделы часто оптимизируются очень умными способами.
Нет, если вы не поддерживаете архитектуру двоично-кодированного десятичного кода, и даже тогда только с большим количеством сбоев сборки.
Вы также можете посмотреть проект libdivide. Он предназначен для ускорения целочисленного деления в общем случае.
Короткий ответ: ЭТО ЗАВИСИТ.
Длительный ответ:
Да, это очень возможно, если вы можете использовать вещи, которые компилятор не может автоматически вывести. Однако, по моему опыту, это довольно редко; большинство компиляторов довольно хороши в векторизации в наши дни. Однако многое зависит от того, как вы моделируете свои данные и как хотите создать невероятно сложный код. Для большинства пользователей я бы не рекомендовал, чтобы вы столкнулись с проблемой в первую очередь.
Чтобы дать вам пример, здесь реализация x/10, где x - целое число со знаком (на самом деле это то, что будет генерировать компилятор):
int eax = value * 0x66666667;
int edx = ([overflow from multiplication] >> 2); // NOTE: use aritmetic shift here!
int result = (edx >> 31) + edx;
Если вы разобрали скомпилированный код на С++, и вы использовали константу для "10", он покажет код сборки, отражающий выше. Если вы не использовали константу, она будет генерировать idiv, что намного медленнее.
Знание вашей памяти выровнено c.q. зная, что ваш код может быть векторизован, это то, что может быть очень полезным. Обратите внимание, что это требует от вас хранения ваших данных таким образом, чтобы это было возможно.
Например, если вы хотите рассчитать сумму-div/10 всех целых чисел, вы можете сделать что-то вроде этого:
__m256i ctr = _mm256_set_epi32(0, 1, 2, 3, 4, 5, 6, 7);
ctr = _mm256_add_epi32(_mm256_set1_epi32(INT32_MIN), ctr);
__m256i sumdiv = _mm256_set1_epi32(0);
const __m256i magic = _mm256_set1_epi32(0x66666667);
const int shift = 2;
// Show that this is correct:
for (long long int i = INT32_MIN; i <= INT32_MAX; i += 8)
{
// Compute the overflow values
__m256i ovf1 = _mm256_srli_epi64(_mm256_mul_epi32(ctr, magic), 32);
__m256i ovf2 = _mm256_mul_epi32(_mm256_srli_epi64(ctr, 32), magic);
// blend the overflows together again
__m256i rem = _mm256_srai_epi32(_mm256_blend_epi32(ovf1, ovf2, 0xAA), shift);
// calculate the div value
__m256i div = _mm256_add_epi32(rem, _mm256_srli_epi32(rem, 31));
// do something with the result; increment the counter
sumdiv = _mm256_add_epi32(sumdiv, div);
ctr = _mm256_add_epi32(ctr, _mm256_set1_epi32(8));
}
int sum = 0;
for (int i = 0; i < 8; ++i) { sum += sumdiv.m256i_i32[i]; }
std::cout << sum << std::endl;
Если вы сравниваете обе реализации, вы обнаружите, что на процессоре Intel Haswell вы получите следующие результаты:
Для других степеней 10 и беззнакового деления я рекомендую прочитать статью.
Если делитель является явной константой времени компиляции (т.е. если ваш x в 10 ^ x является константой времени компиляции), нет смысла использовать что-либо еще, кроме предоставленного языком / и %. Если есть осмысленный способ ускорить их для явных полномочий 10, любой уважающий себя компилятор будет знать, как это сделать, и сделает это за вас.
Единственная ситуация, когда вы можете подумать о "настраиваемой" реализации (кроме немого компилятора), - это ситуация, когда x является значением времени выполнения. В этом случае вам понадобится какой-то десятичный сдвиг и десятичная и аналогия. Вероятно, на двоичной машине возможно ускорение, но я сомневаюсь, что вы сможете достичь чего-то практически значимого. (Если числа были сохранены в двоично-десятичном формате, тогда это было бы легко, но в "нормальных" случаях - нет.)
На самом деле вам не нужно ничего делать. Компилятор достаточно умен, чтобы оптимизировать умножения/деления с константами. Здесь вы можете найти много примеров.
Вы можете даже быстро делить на 5, а затем сдвинуть вправо 1
Если в вашей среде выполнения действительно доминируют операции с 10 x вы могли бы просто использовать базовое 10-целое представление.
В большинстве ситуаций я ожидаю, что замедление всех других целых операций (и уменьшенная точность или потенциально дополнительное использование памяти) будет считаться больше, чем более быстрые 10 x операций.