CppVsCQuora.cpp

//  Benchmark C string vs. C++ std::string for the following task:
//  Replace "," with ",\n".
#include "stdafx.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <random>
#include <string>

int BigLen;

// ======================================================================== //
//  Because this is a wee benchmark, let's save our fingers a bit.          //
// ======================================================================== //
using namespace std;
static random_device rd;
static default_random_engine rng(rd());
static auto alpha = uniform_int_distribution<int>('A', 'Z');

#define WIN32 1
#ifdef WIN32
// ======================================================================== //
//  On Windows, use high resolution performance counters.                   //
// ======================================================================== //
# include <windows.h>
# include <math.h>
# include <time.h>

static bool use_perf_counters = false;
static double perf_rate = 0.0;

// Determine if we can use the performance counters.
static void InitTime(void) {
	LARGE_INTEGER li;
	if (QueryPerformanceFrequency(&li)) {
		perf_rate = 1.0 / double(li.QuadPart);
		use_perf_counters = true;
	}
	else {
		use_perf_counters = false;
		std::cout << "WARNING: Using clock_gettime fallback.\n";
	}
}

// Return time in seconds as a double.
static double GetTime(void) {
	double seconds;
	// High precision counters by default.
	LARGE_INTEGER li;
	QueryPerformanceCounter(&li);
	seconds = double(li.QuadPart) * perf_rate;
	return seconds;
}

#else
# ifdef linux
// ======================================================================== //
//  On Linux, let's use clock_gettime.                                      //
// ======================================================================== //
#  include <time.h>

// Initializer has nothing to do.
static void InitTime(void) { }

// Return time in seconds as a double.
static double GetTime(void) {
	double seconds;
	struct timespec now;
	clock_gettime(CLOCK_MONOTONIC, &now);
	seconds = double(now.tv_sec) + double(now.tv_nsec) * 1e-9;
	return seconds;
}
# else
// ======================================================================== //
//  Otherwise, let's use gettimeofday.                                      //
// ======================================================================== //
#  include <sys/time.h>

// Initializer has nothing to do.
static void InitTime(void) { }

// Return time in seconds as a double.
static double GetTime(void) {
	double seconds;
	struct timeval now;
	gettimeofday(&now, NULL);
	seconds = double(now.tv_sec) + double(now.tv_usec) * 1e-6;
	return seconds;
}
# endif
#endif

// ======================================================================== //
//  To avoid file I/O effects, start with a generous, statically allocated  //
//  buffer to generate our input into.  We'll do this entirely in memory.   //
// ======================================================================== //
const size_t max_size = 1u << 24;
static char input_buf[max_size];

// ======================================================================== //
//  The code we're comparing against modifies the string in-place.          //
//  So, statically allocate an output buffer for it.                        //
// ======================================================================== //
static char output_buf[max_size * 2];

// ======================================================================== //
//  Generate a large random string, where approx every 12th letter is ','.  //
//  Return in both a C string and a C++ std::string.  Uses in-out params,   //
//  which is perhaps a tad gross.                                           //
// ======================================================================== //
static void GenerateString(char *const buf, string& str, const size_t length) {

	// Initially fill with random alphabetic chars.
	std::generate(buf, buf + length, [] { return alpha(rng); });

	// Now randomly replace every ~12th character (+/-4) with a comma.
	auto comma = uniform_int_distribution<int>(8, 16);
	for (auto i = 0 * length; i < length; i += comma(rng)) {
		buf[i] = ',';
	}

	buf[length] = 0;
	str.reserve(length);
	str = buf;
}

// ======================================================================== //
//  C-style string approach.                                                //
// ======================================================================== //
static char *InsertNewlinesCStyle(const char *const source) {
	const size_t source_len = BigLen; // strlen(source);
	const size_t result_len = source_len + source_len;  // Conservative guess
	char *const result = (char *)malloc(result_len + 1);

	const char *s1;
	char *s2;
	assert(result && "Memory allocation failed");
	memset(result, '\n', result_len);
	
	for (s1 = source, s2 = result; *s1; s1++) 
	{
		*s2++ = *s1;
		if(*s1 == ',')
		 s2++;
	
	}
	*s2 = 0;

	return result;  // caller must free it!
}

// ======================================================================== //
//  C++-style string approach.                                              //
// ======================================================================== //
static string InsertNewlinesCppStyle(const string& source) {
	const auto result_len = source.size() * 2;
	string result(result_len, '\n');

	auto ri = begin(result);
	for (const auto c : source) 
	{
		*ri++ = c;
		ri += c == ',';
	}
	result.erase(ri, end(result));   // Throw the rest away

	return result;
}

// ======================================================================== //
//  Generate a checksum so we're sure we're correct.                        //
// ======================================================================== //
static uint64_t Checksum(const char *const s) {
	uint64_t sum = 0;
	for (auto i = 0; s[i]; ++i) {
		sum = sum * 31 + s[i];
	}
	return sum;
}

// ======================================================================== //
//  Dump outputs for debug purposes.                                        //
// ======================================================================== //
static void DumpOutput(const string& reference, const string& result) {
	ofstream ref_file("ref.txt", std::ios::binary);
	ofstream rslt_file("rslt.txt", std::ios::binary);

	ref_file << reference;
	rslt_file << result;
}

// ======================================================================== //
//  The original StrReplace that started this all.                          //
// ======================================================================== //
static int OrigStrReplace(char *target, const char *needle,
	const char *replacement, int len)
{
	char *buffer = (char*)calloc(1, len);
	if (!buffer)
	{
		puts("Wow! That file's too big for me. Out of memory!");
		return -1;
	}

	char *insert_point = &buffer[0];
	const char *tmp = target;
	size_t needle_len = strlen(needle);
	size_t repl_len = strlen(replacement);

	while (1)
	{
		const char *p = strstr(tmp, needle);
		if (p == NULL)
		{
			strcpy(insert_point, tmp);
			break;
		}
		memcpy(insert_point, tmp, p - tmp);
		insert_point += p - tmp;
		memcpy(insert_point, replacement, repl_len);
		insert_point += repl_len;
		tmp = p + needle_len;
	}
	strcpy(target, buffer);
	//delete(buffer);
	free(buffer);   // Don't call delete on a malloc'd buffer.
	return 0;
}


// ======================================================================== //
//  Main benchmark.                                                         //
// ======================================================================== //

int main() {
	auto tot_c_time = 0.0;
	auto tot_cpp_time = 0.0;
	auto tot_oc_time = 0.0;
	// Let's pick a random size between 4MB and 8MB.
	auto dist = uniform_int_distribution<size_t>(1u << 22, 1u << 23);
	auto input_str = string{};

	// Initialize the time.
	InitTime();

	// Now let's benchmark!
	for (auto i = 0; i < 100; ++i) 
	{
		// Generate this test-case.
		GenerateString(input_buf, input_str, dist(rng));

		BigLen = strlen(input_buf);
		// Call the C function once and generate our reference checksum
		auto reference = InsertNewlinesCStyle(input_buf);
		const auto ref_csum = Checksum(reference);

		// Call the C function 10 times.
		for (auto j = 0; j < 10; ++j) 
		{
			const auto start_c = GetTime();
			auto result = InsertNewlinesCStyle(input_buf);
			const auto stop_c = GetTime();
			tot_c_time += stop_c - start_c;

			const auto csum = Checksum(result);
			if (csum != ref_csum) {
				cerr << "Checksum mismatch on C code\n"
					<< csum << " vs. " << ref_csum << '\n';
				DumpOutput(reference, result);
				exit(1);
			}

			// C code requires us to free its result.
			free(result);
		}

		// Call the C++ function 10 times.
		for (auto j = 0; j < 10; ++j) 
		{
			const auto start_cpp = GetTime();
			auto result = InsertNewlinesCppStyle(input_str);
			const auto stop_cpp = GetTime();
			tot_cpp_time += stop_cpp - start_cpp;

			const auto csum = Checksum(result.c_str());
			if (csum != ref_csum) {
				cerr << "Checksum mismatch on C++ code\n"
					<< csum << " vs. " << ref_csum << '\n';
				DumpOutput(reference, result);
				exit(1);
			}
		}

		// Call the Orig C function 10 times.
		// It takes a bit more work, as it modifies the string in-place.
		for (auto j = 0; j < 10; ++j) 
		{

			// Copy the input to the output. This cost is off the books.
			memcpy(output_buf, input_buf, input_str.size() + 1);

			// Benchmark the original C code that started this.
			const auto start_oc = GetTime();
			OrigStrReplace(output_buf, ",", ",\n", max_size * 2);
			const auto stop_oc = GetTime();
			tot_oc_time += stop_oc - start_oc;

			const auto csum = Checksum(output_buf);

			if (csum != ref_csum) {
				cerr << "Checksum mismatch on orig C code\n"
					<< csum << " vs. " << ref_csum << '\n';
				DumpOutput(reference, output_buf);
				exit(1);
			}
		}

		// Free the reference copy.
		free(reference);
	}

	std::cout << "Total C time:     " << tot_c_time << " seconds\n";
	std::cout << "Total C++ time:   " << tot_cpp_time << " seconds\n";
	std::cout << "Total OrigC time: " << tot_oc_time << " seconds\n";

	return 0;
}