benchmarking interval collection lookup

.gitignore

main
test
*.S
*.o
*.vim
.depends
tags

common.h

#pragma once
#include <random>

static auto gen_tile_id = [prng=std::mt19937{42}, dist=std::uniform_int_distribution<>(1,1600<<20)] () mutable 
    { return dist(prng); };

#include <boost/functional/hash.hpp>
template <typename C> size_t digest(C const& c) { return boost::hash_range(c.begin(), c.end()); }

#include <vector>
#include <algorithm>
#include <iostream>
std::vector<int> gen_boundaries() {
    std::vector<int> boundaries(1024);
    std::generate(boundaries.begin(), boundaries.end(), gen_tile_id);
    std::sort(boundaries.begin(), boundaries.end());
    //std::cout << "DEBUG DIGEST boundaries: " << digest(boundaries) << "\n";;

    return boundaries;
}

main.cpp

#include <iostream>
#include <vector>
#include <string>
#include <map>

#include "../Includes/TileSetManager.h"

#include <random>
#include <algorithm>
#include <boost/chrono.hpp>
#include <boost/chrono/chrono_io.hpp>

template <typename F>
auto timed(char const* task, F&& f) {
    using namespace boost::chrono;
    struct _ {
        high_resolution_clock::time_point s;
        const char* task;
        ~_() { std::cout << " -- (" << task << " completed in " << duration_cast<milliseconds>(high_resolution_clock::now() - s) << ")\n"; }
    } timing { high_resolution_clock::now(), task };

    return f();
}

#include "common.h"
std::vector<int> gen_tiles(size_t n = (1ull << 22)) {
    std::vector<int> r(n);
    std::generate(r.begin(), r.end(), gen_tile_id);

    //std::cout << "DEBUG DIGEST tiles #n: " << r.size() << "\n";;
    //std::cout << "DEBUG DIGEST tiles: " << digest(r) << "\n";;

    return r;
}

TileSetManager gen_tilesets() {
    TileSetManager manager;
    int max = 0;

    for (auto b : gen_boundaries()) {
        manager.registerTileSet(TileRange(max, b));
        max = b+1;
    }

    return manager;
}

int main()
{
	std::vector<int> tiles = timed("Generating tiles", [] { return gen_tiles(); });
	TileSetManager manager = timed("Registering tilesets", [] { return gen_tilesets(); });

    std::map<TileRange const*, size_t> tally = timed("TileRange search", [&]
	{
        std::map<TileRange const*, size_t> tally;
		// Loop each tile
		for (auto tileId : tiles)
		{
			// Tiles with no ids have no tilesets. No need to search for them
			if (tileId)
			{
                TileRange const* set = manager.getTileSetByTileId(tileId); // Uses O(1)
                tally[set]++;
			}

		}
        return tally;
	});

#if 1
    for (auto tr : tally) {
        std::cout << "range tally: " << tr.second;
        if (tr.first)
            std::cout << " [" << tr.first->first << "," << tr.first->second << "]\n";
        else               
            std::cout << " [none]\n";
    }
#endif

	return tally.size();
}

Makefile

all:main main.S test test.S

CPPFLAGS+=-std=c++1y -Wall -pedantic
CPPFLAGS+=-g -O3
#BOOST_DIR=/mnt/LARGE/MODULAR_BOOST/modular-boost
BOOST_DIR=/home/sehe/custom/boost
CPPFLAGS+=-isystem /home/sehe/custom/nonius/include
CPPFLAGS+=-isystem $(BOOST_DIR)

# CPPFLAGS+=-fopenmp
CPPFLAGS+=-pthread
CPPFLAGS+=-march=native

LDFLAGS+=-L $(BOOST_DIR)/stage/lib/ -Wl,-rpath,$(BOOST_DIR)/stage/lib
LDFLAGS+=-lboost_system -lboost_chrono

# CXX=g++-5
# CXX=/usr/lib/gcc-snapshot/bin/g++
# CC=/usr/lib/gcc-snapshot/bin/gcc
CXX=clang++-3.6 -stdlib=libc++
# CC=clang

%.S:%.cpp
	$(CXX) $(CPPFLAGS) $< -S -masm=intel -o - | egrep -v '\s*\.' | c++filt > $@

%.o:%.cpp
	$(CXX) $(CPPFLAGS) $< -c -o $@

%:%.o
	$(CXX) $(CPPFLAGS) $^ -o $@ $(LDFLAGS)

.depends: *.cpp
	$(CXX) $(CPPFLAGS) $^ -M > $@

-include .depends

test.cpp

#include <boost/icl/interval_set.hpp>
#include <boost/icl/separate_interval_set.hpp>

namespace icl = boost::icl;

using TileSets = icl::separate_interval_set<int>;

struct TileRange : TileSets::interval_type::type {
    TileRange(int b, int e) : TileSets::interval_type(closed(b, e)) {}
};

struct Tile : TileSets::interval_type::type {
    Tile(int id) : TileSets::interval_type(id) {}
};

#include "common.h"
#include <iostream>
#include <iomanip>
#include <boost/chrono/chrono_io.hpp>

std::vector<int> gen_tiles   (size_t n = (1ull << 22)) {
    std::vector<int> r(n);
    std::generate_n(r.begin(), n, gen_tile_id);

    //std::cout << "DEBUG DIGEST tiles: " << digest(r) << "\n";;
    return r;
}

TileSets gen_tilesets() {
    TileSets r;
    int max = 0;

    for (auto b : gen_boundaries()) {
        r.insert(TileRange(max, b));
        max = b+1;
    }

    //std::cout << "DEBUG TILESETS: " << r << "\n";
    return r;
}

template <typename F>
auto timed(char const* task, F&& f) {
    using namespace boost::chrono;
    struct _ {
        high_resolution_clock::time_point s;
        const char* task;
        ~_() { std::cout << " -- (" << task << " completed in " << duration_cast<milliseconds>(high_resolution_clock::now() - s) << ")\n"; }
    } timing { high_resolution_clock::now(), task };

    return f();
}

int main() {
    auto const tiles = timed("Generate tiles", []     { return gen_tiles(); });
    auto const ts    = timed("Generate tile sets", [] { return gen_tilesets(); });

    //std::cout << ts << "\n----\n";

    {
        auto mm = std::minmax_element(tiles.begin(), tiles.end());
        std::cout << "Random tiles generated:    " << tiles.size()           << " across a domain of " << std::setprecision(2) << static_cast<double>(*mm.second - *mm.first) << "\n";
    }
    std::cout << "Tilesets to match against: " << ts.iterative_size()    << " across a domain of " << std::setprecision(2) << static_cast<double>(ts.size()) << "\n";

    std::map<TileSets::value_type const*, size_t> tally = timed("TileRange search", [&]
	{
        std::map<TileSets::value_type const*, size_t> tally;
		// Loop each tile
		for (auto tileId : tiles)
		{
			// Tiles with no ids have no tilesets. No need to search for them
			if (tileId) {
                auto it = ts.find(tileId); // Uses O(1)
                tally[ts.end() == it? nullptr : &*it]++;
			}

		}
        return tally;
	});
    
#if 1
    for (auto tr : tally)
    {
        std::cout << "range tally: " << tr.second << " ";
        if (tr.first)
            std::cout << *tr.first << "\n";
        else
            std::cout << "[)" << "\n";
    }
#endif

	return tally.size();
}

TileSetManager.h

#ifndef TILESET_MANAGER_H
#define TILESET_MANAGER_H

#include <vector>
#include <set>
#include <string>
#include <cassert>

//#include "TileRange.h"

/// Inclusive range of tiles [first, second]
using TileRange = std::pair<int, int>;

class TileSetManager
{
public:
	TileSetManager()
	{
		lookup.resize(1600u<<20, nullptr); // ~128MiB
	}

	~TileSetManager()
	{
		lookup.clear();
		sets.clear();
	}

	void registerTileSet(TileRange set)
	{
		auto insertion = sets.insert(set);
        assert(insertion.second);

		// Update the lookup table
        // SEHE this implies that ranges are EXCLUSIVE (I mean, no overlaps can be had)
		for (int i = set.first; i <= set.second; ++i) {
#if 0
            // THIS LOOKS VERY BROKEN TO ME, see the comment from `main`:
            // // Note: this is an example. Values are no way guaranteed to be ordered!!
            lookup.push_back(set);
#else // SEHE suggested fixed implementation
            lookup.at(i) = &*insertion.first; // validates the tile id
#endif
		}
	}

    // Instead, if we return a "TileRange" with "return *lookup[tileId - 1]" would this increase the speed?
    // SEHE slower. It might be /as fast/ depending on how it's used
    TileRange const* getTileSetByTileId(size_t tileId) const
    {
        return lookup.at(tileId/* - 1*/); // SEHE explain the "-1"?
    }

/*
 *    // Instead, if we return a "TileRange" with "return *sets[index]" would this increase the speed?
 *    // SEHE see above
 *    TileRange* getTileSetByIndex(size_t index)
 *    {
 *        return sets[index];
 *    }
 *
 *    size_t getTileSetCount() 
 *    { 
 *        return sets.size(); 
 *    }
 */

private:
	std::set<TileRange> sets;
	std::vector<TileRange const*> lookup;
};

#endif

TimeProfiler.h

#ifndef TIME_PROFILER_H
#define TIME_PROFILER_H

#include <stdio.h>
#include <time.h>
#include <chrono>
#include <thread>
#include <string>

namespace profiler
{
// The time profiling class
class Time
{
public:
	Time(const std::string& str) 
		: m_str(str), m_time(std::chrono::high_resolution_clock::now()) { }

	virtual ~Time()
	{
        using namespace std::chrono;
        auto done     = high_resolution_clock::now();
        auto duration = done - m_time;
        auto msecs    = duration_cast<milliseconds>(duration).count();

		printf("%s took %lli milliseconds\n", m_str.empty() ? "Block" : m_str.c_str(), msecs);
	}

private:
	std::string m_str;
	std::chrono::high_resolution_clock::time_point m_time;
};
}

#ifdef _DEBUG
// Profile only if debugging. This profiles the time spent to process the block that this macro was called within
#ifndef TIME
#define TIME(str) profiler::Time timer__(str)
#endif // TIME
#else
// If not debugging, do nothing
#ifndef TIME
#define TIME(str) do { } while(0) // This avoids empty statements
#endif // TIME
#endif // _DEBUG

#ifndef SLEEP
#define SLEEP(ms) std::this_thread::sleep_for(std::chrono::milliseconds(ms));
#endif

// A working example of this profiler. Call EXAMPLE() and it should print 16 milliseconds
#ifndef EXAMPLE
#define EXAMPLE() \
	profiler::Time timer__("Example that takes 16 milliseconds (value should match)"); \
	std::this_thread::sleep_for(std::chrono::milliseconds(1)); \
	std::this_thread::sleep_for(std::chrono::milliseconds(2)); \
	std::this_thread::sleep_for(std::chrono::milliseconds(3)); \
	std::this_thread::sleep_for(std::chrono::milliseconds(10));
#endif

#endif