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

Каков самый быстрый способ обновления переменной при условии?

У меня есть указатель ptr и условие cond. Мне нужен самый быстрый способ reset ptr, если cond есть true или сохранить ptr без изменений, если cond - false. Текущая реализация тривиально:

void reset_if_true(void*& ptr, bool cond)
{
    if (cond)
        ptr = nullptr;
}

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

Я думал о чем-то, что избавилось от ветки, например:

void* p[] = { ptr, nullptr };
ptr = p[cond];

но я не уверен, что это лучший способ продолжить.

4b9b3361

ОТВЕТЫ

Ответ 1

void reset_if_true(void*& ptr, bool cond)
{
    if (cond)
        ptr = nullptr;
}

Наивное решение, несомненно, будет самым быстрым в большинстве случаев. Хотя у этого есть ветвь, которая может быть медленной на современных конвейерных процессорах, это только медленно, если ветвь неверно предсказана. Поскольку предсказатели ветвления очень хороши в наши дни, если значение cond крайне непредсказуемо, вероятно, что простая условная ветка является самым быстрым способом записи кода.

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

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

Такое исследование может быть довольно показательным. Например, рассмотрим x86-64, где ветки могут быть довольно дорогими в случаях, когда отклонение от ветвления (это действительно единственный момент, когда это интересный вопрос, поэтому допустим, что cond полностью непредсказуем). Почти все компиляторы собираются создать для наивной реализации следующее:

reset_if_true(void*&, bool):
    test   sil, sil              ; test 'cond'
    je     CondIsFalse
    mov    QWORD PTR [rdi], 0    ; set 'ptr' to nullptr, and fall through
  CondIsFalse:
    ret

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

reset_if_true(void*&, bool):
    xor    eax, eax              ; pre-zero the register RAX
    test   sil, sil              ; test 'cond'
    cmove  rax, QWORD PTR [rdi]  ; if 'cond' is false, set the register RAX to 'ptr'
    mov    QWORD PTR [rdi], rax  ; set 'ptr' to the value in the register RAX
    ret                          ;  (which is either 'ptr' or 0)

Условные ходы имеют относительно высокую задержку, поэтому они значительно медленнее, чем хорошо предсказанная ветвь, но они могут быть быстрее, чем полностью непредсказуемая ветвь. Вы ожидали бы, что компилятор узнает об этом при ориентации на архитектуру x86, но не имеет (по крайней мере, на этом простом примере) знания о предсказуемости cond. Он предполагает простой случай, что предсказание ветвления будет на вашей стороне и генерирует код A вместо кода B.

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

void reset_if_true_alt(void*& ptr, bool cond)
{
    ptr = (cond) ? nullptr : ptr;
}

Это преуспевает в том, чтобы убедить современные версии Clang генерировать ветвящийся код B, но это полная пессимизация в GCC и MSVC. Если вы не проверили сгенерированную сборку, вы бы этого не знали. Если вы хотите заставить GCC и MSVC генерировать нераспаковывающийся код, вам придется больше работать. Например, вы можете использовать вариант, опубликованный в вопросе:

void reset_if_true(void*& ptr, bool cond)
{
    void* p[] = { ptr, nullptr };
    ptr = p[cond];
}

При таргетинге на x86 все компиляторы генерируют для этого нераспространяемый код, но это не особо красивый код. Фактически, ни один из них не создает условные ходы. Вместо этого вы получаете множественный доступ к памяти, чтобы построить массив:

reset_if_true_alt(void*&, bool):
    mov     rax, QWORD PTR [rdi]
    movzx   esi, sil
    mov     QWORD PTR [rsp-16], 0
    mov     QWORD PTR [rsp-24], rax
    mov     rax, QWORD PTR [rsp-24+rsi*8]
    mov     QWORD PTR [rdi], rax
    ret

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

Если вы все еще отчаянно пытались устранить ветвь на MSVC или GCC, вам нужно было бы сделать что-то более уродливое, включающее переинтерпретирование битов указателя и их скручивание. Что-то вроде:

void reset_if_true_alt(void*& ptr, bool cond)
{
    std::uintptr_t p = reinterpret_cast<std::uintptr_t&>(ptr);
    p &= -(!cond);
    ptr = reinterpret_cast<void*>(p);
}

Это даст вам следующее:

reset_if_true_alt(void*&, bool):
    xor   eax, eax
    test  sil, sil
    sete  al
    neg   eax
    cdqe
    and   QWORD PTR [rdi], rax
    ret

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

Как только я спустился по крошечной кроличьей дыре, я смог заставить MSVC и GCC использовать условные инструкции перемещения. По-видимому, они не делали эту оптимизацию, потому что мы имели дело с указателем:

void reset_if_true_alt(void*& ptr, bool cond)
{
    std::uintptr_t p = reinterpret_cast<std::uintptr_t&>(ptr);
    ptr = reinterpret_cast<void*>(cond ? 0 : p);
}

reset_if_true_alt(void*&, bool):
    mov    rax, QWORD PTR [rdi]
    xor    edx, edx
    test   sil, sil
    cmovne rax, rdx
    mov    QWORD PTR [rdi], rax
    ret

Учитывая задержку CMOVNE и аналогичное количество инструкций, я не уверен, действительно ли это будет быстрее предыдущей версии. Тест, который вы использовали, скажет вам, было ли это.

Точно так же, если мы свернем условие, мы сохраняем один доступ к памяти:

void reset_if_true_alt(void*& ptr, bool cond)
{
   std::uintptr_t c = (cond ? 0 : -1);
   reinterpret_cast<std::uintptr_t&>(ptr) &= c;
}

reset_if_true_alt(void*&, bool):
     xor    esi, 1
     movzx  esi, sil
     neg    rsi
     and    QWORD PTR [rdi], rsi
     ret

(что GCC. MSVC делает что-то немного другое, предпочитая свою характерную последовательность команд neg, sbb, neg и dec, но эти два являются морально эквивалентными. Clang преобразует его в тот же условный перейдите, что мы увидели, что он генерирует выше.) Это может быть лучший код, если нам нужно избегать ветвей, учитывая, что он генерирует разумный вывод для всех тестируемых компиляторов при сохранении (некоторой степени) удобочитаемости в исходном коде.

Ответ 2

Самые низкие висячие фрукты здесь не то, что вы думаете. Как обсуждалось в нескольких других ответах, reset_if_true собирается скомпилироваться в машинный код, который так же быстро, как вы можете разумно ожидать, получить за то, что он делает. Если это не достаточно быстро, вам нужно начать думать о том, как изменить то, что он делает. Я вижу два варианта: один легкий, один не очень простой:

  • Измените соглашение о вызове:

    template <class T>
inline T* reset_if_true(T* ptr, bool condition)
{
    return condition ? nullptr : ptr;
}

    а затем измените вызывающего (-ы), чтобы читать что-то вроде

    ptr_var = reset_if_true(ptr_var, expression);

    То, что это делает, делает более вероятным, что ptr_var будет жить в регистре во время критического самого внутреннего цикла, который вызывает reset_if_true миллионы раз в секунду, и не будет никаких связанных с ним обращений к памяти, ptr_var получение принудительного выхода в память - самая дорогая вещь в вашем коде, как сейчас; даже более дорогостоящих, чем потенциально ошибочные отрасли. (Достаточно хороший компилятор может сделать это преобразование для вас, если reset_if_true является проницаемым, но это не всегда возможно для этого.)

  • Измените окружающий алгоритм, чтобы reset_if_true больше не вызывался миллионы раз в секунду.

    Поскольку вы не сказали нам, что такое окружающий алгоритм, я не могу с этим поделать. Тем не менее, я могу сказать вам, что делать что-то, связанное с проверкой состояния миллионы раз в секунду, вероятно, указывает на алгоритм с квадратичной временной сложностью или хуже, и это всегда означает, что вы должны по крайней мере думать о поиске лучшего. (Может быть, не лучше, увы.)

Ответ 3

Пока мы имеем sizeof(size_t) == sizeof(void*), nullptr представляется в двоичном формате как 0 и size_t, используя все биты (или имеющие std:: uintptr_t), вы можете сделать это:

// typedef std::uintptr_t ptrint_t; // uncomment if you have it
typedef size_t ptrint_t; // comment out if you have std::uintptr_t

void reset_if_true(void*& ptr, bool cond)
{
    ((ptrint_t&)ptr) &= -ptrint_t( !cond );
}

Обратите внимание, однако, что время, проведенное от bool до size_t, очень сильно зависит от реализации и может принимать ветвь сама по себе.

Ответ 4

Код абсолютно прост.

Вы, конечно, делаете многое намного быстрее, добавляя функцию (если компилятор не встроил ее самостоятельно). Например, inlining может означать, что переменная указателя, которую вы устанавливаете на значение null, может оставаться в регистре.

Кроме этого, этот код настолько прост, если есть какие-то трюки, которые могут быть использованы для его ускорения, компилятор будет их использовать.

Ответ 5

Обновление: я повторил свой ответ.

В следующем коде идея превращает указатель в число и умножает его на число (cond). Примечание inline. Умножение может помочь использовать архитектуру, использующую конвейерную обработку.

#include <cstdint>

template <typename T>
inline T* reset_if_true(T* p, bool cond) {
  void* ptr = (void*)p; // The optimising compiler (-O3) will get rid of unnecessary variables.
  intptr_t ptrint;
  // This is an unrecommended practice.
  ptrint = (intptr_t)ptr;
  ptrint = ptrint * cond;  // Multiply the integer
  void* ptr2 = (void*)ptrint;
  T* ptrv = (T*)ptr2;
  return ptrv;
}

Пример использования:

#include <iostream>
#include <vector>

void test1(){
    //doulbe d = 3.141592;
    //typedef std::vector<double> mytype;
    std::vector<double> data = {3,1,4};
    auto ptr = &data;
    std::cout << (void*)ptr << std::endl;
    auto ptr2 = reset_if_true(ptr, 1);
    //auto ptr2 = (mytype*)reset_if_true(ptr, 1);
    std::cout << reset_if_true(ptr, 1) << " -> " << (*(reset_if_true(ptr, 1))).size() << std::endl;
    std::cout << reset_if_true(ptr, 2) << " -> "<< (*(reset_if_true(ptr, 2))).size() << std::endl;
    std::cout << reset_if_true(ptr, 0) <<
        " is null? " << (reset_if_true(ptr, 0) == NULL) <<  // Dont dereference a null.
        std::endl;
}


void test2(){
    double data = 3.141500123;
    auto ptr = &data;
    std::cout << (void*)ptr << std::endl;
    auto ptr2 = reset_if_true(ptr, 1);
    //auto ptr2 = (mytype*)reset_if_true(ptr, 1);
    std::cout << reset_if_true(ptr, 1) << " -> " << (*(reset_if_true(ptr, 1))) << std::endl;
    std::cout << reset_if_true(ptr, 2) << " -> "<< (*(reset_if_true(ptr, 2))) << std::endl;
    std::cout << reset_if_true(ptr, 0) <<
        " is null? " << (reset_if_true(ptr, 0) == NULL) <<  // Dont dereference a null.
        std::endl;

}

int main(){ test1(); test2(); }

Скомпилируйте эти флаги: -O3 -std=c++14. Выход:

0x5690
0x5690 -> 3
0x5690 -> 3
0 is null? 1
0x5690
0x5690 -> 3.1415
0x5690 -> 3.1415
0 is null? 1

У него могут возникнуть проблемы с выравниванием памяти, если такие параметры используются в командной строке компилятора -s FORCE_ALIGNED_MEMORY=1. Также см. reinterpret_cast. Не забудьте использовать -O3.

Конд может быть любым ненулевым значением. Здесь есть место для улучшения производительности, если мы знаем, что оно не отличается от 0 или 1. В этом случае вы можете использовать int другой целочисленный тип для cond.

PS. Это обновленный ответ. Предыдущий ответ, о котором я уже говорил в своем ответе, имел проблемы. Решение использует intptr_t и, конечно, inline.

Используемые параметры компилятора:

 em++ reset_if_true.cpp -O3 -std=c++14 -o reset_if_true.js
 node reset_if_true.js