Boyer-Moore Searcher Comparative Benchmark

boyer_moore.cpp

#include <algorithm>
#include <functional>
#include <string>
#include <string_view>
#include <benchmark/benchmark.h>
#include "file.hpp"

#define NOMINMAX
#define WIN32_LEAN_AND_MEAN
#include <windows.h>

using namespace std;

__declspec(noinline) wstring windows_multi_byte_to_wide_char(const std::string& s)
{
	int desiredSize =
		::MultiByteToWideChar(CP_UTF8, 0, s.c_str(), static_cast<int>(s.size()), nullptr, 0);
	wstring dest(desiredSize, L'\0');
	::MultiByteToWideChar(CP_UTF8, 0, s.c_str(), static_cast<int>(s.size()), &dest[0], desiredSize);
	return dest;
}


static string huckleberryTxt;
static wstring huckleberryTxtW;
struct init_huckleberry {
	init_huckleberry() {
		read_all("huckleberry.txt", huckleberryTxt);
		huckleberryTxtW = windows_multi_byte_to_wide_char(huckleberryTxt);
	}
};

static init_huckleberry init_huckleberry_instance;

static string_view needle("Michael S. Hart is the originator of the Project Gutenberg-tm");
static wstring_view needleW(L"Michael S. Hart is the originator of the Project Gutenberg-tm");

__declspec(noinline) void naive_search(benchmark::State& state) {
	default_searcher<string_view::const_iterator> searcher(needle.begin(), needle.end());
	while (state.KeepRunning()) {
		benchmark::DoNotOptimize(searcher(huckleberryTxt.begin(), huckleberryTxt.end()));
	}
}

BENCHMARK(naive_search);

__declspec(noinline) void bm_search(benchmark::State& state) {
	boyer_moore_searcher<string_view::const_iterator> searcher(needle.begin(), needle.end());
	while (state.KeepRunning()) {
		benchmark::DoNotOptimize(searcher(huckleberryTxt.begin(), huckleberryTxt.end()));
	}
}

BENCHMARK(bm_search);

__declspec(noinline) void bmh_search(benchmark::State& state) {
	boyer_moore_horspool_searcher<string_view::const_iterator> searcher(needle.begin(), needle.end());
	while (state.KeepRunning()) {
		benchmark::DoNotOptimize(searcher(huckleberryTxt.begin(), huckleberryTxt.end()));
	}
}

BENCHMARK(bmh_search);

__declspec(noinline) void naive_search_wide(benchmark::State& state) {
	default_searcher<wstring_view::const_iterator> searcher(needleW.begin(), needleW.end());
	while (state.KeepRunning()) {
		benchmark::DoNotOptimize(searcher(huckleberryTxtW.begin(), huckleberryTxtW.end()));
	}
}

BENCHMARK(naive_search_wide);

__declspec(noinline) void bm_search_wide(benchmark::State& state) {
	boyer_moore_searcher<wstring_view::const_iterator> searcher(needleW.begin(), needleW.end());
	while (state.KeepRunning()) {
		benchmark::DoNotOptimize(searcher(huckleberryTxtW.begin(), huckleberryTxtW.end()));
	}
}

BENCHMARK(bm_search_wide);

__declspec(noinline) void bmh_search_wide(benchmark::State& state) {
	boyer_moore_horspool_searcher<wstring_view::const_iterator> searcher(needleW.begin(), needleW.end());
	while (state.KeepRunning()) {
		benchmark::DoNotOptimize(searcher(huckleberryTxtW.begin(), huckleberryTxtW.end()));
	}
}

BENCHMARK(bmh_search_wide);

BENCHMARK_MAIN();