경로 목록에서 디렉토리 목록을 최적화하는 방법은 무엇입니까?

Question

퓨즈 파일 시스템을 작성하는 동안 하드 드라이브의 읽기를 줄이기 위해 모두 파일 및 디렉토리로 시작하는 캐시로 unordered_map<std::string, struct stat>을 캐시로 사용합니다. readdir() 콜백을 만족하려면

나는 다음과 같은 루프를 썼다 :

const int sp = path == "/" ? 0 : path.size(); 
for (auto it = stat_cache.cbegin(); it != stat_cache.cend(); it++) 
{ 
    if (it->first.size() > sp) 
    { 
     int ls = it->first.find_last_of('/'); 
     if (it->first.find(path, 0) == 0 && ls == sp) 
      filler(buf, it->first.substr(ls + 1).c_str(), const_cast<struct stat*>(&it->second), 0, FUSE_FILL_DIR_PLUS); 
    } 
} 

경로의 객체가 될 것이라고 디렉토리 경로의 끝에서 마지막 슬래시를 디렉토리 경로로 시작 데 있다는 것을 생각 그것의 일원. 나는 이것을 철저히 시험했으며 작동한다.
그림 :

Reading directory: /foo/bar 
Candidate file: /bazboo/oof - not in dir (wrong prefix) 
Candidate file: /foo/bar/baz/boo - not in dir (wrong lastslash location) 
Candidate file: /foo/bar/baz - in dir! 

지금, 그러나,이 (캐시에 백만 절반 이상 객체, 특히 파일 시스템에서) 놀라 울 정도로 느립니다. Valgrind/Callgrind는 특히 std::string:find_last_of()과 std::string::find() 전화를 탓합니다.

루프 속도를 높이기 위해 if (it->first.size() > sp)을 이미 추가했지만 성능 향상 효과는 미미했습니다.

또한이 루틴을 4 개의 청크로 병렬 처리하여 속도를 높이려고했으나 unordered_map::cbegin() 동안 segfault에서 종료되었습니다.
는 더 이상 실제 코드를 가지고 있지 않지만, 나는 이런 식으로 뭔가를보고 생각 :

const int sp = path == "/" ? 0 : path.size(); 
ThreadPool<4> tpool; 
ulong cq = stat_cache.size()/4; 
for (int i = 0; i < 4; i++) 
{ 
    tpool.addTask([&]() { 
     auto it = stat_cache.cbegin(); 
     std::next(it, i * cq); 
     for (int j = 0; j < cq && it != stat_cache.cend(); j++, it++) 
     { 
      if (it->first.size() > sp) 
      { 
       int ls = it->first.find_last_of('/'); 
       if (it->first.find(path, 0) == 0 && ls == sp) 
        filler(buf, it->first.substr(ls + 1).c_str(), const_cast<struct stat*>(&it->second), 0, FUSE_FILL_DIR_PLUS); 
      } 
     } 
    }); 
} 
tpool.joinAll(); 

나는 또한 unordered_map::cbegin(int)가 편리한 과부하를 제공하는지도 버킷하여 분할과 함께이 시도하지만, 여전히 segfaulted.

다시 말하지만, 저는 현재 첫 번째 (비 병렬) 코드로 작업 중이며 병렬 처리 된 코드가 작동하지 않으므로이 코드에 대한 도움이 필요합니다. 나는 단지 완성을위한 나의 평행 한 시도, 멍청한 행동과 노력의 증거를 포함시킬 것이라고 생각했다.

이 루프를 최적화하는 다른 옵션이 있습니까?

Answer 1

여기서 할 수있는 사소한 일이에서 if을 변경하는 것입니다 :

if (it->first.find(path, 0) == 0 && ls == sp) 

단순히 :

if (ls == sp && it->first.find(path, 0) == 0) 

은 물론, 두 개의 정수를 비교하는 문자열을 찾는 것보다 훨씬 빠릅니다.
성능을 향상시킬 수 있다고 보장 할 수는 없지만 많은 불필요한 호출을 건너 뛰는 데 도움이되는 것은 사소한 일입니다. std::string::find 어쩌면 컴파일러가 이미 그렇게했을 것입니다. 분해를 들여다 보겠습니다.

또한 filepathes는 고유하기 때문에 대신 std::vector<std::pair<...>>을 사용합니다. 캐시 위치를 개선하고 메모리 할당을 줄이는 등 크기를 우선적으로 기억해야합니다.

Answer 2

진짜 문제는

for (auto it = stat_cache.cbegin(); it != stat_cache.cend(); it++) 

효과적으로 제거 unordered_maps 큰 장점과 약점 중 하나를 노출합니다.뿐만 아니라 O (1) 검색을하지 않아도 항목을 찾기 위해지도를 검색해야 할 수도 있습니다. 이렇게하면 매우 큰 K가있는 루틴 O (N)이 만들어집니다 (N이 아닌 경우 O^2)).

가장 빠른 솔루션은 조회 (운이 좋지 않은 정렬되지 않은지도), O (strlen (target)) 버킷 스키마 또는 O (lgN) 이진입니다. 그런 다음 struct stat에 따라 O (# 자식)에 대한 하위 목록이 있습니다.