astorage access benchmark.md

WorldAccess wa

Linear access

foreach(index; 0..CHUNK_SIZE_CUBE)
{
	wa.getBlock(index);
}

Random access

auto randIndexes = iota(0, CHUNK_SIZE_CUBE).array;
randomShuffle(randIndexes);
foreach(index; randIndexes)
{
  wa.getBlock(index);
}

                       +-------------------------------------------+
                       |                 time, ms                  |
+----------------+-----+---------------------+---------------------+
|                |     |   squential access  |    random access    |
|  storage type  | len +----------+----------+----------+----------+
|                |     |    x32   |    x64   |    x32   |    x64   |
+----------------+-----+----------+----------+----------+----------+
|        uniform |   0 | 0,164 ms | 0,357 ms | 0,165 ms | 0,367 ms |
+----------------+-----+----------+----------+----------+----------+
|      fullArray | max | 0,198 ms | 0,374 ms | 0,166 ms | 0,385 ms |
+----------------+-----+----------+----------+----------+----------+
|      linearMap |   1 | 0,214 ms | 0,424 ms | 0,221 ms | 0,439 ms |
|      linearMap |   2 | 0,253 ms | 0,506 ms | 0,262 ms | 0,502 ms |
|      linearMap |   3 | 0,308 ms | 0,549 ms | 0,305 ms | 0,567 ms |
|      linearMap |   4 | 0,356 ms | 0,615 ms | 0,450 ms | 0,613 ms |
|      linearMap |   5 | 0,414 ms | 0,695 ms | 0,420 ms | 0,702 ms |
|      linearMap |   6 | 0,466 ms | 0,778 ms | 0,476 ms | 0,774 ms |
|      linearMap |   7 | 0,532 ms | 0,845 ms | 0,631 ms | 0,856 ms |
|      linearMap |   8 | 0,571 ms | 0,956 ms | 0,560 ms | 0,923 ms |
+----------------+-----+----------+----------+----------+----------+
|        hashMap |   1 | 0,739 ms | 0,993 ms | 0,817 ms | 0,972 ms |
|        hashMap |   2 | 0,793 ms | 1,028 ms | 0,796 ms | 1,042 ms |
|        hashMap |   3 | 0,857 ms | 1,092 ms | 0,863 ms | 1,063 ms |
|        hashMap |   4 | 0,913 ms | 1,091 ms | 0,860 ms | 1,048 ms |
|        hashMap |   5 | 0,931 ms | 1,129 ms | 0,837 ms | 1,135 ms |
|        hashMap |   6 | 1,113 ms | 1,338 ms | 1,232 ms | 1,122 ms |
|        hashMap |   7 | 1,056 ms | 1,334 ms | 0,853 ms | 1,097 ms |
|        hashMap |   8 | 0,853 ms | 1,087 ms | 0,864 ms | 1,111 ms |
+----------------+-----+----------+----------+----------+----------+

bmain.d

module main;

import std.experimental.allocator;
import std.experimental.allocator.gc_allocator;
import std.algorithm;
import std.array;
import std.bitmanip;
import std.datetime;
import std.random;
import std.range;
import std.stdio;
import std.string;

enum CHUNK_SIZE_SQR = 32 * 32;
enum CHUNK_SIZE_CUBE = 32 * 32 * 32;
alias BlockId = ubyte;

void main()
{
	enum numEntries = 8;
	numIterations = 16;
	benchAll!false(numEntries);
	benchAll!true(numEntries);
}

void benchAll(bool randomAccess)(uint numEntries)
{
	Layer!(ubyte) layer;
	WorldAccess wa = WorldAccess(allocatorObject(GCAllocator.instance));

	writefln("-----------------------");
	writefln("randomAccess = %s", randomAccess);
	writefln("-----------------------");

	// uniform
	bench(wa, format("% 15s % 3s", "uniform", 0));


	// linear
	auto randomBlockPairs = new layer.KeyValue[CHUNK_SIZE_CUBE];
	auto sortedBlockPairs = new layer.KeyValue[CHUNK_SIZE_CUBE];
	foreach(i, ref pair; randomBlockPairs) {
		pair.key = cast(layer.PosType)i;
		pair.value = uniform!"[]"(BlockId.min, BlockId.max);
	}
	randomShuffle(randomBlockPairs);
	wa.blocks.type = StorageType.linearMap;
	foreach(i; 1..numEntries+1) {
		sortedBlockPairs[0..i] = randomBlockPairs[0..i];
		sort!("a.key < b.key")(sortedBlockPairs[0..i]);
		wa.blocks.linearMap = sortedBlockPairs[0..i];
		bench(wa, format("% 15s % 3s", "linearMap", i));
	}

	// hashMap
	wa.blocks.type = StorageType.hashMap;
	foreach(i; 1..numEntries+1) {
		sortedBlockPairs[0..i] = randomBlockPairs[0..i];
		BlockId[layer.PosType] hashMap;
		foreach(pair; sortedBlockPairs[0..i])
			hashMap[pair.key] = pair.value;
		wa.blocks.hashMap = hashMap;
		bench(wa, format("% 15s % 3s", "hashMap", i));
	}

	// fullArray
	wa.blocks.type = StorageType.fullArray;
	auto randomBlocks = new BlockId[CHUNK_SIZE_CUBE];
	foreach(ref block; randomBlocks)
		block = uniform!"[]"(BlockId.min, BlockId.max);
	wa.blocks.fullArray = randomBlocks;
	bench(wa, format("% 15s % 3s", "fullArray", "max"));
}

MonoTime iterationStartTime;
Duration iterationsSumTime;
size_t numIterations;
void startIteration() {
	iterationStartTime = MonoTime.currTime;
}
void endIteration() {
	auto duration = MonoTime.currTime - iterationStartTime;
	iterationsSumTime += duration;
}
void printResults(string text)
{
	Duration averageTime = iterationsSumTime / numIterations;
	iterationsSumTime = Duration.zero;
	short msecs; short usecs;
	averageTime.split!("msecs", "usecs")(msecs, usecs);
	writefln("%s % 3s,%03s ms", text, msecs, usecs);
}

void bench(bool randomAccess = false)(ref WorldAccess wa, string name)
{
	static if (randomAccess) {
		auto randIndexes = iota(0, CHUNK_SIZE_CUBE).array;
		randomShuffle(randIndexes);
		foreach(_; 0..numIterations)
		{
			startIteration();
			foreach(index; randIndexes)
			{
				wa.getBlock(index);
			}
			endIteration();
		}
		printResults(name);
	} else {
		foreach(_; 0..numIterations)
		{
			startIteration();
			foreach(index; 0..CHUNK_SIZE_CUBE)
			{
				wa.getBlock(index);
			}
			endIteration();
		}
		printResults(name);
	}
}

struct WorldAccess {
	private IAllocator _allocator;
	Layer!(BlockId) blocks;

	this(IAllocator allocator = theAllocator)
	{
		_allocator = allocator;
	}
	BlockId getBlock(size_t index) {
		if (blocks.type == StorageType.compressedArray) {
			// decompress
			//_allocator
			blocks.type = StorageType.fullArray;
		}

		return getItem(blocks, index);
	}
}

enum StorageType
{
	uniform,
	linearMap,
	hashMap,
	compressedArray,
	fullArray,
}

struct Layer(T, size_t size = CHUNK_SIZE_CUBE)
{
	alias PosType = typeForSize!size;
	struct KeyValue {
		PosType key; T value;
	}

	StorageType type;
	union {
		T uniformData;
		KeyValue[] linearMap;
		T[PosType] hashMap;
		T[] compressedArray;
		T[] fullArray;
	}
}

T getItem(L : Layer!T, T)(L layer, size_t index, T defaultValue = T.init)
{
	final switch(layer.type) with(StorageType)
	{
		case uniform:
			return layer.uniformData;
		case linearMap:
			foreach(ref keyValue; layer.linearMap)
				if (keyValue.key == index)
					return keyValue.value;
			return defaultValue;
		case hashMap:
			return layer.hashMap.get(cast(layer.PosType)index, defaultValue);
		case compressedArray:
			assert(false, "Data needs to be uncompressed");
		case fullArray:
			return layer.fullArray[index];
	}
}

template typeForSize(size_t size)
{
	static if (size <= ubyte.max)
		alias typeForSize = ubyte;
	else static if (size <= ushort.max)
		alias typeForSize = ushort;
	else static if (size <= uint.max)
		alias typeForSize = uint;
	else static if (size <= ulong.max)
		alias typeForSize = ulong;
}