내 redblack 트리 구현 개선

Question

rb-tree 구현을 작성했습니다. 노드는 malloc을 사용하여 할당됩니다. 큰 테이블을 처음부터 할당하고 그 공간을 사용하여 노드를 할당하고 테이블이 오버 플로우 될 때마다 크기를 두 배로하는 것이 좋습니다. 이렇게하면 삽입 작업이 다소 빨라집니다. 할당 할 시간이 중요하지 않다고 확신하는 경우입니다.

Answer 1

하나의 큰 블록을 할당하는 것이 더 나은지 (그리고 스스로 분리 할 것인가) 많은 작은 항목을 할당하는 것이 많은 상황에 적용되는지에 대한 의문이 있습니다. 그리고 그것을위한 하나의 크기에 맞는 답이 없습니다. 일반적으로, 그러나, 그것은 아마 큰 블록을 할당하는 것이 빠릅니다. 그러나 속도 향상 (있을 경우)은 클 수 없습니다. 필자의 경험에 비추어 볼 때 단일 할당을 수행하는 것은 일반적으로 동적 할당을 많이 사용하는 고도의 동시 시스템에서의 노력과 복잡성에 가치가 있습니다. 단일 스레드 응용 프로그램이있는 경우, 각 노드의 할당이 삽입 작업에 소요되는 비용이 매우 적을 것이라고 생각합니다.

일부 일반의 생각/의견 :

• 하나의 큰 블록을 할당 (그리고 필요에 따라 성장)은 일반적으로 전체 메모리를 적게 사용합니다. 일반적인 범용 할당 자 (예 : C의 malloc/free)는 각 할당마다 오버 헤드가 있습니다. 예를 들어, 100 바이트의 작은 할당 요청은 128 바이트를 사용하게됩니다.
• 많은 양의 메모리 조각화가있는 메모리 제약 시스템에서는 큰 메모리 블록을 할당하고 조각화 할 수 없지만 여러 개의 작은 할당은 여전히 ​​성공할 수 있습니다.
• 큰 블록을 할당해도 할당 자 수준 (예 : malloc)에서 동기화에 대한 경합이 줄어들지 만 자신의 관리 목록/블록에서 노드를 가져올 때 자신의 동기화를 제공해야합니다 (다중 스레드 시스템). 그러나 노드 자체의 삽입과 관련된 동기화가있을 수 있으므로 동일한 작업에서 처리 할 수 ​​있습니다.

궁극적으로 테스트하고 차이를 측정해야합니다. 당신이 할 수있는 간단한 일은 처리 할 것으로 예상되는 노드의 수를 할당하는 단순한 "버림 (throw-away)"테스트를 작성하는 것입니다. 소요 시간은 얼마입니까? 이렇게하면 할당 비용에 대한 일종의 야간 예상치를 얻을 수 있습니다.