Optimizing C++ Word Count

Yesterday’s post showed that the original C++ version is around 13 times slower than my non-optimized Rust version. Next, I’ll show how to get easily equivalent performance to Rust.

One problem that I immediately made out when first seeing the C++ version is that it uses std::regex. std::regex is known to be horribly slow ¹.

Just replacing the checking of the file name extension with the in-built e.path().extension() != ".txt" speeds up from 373 ms to 52ms!

Before:

const std::regex fname_regex("\\.txt$", std::regex_constants::icase);
// ...
if (!std::regex_search(e.path().c_str(), fname_regex)) {
    continue;
}

After:

if (e.path().extension() != ".txt") {
    continue;
}

Next, I set out to replace the splitting into words with std::regex. I decided to use CTRE because I have never had a chance to use it before. CTRE stands for Compile-Time Regular Expressions, and means that the matching pattern is compiled into a regex matcher.

Unfortunately, I could not get Conan to work with it². So, I copied the single header file (apologies!).

The result looks like this:

static constexpr auto word_regex = ctll::fixed_string{"([a-zA-Z]{2,})"};
// ...
for (auto match : ctre::range<word_regex>(line)) {
   auto word = match.get<0>();
   ++word_counts[std::string(word)];
}

Numbers

The final performance numbers including Go ³ show C++, Rust and Go fairly close to each other. Please run your own benchmarks (use hyperfine) on your relevant workload. I suspect that Go’s runtime takes a few milliseconds to start.

Needless to say, I made sure that all comparisons were done on the same directory and with release builds.

On the C++ side we went from 373 ms to 52ms to 23ms, a 15x improvement.⁴

Update

After publishing this, I saw this post by Jussi Pakkanen, where they make the same changes to the extension checking.

And I realize that the point of their exercise was to only use the C++ Standard Library. That necessarily precludes the usage of CTRE.