Я хочу объединить два целых числа, используя только битовые операции, так как мне нужна максимальная эффективность. Доступны различные ответы, но они недостаточно быстры. Я хочу, чтобы реализация использовала только битовые операции, такие как сдвиг влево или и т. д. Пожалуйста, помогите мне как это сделать.
пример
int x=32;
int y=12;
int result=3212;
У меня есть внедрение AES на FPGA. Мне нужно это в моей системе, чтобы сократить время, затрачиваемое на выполнение некоторых задач.
Наиболее эффективный способ сделать это, вероятно, выглядит примерно так:
uint32_t uintcat (uint32_t ms, uint32_t ls)
{
uint32_t mult=1;
do
{
mult *= 10;
} while(mult <= ls);
return ms * mult + ls;
}
Тогда пусть компилятор позаботится об оптимизации. Вероятно, мало что можно улучшить, так как это основание 10, которое плохо ладит с различными инструкциями компьютера, такими как сдвиг.
РЕДАКТИРОВАТЬ: ЭТАЛОННЫЙ ТЕСТ
Intel i7-3770 2 3,4 GHz
OS: Windows 7/64
Mingw, GCC version 4.6.2
gcc -O3 -std=c99 -pedantic-errors -Wall
10 million random values, from 0 to 3276732767.
Результат (приблизительно):
Algorithm 1: 60287 micro seconds
Algorithm 2: 65185 micro seconds
Используемый эталонный код:
#include <stdint.h>
#include <stdio.h>
#include <windows.h>
#include <time.h>
uint32_t uintcat (uint32_t ms, uint32_t ls)
{
uint32_t mult=1;
do
{
mult *= 10;
} while(mult <= ls);
return ms * mult + ls;
}
uint32_t myConcat (uint32_t a, uint32_t b) {
switch( (b >= 10000000) ? 7 :
(b >= 1000000) ? 6 :
(b >= 100000) ? 5 :
(b >= 10000) ? 4 :
(b >= 1000) ? 3 :
(b >= 100) ? 2 :
(b >= 10) ? 1 : 0 ) {
case 1: return a*100+b; break;
case 2: return a*1000+b; break;
case 3: return a*10000+b; break;
case 4: return a*100000+b; break;
case 5: return a*1000000+b; break;
case 6: return a*10000000+b; break;
case 7: return a*100000000+b; break;
default: return a*10+b; break;
}
}
static LARGE_INTEGER freq;
static void print_benchmark_results (LARGE_INTEGER* start, LARGE_INTEGER* end)
{
LARGE_INTEGER elapsed;
elapsed.QuadPart = end->QuadPart - start->QuadPart;
elapsed.QuadPart *= 1000000;
elapsed.QuadPart /= freq.QuadPart;
printf("%lu micro seconds", elapsed.QuadPart);
}
int main()
{
const uint32_t TEST_N = 10000000;
uint32_t* data1 = malloc (sizeof(uint32_t) * TEST_N);
uint32_t* data2 = malloc (sizeof(uint32_t) * TEST_N);
volatile uint32_t* result_algo1 = malloc (sizeof(uint32_t) * TEST_N);
volatile uint32_t* result_algo2 = malloc (sizeof(uint32_t) * TEST_N);
srand (time(NULL));
// Mingw rand() apparently gives numbers up to 32767
// worst case should therefore be 3,276,732,767
// fill up random data in arrays
for(uint32_t i=0; i<TEST_N; i++)
{
data1[i] = rand();
data2[i] = rand();
}
QueryPerformanceFrequency(&freq);
LARGE_INTEGER start, end;
// run algorithm 1
QueryPerformanceCounter(&start);
for(uint32_t i=0; i<TEST_N; i++)
{
result_algo1[i] = uintcat(data1[i], data2[i]);
}
QueryPerformanceCounter(&end);
// print results
printf("Algorithm 1: ");
print_benchmark_results(&start, &end);
printf("\n");
// run algorithm 2
QueryPerformanceCounter(&start);
for(uint32_t i=0; i<TEST_N; i++)
{
result_algo2[i] = myConcat(data1[i], data2[i]);
}
QueryPerformanceCounter(&end);
// print results
printf("Algorithm 2: ");
print_benchmark_results(&start, &end);
printf("\n\n");
// sanity check both algorithms against each other
for(uint32_t i=0; i<TEST_N; i++)
{
if(result_algo1[i] != result_algo2[i])
{
printf("Results mismatch for %lu %lu. Expected: %lu%lu, algo1: %lu, algo2: %lu\n",
data1[i],
data2[i],
data1[i],
data2[i],
result_algo1[i],
result_algo2[i]);
}
}
// clean up
free((void*)data1);
free((void*)data2);
free((void*)result_algo1);
free((void*)result_algo2);
}
Битовые операции используют двоичное представление чисел. Однако то, что вы пытаетесь достичь, - это объединить числа в десятичной записи. Обратите внимание, что объединение десятичных представлений имеет мало общего с объединением двоичных представлений. Хотя теоретически можно решить проблему с помощью бинарных операций, я уверен, что это будет далеко не самый эффективный способ.
Нам нужно вычислить a*10^N + b очень быстро.
Битовые операции - не лучшая идея для его оптимизации (даже с использованием таких трюков, как := (a‹‹1) + (a‹‹3) ‹=> a := a*10, поскольку компилятор может сделать это сам).
Первая задача — вычислить 10^N, но вычислять его не нужно, всего 9 возможных значений.
Вторая проблема состоит в том, чтобы вычислить N из b (длина представления 10). Если ваши данные имеют равномерное распределение, вы можете минимизировать количество операций в среднем.
Проверить b ‹= 10^9, b ‹= 10^8, ..., b ‹= 10 с помощью ()?: (это быстрее, чем if( ) после оптимизаций, имеет гораздо более простую грамматику и функциональность), вызовите результат N. Затем сделайте switch(N) со строками «return a*10^N + b» (где 10^N — константа). Насколько я знаю, switch() с 3-4 "case" работает быстрее, чем такая же конструкция if() после оптимизаций.
unsigned int myConcat(unsigned int& a, unsigned int& b) {
switch( (b >= 10000000) ? 7 :
(b >= 1000000) ? 6 :
(b >= 100000) ? 5 :
(b >= 10000) ? 4 :
(b >= 1000) ? 3 :
(b >= 100) ? 2 :
(b >= 10) ? 1 : 0 ) {
case 1: return a*100+b; break;
case 2: return a*1000+b; break;
case 3: return a*10000+b; break;
case 4: return a*100000+b; break;
case 5: return a*1000000+b; break;
case 6: return a*10000000+b; break;
case 7: return a*100000000+b; break;
default: return a*10+b; break;
// I don't really know what to do here
//case 8: return a*1000*1000*1000+b; break;
//case 9: return a*10*1000*1000*1000+b; break;
}
}
Как видите, операций в среднем 2-3 + оптимизация здесь очень эффективна. Я сравнил его с предложением Лундина, вот результат. 0 мс против 100 мс
Если вы заботитесь о конкатенации десятичных цифр, вы можете просто сделать это во время печати и последовательно преобразовать оба числа в последовательность цифр. например Как напечатать целое число в программировании на уровне ассемблера без printf из библиотеки c? показывает эффективную функцию C, а также asm. Вызовите его дважды в один и тот же буфер.
Ответ @Lundin зацикливается, увеличивая степень 10, чтобы найти правильный десятичный сдвиг, то есть линейный поиск правильной степени 10. Если он вызывается очень часто, поэтому таблица поиска может оставаться горячей в кеше, ускорение может быть возможно.
Если вы можете использовать GNU C __builtin_clz (подсчет начальных нулей ) или какой-либо другой способ быстрого нахождения позиции MSB правого ввода (ls, наименее значащая часть результирующей конкатенации), вы можете начать поиск правильного mult из таблицы поиска с 32 элементами. (И вам нужно проверить не более одной итерации, так что это не цикл.)
Большинство распространенных современных архитектур ЦП имеют инструкцию HW, которую компилятор может использовать напрямую или с небольшой обработкой для реализации clz. https://en.wikipedia.org/wiki/Find_first_set#Hardware_support. (И на всех, кроме x86, результат хорошо определен для ввода 0, но, к сожалению, GNU C не дает нам переносимого доступа к этому.)
Если таблица остается горячей в кэше L1d, это может быть очень хорошо. Дополнительная задержка clz и поиска в таблице сравнима с парой итераций цикла (например, на современном x86, таком как Skylake или Ryzen, где bsf или tzcnt — задержка в 3 цикла, задержка L1d — 4 или 5 циклов, imul задержка составляет 3 цикла.)
Конечно, на многих архитектурах (включая x86) умножение на 10 дешевле, чем на переменную времени выполнения с использованием сдвига и сложения. 2 инструкции LEA на x86 или add+lsl на ARM/AArch64 с использованием сдвинутого ввода для выполнения tmp = x + x*4 с добавлением. Таким образом, на процессорах Intel мы рассматриваем только цепочку зависимостей с циклом из 2 циклов, а не 3. Но процессоры AMD имеют более медленный LEA при использовании масштабированного индекса.
Это не очень хорошо для небольших чисел. Но это может уменьшить число неверных прогнозов ветвления, если потребуется не более одной итерации. Это даже делает возможной реализацию без ответвлений. И это означает меньшую общую работу для больших нижних частей (большие степени 10). Но большие целые числа легко переполнятся, если вы не используете более широкий тип результата.
К сожалению, 10 не является степенью числа 2, поэтому одна только позиция старшего бита не может дать нам точную степень числа 10, на которую нужно умножить. например все числа от 64 до 127 имеют MSB = 1<<7, но некоторые из них имеют 2 десятичных знака, а некоторые — 3. Поскольку мы хотим избежать деления (потому что оно требует умножения на магическую константу и сдвига старшей половины), мы хотим всегда начинать с меньшей мощности 10 и смотреть, достаточно ли это.
Но, к счастью, битовое сканирование позволяет нам с точностью до степени 10, поэтому нам больше не нужен цикл.
Вероятно, я бы не стал писать часть с _lzcnt_u32 или ARM __clz, если бы заранее узнал об уловке clz(a|1), позволяющей избежать проблем с input=0. Но я это сделал и немного поиграл с исходным кодом, чтобы попытаться получить более приятный ассемблер от gcc и clang. Индексация таблицы на clz или BSR в зависимости от целевой платформы делает ее немного беспорядочной.
#include <stdint.h>
#include <limits.h>
#include <assert.h>
// builtin_clz matches Intel's docs for x86 BSR: garbage result for input=0
// actual x86 HW leaves the destination register unmodified; AMD even documents this.
// but GNU C doesn't let us take advantage with intrinsics.
// unless you use BMI1 _lzcnt_u32
// if available, use an intrinsic that gives us a leading-zero count
// *without* an undefined result for input=0
#ifdef __LZCNT__ // x86 CPU feature
#include <immintrin.h> // Intel's intrinsics
#define HAVE_LZCNT32
#define lzcnt32(a) _lzcnt_u32(a)
#endif
#ifdef __ARM__ // TODO: do older ARMs not have this?
#define HAVE_LZCNT32
#define lzcnt32(a) __clz(a) // builtin, no header needed
#endif
// Some POWER compilers define `__cntlzw`?
// index = msb position, or lzcnt, depending on which the HW can do more efficiently
// defined later; one or the other is unused and optimized out, depending on target platform
// alternative: fill this at run-time startup
// with a loop that does mult*=10 when (x<<1)-1 > mult, or something
//#if INDEX_BY_MSB_POS == 1
__attribute__((unused))
static const uint32_t catpower_msb[] = {
10, // 1 and 0
10, // 2..3
10, // 4..7
10, // 8..15
100, // 16..31 // 2 digits even for the low end of the range
100, // 32..63
100, // 64..127
1000, // 128..255 // 3 digits
1000, // 256..511
1000, // 512..1023
10000, // 1024..2047
10000, // 2048..4095
10000, // 4096..8191
10000, // 8192..16383
100000, // 16384..32767
100000, // 32768..65535 // up to 2^16-1, enough for 16-bit inputs
// ... // fill in the rest yourself
};
//#elif INDEX_BY_MSB_POS == 0
// index on leading zeros
__attribute__((unused))
static const uint32_t catpower_lz32[] = {
// top entries overflow: 10^10 doesn't fit in uint32_t
// intentionally wrong to make it easier to spot bad output.
4000000000, // 2^31 .. 2^32-1 2*10^9 .. 4*10^9
2000000000, // 1,073,741,824 .. 2,147,483,647
// first correct entry
1000000000, // 536,870,912 .. 1,073,741,823
// ... fill in the rest
// for testing, skip until 16 leading zeros
[16] = 100000, // 32768..65535 // up to 2^16-1, enough for 16-bit inputs
100000, // 16384..32767
10000, // 8192..16383
10000, // 4096..8191
10000, // 2048..4095
10000, // 1024..2047
1000, // 512..1023
1000, // 256..511
1000, // 128..255
100, // 64..127
100, // 32..63
100, // 16..31 // low end of the range has 2 digits
10, // 8..15
10, // 4..7
10, // 2..3
10, // 1
// lzcnt32(0) == 32
10, // 0 // treat 0 as having one significant digit.
};
//#else
//#error "INDEX_BY_MSB_POS not set correctly"
//#endif
//#undef HAVE_LZCNT32 // codegen for the other path, for fun
static inline uint32_t msb_power10(uint32_t a)
{
#ifdef HAVE_LZCNT32 // 0-safe lzcnt32 macro available
#define INDEX_BY_MSB_POS 0
// a |= 1 would let us shorten the table, in case 32*4 is a lot nicer than 33*4 bytes
unsigned lzcnt = lzcnt32(a); // 32 for a=0
return catpower_lz32[lzcnt];
#else
// only generic __builtin_clz available
static_assert(sizeof(uint32_t) == sizeof(unsigned) && UINT_MAX == (1ULL<<32)-1, "__builtin_clz isn't 32-bit");
// See also https://foonathan.net/blog/2016/02/11/implementation-challenge-2.html
// for C++ templates for fixed-width wrappers for __builtin_clz
#if defined(__i386__) || defined(__x86_64__)
// x86 where MSB_index = 31-clz = BSR is most efficient
#define INDEX_BY_MSB_POS 1
unsigned msb = 31 - __builtin_clz(a|1); // BSR
return catpower_msb[msb];
//return unlikely(a==0) ? 10 : catpower_msb[msb];
#else
// use clz directly while still avoiding input=0
// I think all non-x86 CPUs with hardware CLZ do define clz(0) = 32 or 64 (the operand width),
// but gcc's builtin is still documented as not valid for input=0
// Most ISAs like PowerPC and ARM that have a bitscan instruction have clz, not MSB-index
// set the LSB to avoid the a==0 special case
unsigned clz = __builtin_clz(a|1);
// table[32] unused, could add yet another #ifdef for that
#define INDEX_BY_MSB_POS 0
//return unlikely(a==0) ? 10 : catpower_lz32[clz];
return catpower_lz32[clz]; // a|1 avoids the special-casing
#endif // optimize for BSR or not
#endif // HAVE_LZCNT32
}
uint32_t uintcat (uint32_t ms, uint32_t ls)
{
// if (ls==0) return ms * 10; // Another way to avoid the special case for clz
uint32_t mult = msb_power10(ls); // catpower[clz(ls)];
uint32_t high = mult * ms;
#if 0
if (mult <= ls)
high *= 10;
return high + ls;
#else
// hopefully compute both and then select
// because some CPUs can shift and add at the same time (x86, ARM)
// so this avoids having an ADD *after* the cmov / csel, if the compiler is smart
uint32_t another10 = high*10 + ls;
uint32_t enough = high + ls;
return (mult<=ls) ? another10 : enough;
#endif
}
Или с lzcnt (включено -march=haswell или более поздней версией или некоторыми архитектурами AMD),
# clang7.0 -O3 for x86-64 SysV, -march=skylake -mno-lzcnt
uintcat(unsigned int, unsigned int):
mov eax, esi
or eax, 1
bsr eax, eax # 31-clz(ls|1)
mov ecx, dword ptr [4*rax + catpower_msb]
imul edi, ecx # high = mult * ms
lea eax, [rdi + rdi]
lea eax, [rax + 4*rax] # retval = high * 10
cmp ecx, esi
cmova eax, edi # if(mult>ls) retval = high (drop the *10 result)
add eax, esi # retval += ls
ret
Факторизация последнего add из обеих сторон тройки является пропущенной оптимизацией, добавляющей 1 цикл задержки после cmov. Мы можем умножить на 10 и сложить так же дешево, как просто умножить на 10 на процессорах Intel:
uintcat(unsigned int, unsigned int):
# clang doesn't try to break the false dependency on EAX; gcc uses xor eax,eax
lzcnt eax, esi # C source avoids the |1, saving instructions
mov ecx, dword ptr [4*rax + catpower_lz32]
imul edi, ecx # same as above from here on
lea eax, [rdi + rdi]
lea eax, [rax + 4*rax]
cmp ecx, esi
cmova eax, edi
add eax, esi
ret
Таким образом, задержка high + ls будет работать параллельно с задержкой high*10 + ls, обе необходимы в качестве входных данных для cmov.
... same start # hand-optimized version that clang should use
imul edi, ecx # high = mult * ms
lea eax, [rdi + 4*rdi] # high * 5
lea eax, [rsi + rdi*2] # retval = high * 10 + ls
add edi, esi # tmp = high + ls
cmp ecx, esi
cmova eax, edi # if(mult>ls) retval = high+ls
ret
Ветви GCC вместо использования CMOV для последнего условия. GCC также путает 31-clz(a|1), вычисляя clz с BSR и XOR с 31. Но затем вычитая это из 31. И у него есть дополнительные инструкции mov. Как ни странно, gcc, кажется, лучше справляется с этим кодом BSR, когда доступен lzcnt, даже если он предпочитает его не использовать.
clang без проблем оптимизирует двойную инверсию 31-clz и просто использует BSR напрямую.
Для PowerPC64 clang также делает ассемблер без ответвлений. gcc делает нечто подобное, но с веткой как на x86-64.
Использование clz(ls|1) >> 1 или этого +1 должно работать, потому что 4 ‹ 10. В таблице всегда требуется не менее 3 записей, чтобы получить еще одну цифру. Я не исследовал это. (И уже потратил на это больше времени, чем собирался. :P)
uintcat:
.Lfunc_gep0:
addis 2, 12, .TOC.-.Lfunc_gep0@ha
addi 2, 2, .TOC.-.Lfunc_gep0@l
ori 6, 4, 1 # OR immediate
addis 5, 2, catpower_lz32@toc@ha
cntlzw 6, 6 # CLZ word
addi 5, 5, catpower_lz32@toc@l # static table address
rldic 6, 6, 2, 30 # rotate left and clear immediate (shift and zero-extend the CLZ result)
lwzx 5, 5, 6 # Load Word Zero eXtend, catpower_lz32[clz]
mullw 3, 5, 3 # mul word
cmplw 5, 4 # compare mult, ls
mulli 6, 3, 10 # mul immediate
isel 3, 3, 6, 1 # conditional select high vs. high*10
add 3, 3, 4 # + ls
clrldi 3, 3, 32 # zero extend, clearing upper 32 bits
blr # return
Или еще раз сдвиньте вправо, чтобы получить начальную точку цикла. например. mult = clz(ls) >= 18 ? 100000 : 10; или 3-х или 4-х ходовая цепочка из if.
Или зациклиться на mult *= 100, и после выхода из этого цикла разобраться, хотите ли вы old_mult * 10 или mult. (т.е. проверьте, не зашли ли вы слишком далеко). Это сокращает количество итераций вдвое для четного числа цифр.
(Остерегайтесь возможного бесконечного цикла на большом ls, который может привести к переполнению результата. Если mult *= 100 преобразуется в 0, он всегда останется <= ls для ls = 1000000000, например.)
Сжатие таблицы
