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.
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.
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 (早い) 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:
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
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:
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.
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.
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:
You will also see references to the function
In essence, this function applies a given predicate using
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:
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
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
is in InputIterator, the constructor of
has no way of determining how many elements are in the range
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
the vector before returning it, but this would mean another reallocation of the
data buffer. How about preallocating the vector before filling it:
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):
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:
While performance tends to be a very broad term, we will take a look at two very different aspects: readability and runtime.
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
especially when we are not preallocating the vector. But as always, beauty is in
the eye of the beholder.
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:
|File||7266 ms||7858 ms|
|File (PA)||7947 ms||8305 ms|
|File Extension||7446 ms||7954 ms|
|File Extension (PA)||8711 ms||8559 ms|
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.
Subscribe via RSS