Почему встроенная функция имеет более низкую эффективность, чем встроенная функция?
Я задавал вопрос о массивах в InterviewBit. В этом вопросе я сделал встроенную функцию, возвращающую абсолютное значение целого числа. Но мне сказали, что мой алгоритм неэффективен при его представлении. Но когда я перешел на использование abs() из библиотеки С++, он дал правильный вердикт ответа.
Вот моя функция, получившая неэффективный вердикт -
inline int abs(int x){return x>0 ? x : -x;}
int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
int l = X.size();
int i = 0;
int ans = 0;
while (i<l-1){
ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
i++;
}
return ans;
}
Вот тот, который получил правильный ответ -
int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
int l = X.size();
int i = 0;
int ans = 0;
while (i<l-1){
ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
i++;
}
return ans;
}
Почему это произошло, поскольку я думал, что встроенные функции выполняются быстрее всего, поскольку вызов не выполняется? Или сайт имеет ошибку? И если сайт правильный, то что использует С++ abs(), что быстрее, чем inline abs()?
Ответы
Ответ 1
Ваш abs выполняет ветвление на основе условия. Хотя встроенный вариант просто удаляет бит знака из целого числа, скорее всего, используя только пару инструкций. Возможный пример сборки (взято из здесь):
cdq
xor eax, edx
sub eax, edx
cdq копирует знак регистра eax для регистрации edx. Например, если это положительное число, edx будет равен нулю, в противном случае edx будет 0xFFFFFF, что означает -1. Операция xor с номером начала ничего не изменит, если это положительное число (любое число xor 0 не изменится). Однако, когда eax отрицательный, eax xor 0xFFFFFF дает (не eax). Последний шаг - вычесть edx из eax. Опять же, если eax положителен, edx равен нулю, а конечное значение остается неизменным. Для отрицательных значений (~ eax) - (-1) = -eax, который является желаемым значением.
Как вы можете видеть, этот подход использует только три простые арифметические инструкции и вообще не имеет условного разветвления.
Изменить. После некоторых исследований выяснилось, что многие встроенные реализации абс используют один и тот же подход, return __x >= 0 ? __x : -__x;, и такой шаблон является очевидной целью оптимизации компилятора, чтобы избежать ненужного разветвления.
Однако это не оправдывает использование пользовательской реализации abs, поскольку оно нарушает принцип DRY, и никто не может гарантировать, что ваша реализация будет так же хорош для более сложных сценариев и/или необычных платформ. Как правило, следует подумать о переписывании некоторых функций библиотеки только тогда, когда в существующей реализации обнаружена определенная проблема с производительностью или какой-либо другой дефект.
Edit2: просто переключение с int на float показывает значительное снижение производительности:
float libfoo(float x)
{
return ::std::fabs(x);
}
andps xmm0, xmmword ptr [rip + .LCPI0_0]
И пользовательская версия:
inline float my_fabs(float x)
{
return x>0.0f?x:-x;
}
float myfoo(float x)
{
return my_fabs(x);
}
movaps xmm1, xmmword ptr [rip + .LCPI1_0] # xmm1 = [-0.000000e+00,-0.000000e+00,-0.000000e+00,-0.000000e+00]
xorps xmm1, xmm0
xorps xmm2, xmm2
cmpltss xmm2, xmm0
andps xmm0, xmm2
andnps xmm2, xmm1
orps xmm0, xmm2
онлайн-компилятор
Ответ 2
Я не согласен с их вердиктом. Они явно неверны.
В текущем, оптимизирующем компиляторе, оба решения производят точно такой же вывод. И даже если бы они не производили точно такой же, они могли бы создать эффективный код, как библиотечный (может быть немного удивительно, что все соответствует: алгоритм, используемые регистры. фактическая реализация библиотеки такая же, как и OP one?).
Никакой разумный оптимизирующий компилятор не создаст ветвь в коде abs() (если это можно сделать без ветки), как предполагает другой ответ. Если компилятор не оптимизирует, то он может не встроить библиотеку abs(), поэтому она также не будет быстрой.
Оптимизация abs() - одна из самых простых задач для компилятора (просто добавьте в нее запись в оптимизаторе подкачки и сделайте).
Кроме того, я видел реализации библиотек в прошлом, где abs() были реализованы как функция non-inline, library (это было давно, хотя).
Доказательство того, что обе реализации одинаковы:
GCC:
myabs:
mov edx, edi ; argument passed in EDI by System V AMD64 calling convention
mov eax, edi
sar edx, 31
xor eax, edx
sub eax, edx
ret
libabs:
mov edx, edi ; argument passed in EDI by System V AMD64 calling convention
mov eax, edi
sar edx, 31
xor eax, edx
sub eax, edx
ret
Clang:
myabs:
mov eax, edi ; argument passed in EDI by System V AMD64 calling convention
neg eax
cmovl eax, edi
ret
libabs:
mov eax, edi ; argument passed in EDI by System V AMD64 calling convention
neg eax
cmovl eax, edi
ret
Visual Studio (MSVC):
libabs:
mov eax, ecx ; argument passed in ECX by Windows 64-bit calling convention
cdq
xor eax, edx
sub eax, edx
ret 0
myabs:
mov eax, ecx ; argument passed in ECX by Windows 64-bit calling convention
cdq
xor eax, edx
sub eax, edx
ret 0
ICC:
myabs:
mov eax, edi ; argument passed in EDI by System V AMD64 calling convention
cdq
xor edi, edx
sub edi, edx
mov eax, edi
ret
libabs:
mov eax, edi ; argument passed in EDI by System V AMD64 calling convention
cdq
xor edi, edx
sub edi, edx
mov eax, edi
ret
Посмотрите сами в учебнике компиляторов Godbolt, где вы можете проверить машинный код, сгенерированный различными компиляторами. (Ссылка любезно предоставлена Питером Кордесом.)
Ответ 3
Ваше решение может быть "чище" учебником, если вы использовали стандартную версию библиотеки, но я считаю, что оценка неверна. Нет действительно хорошей, оправданной причины отказа вашего кода.
Это один из тех случаев, когда кто-то формально прав (по учебнику), но настаивает на том, чтобы знать единственное правильное решение самым глупым способом, а не принимать альтернативное решение и говорить "... но это здесь было бы вы знаете".
Технически, это правильный, практичный подход, чтобы сказать "используйте стандартную библиотеку, для чего она предназначена, и она, вероятно, оптимизирована настолько, насколько может быть". Несмотря на то, что часть "оптимизированная, насколько может быть", в некоторых ситуациях может быть ошибочной из-за некоторых ограничений, которые стандарт ставит на определенные алогорифмы и/или контейнеры.
Теперь мнения, передовая практика и религия в стороне. Фактически, если вы сравните два подхода...
int main(int argc, char**)
{
40f360: 53 push %rbx
40f361: 48 83 ec 20 sub $0x20,%rsp
40f365: 89 cb mov %ecx,%ebx
40f367: e8 a4 be ff ff callq 40b210 <__main>
return std::abs(argc);
40f36c: 89 da mov %ebx,%edx
40f36e: 89 d8 mov %ebx,%eax
40f370: c1 fa 1f sar $0x1f,%edx
40f373: 31 d0 xor %edx,%eax
40f375: 29 d0 sub %edx,%eax
//}
int main(int argc, char**)
{
40f360: 53 push %rbx
40f361: 48 83 ec 20 sub $0x20,%rsp
40f365: 89 cb mov %ecx,%ebx
40f367: e8 a4 be ff ff callq 40b210 <__main>
return (argc > 0) ? argc : -argc;
40f36c: 89 da mov %ebx,%edx
40f36e: 89 d8 mov %ebx,%eax
40f370: c1 fa 1f sar $0x1f,%edx
40f373: 31 d0 xor %edx,%eax
40f375: 29 d0 sub %edx,%eax
//}
... они приводят к точно к тем же, идентичным инструкциям.
Но даже если компилятор использовал сравнение, за которым следует условное перемещение (которое он может выполнять в более сложных "назначениях ветвления" и которое он будет делать, например, в случае min/max), это возможно, один процессорный цикл или так медленнее, чем бит-хаки, поэтому, если вы не сделаете это несколько миллионов раз, утверждение "неэффективно" в любом случае сомнительно.
Один промах кеша, и вы в сто раз превысили условный ход.
Есть допустимые аргументы для и против любого подхода, о которых я не буду говорить подробно. Я хочу сказать, что отказ от решения ОП "совершенно неправ" из-за такой мелочной, несущественной детали довольно ограниченный.
EDIT:
(забавные мелочи)
Я просто попробовал, для удовольствия и без прибыли, в своем ящике Linux Mint, который использует несколько более старую версию GCC (5.4 по сравнению с 7.1 выше).
Из-за меня включая <cmath> без большой мысли (эй, функция типа abs очень четко принадлежит математике, не так ли!), а не <cstdlib>, которая содержит целую перегрузку, результат был, ну... удивительно. Вызов функции библиотеки намного уступал оболочке с одним выражением.
Теперь, защищая стандартную библиотеку, если вы включите <cstdlib>, то, опять же, полученный результат будет точно идентичным в любом случае.
Для справки, тестовый код выглядел так:
#ifdef DRY
#include <cmath>
int main(int argc, char**)
{
return std::abs(argc);
}
#else
int abs(int v) noexcept { return (v >= 0) ? v : -v; }
int main(int argc, char**)
{
return abs(argc);
}
#endif
... в результате
4004f0: 89 fa mov %edi,%edx
4004f2: 89 f8 mov %edi,%eax
4004f4: c1 fa 1f sar $0x1f,%edx
4004f7: 31 d0 xor %edx,%eax
4004f9: 29 d0 sub %edx,%eax
4004fb: c3 retq
Теперь, по-видимому, довольно легко попасть в ловушку невольно используя неправильную стандартную библиотечную функцию (я продемонстрировал, насколько легко это я!). И все, что без малейшего предупреждения от компилятора, например "эй, вы знаете, вы используете перегрузку double для целочисленного значения (ну, очевидно, нет никакого предупреждения, это действительное преобразование).
Имея это в виду, может быть еще одно "оправдание", почему ОП, обеспечивающий его собственный однострочный лайнер, не был настолько ужасно плохим и неправильным. В конце концов, он мог совершить ту же ошибку.
