[algorithm] 건너 뛰기 목록 대 이진 검색 트리

첫째, 무작위 데이터 구조를 최악의 경우 보장하는 구조와 비교할 수는 없습니다.

건너 뛰기 목록은 Dean and Jones의 “건너 뛰기 목록과 이진 검색 트리 간의 이중성 탐색”에 자세히 설명되어있는 RBST (Random Balanced Binary Search Tree)와 동일 합니다.

다른 방법으로, 최악의 성능을 보장하는 결정적 스킵 목록을 가질 수도 있습니다. Munro et al.

위의 주장과 달리 동시 프로그래밍에서 잘 작동하는 이진 검색 트리 (BST)를 구현할 수 있습니다. 동시성에 중점을 둔 BST의 잠재적 인 문제는 RB (Red-Black) 트리에서와 마찬가지로 밸런싱에 대한 보장을 쉽게 얻을 수 없다는 것입니다. (그러나 “표준”, 즉 무작위, 건너 뛰기 목록은 이러한 보장도 제공하지 않습니다.) 항상 균형을 유지하는 것과 좋은 (그리고 프로그래밍하기 쉬운) 동시 액세스간에 균형이 있으므로 완화 된 RB 트리가 일반적으로 사용됩니다 좋은 동시성이 필요할 때 휴식은 바로 나무를 재조정하지 않는 것입니다. 다소 오래된 (1998 년) 설문 조사에 대해서는 Hanke의“동시 레드-블랙 트리 알고리즘의 성능 ” [ps.gz]을 참조하십시오 .

이것에 대한 가장 최근의 개선 중 하나는 소위 색채 나무입니다 (기본적으로 검은 색이 1이고 빨간색이 0이되도록 가중치가 있지만 사이에 값을 허용합니다). 그리고 크로마 트리는 스킵 목록에 어떻게 대응합니까? Brown et al. “비 차단 트리에 대한 일반적인 기술” (2014)은 다음과 같이 말해야합니다.

128 개의 스레드를 사용하는 알고리즘은 잠금 기반 AVL 트리 인 Bronson et al. 63 ~ 224 %, 소프트웨어 트랜잭션 메모리 (STM)를 13 ~ 134 배 사용하는 RBT

추가 편집 : Pugh의 잠금 기반 건너 뛰기 목록은 프레이저와 해리스 (2007) “잠금없는 동시 프로그래밍” 에서 자체 잠금이없는 버전 (여기의 상단 답변에서 충분히 주장 된 지점)에 가깝게 벤치 마크되었습니다 . 또한 우수한 동시 작동을 위해 조정되었습니다. cf. Pugh의 “건너 뛰기 목록의 동시 유지 보수” 는 다소 경미한 방법입니다. 그럼에도 불구하고 한 가지 최신 / 2009 논문 “단순 낙관적 건너 뛰기 목록 알고리즘”Pugh의 잠금 기반 동시 건너 뛰기 목록 구현을 제안하는 Herlihy et al.은 Pugh에게 충분한 설득력을 제공하지 않는다고 비난했다. Herlihy et al. 건너 뛰기 목록의 간단한 잠금 기반 구현은 실제로 JDK의 잠금없는 구현뿐만 아니라 확장도 실패하지만 높은 경합 (50 % 삽입, 50 % 삭제 및 0 % 조회)에 대해서만 표시됩니다. 해리스는 전혀 테스트하지 않았습니다. 프레이저와 해리스는 75 % 조회, 12.5 % 삽입 및 12.5 % 삭제 (~ 500K 요소의 건너 뛰기 목록) 만 테스트했습니다. Herlihy et al.의 간단한 구현. 또한 테스트 한 경합이 낮은 경우 (70 % 조회, 20 % 삽입, 10 % 삭제) JDK의 잠금없는 솔루션에 가깝습니다. 스킵 목록을 충분히 크게 만들 때 (예 : 200K에서 2M 요소로)이 잠금에 대한 잠금없는 솔루션을 실제로 능가했습니다. Herlihy et al. Pugh의 증거에 대한 그들의 끊기를 극복하고 그의 구현도 테스트했지만 아아 그들은 그렇게하지 않았습니다.

EDIT2 : 모든 벤치 마크에서 (2015 년 출판) 머더로드를 발견했습니다 : Gramoli의 “동기화에 대해 알고 싶었던 것 이상. Synchrobench, 동시 알고리즘에 대한 동기화의 영향 측정” :이 질문과 관련된 발췌 이미지가 있습니다.

“Algo.4″는 상기 언급 된 브라운 등의 전구체 (구형, 2011 버전)이다. (2014 버전이 얼마나 좋거나 나쁜지 모르겠습니다). “Algo.26″은 위에서 언급 한 Herlihy입니다. 보시다시피 업데이트시 휴지통에 버리고 여기에서 사용 된 Intel CPU는 원래 용지의 Sun CPU보다 훨씬 나쁩니다. “Algo.28″은 JDK의 ConcurrentSkipListMap입니다. 다른 CAS 기반 건너 뛰기 목록 구현과 비교했을 때 기대했던 것만 큼 효과적이지 않습니다. 높은 관심을 받고있는 승자는 Crain 등의 잠금 기반 알고리즘 (!!) 인 “Algo.2″입니다. 에서 “A 경합 친화적 이진 검색 나무” 와 “Algo.30″에서 “회전 skiplist”입니다 “멀티 코어에 대한 대수 데이터 구조” . “. Gramoli는이 세 가지 승자 알고리즘 논문의 공동 저자입니다. “Algo.27″은 Fraser의 건너 뛰기 목록의 C ++ 구현입니다.

Gramoli의 결론은 유사한 건너 뛰기 목록을 망치는 것보다 CAS 기반 동시 트리 구현을 망치는 것이 훨씬 쉽다는 것입니다. 그리고 수치에 따르면 동의하기가 어렵습니다. 이 사실에 대한 그의 설명은 다음과 같습니다.

잠금이없는 트리를 설계하는 데 어려움은 여러 참조를 원자 적으로 수정하는 데 어려움이 있습니다. 스킵 목록은 후속 포인터를 통해 서로 연결된 타워로 구성되며 각 노드는 바로 아래에있는 노드를 가리 킵니다. 각 노드는 후계자 타워와 그 아래에 후속 노드가 있기 때문에 종종 트리와 유사한 것으로 간주되지만, 하향 포인터는 일반적으로 불변이므로 노드의 원자 수정을 단순화한다는 것이 큰 차이점입니다. 이 차이는 아마도 스킵이 그림 [위]에서 볼 수 있듯이 경쟁이 심한 나무보다 성능이 뛰어난 나무를 나열하는 이유 일 것입니다.

이러한 어려움을 극복하는 것은 브라운 등의 최근 연구에서 주요 관심사였다. 그들은
다중 레코드 LL / SC 복합 “기본 체”를 구축 하는 것에 대해 완전히 별도의 (2013) 논문 “비 차단 데이터 구조를위한 기본적 프리미티브”를 보유하고 있으며,이를 LLX / SCX라고하며 자체적으로 (기계 수준) CAS를 사용하여 구현됩니다. 브라운 등. 이 LLX / SCX 빌딩 블록을 2014 년 (2011 년은 아님) 동시 트리 구현에 사용했습니다.

“핫 스폿 없음”/ CF (Contention-friendly) 건너 뛰기 목록 의 기본 아이디어를 여기에 요약 할 가치가 있다고 생각 합니다.. 편안한 RB 트리 (및 유사한 동시성 데이터 구조)에서 필수적인 아이디어를 추가합니다. 타워는 더 이상 삽입 즉시 구축되지 않지만 경합이 줄어들 때까지 지연됩니다. 반대로, 높은 타워를 삭제하면 많은 경합이 발생할 수 있습니다. 이것은 Pugh의 1990 년 동시 건너 뛰기 목록 논문만큼이나 거꾸로 관찰되었는데, 이는 Pugh가 삭제에 대한 포인터 반전을 도입 한 이유입니다 (스킵 목록에 대한 Wikipedia의 페이지가 여전히 오늘날까지 언급되지 않은 경건). CF 건너 뛰기 목록은이 단계를 한 단계 더 높이고 높은 타워의 상위 레벨 삭제를 지연시킵니다. CF 스킵리스트의 두 가지 지연된 조작은 (CAS 기반) 별도의 가비지 콜렉터와 유사한 스레드에 의해 수행되며, 작성자는이를 “적응 스레드”라고합니다.

Synchrobench 코드 (테스트 된 모든 알고리즘 포함)는 https://github.com/gramoli/synchrobench 에서 사용할 수 있습니다 . 최신 브라운 외. 구현 (위에 포함되지 않음)은 http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java 에서 사용 가능합니다 . 누구나 32 개 이상의 코어 시스템을 사용할 수 있습니까? J / K 제 요점은 당신이 스스로를 실행할 수 있다는 것입니다.

---

답변