Compiler Explorer

Source code

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <chrono>
#include <fstream>
#include <string_view>
#include <sstream>
#include <numeric>
#include <string.h>
#include <ranges>

#ifdef _MSC_VER

#pragma optimize("", off)

template <class T>
void DoNotOptimizeAway(T&& datum) {
	datum = datum;
}

#pragma optimize("", on)

#elif defined(__clang__)

template <class T>
__attribute__((__optnone__)) void DoNotOptimizeAway(T&& /* datum */) {}

#else

template <class T>
void DoNotOptimizeAway(T&& datum) {
	asm volatile("" : "+r" (datum));
}

#endif

template <typename TFunc> void RunAndMeasure(const char* title, TFunc func)
{
	const auto start = std::chrono::steady_clock::now();
	auto ret = func();
	const auto end = std::chrono::steady_clock::now();
	DoNotOptimizeAway(ret);
	std::cout << title << ": " << std::chrono::duration <double, std::milli>(end - start).count() << " ms\n";
}

using namespace std::literals;

const std::string_view LoremIpsumStrv{ R"(Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ullamcorper malesuada proin libero nunc consequat interdum varius sit amet. Quis lectus nulla at volutpat diam. Tellus rutrum tellus pellentesque eu. Varius duis at consectetur lorem donec massa sapien faucibus. Tristique nulla aliquet enim tortor at auctor urna nunc id. Risus in hendrerit gravida rutrum quisque non tellus orci. Sem nulla pharetra diam sit amet nisl. Vitae aliquet nec ullamcorper sit. Aliquam ut porttitor leo a. Ipsum suspendisse ultrices gravida dictum fusce ut. Auctor neque vitae tempus quam pellentesque nec. Ultrices in iaculis nunc sed augue lacus. Sem fringilla ut morbi tincidunt augue interdum velit. Maecenas accumsan lacus vel facilisis volutpat est velit egestas. Eu consequat ac felis donec et odio pellentesque. Leo urna molestie at elementum. Enim facilisis gravida neque convallis a. Suspendisse faucibus interdum posuere lorem. Proin sed libero enim sed faucibus.

Feugiat nibh sed pulvinar proin gravida hendrerit lectus. Ultrices vitae auctor eu augue ut. Accumsan sit amet nulla facilisi morbi tempus iaculis urna. At lectus urna duis convallis convallis tellus id interdum velit. Vel quam elementum pulvinar etiam non. Ac placerat vestibulum lectus mauris. Amet mauris commodo quis imperdiet massa tincidunt nunc pulvinar. Molestie at elementum eu facilisis. Nunc pulvinar sapien et ligula ullamcorper malesuada proin. Lacus luctus accumsan tortor posuere ac ut consequat semper viverra. Quis imperdiet massa tincidunt nunc pulvinar sapien. Amet tellus cras adipiscing enim eu turpis. Et ligula ullamcorper malesuada proin libero nunc consequat. In fermentum posuere urna nec tincidunt praesent semper feugiat. Aenean sed adipiscing diam donec adipiscing tristique risus nec feugiat. Pellentesque elit eget gravida cum sociis natoque penatibus et. Lobortis scelerisque fermentum dui faucibus in ornare quam viverra. Est ante in nibh mauris cursus mattis.

Mattis rhoncus urna neque viverra justo. Ridiculus mus mauris vitae ultricies leo integer malesuada nunc. Auctor eu augue ut lectus arcu bibendum at varius. Diam volutpat commodo sed egestas egestas fringilla phasellus faucibus scelerisque. Orci eu lobortis elementum nibh. Ullamcorper sit amet risus nullam eget felis eget nunc lobortis. Habitasse platea dictumst vestibulum rhoncus est pellentesque. Nam at lectus urna duis. Ultrices in iaculis nunc sed. Nullam eget felis eget nunc lobortis mattis aliquam faucibus. Vel orci porta non pulvinar. At in tellus integer feugiat scelerisque varius. Sed elementum tempus egestas sed sed risus pretium quam. Id cursus metus aliquam eleifend mi. Et leo duis ut diam quam nulla.

Nibh sit amet commodo nulla. Lectus quam id leo in vitae turpis massa sed elementum. Odio aenean sed adipiscing diam donec. Pellentesque elit ullamcorper dignissim cras. Ac turpis egestas maecenas pharetra convallis posuere morbi leo. Pharetra magna ac placerat vestibulum lectus mauris ultrices eros in. Auctor urna nunc id cursus metus. Ipsum a arcu cursus vitae congue mauris rhoncus. Lacus sed turpis tincidunt id aliquet risus feugiat in ante. Ut porttitor leo a diam sollicitudin tempor id.

Nec feugiat nisl pretium fusce id velit. Et netus et malesuada fames ac turpis egestas. Eu turpis egestas pretium aenean pharetra magna ac. Ut pharetra sit amet aliquam id diam maecenas ultricies mi. Lacus vestibulum sed arcu non. Sem nulla pharetra diam sit amet nisl. In ante metus dictum at tempor commodo ullamcorper a lacus. Volutpat ac tincidunt vitae semper quis lectus. Volutpat est velit egestas dui id ornare arcu odio ut. Fermentum posuere urna nec tincidunt praesent semper feugiat nibh sed. Mattis vulputate enim nulla aliquet porttitor lacus luctus. Felis donec et odio pellentesque diam volutpat commodo sed. Facilisi morbi tempus iaculis urna id volutpat lacus laoreet. Ipsum consequat nisl vel pretium lectus. Commodo viverra maecenas accumsan lacus vel facilisis volutpat est. At quis risus sed vulputate odio ut enim. At quis risus sed vulputate odio. Consequat id porta nibh venenatis cras sed felis eget.

Venenatis urna cursus eget nunc scelerisque viverra mauris in. Quis auctor elit sed vulputate mi sit. Elit ut aliquam purus sit amet. Sit amet consectetur adipiscing elit duis tristique sollicitudin nibh. Tellus mauris a diam maecenas sed enim ut sem viverra. Scelerisque felis imperdiet proin fermentum leo vel. Amet purus gravida quis blandit turpis. Sollicitudin ac orci phasellus egestas tellus rutrum tellus pellentesque. Scelerisque fermentum dui faucibus in ornare quam viverra. Quam vulputate dignissim suspendisse in est ante in nibh mauris. Et egestas quis ipsum suspendisse. Pellentesque habitant morbi tristique senectus et netus et malesuada fames. Velit egestas dui id ornare. Est pellentesque elit ullamcorper dignissim cras tincidunt lobortis feugiat. Posuere urna nec tincidunt praesent. Quis imperdiet massa tincidunt nunc pulvinar. Amet mattis vulputate enim nulla aliquet porttitor lacus luctus accumsan. Enim tortor at auctor urna nunc id cursus metus. Suscipit adipiscing bibendum est ultricies integer quis auctor elit. Et molestie ac feugiat sed lectus.

Quam quisque id diam vel. Orci eu lobortis elementum nibh tellus molestie nunc non blandit. Suspendisse in est ante in nibh mauris cursus. Aliquam purus sit amet luctus venenatis lectus magna fringilla. Dignissim suspendisse in est ante in nibh mauris cursus mattis. Diam quam nulla porttitor massa id neque aliquam. Duis at consectetur lorem donec massa sapien. Eget duis at tellus at urna. Placerat vestibulum lectus mauris ultrices eros. Nisi est sit amet facilisis. Risus sed vulputate odio ut enim blandit.

Morbi tincidunt augue interdum velit euismod. Sit amet tellus cras adipiscing enim eu turpis egestas pretium. Facilisis leo vel fringilla est ullamcorper eget nulla. Dictumst vestibulum rhoncus est pellentesque elit ullamcorper dignissim cras. Sagittis vitae et leo duis ut. Amet cursus sit amet dictum sit amet justo. Tortor condimentum lacinia quis vel eros. Purus ut faucibus pulvinar elementum integer enim neque. Montes nascetur ridiculus mus mauris vitae ultricies leo. Pretium aenean pharetra magna ac placerat vestibulum lectus. Molestie a iaculis at erat pellentesque adipiscing commodo. Aliquam purus sit amet luctus venenatis lectus magna fringilla.

Dignissim sodales ut eu sem. Aliquet risus feugiat in ante metus dictum at. Est sit amet facilisis magna etiam. Ornare aenean euismod elementum nisi. Aliquam eleifend mi in nulla posuere sollicitudin. Id interdum velit laoreet id donec ultrices tincidunt arcu non. Maecenas sed enim ut sem viverra aliquet. Est pellentesque elit ullamcorper dignissim. Morbi tristique senectus et netus et malesuada fames. Aliquam eleifend mi in nulla. Felis eget velit aliquet sagittis id consectetur purus ut faucibus. Sit amet cursus sit amet dictum sit amet justo donec. Duis ut diam quam nulla porttitor massa id neque aliquam. Sollicitudin ac orci phasellus egestas tellus rutrum. Mattis enim ut tellus elementum sagittis vitae et. Tristique nulla aliquet enim tortor at auctor. Natoque penatibus et magnis dis parturient. Ullamcorper a lacus vestibulum sed arcu non odio. Ut morbi tincidunt augue interdum velit euismod in pellentesque.

Lacus viverra vitae congue eu consequat ac felis. Ultrices dui sapien eget mi proin sed libero enim sed. Convallis a cras semper auctor neque. Donec adipiscing tristique risus nec feugiat in fermentum posuere urna. Id eu nisl nunc mi ipsum faucibus vitae aliquet. Felis eget nunc lobortis mattis aliquam faucibus purus in massa. Dignissim enim sit amet venenatis. Pharetra magna ac placerat vestibulum. Eu ultrices vitae auctor eu augue ut lectus arcu. Bibendum ut tristique et egestas. Odio morbi quis commodo odio. Est sit amet facilisis magna etiam tempor. Est sit amet facilisis magna etiam tempor orci eu lobortis.

Sagittis purus sit amet volutpat consequat mauris nunc congue nisi. Elementum tempus egestas sed sed risus pretium. Et netus et malesuada fames ac turpis. Tellus elementum sagittis vitae et leo duis. In hac habitasse platea dictumst quisque. Felis eget velit aliquet sagittis id consectetur purus. Risus nullam eget felis eget. Maecenas accumsan lacus vel facilisis volutpat. Odio tempor orci dapibus ultrices in iaculis. In est ante in nibh mauris. Dapibus ultrices in iaculis nunc sed. Sed odio morbi quis commodo odio. Feugiat vivamus at augue eget. Sapien faucibus et molestie ac feugiat sed lectus vestibulum mattis. Purus non enim praesent elementum facilisis leo.

Aliquet lectus proin nibh nisl condimentum id venenatis. Massa tempor nec feugiat nisl. Ut sem nulla pharetra diam sit amet nisl suscipit. Ut eu sem integer vitae justo eget magna fermentum. Condimentum id venenatis a condimentum vitae sapien pellentesque habitant morbi. Scelerisque fermentum dui faucibus in ornare quam viverra. Pretium aenean pharetra magna ac placerat vestibulum lectus mauris. Eget mi proin sed libero enim sed faucibus turpis in. Tincidunt ornare massa eget egestas purus viverra accumsan in. At augue eget arcu dictum varius duis at consectetur lorem. Vulputate mi sit amet mauris commodo quis imperdiet massa. Sit amet massa vitae tortor condimentum lacinia quis. Neque sodales ut etiam sit amet nisl purus in mollis. Sagittis id consectetur purus ut faucibus pulvinar. Morbi tincidunt ornare massa eget egestas.

Urna duis convallis convallis tellus id. Amet consectetur adipiscing elit pellentesque habitant morbi. Dictum fusce ut placerat orci nulla pellentesque dignissim enim. Sem et tortor consequat id porta nibh. Donec enim diam vulputate ut pharetra sit. Egestas fringilla phasellus faucibus scelerisque. Rhoncus aenean vel elit scelerisque mauris pellentesque. Est sit amet facilisis magna etiam. Mauris rhoncus aenean vel elit. Nulla facilisi etiam dignissim diam quis enim lobortis. Amet luctus venenatis lectus magna fringilla urna. Id leo in vitae turpis. Mi eget mauris pharetra et ultrices neque. Nec sagittis aliquam malesuada bibendum arcu vitae elementum. Iaculis nunc sed augue lacus viverra.

Viverra nibh cras pulvinar mattis nunc sed blandit libero. Dignissim suspendisse in est ante in nibh mauris cursus mattis. Enim tortor at auctor urna nunc id cursus. Auctor neque vitae tempus quam pellentesque nec nam. Pharetra pharetra massa massa ultricies mi quis. Tristique nulla aliquet enim tortor at auctor. Pulvinar elementum integer enim neque. Velit aliquet sagittis id consectetur purus. Feugiat sed lectus vestibulum mattis. Odio eu feugiat pretium nibh ipsum consequat. Dignissim enim sit amet venenatis urna cursus. Sed enim ut sem viverra aliquet eget sit. Mattis rhoncus urna neque viverra justo nec ultrices. Amet consectetur adipiscing elit duis tristique sollicitudin.

Nam at lectus urna duis convallis. Ut placerat orci nulla pellentesque dignissim enim sit amet. Quis eleifend quam adipiscing vitae proin. Enim eu turpis egestas pretium. Sollicitudin nibh sit amet commodo nulla facilisi. Sed risus pretium quam vulputate. Eget mi proin sed libero enim sed faucibus. Turpis egestas pretium aenean pharetra. Quisque non tellus orci ac auctor. Quam nulla porttitor massa id neque aliquam. Vel eros donec ac odio tempor orci dapibus. Donec et odio pellentesque diam volutpat commodo sed egestas. Vel pretium lectus quam id leo in vitae turpis. Accumsan tortor posuere ac ut consequat semper viverra. Eros donec ac odio tempor orci dapibus. Ultrices mi tempus imperdiet nulla malesuada pellentesque elit eget gravida.
)" };

std::vector<std::string> GetNeedleStrings(int argc, const char** argv, std::string &testString, size_t needleCount)
{
	const auto testStringLen = testString.length();
	std::vector<std::string> out;
	out.resize(needleCount);
	long posStart = 0;
	size_t patternLen = testStringLen;
	if (argc > 3)
	{
		const size_t tempLen = atoi(argv[3]);
		if (tempLen == 0) // some word?
		{
			std::cout << "needle is a string...\n";
			out[0] = argv[3];
		}
		else
		{
			patternLen = tempLen > testStringLen ? testStringLen : tempLen;
			const int pos = argc > 4 ? atoi(argv[4]) : 0;

if (pos == 0)
			{
				std::cout << "needle from the start...\n";
				posStart = 0;				
			}
			else if (pos == 1)
			{
				std::cout << "needle from the center...\n";
				posStart = static_cast<long>(testStringLen / 2 - patternLen / 2 - needleCount/2);
			}
			else
			{
				std::cout << "needle from the end\n";				
				posStart = static_cast<long>(testStringLen - patternLen - needleCount);
			}
		}
	}
	else
	{
		// just take the 1/4 of the input string from the end...
        std::cout << "needle in 1/4 of the input string from the end...\n";
		posStart = static_cast<long>(testStringLen - testStringLen / 4 - needleCount / 2);
	}

posStart = std::max(0L, posStart);
	for (size_t i = 0; i < needleCount; ++i)
	{
		out[i] = testString.substr(posStart + i, patternLen);
	}

return out;
}

// based on a twitter suggestion - Gregory Pakosz 
// https://gist.github.com/gpakosz/22ff3793017d6823c65727c8ba3480b7
static char* strchr_find(const char* haystackBegin, const char* haystackEnd, const char* needleBegin, const char* needleEnd)
{
	if (haystackEnd == NULL)
		haystackEnd = haystackBegin + strlen(haystackBegin);

if (needleEnd == NULL)
		needleEnd = needleBegin + strlen(needleBegin);

size_t haystackLength = haystackEnd - haystackBegin;
	size_t needleLength = needleEnd - needleBegin;

if (haystackLength < needleLength)
		return NULL;

if (needleBegin == needleEnd)
		return (char*)haystackBegin;

if (needleLength == 1)
		return (char*)memchr(haystackBegin, needleBegin[0], haystackLength);

while ((haystackBegin = (const char*)memchr(haystackBegin, needleBegin[0], haystackLength)) != NULL)
	{
		haystackLength = (size_t)(haystackEnd - haystackBegin);
		if (haystackLength == 0 || haystackLength < needleLength)
			return NULL;

if (haystackBegin[needleLength - 1] == needleBegin[needleLength - 1])
		{
			if (needleLength == 2 || memcmp(haystackBegin + 1, needleBegin + 1, needleLength - 2) == 0)
				return (char*)haystackBegin;
		}

++haystackBegin;
		--haystackLength;
	}

return nullptr;
}

int main(int argc, const char** argv)
{
	std::string testString{ LoremIpsumStrv };

if (argc > 1 && "nofile"s != argv[1])
	{
		std::ifstream inFile(argv[1]);

std::stringstream strStream;
		strStream << inFile.rdbuf();
		testString = strStream.str();
	}

std::cout << "string length: " << testString.length() << '\n';

const size_t ITERS = argc > 2 ? atoi(argv[2]) : 5000;
	std::cout << "test iterations: " << ITERS << '\n';

const size_t PATTERNS = ITERS / 10;
	const auto needles = GetNeedleStrings(argc, argv, testString, PATTERNS);
	std::cout << "patterns count: " << needles.size() << '\n';
	std::cout << "patterns len: " << needles[0].length() << '\n';

std::cout << "5 first patterns, 30 letters max: \n";
	for (auto pat : needles | std::views::take(5)) {
		if (pat.length() > 30)
			pat[30] = '\0';
		std::cout << pat.c_str() << '\n';
	}

RunAndMeasure("string::find", [&]() {
		for (size_t i = 0; i < ITERS; ++i)
		{
			std::size_t found = testString.find(needles[i % PATTERNS]);
			if (found == std::string::npos)
				std::cout << "The string " << needles[i % PATTERNS] << " not found\n";
		}
		return 0;
	});

RunAndMeasure("strchr_find", [&]() {		
		for (size_t i = 0; i < ITERS; ++i)
		{
			const char* strEnd = &testString[0] + testString.length();
			const char* needleEnd = &needles[i % PATTERNS][0] + needles[i % PATTERNS].length();
			auto found = strchr_find(&testString[0], strEnd, &needles[i % PATTERNS][0], needleEnd);
			if (found == nullptr)
				std::cout << "The string " << needles[i % PATTERNS] << " not found\n";
		}
		return 0;
	});

RunAndMeasure("std::ranges::search", [&]() {
		for (size_t i = 0; i < ITERS; ++i)
		{
			auto res = std::ranges::search(testString, needles[i % PATTERNS]);
			if (res.empty())
				std::cout << "The string " << needles[i % PATTERNS] << " not found\n";
		}
		return 0;
	});

RunAndMeasure("default searcher", [&]() {
		for (size_t i = 0; i < ITERS; ++i)
		{
			auto it = std::search(testString.begin(), testString.end(),
				std::default_searcher(
					needles[i % PATTERNS].begin(), needles[i % PATTERNS].end()));
			if (it == testString.end())
				std::cout << "The string " << needles[i % PATTERNS] << " not found\n";
		}
		return 0;
	});

RunAndMeasure("boyer_moore_searcher init only", [&]() {
		for (size_t i = 0; i < ITERS; ++i)
		{
			std::boyer_moore_searcher b(needles[i % PATTERNS].begin(), needles[i % PATTERNS].end());
			//DoNotOptimizeAway(&b);
		}
		return 0;
	});

RunAndMeasure("boyer_moore_searcher", [&]() {
		for (size_t i = 0; i < ITERS; ++i)
		{
			auto it = std::search(testString.begin(), testString.end(),
				std::boyer_moore_searcher(
					needles[i % PATTERNS].begin(), needles[i % PATTERNS].end()));
			if (it == testString.end())
				std::cout << "The string " << needles[i % PATTERNS] << " not found\n";
		}
		return 0;
	});

RunAndMeasure("boyer_moore_horspool_searcher init only", [&]() {
		for (size_t i = 0; i < ITERS; ++i)
		{
			std::boyer_moore_horspool_searcher b(needles[i % PATTERNS].begin(), needles[i % PATTERNS].end());
			//DoNotOptimizeAway(&b);
		}
		return 0;
	});

RunAndMeasure("boyer_moore_horspool_searcher", [&]() {
		for (size_t i = 0; i < ITERS; ++i)
		{
			auto it = std::search(testString.begin(), testString.end(),
				std::boyer_moore_horspool_searcher(
					needles[i % PATTERNS].begin(), needles[i % PATTERNS].end()));
			if (it == testString.end())
				std::cout << "The string " << needles[i % PATTERNS] << " not found\n";
		}
		return 0;
	});
}