Recently, I was working on wallpaper changer for the GNOME desktop environment. After fumbling around with the, less-than-stellar, python bindings for Glib, I decided to go back to my roots and do it in C++. It turned out that the new filesystem features in C++, while awesome, are missing one feature I figure would often be useful – filtering during directory iteration. In this post, I show how to easily retrofit this feature using the Boost Iterator library.

The Problem

While there exist plenty of different tools to automatically change the wallpaper of a GNOME session, I had issues with all of them. Without going into too much detail, I find that the existing solution provide either too many or too few features, come with other clutter and overhead, or simply don’t work for my scenario. My goal is to have a simple tool that can easily be extended, while still providing reasonable performance. I want to be able to use my Photos folder, which contains a several layers deep hierarchy of around 35.000 files.

Environment

The code presented in this post assumes a modern C++ compiler (like GCC 7.1) that supports modern C++17 features, for example class-template type deduction. You will also need a reasonably modern STL implementation, that supports the upcoming file-system library. Note that AFAIK, Clang 4.0 does not support class-template type-deduction, so you will need to retrofit the code a little.

Aside from a modern, generic C++ subsystem, I will also be using parts of Boost as well as Hayai. While Boost will be familiar to C++ programmers, Hayai might not be so well-known.

Hayai

Hayai (早い) is Japanese for “fast” (as the opposite of slow). It is also a microbenchmarking framework for C++, developed by Nick Bruun Being a header-only framework, makes it easy to integrate into C++ projects, and its simple API makes it possible to quickly write benchmarks using only a couple of lines of code. Here is an example, taken from my experiments, of how to write a benchmark in Hayai:

BENCHMARK(FileFilter, BoostFileFilter, 10, 25)
    {
    boost_file_entries(test_root);
    }

In this snippet, BENCHMARK is a macro provided by the framework. Its first argument is the group of the benchmark. You can choose any valid C++ identifier here. The second argument is the actual name of the benchmark (again, any valid C++ identifier will do here). The third argument specifies the number of runs that will be executed, while the fourth parameter is the number of iterations of the benchmark body for every run of the benchmark. So in the above example, the function all_entries(...) will be exercised 250 times.

If you want to be truly header-only, you will also need a basic int main() function, like this one:

int main()
    {
    hayai::ConsoleOutputter out{};
    hayai::Benchmarker::AddOutputter(out);
    hayai::Benchmarker::RunAllTests();
    }

Of course you will need to include the hayai.hpp header, but as you can see, it is extremely easy to get started with benchmarking using Hayai. I will not cover every little detail of how to customize and extend Hayai. if you are interested in those kind of things, head over to Hayai’s GitHub Page and take a look at the code.

Boost.Iterator

The Boost.Iterator library is an extremely useful, header-only library for working with C++ iterators. Besides utilities to simplify writing custom iterators, Boost.Iterator provides iterator adaptors, that make it easy to extend existing iterators with custom filtering and transformations.

Boost.Iterator also ships with a set of predefined iterator adaptors, that satisfy the most general use-cases like zipping elements of two containers, transforming elements during iteration, or – as you might have guessed already – filtering out certain elements. If you want to find out more on how to use Boost.Iterator be sure to check out the documentation.

Some Solutions

As is almost always the case with engineering problems, there are multiple solutions to choose from. We will take a look at two different approaches, a purely STL based implementation and a Boost.Iterator based one. For every approach, I implemented two versions, one which preallocates the target vector before filling it, and one that doesn’t.

Besides the obvious differences, all of the solutions I present here will be using the same predicate lambda to filter out the directory_entry objects we don’t want to be part of our final list:

auto constexpr file_extension_filter = [](auto const & entry) {
    auto static const kExtensions = std::set<std::string>{".jpg", ".png", ".tga"};
    return fs::is_regular_file(entry) && kExtensions.count(entry.path().extension());
  };

You will also see references to the function get_num_entries(...). In essence, this function applies a given predicate using std::count_if(...) to calculate how many entries match the predicate. As we will see later, this function has a profound impact on the performance of the collection process.

Boosted File Filtering

As we are talking about using Boost.Iterator to extend the STL’s directory entry iteration capabilities, I will start off with a naïve implementation using the filter_iterator adaptor from Boost.Iterator. Take a look at the following code:

auto boost_file_extension_entries(fs::path const & root)
    {
    auto && iterator = fs::recursive_directory_iterator{root};
    auto && begin = boost::make_filter_iterator(file_extension_filter,
      fs::begin(iterator), fs::end(iterator));
    auto && end = boost::make_filter_iterator(file_extension_filter,
      fs::end(iterator), fs::end(iterator));
    return std::vector<fs::directory_entry>{begin, end};
    }

As you can see, the implementation is pretty straight forward. We first get a recursive_directory_iterator that will allow us to traverse all subfolders and files of the root directory. We then create the actual begin and end iterators using Boost’s make_filter_iterator to attach our desired predicate to the iteration process.

Using Boost With Preallocation

As you might have noticed already, there is a problem with the above implementation. Since the recursive_directory_iterator is in InputIterator, the constructor of std::vector has no way of determining how many elements are in the range [begin, end). Therefore, it can’t preallocate the memory required to store all entries, causing multiple reallocations of it data storage during construction. One consequence arising from this issue is that the final vector will most likely have a larger capacity than actually required. Of course we could shrink_to_fit the vector before returning it, but this would mean another reallocation of the data buffer. How about preallocating the vector before filling it:

auto boost_file_extension_entries_prealloc(fs::path const & root)
    {
    auto && iterator = fs::recursive_directory_iterator{root};
    auto && begin = boost::make_filter_iterator(file_extension_filter,
      fs::begin(iterator), fs::end(iterator));
    auto && end = boost::make_filter_iterator(file_extension_filter,
      fs::end(iterator), fs::end(iterator));
    auto && result = std::vector<fs::directory_entry>{};
    result.reserve(get_num_entries(root, file_extension_filter));
    result.insert(result.end(), begin, end);
    return result;
    }

While this makes the code a little more involved, it also makes sure that the memory backing the vector does not need to be reallocated multiple times. We will take a look at the performance implications later.

Filtering the STL Way

Of course, we can do away using the STL’s Algorithm library only. The code is fairly similar in length to implementation based on Boost.Iterator (if you ignore additional lines introduced by wrapping):

auto std_file_extension_entries(fs::path const & root)
    {
    auto && result = std::vector<fs::directory_entry>{};
    auto && iterator = fs::recursive_directory_iterator{root};
    copy_if(begin(iterator), end(iterator), back_inserter(result), file_extension_filter);
    return result;
    }

Interestingly enough, there seems to be a difference in performance when comparing the Boost.Iterator and the STL variant, as we will see soon. Even though the changes required to support preallocation in the STL implementation are basically the same as in the Boost.Iterator variant, here is the code for the sake of completeness:

auto std_file_extension_entries_prealloc(fs::path const & root)
    {
    auto && iterator = fs::recursive_directory_iterator{root};
    auto && result = std::vector<fs::directory_entry>{};
    result.reserve(get_num_entries(root, file_extension_filter));
    copy_if(begin(iterator), end(iterator), back_inserter(result), file_extension_filter);
    return result;
    }

Performance Comparison

While performance tends to be a very broad term, we will take a look at two very different aspects: readability and runtime.

Readability

While the length of the different implementations is very much the same, I personally prefer the Boost.Iterator variant. To me, it feels like the Boost variant is much more idiomatic. If you think about it, what we really want to express is: Iterate all files with one of the given extensions in the tree rooted in ‘root’. This is exactly what the Boost variant expresses.

The STL implementation, on the other hand, looks more like: Copy every element in the range [begin, end) to the result vector. Aside from that fact, it feels a little clumsy to me to use a back_inserter, especially when we are not preallocating the vector. But as always, beauty is in the eye of the beholder.

Runtime

As C++ programmers, we tend to care a lot about runtime performance. While it is obvious that the amount of memory consumed will be lower when preallocating the target vector, we must also think about the influence on the runtime. Take a look at this chart (JS required):

The numbers on the Y-axis are in milliseconds. The bars are the average runtime for one run of the Hayai benchmark. In this example, each run consists of 25 iterations where each iteration collected the files using either the STL or the Boost.Iterator variant.

As you have most likely noticed, there are two additional benchmarks. These two benchmarks did not take into account what extension the candidate file had. As you can clearly see, without preallocation, the STL implementation seems to be around 8% slower than the Boost.Iterator one. When we preallocate the target vector, the gap closes a little in the extension-less implementation, and even turns around slightly when taking the file extension into account.

All benchmarks have been performed on a Purism Librem 13 using a Samsung EVO SSD on Arch Linux. If your are interested into how the comparison turns out on your system, check out this Gist. Below are the cold, hard numbers I acquired on my system:

Conclusion

While I would not go as far as to draw general conclusions from the benchmarks, this experiment left me wondering what the cause for the difference is. On the other hand, as I already mentioned above, I prefer the Boost solution for being more idiomatic.