조건에서 변수를 업데이트하는 가장 빠른 방법은 무엇입니까?

조건에서 변수를 업데이트하는 가장 빠른 방법은 무엇입니까?

---

포인터 ptr및 조건이 cond있습니다. 나는 재설정 할 수있는 가장 빠른 방법을 필요로 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];

하지만 이것이 진행하는 가장 좋은 방법인지 모르겠습니다.

---

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

순진한 솔루션은 의심 할 여지없이 대부분의 경우에서 가장 빠릅니다. 최신 파이프 라인 프로세서에서 느릴 수있는 분기가 있지만 분기가 잘못 예측 된 경우에만 느립니다 . 오늘날 분기 예측자는 매우 훌륭하기 때문에의 값을 cond매우 예측할 수없는 경우가 아니면 간단한 조건 분기가 코드를 작성하는 가장 빠른 방법 일 가능성이 높습니다.

그렇지 않은 경우 좋은 컴파일러 는이를 알고 대상 아키텍처를 고려하여 코드를 더 나은 것으로 최적화 할 수 있어야합니다. gnasher729의 요점으로 이동 합니다. 간단한 방법으로 코드를 작성하고 최적화는 최적화 도구의 손에 맡깁니다.

이것은 일반적으로 좋은 조언이지만 때로는 너무 멀리 걸립니다. 실제로이 코드의 속도에 관심이 있다면 컴파일러가 실제로 수행하는 작업을 확인하고 확인해야합니다. 생성중인 객체 코드를 확인하고 그것이 합리적인지 그리고 함수의 코드가 인라인되고 있는지 확인하십시오.

그러한 조사는 상당히 드러날 수 있습니다. 예를 들어 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의 예측 가능성 에 대한 지식이 없습니다 . 간단한 경우를 가정하고 분기 예측이 사용자 편이며 코드 B 대신 코드 A를 생성합니다.

예측할 수없는 조건으로 인해 컴파일러가 분기없는 코드를 생성하도록 권장하기로 결정한 경우 다음을 시도 할 수 있습니다.

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지침을하지만, 두 사람은 도덕적으로 동일합니다. 연타는 우리가 위의 생성 본 것과 같은 조건 이동로 변환합니다.) 이것은 최선의 코드가 될 수있다 그러나 분기를 피해야한다면 소스 코드의 가독성을 어느 정도 유지하면서 테스트 된 모든 컴파일러에서 정상 출력을 생성한다는 점을 고려하십시오.

---

The lowest-hanging fruit here isn't what you think it is. As discussed in several other answers, reset_if_true is going to be compiled to machine code that is as fast as you can reasonably expect to get for what it does. If that's not fast enough, you need to start thinking about changing what it does. I see two options there, one easy, one not so easy:

1. Change the calling convention:

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

   and then change the caller(s) to read something like

   ptr_var = reset_if_true(ptr_var, expression);
   

   What this does is make it more likely that ptr_var will get to live in a register during the critical innermost loop that's calling reset_if_true millions of times a second, and there won't be any memory accesses associated with it. ptr_var getting forced out to memory is the most expensive thing in your code the way it is right now; even more expensive than potentially mispredicted branches. (A sufficiently good compiler may make this transformation for you provided reset_if_true is inlinable, but it's not always possible for it to do so.)

2. Change the surrounding algorithm, so that reset_if_true does not get called millions of times a second anymore.

   Since you didn't tell us what the surrounding algorithm is, I can't help you with that. I can, however, tell you that doing something involving checking a condition millions of times a second, probably indicates an algorithm with quadratic time complexity or worse, and that always means you should at least think about finding a better one. (There may not be a better one, alas.)

---

As long as we have sizeof(size_t) == sizeof(void*), nullptr being represented in binary as 0 and size_t using all bits (or having std::uintptr_t), you can do this:

// 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 );
}

Note, however, that the time the cast from bool to size_t takes is very much implementation-dependent and might take a branch in itself.

---

The code is absolutely straightforward.

You certainly make things a lot faster by inlining the function (if the compiler didn't inline it on its own). For example, inlining could mean that the pointer variable that you are setting to null could stay in a register.

Other than that, this code is so straightforward, if there are any tricks that could be used to make it faster, the compiler would use them.

---

Update: I reimplemented my answer.

In the following code the idea is converting the pointer into a number and multiplying it by a number (cond). Note inline used. Multiplication may help using an architecture that uses pipelining.

#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;
}

Example usage:

#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(); }

Compile using these flags: -O3 -std=c++14. The output is:

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

It might have memory alignment problems when such options are used in the compiler commandline -s FORCE_ALIGNED_MEMORY=1 . Also see reinterpret_cast. Don't forget to use -O3.

The cond can be any non-zero value. There is some room for performance improvement here if we know it is not other than 0 or 1. In that case, you can use int another integer type for cond.

PS. This is an updated answer. The previous answer, as I already clearly mentioned in my answer, had issues. The solution is using intptr_t, and of course inline.

Compiler options used:

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

ReferenceURL : https://stackoverflow.com/questions/37945626/what-is-the-fastest-way-to-update-a-variable-on-a-condition