buddy allocator workshop
1.0.0
이 저장소에는 버디 할당 자의 작은 예제 구현이 포함되어 있습니다. 그들은 힙과 같은 다른 유형의 할당에 사용될 수 있지만 물리적 기억을 할당하도록 설계되었습니다. 결국, 최고의 성능은 꽃으로 합쳐질 것입니다.
먼저 레포를 복제하십시오. 그런 다음 cd 에 들어가서 cargo +nightly run 수행하여 모든 데모 할당자를 실행하십시오. 기본적으로 블록 크기는 4kib이고 블록의 양은 100 000이므로 링크 된 목록 예제의 경우 시간이 걸릴 수 있습니다. 걱정하지 마십시오. 실제로 메모리 블록 만 할당하지 않습니다. 도움을 받고 사용을 볼 수 있도록 -h 또는 --help 를 통과하십시오. 소스 코드를 편집하여 최소/최대 블록 크기 등을 변경하여 단위 테스트를 실행하고 cargo test 실행할 수 있습니다. 불행히도 아직화물 벤치 마크는 없지만 Windows 시스템에서 비과분기적으로 벤치마킹했습니다.
내장 보고서를 사용하여 다양한 구현을 타이핑하여 알고리즘을 테스트하여 Windows 시스템의 4kib 블록 (인쇄 꺼짐)으로 Gibibyte를 할당했습니다. 추가 할 다른 벤치 마크가 있으면 기여를 참조하십시오.
(MSI CX61-2QF)
| 구현 | 시간 | 처리량 |
|---|---|---|
| 목록 - 벡터 | 2 분 | ~ 8.33E-3 gib/s |
| 목록 - 이중 링크 된 목록 | 25 분 | ~ 6.66E-4 gib/s |
| RB 나무 - 벡터 | ~ 0.3S | ~ 3.33 gib/s |
| RB 나무 - 단독 링크 된 목록 | ~ 0.5s | ~ 2 gib/s |
| 비트 맵 트리 | ~ 0.07s | ~ 14.28 gib/s |
참고 : 처리량은 4kib 블록에서 1 개의 gib를 할당하는 데 걸리는 시간으로부터 추정됩니다. 복잡성> O (log n) (예 : 순진한 목록 기반 구현)를 갖는 구현의 경우 정확하지 않습니다. 더 많은 블록이 할당되면 처리량 속도가 느려집니다. 이것은 O (log n) 이하의 복잡성이있는 사람들에게는 정확해야합니다.
이 구현은 블록 순서 당 목록을 유지합니다. 사용 된 Typeof 목록보다 일반적입니다. 두 가지 종류의 목록을 사용하기로 결정했습니다 : 벡터 ( std 의 Vec )와 이중 링크 된 목록 ( LinkedList , std ). 링크 된 목록은 종종 예측 가능한 푸시 시간 (푸시 할 준비가 필요하지 않음)에 대해 소중한 반면, 벡터는 연속 메모리 블록에 요소가 할당되므로 더 나은 캐시 위치를 갖습니다. 인덱스가 목록의 시작 또는 끝에 더 가까운 지에 따라 뒷면 또는 앞면에서 반복 할 수 있으므로 단일 링크 된 목록보다 인덱싱이 더 빠르기 때문에 이중 링크 된 목록을 사용했습니다. 나는 어느 쪽이 더 나은 성능이 더 나을 것인지 확인하기 위해 둘 다 테스트하기로 결정했습니다.
구현은 재귀 적입니다. 주문 k 의 자유 블록을 할당하려면 먼저 순서 k 블록 목록에서 자유 블록을 검색합니다. 무료 목록을 유지하지 않습니다. 아무것도 발견되지 않으면, 순서 K + 1 블록을 할당하려고 시도함으로써 되풀이됩니다. 마지막으로, 어떤 시점도없는 경우 어떤 자유 블록이 포기하고 공황을 발견했다면. 하나가 되 자마자 반으로 나뉘어 주문 목록에서 원래 블록을 제거하고 반쪽을 주문 목록으로 즉시 밀어 넣습니다. 그런 다음 주문 목록에서 첫 번째 블록의 순서와 색인을 반환합니다. 이 알고리즘은 find_or_split 에서 찾을 수 있습니다.
Windows 기계의 빠르고 과학적 벤치 마크에 따르면 전체 gibibyte (1024^3 바이트)를 할당하는 데 약 2 분이 걸렸습니다. 나는 전체 벡터를 재 할당하여 요소를 밀어야 할 때 매번 몇 번의 스플릿 멈춤을 보았습니다.
std 의 이중 연결 목록비슷한 벤치 마크에 따르면 전체 gibibyte를 할당하는 데 25 분이 걸렸습니다. 이것은 벡터와 동일한 구현보다 12 배 이상 느립니다 . 그러나이 구현은 링크 된 목록에 최적화되지 않았으므로 약간 불공평합니다. 벡터를 사용한 구현과 달리 일시 정지를 발견하지 못했지만 할당은 점차 느리고 느려졌습니다.
우리는 이론적으로 이론적 으로 링크 된 목록이 벡터보다 밀기가 더 빠르지 만 여전히 벡터보다 12 배 느 렸다고 결론 지을 수 있습니다. 이는 구현이 벡터 (많은 인덱싱)에 약간 유리하거나 벡터의 캐시 위치가 높아 캐시 미스가 적었 기 때문에 링크 된 목록은 개별적으로 힙합 요소를 가지고 있기 때문에 높은 캐시 미스를 경험하기 때문일 수 있습니다.
이 구현은 모든 블록에 대해 하나의 빨간색 블랙 트리 ( intrusive_collections )와 각 주문에 대한 무료 목록을 유지합니다. 무료 목록은 STD의 Vec 및 intrusive_collections 의 SinglyLinkedList 에 대해 구현되었습니다. 이중 링크에 실질적인 이점이 없었기 때문에 싱글 링크 된 목록을 선택했습니다. (무시할 수없는) 유일한 방법은 FreeList::remove 입니다. 그러나 이것은이 무료 목록의 두 번째 요소에서 항상 최대로 호출되므로 이것을 최적화하는 데있어 실제 포인트는 없습니다. 빨간색 블랙 트리는 개별적으로 힙을 할당하여 각 노드를 할당하여 캐시 효율을 악화시킵니다. 그러나 std 의 BTreeSet / BTreeMap 과 달리 검색은 O(log n) O(log n) )이며 std 는 선형 검색을 사용합니다. 그러나 std 의 나무는 개별적으로 힙을 할당하지 않으므로 캐시 지역이 더 좋습니다. 나는 이것이 사실이지만, 친구 할당자가 엄청나게 많은 수의 블록을 처리해야하기 때문에,보다 효율적인 검색 알고리즘을 갖는 것이 더 중요하다고 결정했습니다.
구현은 재귀 적입니다. 주문 k 의 무료 블록을 할당하려면 먼저 주문 k 블록의 무료 목록에서 무료 블록을 검색합니다. 아무것도 발견되지 않으면, 순서 K + 1 블록을 할당하려고 시도함으로써 되풀이됩니다. 마지막으로, 어떤 시점도없는 경우 어떤 자유 블록이 포기하고 공황을 발견했다면. 하나가 되 자마자 나무에서 원래 블록을 제거하고 반쪽을 삽입하여 주소를 관련 무료 목록으로 밀어 넣습니다. 그런 다음 첫 번째 블록을 가리키는 커서를 반환합니다. 이 알고리즘은 find_or_split 에서 찾을 수 있습니다. 재귀의 가장 바깥 쪽 층 (실제로 재귀 find_or_split 함수라고하는 함수)에서 반환 된 블록은 사용 된 것으로 표시되어 자유 목록에서 제거됩니다.
벡터를 무료 목록으로 사용하면 전체 gib를 할당하는 데 ~ 0.3 초가 걸렸습니다. 이는 무료 목록 버전으로 링크 된 목록보다 ~ 0.2s 빠릅니다. 이것은 아마도 더 나은 캐시 로컬을 가진 벡터 때문일 것입니다.
링크 된 목록을 무료 목록으로 사용하려면 전체 GIB를 할당하는 데 ~ 0.5 초가 걸렸습니다. 벡터를 위의 무료 목록 섹션으로 참조하십시오.
이 구현은 순진한 목록 기반 구현보다 400 배 빠릅니다 (기껏해야 벡터를 무료 목록으로 사용). 이것은 아마도 벡터 또는 링크 된 목록의 검색, 인서트 및 제거보다 빠른 O(log n) 작업을 보유한 붉은 블랙 트리 때문일 수 있습니다.
이 구현은 그 자체로 엄격하게 비트 맵이 아니지만 비트 맵 시스템의 수정입니다. 본질적으로, 나무의 각 블록은 그 아래 어딘가에 가장 큰 순서 (완전히 합병)를 저장합니다. 예를 들어, 4 개의 주문으로 모두 무료 인 나무는 다음과 같습니다.
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
하나의 순서 0 블록을 할당하면 다음과 같습니다 (t is t aken) :
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
그것은 나무와 같은 평평한 배열로 구현됩니다.
1
2 3
표현은 1; 2; 3 . 이것은 우리가 1에서 시작하는 지수를 사용하는 경우 (즉, 오프셋이 아닌 지수), 주어진 지수의 좌파 자식의 지수는 2 * index 이고 오른쪽 자식은 단순히 2 * index + 1 입니다. 부모는 floor(index / 2) 입니다. 이러한 모든 작업은 2S에서 작동하기 때문에 효율적인 비트 변속을 사용하여이를 실행할 수 있습니다 ( index << 1 , (index << 1) | 1 및 index >> 1 ).
이진 검색을 수행하여 원하는 순서가없는 블록을 찾을 수 있습니다. 먼저 루트 블록을 확인하여 원하는 주문의 블록이 무료인지 확인합니다. 있는 경우 좌파 자녀가 충분히 무료가 있는지 확인합니다. 그렇다면, 우리는 다시 왼쪽 아이 등을 확인합니다. 우리는 올바른 아이가 충분히 자유롭거나 루트 블록이 유효하지 않다는 것을 알고 있습니다.
이 구현은 매우 빠릅니다. 내 컴퓨터에서는 1GIB를 할당하는 데 ~ 0.07S 만 필요했습니다. 그러나 내 컴퓨터에서 최대 0.04s를 수행하는 것을 보았습니다. 성능은 약간 변동합니다. 나는 이것이 CPU로드와 관련이 있다고 가정합니다.
이 구현에는 레벨이 서로 멀리 떨어져 저장되므로 부모 블록은 자식과는 거리가 멀기 때문에 캐시 지역이 매우 우수하지 않습니다. 그러나 다른 모든 것은 여전히 매우 빠르므로 구성됩니다. 그것은 또한 O (log n)이지만 실제로는 너무 빠르기 때문에 이것이 중요하지 않습니다. 참조 : 8Gib를 할당하는 데 0.6 초가 걸렸지 만 @gegy1000의 랩톱에서> 150ms에서 훨씬 더 잘 작동하는 것을 보았습니다.
추가 할 것이있는 경우 (예 : ReadMe 또는 다른 구현 또는 벤치 마크에 대한 편집과 같은) 풀 요청을 제출하십시오! 문제를 만들 수도 있습니다. 채팅을하고 싶다면 녹음 불화에 대해 저를 자유롭게 핑하십시오 (Restioson#8323).
