Подтвердить что ты не робот

Почему встроенная функция имеет более низкую эффективность, чем встроенная функция?

Я задавал вопрос о массивах в 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()?

4b9b3361

ОТВЕТЫ

Ответ 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 для целочисленного значения (ну, очевидно, нет никакого предупреждения, это действительное преобразование).

Имея это в виду, может быть еще одно "оправдание", почему ОП, обеспечивающий его собственный однострочный лайнер, не был настолько ужасно плохим и неправильным. В конце концов, он мог совершить ту же ошибку.