Comment optimiser la liste des répertoires à partir de la liste des chemins?

Question

Lors de l'écriture d'un système de fichiers fusible, j'ai un unordered_map<std::string, struct stat> en cache, qui est amorcée avec tous les fichiers et les répertoires au démarrage afin de réduire les lectures sur les disques durs.

Pour satisfaire readdir() callbacks j'ai écrit la boucle suivante:

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); 
    } 
} 

L'idée étant qu'un objet qui est chemin commence avec le chemin du répertoire et ayant sa dernière barre à la fin du chemin du répertoire serait membre de celui-ci. Je l'ai testé à fond et cela fonctionne.
Illustration:

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! 

Maintenant, cependant, cela est étonnamment lent (surtout dans un système de fichiers avec plus de un demi-million d'objets dans le cache). Valgrind/Callgrind accuse en particulier les appels std::string:find_last_of() et std::string::find().

J'ai déjà ajouté le if (it->first.size() > sp) pour tenter d'accélérer la boucle, mais le gain de performance était au mieux minimal.

J'ai également essayé d'accélérer cette routine en parallélisant la boucle en quatre segments, mais cela s'est terminé par une erreur de segmentation pendant unordered_map::cbegin().
Je n'ai pas le code réel plus, mais je crois qu'il avait l'air quelque chose comme ceci:

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(); 

J'ai aussi essayé cela avec le fractionnement par des seaux cartographiques qui unordered_map::cbegin(int) fournit une surcharge pratique pour, mais encore segfaulted.

Encore une fois, je travaille actuellement avec le premier code (non parallèle) et je voudrais de l'aide pour celui-ci puisque le parallélisé ne fonctionnait pas. Je pensais juste inclure ma tentative parallélisée d'exhaustivité, de dénigrement et de preuve d'effort.

Existe-t-il d'autres options pour optimiser cette boucle?

Answer 1

La chose triviale à faire ici est de changer les if de ceci:

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

simplement:

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

De toute évidence, la comparaison de deux entiers est beaucoup plus rapide que la recherche d'une sous-chaîne.
Je ne garantirais pas que ça va tourner la performance, mais c'est une chose triviale qui peut aider à passer beaucoup d'appels inutiles std::string::find. Peut-être que le compilateur le fait déjà, je regarderais dans le démontage.

De plus, comme les chemins de fichiers sont uniques, j'utiliserais std::vector<std::pair<...>> à la place - meilleure localisation du cache, moins d'allocations de mémoire, etc. N'oubliez pas de réserver la taille en premier.

Answer 2

Le vrai problème est

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

éliminer efficacement unordered_maps plus grand avantage et d'exposer l'une des faiblesses.Non seulement vous n'avez pas sa recherche O (1), mais vous devrez peut-être chercher dans la carte pour trouver une entrée, ce qui rend la rutine O (N) avec un très grand K (sinon un N supplémentaire, c'est-à-dire O (N^2)).

La solution la plus rapide serait O (1) pour la recherche (dans une carte chanceuse non ordonnée), O (strlen (cible)) dans un schéma de seau ou O (lgN) dans un binaire. Ensuite, le long de la struct stat ont une liste d'enfants, pour O (#children).