radix_experiment.cpp

/*
	Basic test program for running experiments.

	$ ./radix <entries> [<use_mmap> <use_huge> <type> <hex-mask>]

	Example:

	$ ./radix 0 1 0 uint32_t 0x00FFFFFF

	Note: Will not compile on WIN32 in current state.
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cinttypes>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <sys/mman.h> // for mmap

#include "radix_sort.hpp"

static int RADIX_MMAP_FLAGS = MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE | MAP_POPULATE; // | MAP_HUGE_2MB

#ifdef WIN32
#include <windows.h>
#define CLOCK_MONOTONIC_RAW 0
// via https://stackoverflow.com/a/31335254/156769
int clock_gettime(int, struct timespec *spec)
{
	__int64 wintime; GetSystemTimeAsFileTime((FILETIME*)&wintime);
	wintime -= 116444736000000000LL; // 1 jan 1601 to 1 jan 1970
	spec->tv_sec  =wintime / 10000000LL;      // seconds
	spec->tv_nsec =wintime % 10000000LL *100; // nano-seconds
	return 0;
}
#endif

#define RESTRICT __restrict__

void timespec_diff(struct timespec *start, struct timespec *stop,
				struct timespec *result)
{
	if ((stop->tv_nsec - start->tv_nsec) < 0) {
		result->tv_sec = stop->tv_sec - start->tv_sec - 1;
		result->tv_nsec = stop->tv_nsec - start->tv_nsec + 1000000000;
	} else {
		result->tv_sec = stop->tv_sec - start->tv_sec;
		result->tv_nsec = stop->tv_nsec - start->tv_nsec;
	}
}

auto my_allocate(size_t size, int use_mmap, int use_huge, const char *usage) -> void* {
	void *mem = nullptr;

	if (use_mmap) {
		mem = (uint32_t*)mmap(nullptr, size, PROT_READ | PROT_WRITE, RADIX_MMAP_FLAGS, -1, 0);
		assert(mem && mem != MAP_FAILED);
		printf("Mapped memory at %p, %zu bytes for %s\n", mem, size, usage);
	} else {
		printf("Allocating %zu bytes for %s.\n", size, usage);
		if (use_huge) {
			int res = posix_memalign((void**)&mem, 1UL << 21, size);
			if (res) {
				fprintf(stderr, "Failed to allocate: %d\n", res); // ENOMEM or EINVAL
				abort();
			}
			madvise(mem, size, MADV_HUGEPAGE);
			printf("Requested MADV_HUGEPAGE for pages.\n");
		} else {
			mem = malloc(size);
		}
		assert(mem);
	}
	return mem;
}

static auto read_file(const char *filename, size_t *limit, int use_mmap, int use_huge) -> void* {
	void *keys = nullptr;
	size_t bytes = 0;

	FILE *f = fopen(filename, "rb");
	if (f) {
		fseek(f, 0, SEEK_END);
		bytes = ftell(f);
		fseek(f, 0, SEEK_SET);

		if (*limit > 0 && *limit < bytes)
			bytes = *limit;

		keys = my_allocate(bytes, use_mmap, use_huge, "input.");
		assert(keys);

		long rnum = fread(keys, bytes, 1, f);
		fclose(f);
		if (rnum != 1) {
			free(keys);
			return nullptr;
		}
	}

	*limit = bytes;
	return keys;
}

template <typename T>
void print_sort(T *keys, size_t offset, size_t n) {
	for (size_t i = offset ; i < offset + n ; ++i) {
		// NOTE: Hackety-hack.
		if constexpr(sizeof(T) > 4) {
			printf("%08zu: %016" PRIx64, i, (uint64_t)keys[i]);
		} else if constexpr(sizeof(T) > 2) {
			printf("%08zu: %08" PRIx32, i, (uint32_t)keys[i]);
		} else if constexpr(sizeof(T) == 2) {
			printf("%08zu: %04" PRIx16, i, (uint16_t)keys[i]);
		} else {
			printf("%08zu: %02" PRIx8, i, (uint8_t)keys[i]);
		}
		printf("\n");
	}
}

template <>
void print_sort(float *keys, size_t offset, size_t n) {
	for (size_t i = offset ; i < offset + n ; ++i) {
		printf("%08zu: %f\n", i, keys[i]);
	}
}

template <>
void print_sort(double *keys, size_t offset, size_t n) {
	for (size_t i = offset ; i < offset + n ; ++i) {
		printf("%16zu: %f\n", i, keys[i]);
	}
}

template <typename T>
auto verify_sort_kf(T *keys, size_t n) -> size_t {
	// Could Use std::is_sorted(keys, keys+n); from <algorithm> but no index.
	printf("Verifying sort... ");
	size_t forward_fail = 0;
	for (size_t i = 1 ; i < n ; ++i) {
		if (keys[i-1] > keys[i]) {
			forward_fail = i;
			break;
		}
	}
	if (forward_fail == 0) {
		printf("Forward sorted OK.\n");
		return 0;
	}

	size_t reverse_fail = 0;
	for (size_t i = 1 ; i < n ; ++i) {
		if (keys[i-1] < keys[i]) {
			reverse_fail = i;
			break;
		}
	}
	if (reverse_fail == 0) {
		printf("Reverse sorted OK.\n");
		return 0;
	}

	printf("Forward sort of array invalid at index %zu.\n", forward_fail);
	printf("%zu: %" PRIx64 " < ", forward_fail-1, (uint64_t)keys[forward_fail-1]);
	printf("%zu: %" PRIx64 "\n", forward_fail, (uint64_t)keys[forward_fail]);

	printf("Reverse sort of array invalid at index %zu.\n", reverse_fail);
	printf("%zu: %" PRIx64 " < ", reverse_fail-1, (uint64_t)keys[reverse_fail-1]);
	printf("%zu: %" PRIx64 "\n", reverse_fail, (uint64_t)keys[reverse_fail]);

	return 1;
}

template <typename T>
auto test_radix_sort(const char *filename, size_t entries, int use_mmap, int use_huge, uint64_t value_mask) -> int {

	size_t bytes = sizeof(T)*entries;

	T *src = (T*)read_file(filename, &bytes, use_mmap, use_huge);
	assert(src);
	T *aux = (T*)my_allocate(bytes, use_mmap, use_huge, "auxilary buffer.");
	assert(aux);

	size_t n = bytes / sizeof(*src);

	// Mangle input to demonstrate column selection.
	if (value_mask != (uint64_t)-1) {
		printf("Applying value mask to input.\n");
		for (size_t i=0 ; i < n ; ++i) {
			// src[i] &= value_mask;
			uint64_t buf;
			std::memcpy(&buf, src + i, sizeof(T));
			buf &= value_mask;
			std::memcpy(src + i, &buf, sizeof(T));
		}
	}

	struct timespec tp_start;
	struct timespec tp_end;

	printf("Sorting %zu entries...\n", n);
	clock_gettime(CLOCK_MONOTONIC_RAW, &tp_start);
	auto *sorted = radix_sort(src, aux, n);
	clock_gettime(CLOCK_MONOTONIC_RAW, &tp_end);

#ifdef VERIFY_SORT
	if (verify_sort_kf(sorted, n) != 0) {
		return 1;
	}
#endif

	// Debug print head and tail of the sorted list
	size_t nprint = 20;
	if (n <= nprint) {
		print_sort(sorted, 0, std::min(n, nprint));
	} else {
		print_sort(sorted, 0, nprint/2);
		printf("[...]\n");
		int left = std::min(nprint/2, n - nprint/2);
		print_sort(sorted, n - left, left);
	}

	struct timespec tp_res;
	timespec_diff(&tp_start, &tp_end, &tp_res);
	double time_ms = (tp_res.tv_sec * 1000) + (tp_res.tv_nsec / 1.0e6f);
	printf("Sorted %zu entries in %.4f ms\n", n, time_ms);

	if (use_mmap) {
		munmap(src, bytes);
		munmap(aux, bytes);
	} else {
		free(src);
		free(aux);
	}
	return 0;
}


auto main(int argc, char *argv[]) -> int
{
	int entries = argc > 1 ? atoi(argv[1]) : 0;
	int use_mmap = argc > 2 ? atoi(argv[2]) : 0;
	int use_huge = argc > 3 ? atoi(argv[3]) : 0;
	const char *ktype = argc > 4 ? argv[4] : "uint32_t";
	uint64_t value_mask = argc > 5 ? strtoull(argv[5], nullptr, 16) : -1;

	if (argc == 1) {
		printf("Usage: %s <count> [<use_mmap> <use_huge> <uint8_t|uint16_t|uint32_t|uint64_t|int32_t|int64_t|float|double> <hex-mask>]\n", argv[0]);
		exit(0);
	}

	const char *src_fn = "40M_32bit_keys.dat";

	if (use_huge)
		RADIX_MMAP_FLAGS |= MAP_HUGETLB;

	printf("src='%s', entries=%d, use_mmap=%d, use_huge=%d, type='%s', mask=0x%08lx \n", src_fn, entries, use_mmap, use_huge, ktype, value_mask);

	int res = 100;
	// TODO: special-case for bool
	//
	if (strcmp(ktype, "uint8_t") == 0) {
		res = test_radix_sort<uint8_t>(src_fn, entries, use_mmap, use_huge, value_mask);
	} else if (strcmp(ktype, "uint16_t") == 0) {
		res = test_radix_sort<uint16_t>(src_fn, entries, use_mmap, use_huge, value_mask);
	} else if (strcmp(ktype, "uint32_t") == 0) {
		res = test_radix_sort<uint32_t>(src_fn, entries, use_mmap, use_huge, value_mask);
	} else if (strcmp(ktype, "uint64_t") == 0) {
		res = test_radix_sort<uint64_t>(src_fn, entries, use_mmap, use_huge, value_mask);
	} else if (strcmp(ktype, "int32_t") == 0) {
		res = test_radix_sort<int32_t>(src_fn, entries, use_mmap, use_huge, value_mask);
	} else if (strcmp(ktype, "int64_t") == 0) {
		res = test_radix_sort<int64_t>(src_fn, entries, use_mmap, use_huge, value_mask);
	} else if (strcmp(ktype, "float") == 0) {
		res = test_radix_sort<float>(src_fn, entries, use_mmap, use_huge, value_mask);
	} else if (strcmp(ktype, "double") == 0) {
		res = test_radix_sort<double>(src_fn, entries, use_mmap, use_huge, value_mask);
	} else {
		printf("Error: unknown key type, '%s'.\n", ktype);
	}

	return res;
}