Compile time regex for C++

[bstaletic]

I've just tried CTRE on these benchmarks. On my machine, it beats rust.

Here's the code:

#include "ctre.hpp"
#include <array>
#include <chrono>
#include <fstream>
#include <iostream>
#include <numeric>

template<size_t N>
void measure(const std::string& data) {
  using clock = std::chrono::high_resolution_clock;
  const auto start = clock::now();
  unsigned count = 0;
  if constexpr ( N == 0 )
    // Email
    for(auto match : ctre::range<"[\\w.+\\-]+@[\\w.\\-]+\\.[\\w.\\-]+">(data)) count++;
  else if constexpr ( N == 1 )
    // URI
    for(auto match : ctre::range<"[\\w]+:\\/\\/[^\\/\\s?#]+[^\\s?#]+(?:\\?[^\\s#]*)?(?:#[^\\s]*)?">(data)) count++;
  else
    // IP
    for(auto match : ctre::range<"(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])">(data)) count++;

  const auto end = clock::now();
  const double elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 1e-6;
  std::cout << elapsed << " - " << count << "\n";
}

int main(int argc, char** argv) {
  if (argc != 2) {
    std::cerr << "Usage: benchmark <filename>\n";
    return 1;
  }

  std::ifstream file{argv[1]};
  if (!file) {
    std::cerr << "unable to open " << argv[1] << "\n";
    return 1;
  }

  const std::string data{std::istreambuf_iterator<char>{file}, std::istreambuf_iterator<char>{}};

  measure<0>(data);
  measure<1>(data);
  measure<2>(data);
}

CTRE is different from other C++ regex libraries in that it computes the state machine at compile time. The hard part about submitting a CTRE pull request for this repo is that it isn't packaged for Ubuntu. On my machine I have just downloaded the header straight from raw.githubuserconent.com with wget. The API is also completely different, so I don't know if I should make a new file for the PR or...

Also, it needs GCC 9.

[BurntSushi]

On my machine, it beats rust.

Out of curiosity, could you try it on larger inputs? (Try duplicating the current input 100 times or so.) The input in this benchmark is so small that the effects of compilation time are measurable. I talked about this a bit more in #21. (Of course, a constexpr C++ regex engine materially benefits here, as it should, but it's also interesting to know what happens when compilation time isn't a factor.)

I'd be happy to do this myself if you could provide build instructions. :-)

[bstaletic]

With slightly more optimized CTRE patterns:

#include "ctre.hpp"
#include <array>
#include <chrono>
#include <fstream>
#include <iostream>
#include <numeric>

template<size_t N>
void measure(const std::string& data) {
	using clock = std::chrono::high_resolution_clock;
	const auto start = clock::now();
	unsigned count = 0;
	if constexpr ( N == 0 ) {
		// Email
		count = std::ranges::distance(ctre::range<"[\\w.+\\-]++@[\\w.\\-]+\\.[\\w.\\-]++">(data));
	} else if constexpr ( N == 1 ) {
		// URI
		count = std::ranges::distance(ctre::range<"[\\w]++:\\/\\/[^\\/\\s?#]+[^\\s?#]++(?:\\?[^\\s#]*+)?(?:#[^\\s]*+)?">(data));
	} else {
		// IP
		count = std::ranges::distance(ctre::range<"(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])">(data));
	}

	const auto end = clock::now();
	const double elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 1e-6;
	std::cout << elapsed << " - " << count << "\n";
}

int main(int argc, char** argv) {
	if (argc != 2) {
		std::cerr << "Usage: benchmark <filename>\n";
		return 1;
	}

	std::ifstream file{argv[1]};
	if (!file) {
		std::cerr << "unable to open " << argv[1] << "\n";
		return 1;
	}

	const std::string data{std::istreambuf_iterator<char>{file}, std::istreambuf_iterator<char>{}};

	measure<0>(data);
	measure<1>(data);
	measure<2>(data);
}

C++ times with 100x the input:

4316.94 - 9200
4171.82 - 530100
945.138 - 500

Rust:

1456.6234630000001 - 9200
1604.873194 - 530100
600.1624429999999 - 500

That's a very big difference!

provide build instructions.

1. Grab ctre.hpp from here: https://github.com/hanickadot/compile-time-regular-expressions/tree/main/single-header
2. Get your hands on gcc 9
   2.1. Clang can work with CTRE, but not with the same syntax.
3. g++ -std=c++20 -O3 bench.cpp

Note that I used ctre.hpp, not ctre-unicode.hpp. Originally I did benchmark with both and found them performing about the same.

[straywriter]

@BurntSushi @bstaletic
I ran a simple test in my machine.
windows 10 vs2019 C++20 release

boost

56.0437 - 92
49.2512 - 5305
12.1795 - 5

ctre

197.84 - 92
162.863 - 5301
125.863 - 5

stl

3061.15 - 92
4246.54 - 5301
5651.34 - 5

Seems boost's a little better? Are there any options for ctre?

[BurntSushi]

@straywriter I think it would be good to share precisely how you got your measurements. e.g., git clone ... && ./run-benchmark or something to that effect.