set_test.cpp

application/octet-stream

Download

/*
 * set_test.cpp:
 *
 * Measure the performance characteristics of using strcoll() as
 * a string comparator rather than caching strxfrm() blobs.
 *
 * Author: Peter Geoghegan
 *
 * A std::set is an ascending container of unique elements. The implementation
 * that I used for any numbers published was the one from Gnu libstdc++, on
 * Fedora 16. That particular implementation uses a red-black tree, but the
 * standard's requirement that common operations (search, insert, delete) take
 * logarithmic time effectively requires the use of some kind of self-balancing
 * binary search tree, which isn't a bad proxy for a btree for my purposes.
 */

#include <set>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <sys/time.h>
#include <cassert>
#include <algorithm>

#include <boost/shared_array.hpp>

#define ORIG_STRING_SIZE	32
#define BLOB_STRING_SIZE	128

using namespace std;

double
timeval_subtract(struct timeval *x, struct timeval *y)
{
	struct timeval result;
	/* Compute the time remaining to wait. tv_usec is certainly positive. */
	result.tv_sec = x->tv_sec - y->tv_sec;
	result.tv_usec = x->tv_usec - y->tv_usec;

	/* return difference in seconds */
	return result.tv_sec + ((double) result.tv_usec / 1000000);
}

void
reset_prng_seed()
{
    srand(0);
}

/*
 * Enter a psuedo-random sequence of characters into a buffer specified by buf
 *
 * This just places lower-case ascii characters into the buffer, so strings
 * generated by this function should be relatively cheap to do a
 * collation-aware sort with when LC_COLLATE is set to en_*.UTF-8. I've made a
 * point of using en_US.UTF-8 in benchmarks.
 */
void
place_random_string(char *buf)
{
    static std::string charset = "abcdefghijklmnopqrstuvwxyz";

    for (int i = 0; i < ORIG_STRING_SIZE; i++)
        buf[i] = charset[rand() % charset.length()];
    buf[ORIG_STRING_SIZE] = '\0';
}

class string_wrapper
{
public:
	static bool use_strcoll;

	string_wrapper();
	virtual ~string_wrapper();
	// operator< is our comparator, required by std::set
	bool operator<(const string_wrapper &rhs) const;
	// If you want to see the strings contents printed to stdout, call this
	// function:
	void print_contents() const;
private:
	// Generate sort key, return cached key if one exists
	const char* sortkey() const;
	char orig_string[ORIG_STRING_SIZE+1];
	// mark these "mutable" so they can be modified in our comparator as part
	// of the required lazy initialization (std::set in turn requires that it
	// is a const member function). Not very idiomatic, but the easiest way to
	// approximate how this might work in Postgres.
	mutable boost::shared_array<char> strxfrm_buf;
};

bool string_wrapper::use_strcoll = true;

/*
 * Default constructor
 */
string_wrapper::string_wrapper()
{
	// Generate a random string in a buffer. This class conceptually manages
	// that resource.
	place_random_string(orig_string);
}

/*
 * Boilerplate destructor
 */
string_wrapper::~string_wrapper()
{
}

const char* string_wrapper::sortkey() const
{
	if (!strxfrm_buf) {
		strxfrm_buf.reset(new char [BLOB_STRING_SIZE+1]);
		const size_t l = strxfrm(strxfrm_buf.get(), orig_string, BLOB_STRING_SIZE+1);
		assert(l < BLOB_STRING_SIZE+1);
	}
	
	return strxfrm_buf.get();
}

/*
 * Comparator required by std::set
 */
bool string_wrapper::operator<(const string_wrapper &rhs) const
{
	if (use_strcoll)
	{
		/*
		 * I might have simulated the extra strcmp() tie-break overhead here,
		 * but that interface isn't supported.
		 */
		return strcoll(orig_string, rhs.orig_string) < 0;
	}
	else
	{
		return strcmp(sortkey(), rhs.sortkey()) < 0;
	}
}

void
string_wrapper::print_contents() const
{
	printf("String contents: %s\n", orig_string);
}

#define NUM_ELEMS	500000

int
main(int argc, const char *argv[])
{
	double non_opt_tot = 0, opt_tot = 0;

	int runs = 0;
	for(;;)
	{
		struct timeval begin, end;
		double secs_result;
		// Just so there's no ambiguity about what memory is allocated when,
		// allocate set dynamically:
		string_wrapper* non_opt = new string_wrapper [NUM_ELEMS];

		/* simple strcoll run */
		string_wrapper::use_strcoll = true;
		gettimeofday(&begin, NULL);
		std::sort(non_opt, non_opt + NUM_ELEMS);
		gettimeofday(&end, NULL);

		secs_result = timeval_subtract(&end, &begin);

		printf("Time elapsed with strcoll: %f seconds\n", secs_result);

		non_opt_tot += secs_result;

		// You may wish to uncomment this to see the sorted elements printed
		//
		//print_set_contents(*non_opt);

		// This delete statement calls the set's destructor, which is turn calls
		// each string's destructor, freeing all resources used.
		delete [] non_opt;

		// Actual string values should be completely deterministic for both sets of behaviours
		reset_prng_seed();

		string_wrapper* opt = new string_wrapper [NUM_ELEMS];

		/* strxfrm run */
		string_wrapper::use_strcoll = false;
		gettimeofday(&begin, NULL);
		std::sort(opt, opt + NUM_ELEMS);
		gettimeofday(&end, NULL);

		secs_result = timeval_subtract(&end, &begin);
		printf("Time elapsed with strxfrm optimization: %f seconds\n", secs_result);

		opt_tot += secs_result;

		// You may wish to uncomment this to see the sorted elements printed
		//
		//print_set_contents(*opt);

		delete [] opt;

		++runs;
		if (runs % 5 ==0)
			printf("*****strcoll average: %f strxfrm average: %f*****\n", non_opt_tot / runs, opt_tot / runs);
	}
	return 0;
}