어떻게 잠금없는 큐의 성능을 평가할 수 있습니까?

Question

http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf에 설명 된 hazard pointer 방법론을 사용하여 lockless queue를 구현했습니다. 구현시 GCC CAS 명령어를 사용하고 스레드 로컬 구조에 대해서는 pthread 로컬 저장소를 사용합니다. 이제 필자가 작성한 코드의 성능을 평가하려고합니다. 특히이 구현과 잠금 (pthread mutexes)을 사용하여 큐를 보호하는 방법을 비교하려고합니다.
"잠긴"대기열과 비교해 보았 기 때문에 여기에 묻습니다.이 방법은 잠금이없는 구현과 관련하여 더 나은 성능을 제공합니다. 내가 시험해 본 유일한 테스트는 큐에 10.000.000 랜덤 작업을 수행하는 4 코어 x86_64 시스템에서 4 스레드를 생성하는 것이며 잠금없는 버전보다 훨씬 빠릅니다.

내가 따라야 할 접근 방식을 제안 할 수 있는지, 즉 대기열에서 어떤 종류의 작업을 테스트해야하는지, 그리고 잠기지 않은 코드가 시간을 낭비하고 있는지 확인할 때 어떤 도구를 사용할 수 있는지 알고 싶습니다.

나는 또한 성능이 4 개 스레드가 주요 개선이 충분하지 않은 이유만으로 잠금없는 큐에 대한 더 나쁜 것을 가능하면 이해 할

...

감사

Answer 1

첫 번째 포인트 : 잠금없는 프로그래밍으로 반드시 속도가 향상되지는 않습니다. 잠금이 필요없는 프로그래밍 (올바르게 수행 된 경우)은 진행 상황을 보장합니다. 잠금을 사용할 때 뮤텍스를 유지하면서 하나의 스레드가 충돌 (예 : 무한 루프) 할 수 있습니다. /이 경우 뮤텍스에서 대기중인 다른 스레드가 더 이상 진행할 수 없습니다. 해당 뮤텍스가 정상 작동의 중심이라면 더 많은 작업을 수행하기 전에 전체 프로세스를 다시 시작해야 할 수도 있습니다. 잠금없는 프로그래밍으로 이러한 상황이 발생할 수 없습니다. 다른 스레드는 한 스레드에서 발생하는 상황에 관계없이 앞으로 진행할 수 있습니다. .

그렇습니다. 그렇습니다. 에 대한 희망은입니다.하지만 더 나은 성능을 요구하는 경우가 많지만, 실제로는 4 개 이상의 스레드가 필요합니다. 수십에서 수백 개의 스레드 범위에서 lock-free 코드는 잠금 기반 큐에 비해 성능이 향상 될 가능성이 훨씬 더 높습니다. 그러나 실제로 많은 것을 수행하려면 스레드를 더 많이 필요로 할뿐만 아니라 더 많은 코어도 필요합니다. 적어도 4 개의 코어와 잘 작성된 코드로 지금까지 내가 본 것을 기반으로하면 충분하지 않을 것입니다 lock-free 프로그래밍을위한 잠금에 대한 경쟁으로 인해 성능상의 이점이 많이있다.

결론 : 잠금 해제 큐가 성능상의 이점을 보여주는 가능성을 향상 시키지만, 코어가 4 개인 경우 잠금 기반 큐 (예 : 여전히 계속됩니다. 충분한 스레드와 코어를 추가하면 잠금 해제 버전이 승리 할 수밖에 없을 것입니다.필요한 스레드와 코어의 정확한 수는 예측하기 어렵지만 최소 수십 개의 관점에서 생각해야합니다.

---

¹ 적어도 뮤텍스 같은에 대한. 모든 시스템 리소스를 먹은 포크 폭탄과 같은 것이 다른 리소스에 충분한 리소스를 제공하지 못하게 할 수 있습니다.하지만 할당량 같은 것들로 인해 보편적으로 막을 수 있습니다.

Answer 2

문제는 정말 어떤 워크로드로 최적화 할 것인가? 혼잡이 드문 경우, 최신 OS의 잠금 구조가 너무 나쁘지는 않습니다. 그들은 빠른 경로에있는 한 후드에서 주로 CAS 명령어를 사용합니다. 이것들은 매우 최적화되어 있기 때문에 자신의 코드로 이길 수는 없습니다.

우리 자신의 구현은 혼잡 한 부분에서만 실질적으로 이길 수 있습니다. 평균 큐 길이가 병렬로 해킹하는 스레드의 수보다 훨씬 길면 대기열의 임의 작업 (사용자 질문에 너무 정확하지는 않음)은 아마이 작업을 수행하지 않습니다. 따라서 대기열이 너무 길거나 너무 짧은 경우에 선택되는 임의의 작업에 대한 편향을 도입하여 대기열이 짧아야합니다. 그런 다음 코어보다 적어도 두 배 많은 스레드로 시스템을 충전 할 것입니다. 이렇게하면 대기 시간 (메모리 용)이 잠금 버전에 유리하게 재생되지 않습니다.

Answer 3

내 생각에 가장 좋은 방법은 코드를 프로파일 링하여 자물쇠가있는 응용 프로그램에서 핫스팟을 식별하는 것입니다. 잠금이 해제 된 메커니즘을 소개하고 다시 같은 것을 측정하십시오. 다른 포스터에서 이미 언급했듯이 낮은 배율 (스레드 수, 응용 프로그램 크기, 코어 수)에서는 큰 향상이 없을 수 있지만 시스템을 확장 할 때 처리량 향상을 확인할 수 있습니다. 이것은 교착 상태 상황이 제거되고 스레드가 항상 앞으로 진행됩니다.

잠금없는 계획과 장점을 보는 또 다른 방법이 에는 커널/스케줄러의 참여가없고 코드의 대부분은이다 CAS에 대한 제외 유저 랜드 있기 때문에 일부 정도 하나는 애플리케이션 성능에서 시스템 상태를 디커플링 점이다 hw 명령.

는 심하게 스레드 차단 번 잠금 기본적들은 (특정 프리 오 레벨) 실행 큐의 끝에 배치된다 의미 얻어 스케줄, 경합되는 로크와

는 .Inadvertently이 시스템에 적용 링크 응용 프로그램의 상태 및 응답 시간은 이제 실행 대기열 길이에 따라 다릅니다.

그냥 2 센트입니다.