[optimization] libc++ std::regex and std::regex_match very slow, ~10x slower than libstdc++

[raidenluikang]

I searched for issues but didn't find anything like it.

Let https://godbolt.org/z/o5Wx9x3Gq

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <ctre.hpp>

#include <string_view>
#include <regex>
#include <chrono>
#include <string>
#include <vector>

bool is_valid_email_ctre (const std::string& email)
{
    return (bool)ctre::match<R"rx((?:(?:[^<>()\[\].,;:\s@"]+(?:\.[^<>()\[\].,;:\s@"]+)*)|".+")@(?:(?:[^<>()\[\].,;:\s@"]+\.)+[^<>()\[\].,;:\s@"]{2,}))rx">(email);
}

bool is_valid_email(const std::string& email) 
{
    static const std::regex rx{R"rx((?:(?:[^<>()\[\].,;:\s@"]+(?:\.[^<>()\[\].,;:\s@"]+)*)|".+")@(?:(?:[^<>()\[\].,;:\s@"]+\.)+[^<>()\[\].,;:\s@"]{2,}))rx"};
    return std::regex_match(email, rx);
}
//......

Clang libc++ output:

STD: less_valid = 1  upp_valid = 1
CTRE: less_valid = 1  upp_valid = 1
STD: valid_count = 4291
STD: elapsed time = 1.147848643
STD: is_valid_email took 11478 nanoseconds
CTRE: valid_count = 4291
CTRE: elapsed time = 0.038445505
CTRE: is_valid_email took 384 nanoseconds

GCC libstdc++ output:

STD: less_valid = 1  upp_valid = 1
CTRE: less_valid = 1  upp_valid = 1
STD: valid_count = 4245
STD: elapsed time = 0.116426089
STD: is_valid_email took 1164 nanoseconds
CTRE: valid_count = 4245
CTRE: elapsed time = 0.010598227
CTRE: is_valid_email took 105 nanoseconds

libc++ STD: elapsed time = 1.147848643 s vs libstdc++ STD elapsed time = 0.116426089, - which 9.86 times slower.

[philnik777]

We are aware that our implementation of regex isn't great. The truth is that it's been pretty much untouched since it's been implemented more than ten years ago. Most people just don't care that much about regex, or use CTRE. If you want to improve the performance, patches are welcome; but don't expect huge improvements otherwise.

[mordante]

Actually people care about regex, but it's well known std::regex has its flaws and fixing it is hard. If you can use CTRE I would strongly encourage you to use it. @hanickadot has created a wonderful library, unfortunately I don't expect it to be part of the Standard in the near future.

[philnik777]

Actually people care about regex

Obviously not enough to optimize it in any way.

[firewave]

The libstdc++ implementation might be faster but it is still way too slow to be used. My guess is that when people came across this they immediately moved on to Boost or some other library. Or worse - started their own custom (and obviously partial) implementation. It's really unfortunate.

As the API has seemingly not changed at all since it was introduced it seems it isn't just about nobody caring about the implementation but nobody caring about it at all in general. To me it looks like something that should be ripped out of the standard as the two major implementations are just unusable. I haven't used it with Microsoft STL though and cannot speak for that.

[raidenluikang]

@firewave You're right, I'm implement own custom email validation functions, and it more 2 times faster even than CTRE.

/*
(?:(?:[^<>()\[\].,;:\s@"]+(?:\.[^<>()\[\].,;:\s@"]+)*)|".+")@(?:(?:[^<>()\[\].,;:\s@"]+\.)+[^<>()\[\].,;:\s@"]{2,})

[^<>()\[\].,;:\s@"] = T
[^<>()\[\].,;:\s@"]
[^<>()\[\].,;:\s@"]
[^<>()\[\].,;:\s@"]


(?:(?:T+(?:\.T+)*)|".+")@(?:(?:T+\.)+T{2,})

       A @ B
       
A = (?:(?:T+(?:\.T+)*)|".+")  ==> if avoid group ==>  T+(\.T+)*|".+"   -> T+(\.T+)*  OR  ".+"
B = (?:(?:T+\.)+T{2,})        ==> if avoid group ==>  (T+\.)+T{2,}   --> s1 . s2 . ... . sn   every si -> is T,  and strlen(sn) >= 2

*/


constexpr bool is_valid_T(const char c) noexcept
{
    switch(c)
    {
	    case '<':
	    case '>':
	    case '(':
	    case ')':
	    case '[':
	    case ']':
	    case '.':
	    case ',':
	    case ';':
	    case ':':
	    
	    //whitespace C local
	    case 0x20: //space ' '
	    case 0x0c: //form feed '\f'
	    case 0x0a: //line feed '\n'
	    case 0x0d: //carriage return (0x0d, '\r')
	    case 0x09: //horizontal tab (0x09, '\t') 
	    case 0x0b: //vertical tab (0x0b, '\v') 

	    //dog sign
	    case '@':

    	    //and last quote symbol
	    case '\"':
	    	return false;

	    default:
	    	return true;
	    
    }
}

constexpr bool is_valid_A(const char* str, size_t len) noexcept
{
	//An empty string not allowed
	if (len == 0) return false;
	
	//1. fully quoted string
	if (str[0] == '\"')
	{
		if (len <= 2) return false;
		if (str[len-1] != '\"') return false;
		return true;
	}
	
	//2. T+(\.T+)*
	size_t hlen = 0;
	for (size_t x = 0; x != len; ++x){
		const char c = str[x];
		if (c == '.')
		{
			if (hlen == 0) return false; // dot dot not allowed
			hlen = 0;
		} 
		else if (is_valid_T(c))
		{
			++hlen;
		}
		else
		{
			return false;
		}
	}
	
	return hlen > 0; // last symbol must be T symbol.

}

constexpr bool is_valid_B(const char* str, size_t len) noexcept
{
	//(T+\.)+T{2,} 

     size_t hlen = 0;
     bool dot_found = false;
     for (size_t x = 0; x != len; ++x)
     {
     	 const char c = str[x];
         if (c == '.')
         {
               if (hlen == 0) return false; // dot dot  not allowed. Also dot should not be a first character.
               hlen = 0; //start a new group
               dot_found = true;
         } else if (is_valid_T(c)){
             hlen++;
         } else {
         	return false;
         }
     }
     
     if (!dot_found) return false; // must be at least one dot
     return hlen >= 2; //last group should have  two or more symbols.
}

constexpr bool is_valid_email_me(const char* str, size_t len) noexcept
{
	for (size_t x = len; x > 0 ; --x){
		if ( str[x - 1] == '@' )
		{
		    // B: str[x] ... str[len-1]:  total len -x
		    // A: str[0] ... str[x-2]  :  total x - 1
		    return is_valid_B(str + x, len - x) && is_valid_A(str, x - 1);
		}
	}
	return false;
}

bool is_valid_email_me(const std::string& email) { 
	const auto pos = email.rfind('@');
	const auto size = email.size();
	return pos != email.npos  && is_valid_A(email.data(), pos) && is_valid_B(email.data() + pos + 1, size - (pos + 1));
	//return is_valid_email_me(email.c_str(), email.size()); 
}

Result built in g++11.0:

STD: less_valid = 1  upp_valid = 1
BOOST: less_valid = 1  upp_valid = 1
CTRE: less_valid = 1  upp_valid = 1
====================================================
STD: valid_count = 43805
STD: elapsed time = 1.047430627
STD: is_valid_email took 1047 nanoseconds
=====================================================
BOOST: valid_count = 43805
BOOST: elapsed time = 0.450087993
BOOST: is_valid_email took 450 nanoseconds
=====================================================
CTRE: valid_count = 43805
CTRE: elapsed time = 0.074779377
CTRE: is_valid_email took 74 nanoseconds
====================================================
ME: valid_count = 43805
ME: elapsed time = 0.032382234
ME: is_valid_email took 32 nanoseconds

[firewave]

@raidenluikang

If you can bypass/tune certain constraints a custom implementation will always be faster. That's not fair compared to something which has to follow a specification.

Mail address validation brings back memories though - having that one address which ticks all the boxes. Making your software work with it correctly just to find out that the rest of the world is not able to handle it. This perfectly reflects the lack of a (usable) reference implementation or the usage of custom implementations.

[raidenluikang]

What difference libc++ std::regex and boost::regex implementations ? boost::regex is enough fast.

[focusexplorer]

I wrap hyperscan myself, and it's fast enough, https://github.com/focusexplorer/hyperscan_regex_cpp