매우 큰 파일 150GB가 있습니다. 나는 읽기 전용 mmap을 사용하고 파일로 이진 검색을 수행합니다.매우 큰 파일에 mmap 최적화
현재 이진 검색은 매우 느립니다.
그러나 나는 최적화를 생각하고있다. (디스크 찾기와 같은) 어떤 값을 체크 할 때,이 값은 "디스크"블록에 속하기 때문에이 값은 이미 메모리에있다. 파일의 다른 위치로 점프하는 대신 "가까운"값을 확인하고 그 후에 점프 할 수 있습니다.
이 최적화 작업을 수행 할 가치가 있습니까?
또한 디스크 블록이 "끝나는 위치"를 어떻게 예측할 수 있습니까?
데이터 구조가 B-tree 인 추론 라인을 발견했습니다. 의 최적화는 수행 할 가치가있는이지만 가능한 한 많이 얻으려면 디스크의 데이터를 실질적으로 재구성하고 2 진 검색보다 복잡한 알고리즘을 사용해야합니다. 아마도 처음부터 구현하기보다는 기존의 오픈 소스 B-tree 라이브러리를 조사해야 할 것이다.
mmap을 사용하고 있기 때문에 액세스의 최소 세분성은 디스크 블록 크기가 아니고 sysconf(_SC_PAGESIZE)으로 쿼리 할 수있는 메모리 "페이지"크기입니다. 일부 OS는 파일 백업 영역에 대한 무작위 액세스로 더 큰 메모리 덩어리를 읽고 채 웁니다. 그러나 나는 얼마나 많은 양의 휴대용 방법을 알지 못합니다. madvise(MADV_RANDOM)의 혜택을 얻을 수도 있습니다.
이 추론이 이끌어 낼 수있는 또 다른 방향은 캐시를 잊어 버리는 데이터 구조입니다. 이들은 페이지 크기를 알 필요가 없으며 여러 수준의 CPU 캐시를 활용할 수도 있습니다. 자세한 내용은 https://blogs.msdn.microsoft.com/devdev/2007/06/12/cache-oblivious-data-structures/를 참조하십시오. – btilly
'madvise (MADV_RANDOM)'속도 60 %. 좋았지 만 여전히 느립니다. – Nick