`std :: kill_dependency`의 기능은 무엇이며 왜 사용해야합니까?

`std :: kill_dependency`의 기능은 무엇이며 왜 사용해야합니까?

---

저는 새로운 C ++ 11 메모리 모델에 대해 std::kill_dependency읽었 으며 함수 (§29.3 / 14-15)에 대해 알아 보았습니다. 왜 내가 그것을 사용하고 싶어하는지 이해하기 위해 고군분투하고 있습니다.

N2664 제안 에서 예제를 찾았 지만 별 도움이되지 않았습니다.

그것은하지 않고 코드를 보여주는 것으로 시작한다 std::kill_dependency. 여기에서 첫 번째 줄은 두 번째 줄에 종속성을 전달하고 색인 작업에 종속성을 전달한 다음 do_something_with함수에 종속성을 전달 합니다.

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[r2]);

std::kill_dependency두 번째 줄과 인덱싱 사이의 종속성을 끊는 데 사용 하는 추가 예제가 있습니다.

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[std::kill_dependency(r2)]);

내가 알 수있는 한, 이것은 인덱싱과 호출 do_something_with이 두 번째 줄 이전에 정렬 된 종속성이 아님 을 의미합니다 . N2664에 따르면 :

이를 통해 컴파일러 do_something_with는 예를 들어의 값을 예측하는 예측 최적화를 수행 하여 에 대한 호출을 재정렬 할 수 있습니다 a[r2].

do_something_with값을 호출하기 a[r2]위해서는 필요합니다. 가상적으로 컴파일러가 배열이 0으로 채워져 있음을 "인식"하면 원하는 do_something_with(0);대로 다른 두 명령어에 대한 호출을 최적화 하고이 호출을 재정렬 할 수 있습니다 . 다음 중 하나를 생성 할 수 있습니다.

// 1
r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(0);
// 2
r1 = x.load(memory_order_consume);
do_something_with(0);
r2 = r1->index;
// 3
do_something_with(0);
r1 = x.load(memory_order_consume);
r2 = r1->index;

내 이해가 맞습니까?

do_something_with다른 방법으로 다른 스레드와 동기화하는 경우 x.load호출 및이 다른 스레드 의 순서와 관련하여 이것은 무엇을 의미 합니까?

내 이해가 정확하다고 가정 할 때 여전히 나를 괴롭히는 한 가지가 있습니다. 코드를 작성할 때 어떤 이유로 종속성을 없애도록 선택하게 될까요?

---

memory_order_consume의 목적은 컴파일러가 잠금없는 알고리즘을 손상시킬 수있는 특정 불행한 최적화를 수행하지 않도록하는 것입니다. 예를 들어 다음 코드를 고려하십시오.

int t;
volatile int a, b;

t = *x;
a = t;
b = t;

준수 컴파일러는 이것을 다음과 같이 변환 할 수 있습니다.

a = *x;
b = *x;

따라서 a는 b와 같지 않을 수 있습니다. 또한 다음을 수행 할 수 있습니다.

t2 = *x;
// use t2 somewhere
// later
t = *x;
a = t2;
b = t;

를 사용 load(memory_order_consume)하면로드되는 값의 사용이 사용 지점 이전에 이동되지 않도록합니다. 다시 말해,

t = x.load(memory_order_consume);
a = t;
b = t;
assert(a == b); // always true

표준 문서는 구조의 특정 필드를 주문하는 데에만 관심이있는 경우를 고려합니다. 예는 다음과 같습니다.

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[std::kill_dependency(r2)]);

이는 컴파일러에게 다음과 같이 효과적으로 수행 할 수 있음을 지시합니다.

predicted_r2 = x->index; // unordered load
r1 = x; // ordered load
r2 = r1->index;
do_something_with(a[predicted_r2]); // may be faster than waiting for r2's value to be available

또는 이것도 :

predicted_r2 = x->index; // unordered load
predicted_a  = a[predicted_r2]; // get the CPU loading it early on
r1 = x; // ordered load
r2 = r1->index; // ordered load
do_something_with(predicted_a);

If the compiler knows that do_something_with won't change the result of the loads for r1 or r2, then it can even hoist it all the way up:

do_something_with(a[x->index]); // completely unordered
r1 = x; // ordered
r2 = r1->index; // ordered

This allows the compiler a little more freedom in its optimization.

---

In addition to the other answer, I will point out that Scott Meyers, one of the definitive leaders in the C++ community, bashed memory_order_consume pretty strongly. He basically said that he believed it had no place in the standard. He said there are two cases where memory_order_consume has any effect:

• Exotic architectures designed to support 1024+ core shared memory machines.
• The DEC Alpha

Yes, once again, the DEC Alpha finds its way into infamy by using an optimization not seen in any other chip until many years later on absurdly specialized machines.

The particular optimization is that those processors allow one to dereference a field before actually getting the address of that field (i.e. it can look up x->y BEFORE it even looks up x, using a predicted value of x). It then goes back and determines whether x was the value it expected it to be. On success, it saved time. On failure, it has to go back and get x->y again.

Memory_order_consume tells the compiler/architecture that these operations have to happen in order. However, in the most useful case, one will end up wanting to do (x->y.z), where z doesn't change. memory_order_consume would force the compiler to keep x y and z in order. kill_dependency(x->y).z tells the compiler/architecture that it may resume doing such nefarious reorderings.

99.999% of developers will probably never work on a platform where this feature is required (or has any effect at all).

---

The usual use case of kill_dependency arises from the following. Suppose you want to do atomic updates to a nontrivial shared data structure. A typical way to do this is to nonatomically create some new data and to atomically swing a pointer from the data structure to the new data. Once you do this, you are not going to change the new data until you have swung the pointer away from it to something else (and waited for all readers to vacate). This paradigm is widely used, e.g. read-copy-update in the Linux kernel.

Now, suppose the reader reads the pointer, reads the new data, and comes back later and reads the pointer again, finding that the pointer hasn't changed. The hardware can't tell that the pointer hasn't been updated again, so by consume semantics he can't use a cached copy of the data but has to read it again from memory. (Or to think of it another way, the hardware and compiler can't speculatively move the read of the data up before the read of the pointer.)

This is where kill_dependency comes to the rescue. By wrapping the pointer in a kill_dependency, you create a value that will no longer propagate dependency, allowing accesses through the pointer to use the cached copy of the new data.

---

My guess is that it enables this optimization.

r1 = x.load(memory_order_consume);
do_something_with(a[r1->index]);

ReferenceURL : https://stackoverflow.com/questions/7150395/what-does-stdkill-dependency-do-and-why-would-i-want-to-use-it