메모리의 Boost r-tree와 매핑 된 파일의 성능 차이

Question

오랫동안 저장하기 위해 3D R * -tree를 생성해야하지만 성능 또한 문제가됩니다. 트리를 만들려면 Boost의 spacialindex를 사용하기로 결정했으며 두 가지 가능한 방법을 기본적으로 발견했습니다.

여기에있는 객체를 사용하여 직접 만듭니다. Index of polygons stored in vector하지만 R * -tree를 다시 만들지 않고 저장하고로드 할 수 없습니다.

여기에 설명 된대로 매핑 된 파일을 사용할 수 있습니다. 그러나이 경우 쿼리 성능이 충분한 지 확신 할 수 없습니다.

내 r 트리는 수천 개의 항목을 포함하지만 대부분은 약 100,000 개 미만입니다. 이제 내 질문은, 거기에 매핑 된 파일을 사용하여 표준 개체를 사용하여 비교하여 어떤 강력한 성능 문제가 있습니까? 또한, 약 100,000 개의 값을 갖는 R * -tree를 생성하는 데 상당한 시간이 필요하지 않은 경우 (모든 경계 상자와 해당 키/데이터가 파일에 저장 될 수 있음) 해당 항목을 건너 뛰는 것이 더 좋은 옵션 일 수 있습니다 매핑 된 파일을 만들고 프로그램을 실행할 때마다 트리를 만듭니 까?

설명서가 실제로 많은 정보를 제공하지 않기 때문에 (누군가가 libspacialindex의 문서보다 더 나은 세상이지만) 도움이되기를 바랍니다.

Answer 1

매핑 된 파일은 대부분 일반 메모리처럼 작동합니다. 실제로는 new 또는 malloc을 사용하는 메모리 할당은 mmap [기본 할당 방법으로 "파일 없음"저장 장치를 사용합니다. 그러나 "장소 전체에"작은 글을 많이 쓰고 실제 파일에 매핑하는 경우 OS는 파일에 쓰기 전에 버퍼링 된 쓰기의 양을 제한합니다.

필자가 얼마 전에 필자의 실험을했는데, OS가 이러한 "보류중인 쓰기"를 처리하는 방법에 대한 설정을 조정하여 임의의 읽기/쓰기 패턴을 가진 파일 백 메모리 매핑의 경우에도 합리적으로 성능을 얻었다 [ 당신이 당신의 나무를 짓고있을 때 내가 기대하는 어떤 것이].

여기에 내가 생각하는 질문은 "임의 쓰기와 mmap에의 성능"의 매우 관련이있다 : Bad Linux Memory Mapped File Performance with Random Access C++ & Python (이 답변은 리눅스에 적용 - 그것을 어떻게에 관해서는 완전히 다르게 다른 OS 용의가, 특히 Windows에서 잘 작동 할 수 있습니다

물론 맵핑 된 파일이나 프로그램을 실행할 때마다 "어느 것이 더 낫다"는 말을하는 것은 꽤 어렵습니다. 실제로 실행중인 프로그램의 종류에 달려 있습니다. 1 초에 100 번이나, 하루에 한 번, 나는 [나는 절대적으로 아무 생각이 없다!], 그리고 다른 많은 것들을 재건하는데 얼마나 오래 걸리는지. 두 가지 선택이 있습니다. 가장 간단한 버전을 빌드하고 "충분히 빠르다"는 것을 확인하거나 두 버전을 모두 빌드하고 차이가 얼마나 나는지 측정 한 다음 어느 경로가 다운 될지 결정하십시오.

성능이 좋지 않은 경우 성능이 좋지 않은 경우 속도가 느린 곳을 파악한 다음 수정하여 시간을 절약하고 총 실행 시간은 5 클럭주기가 더 빨라지고 예상보다 500 배 느리게 실행되는 큰 thinko로 끝납니다. ...

Answer 2

대량로드는 인덱스가 많이 반복 삽입보다 빠릅니다. , 그리고 훨씬 더 효율적인 트리를 만듭니다. 따라서 모든 데이터를 메인 메모리에 저장할 수 있다면 STR 벌크로드를 사용하여 트리를 재구성하는 것이 좋습니다. 내 경험상 이것은 충분히 빠르다. (벌크 로딩 시간은 I/O 시간에 비하면 왜소하다.)

STR의 비용은 대략 정렬 비용입니다. 이론적으로 매우 낮은 상수 (O(n log n log n) 일 수는 있지만 아직까지는 상당히 저렴합니다).