Возможна пользовательская встроенная функция для x64 вместо встроенной сборки?

В настоящее время я экспериментирую с созданием высокооптимизированных многоразовых функций для моей библиотеки. Например, я пишу функцию "степень двойки" следующим образом:

template<class IntType>  
inline bool is_power_of_two( const IntType x )
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

Это переносимая реализация с низким уровнем обслуживания в виде встроенного шаблона C ++. Этот код компилируется VC ++ 2008 в следующий код с ветвями:

is_power_of_two PROC
    test    rcx, rcx
    je  SHORT $LN3@is_power_o
    lea rax, QWORD PTR [rcx-1]
    test    rax, rcx
    jne SHORT $LN3@is_power_o
    mov al, 1
    ret 0
$LN3@is_power_o:
    xor al, al
    ret 0
is_power_of_two ENDP

Я нашел также реализацию отсюда: "The bit twiddler", который будет закодирован в сборка для x64 следующая:

is_power_of_two_fast PROC
    test rcx, rcx
    je  SHORT NotAPowerOfTwo
    lea rax, [rcx-1]
    and rax, rcx
    neg rax
    sbb rax, rax
    inc rax
    ret
NotAPowerOfTwo:
    xor rax, rax
    ret
is_power_of_two_fast ENDP

Обе подпрограммы, написанные отдельно от C ++, я тестировал в сборочном модуле (файл .asm), а вторая работает примерно на 20% быстрее!

И все же накладные расходы на вызов функции значительны: если я сравниваю вторую реализацию сборки "is_power_of_two_fast" со встроенной версией функции шаблона, последняя работает быстрее, несмотря на ветвления!

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

Теперь вопрос: могу ли я реализовать более быструю версию is_power_of_two_fast как пользовательскую встроенную функцию или что-то подобное, чтобы ее можно было использовать встроенно? Или, в качестве альтернативы, можно ли каким-то образом заставить компилятор создавать версию функции с низкой ветвью?


c++ 64-bit assembly inline-assembly intrinsics
person Angel Sinigersky    schedule 04.04.2011    source источник
comment
GCC и ICC по-прежнему позволяют встроенную сборку   -  person Gunther Piez    schedule 04.04.2011
comment
Избегайте ветки, используя & вместо &&.   -  person Hans Passant    schedule 04.04.2011
comment
@drhirsch: спасибо, я имею в виду. @Hans Passant: Я уже пробовал, но это приводит к более медленному коду (слишком много инструкций).   -  person Angel Sinigersky    schedule 05.04.2011

Ответы (4)


arrow_upward
2
arrow_downward

Даже VC 2005 может создавать код с инструкциями sbb.

для кода C

bool __declspec(noinline) IsPowOf2(unsigned int a)
{
    return (a>=1)&((a&(a-1))<1);
}

компилируется в следующие

00401000  lea         eax,[ecx-1] 
00401003  and         eax,ecx 
00401005  cmp         eax,1 
00401008  sbb         eax,eax 
0040100A  neg         eax  
0040100C  cmp         ecx,1 
0040100F  sbb         ecx,ecx 
00401011  add         ecx,1 
00401014  and         eax,ecx 
00401016  ret
person D Gershuny    schedule 16.04.2012

arrow_upward
3
arrow_downward

Нет, вы не можете реализовать какие-либо собственные встроенные функции, все они встроены в компилятор. Это не только встроенные инструкции, но и компилятор также знает семантику встроенной функции и адаптирует код для другого окружающего кода.

Одна из причин удаления встроенной сборки для x86-64 заключается в том, что вставка сборки в середину функции мешает оптимизатору и часто приводит к менее хорошо оптимизированному коду вокруг кода ассемблера. Там легко может быть чистый убыток!

Единственное реальное использование встроенных функций - это "интересные" специальные инструкции, которые компилятор не может сгенерировать из конструкций C или C ++, таких как BSF или BSR. Почти все остальное будет работать лучше с использованием встроенных функций, таких как ваш шаблон выше.

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

Доверьтесь своему компилятору (тм)!

person Bo Persson    schedule 04.04.2011

arrow_upward
1
arrow_downward

Встроенные функции VC10 x64 не очень помогут в этом простом случае. У вас есть динамическое ветвление из-за оператора &&, который является оператором раннего выхода. Во многих случаях (ваш случай является прекрасным примером) лучше избегать ветвления, вычисляя результат для всех ветвей, а затем применяя маску, чтобы выбрать подходящий. Код cpp с маскировкой будет выглядеть так:

template<typename T_Type>
inline bool isPowerOfTwo(T_Type const& x)
{
    // static type checking for the example
    static_assert( std::is_integral<T_Type>::value && std::is_unsigned<T_Type>::value, "limited to unsigned types for the example" );
    typedef std::make_signed<T_Type>::type s_Type;

    // same as yours but with no branching
    return bool(  ((s_Type( s_Type(x != 0) << (s_Type(sizeof(T_Type)<<3u)-1) )) >> (s_Type(s_Type(sizeof(T_Type)<<3u)-1)))  & ((x & (x - 1)) == 0)  );
}

В приведенном выше коде я не проверяю, является ли число отрицательным или нет для подписанных типов. Снова простая маска сделает свое дело, выполнив арифметический сдвиг вправо (numBit-1) раз, чтобы получить значение (~ 0) для отрицательных чисел и 0 для положительных.

person a.lasram    schedule 19.10.2011
comment
К сожалению, то, что вы предлагаете, не сильно отличается от исходной функции C ++. Компиляция с выводом сборки показывает, что VC ++ 2008 использует тестовую инструкцию при компиляции вашего кода, и ветки все еще существуют. - person Angel Sinigersky; 11.11.2011

arrow_upward
0
arrow_downward

Единственный путь вперед - это немного отступить и начать смотреть на картину в целом. Либо прекратите реализацию микрооптимизированного API, либо переходите к более крупным вызовам API, оптимизированным для MASM64, YASM, NASM и т. Д.

Если вы используете один из более мощных ассемблеров, вы можете превратить небольшие функции в макросы, поэтому в основном замените встроенную функцию ассемблера на основе заголовка C / C ++ во включаемый файл ассемблера.

person Steve-o    schedule 04.04.2011