How to optimize directory listing from list of paths?

user_522479 0
Viewed 93

While writing a fuse filesystem, I have an unordered_map<std::string, struct stat> as a cache, that is primed with all files and directories at startup in order to reduce reads on hard drives.

To satisfy readdir() callbacks I wrote the following loop:

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

The idea being that an object which's path is beginning with the directory path and having its last slash at the end of the directory path would be a member of it. I've tested this thoroughly and it works.
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!

Now, however, this is surprisingly slow (especially in a filesystem with over half a million objects in the cache). Valgrind/Callgrind especially blames the std::string:find_last_of() and std::string::find() calls.

I already added the if (it->first.size() > sp) in an attempt to speed up the loop, but the performance gain was minimal at best.

I also tried speeding this routine up by parallelizing the loop in four chunks, but that ended in a segfault during unordered_map::cbegin().
I don't have the actual code anymore, but I believe it looked something like this:

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

I also tried this with splitting it by map buckets, which unordered_map::cbegin(int) provides a convenient overload for, but it still segfaulted out.

Again, I'm currently working with the first (non-parallel) code and would like help for that one since the parallelized one didn't work. I just thought I'd include my parallelized attempt for completeness, noob-bashing and proof of effort.

Are there any other options for optimizing this loop?

fuse optimization c++ string performance
2 Answers

The trivial thing to do here is to change the if from this:

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

to simply:

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

Obviously, comparing two integers is much faster than looking for a substring.
I wouldn't guarantee it'll turn the performance around, but it's a trivial thing that may help to skip a lot of unnecessary std::string::find calls. Maybe the compiler already does that, I'd look into the disassembly.

Also, since filepathes are anyway unique, I would use std::vector<std::pair<...>> instead - better cache locality, less memory allocations etc. just remember to reserve the size first.

user_36135000

The real problem is 

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

effectively removing unordered_maps greatest advantage and exposing one of the weaknesses. Not only do you not have its O(1) lookup but you might have to search through the map to find an entry, this makes the rutine O(N) with a very large K (if not an extra N ie. O(N^2)).

Fastest solution would be O(1) for the lookup (in a lucky unordered map), O(strlen(target)) in a bucket scheme or O(lgN) in a binary. Then along the struct stat have list of children, for O(#children).

user_40132580
Related