Oneplus/Makefile

## charts-template.html
<html>
    <head>
        <!--[if IE]><script language="javascript" type="text/javascript" src="http://flot.googlecode.com/svn/trunk/excanvas.min.js"></script><![endif]-->
        <script language="javascript" type="text/javascript" src="http://flot.googlecode.com/svn/trunk/jquery.js"></script>
        <script language="javascript" type="text/javascript" src="http://flot.googlecode.com/svn/trunk/jquery.flot.js"></script>
    </head>
    <body>

<script>
    series_settings = {
        lines: { show: true },
        points: { show: true }
    };

    grid_settings = { tickColor: '#ddd' };

    xaxis_settings = {
        tickSize: 5000000,
        tickFormatter: function(num, obj) { return parseInt(num/1000000) + 'M'; }
    };

    yaxis_runtime_settings = {
        tickSize: 10,
        tickFormatter: function(num, obj) { return num + ' sec.'; }
    };

    yaxis_memory_settings = {
        tickSize: 200*1024*1024,
        tickFormatter: function(num, obj) { return parseInt(num/1024/1024) + 'MiB'; }
    };

    legend_settings = {
        position: 'nw',
        backgroundOpacity: 0
    };

    runtime_settings = {
        series: series_settings,
        grid: grid_settings,
        xaxis: xaxis_settings,
        yaxis: yaxis_runtime_settings,
        legend: legend_settings
    };

    memory_settings = {
        series: series_settings,
        grid: grid_settings,
        xaxis: xaxis_settings,
        yaxis: yaxis_memory_settings,
        legend: legend_settings
    };

    __CHART_DATA_GOES_HERE__

    $(function () {
        $.plot($("#query_random-runtime"), chart_data['query_random-runtime'], runtime_settings);
        $.plot($("#query_ordered-runtime"), chart_data['query_ordered-runtime'], runtime_settings);
        $.plot($("#insert_random-runtime"), chart_data['insert_random-runtime'], runtime_settings);
        $.plot($("#insert_ordered-runtime"), chart_data['insert_ordered-runtime'], runtime_settings);
    });
</script>

<style>
    body, * { font-family: sans-serif; }
    div.chart {
        width: 700px;
        height: 230px;
    }
    div.xaxis-title {
        width: 700px;
        text-align: center;
        font-style: italic;
        font-size: small;
        color: #666;
    }
</style>

<div class="chart" id="insert_ordered-runtime"></div>
<div class="xaxis-title">number of entries in hash table</div>

<div class="chart" id="insert_random-runtime"></div>
<div class="xaxis-title">number of entries in hash table</div>

<div class="chart" id="query_ordered-runtime"></div>
<div class="xaxis-title">number of entries in hash table</div>

<div class="chart" id="query_random-runtime"></div>
<div class="xaxis-title">number of entries in hash table</div>

<div class="chart" id="randomstring-runtime"></div>
<div class="xaxis-title">number of entries in hash table</div>

</body>
</html>

## main.cc
#include <iostream>
#include <iomanip>
#include <locale>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <set>
#include <vector>
#include <unordered_map>
#include <map>
#include <google/dense_hash_map>
#include <google/sparse_hash_map>
#include <boost/unordered_map.hpp>
#include <boost/container/flat_map.hpp>
#include <boost/timer/timer.hpp>
#include <boost/lexical_cast.hpp>

std::vector<int> keys, random_keys, ordered_keys;
std::vector<int> queries, random_queries, ordered_queries;

void generate_random_unique_integers(std::size_t nr_keys,
    std::vector<int>& integers) {
  srand(time(NULL));
  std::set<int> mask;
  while (mask.size() < nr_keys) { mask.insert(rand()); }
  for (std::set<int>::const_iterator i = mask.begin();
      i != mask.end(); ++ i) {
    integers.push_back(*i);
  }
}

void generate_random_integers(std::size_t nr_keys,
    std::vector<int>& integers) {
  srand(time(NULL));
  for (auto i = 0; i < nr_keys; ++ i) {
    integers.push_back(rand());
  }
}

template <class map_type>
class Benchmark {
private:
  std::size_t repeat_times;
  std::string comments;
public:
  Benchmark(const std::string& _comments,
      std::size_t _repeat_times = 10000): comments(_comments), repeat_times(_repeat_times) {}

  void insert(const std::vector<int>& keys, const std::string& sign) {
    boost::timer::auto_cpu_timer _;
    for (auto i = 0; i < repeat_times; ++ i) { map_type rep; for (int key: keys) { rep[key] = 1024; } }
    std::cout << "insert_" << sign << "," << keys.size() << "," << comments << ",";
  }

  void queries(const std::vector<int>& keys, const std::vector<int> queries, const std::string& sign) {
    map_type rep; for (auto key: keys) { rep[key] = 1024; }
    boost::timer::auto_cpu_timer _;
    for (auto query: queries) { typename map_type::const_iterator itx = rep.find(query); if (itx != rep.end()) {} }
    std::cout << "query_" << sign << "," << keys.size() << "," << comments << ",";
  }
};

class BenchmarkGoogleDenseHashMap {
private:
  std::size_t repeat_times;
  std::string comments;
  typedef google::dense_hash_map<int, double> map_type;
public:
  BenchmarkGoogleDenseHashMap(const std::string& _comments,
      std::size_t _repeat_times = 10000): comments(_comments), repeat_times(_repeat_times) {}

  void insert(const std::vector<int>& keys, const std::string& sign) {
    boost::timer::auto_cpu_timer _;
    for (auto i = 0; i < repeat_times; ++ i) {map_type rep; rep.set_empty_key(-1); for (int key: keys) { rep[key] = 1024; } }
    std::cout << "insert_" << sign << "," << keys.size() << "," << comments << ",";
  }

  void queries(const std::vector<int>& keys, const std::vector<int> queries, const std::string& sign) {
    map_type rep; rep.set_empty_key(-1); for (auto key: keys) { rep[key] = 1024; }
    boost::timer::auto_cpu_timer _;
    for (auto query: queries) { typename map_type::const_iterator itx = rep.find(query); if (itx != rep.end()) {} }
    std::cout << "query_" << sign << "," << keys.size() << "," << comments << ",";
  }
};


template<class map_type>
void run(const std::string& name, std::size_t nr_tests) {
  Benchmark< map_type > bench(name, nr_tests);
  bench.insert(random_keys, "random");
  bench.insert(ordered_keys, "ordered");
  bench.queries(keys, random_queries, "random");
  bench.queries(keys, ordered_queries, "ordered");
}

int main(int argc, char* argv[]) {
  std::size_t nr_keys = boost::lexical_cast<int>(argv[1]);
  std::size_t nr_insertions = boost::lexical_cast<int>(argv[2]);
  std::size_t nr_queries = boost::lexical_cast<int>(argv[3]);
  generate_random_unique_integers(nr_keys, keys);
  random_keys = keys;   std::random_shuffle(random_keys.begin(), random_keys.end());
  ordered_keys = keys;  std::sort(ordered_keys.begin(), ordered_keys.end());

  generate_random_integers(nr_queries, queries);
  random_queries= queries;    std::random_shuffle(random_queries.begin(), random_queries.end());
  ordered_queries = queries;  std::sort(ordered_queries.begin(), ordered_queries.end());

  run< std::map<int, double> >("std::map", nr_insertions);
  run< std::unordered_map<int, double> >("std::unordered_map", nr_insertions);
  run< google::sparse_hash_map<int, double> >("google::sparse_hash_map", nr_insertions);
  run< boost::unordered_map<int, double> >("boost::unordered_map", nr_insertions);
  run< boost::container::flat_map<int, double> >("boost::flat_map", nr_insertions);

  {
    BenchmarkGoogleDenseHashMap bench("google::dense_hash_map", nr_insertions);
    bench.insert(random_keys, "random");
    bench.insert(ordered_keys, "ordered");
    bench.queries(keys, random_queries, "random");
    bench.queries(keys, ordered_queries, "ordered");
  }

  return 0;
}

## make_chart_data.py
import sys, json

lines = [ line.strip() for line in sys.stdin if line.strip() ]

by_benchtype = {}

for line in lines:
    benchtype, nkeys, program, runtime = line.split(',')[:4]
    nkeys = int(nkeys)
    #nbytes = int(nbytes)
    runtime = float(runtime.split()[0].rstrip("s"))

    by_benchtype.setdefault("%s" % benchtype, {}).setdefault(program, []).append([nkeys, runtime])

proper_names = {
        'std::map':                 'GCC 4.8.2 std::map',
        'std::unordered_map':       'GCC 4.8.2 std::unordered_map',
        'google::sparse_hash_map':  'Google sparsehash 2.0 sparse_hash_map',
        'google::dense_hash_map':   'Google sparsehash 2.0 dense_hash_map',
        'boost::unordered_map':     'Boost 1.57 unordered_map',
        'boost::flat_map':          'Boost 1.57 container/flat_map'
}

# do them in the desired order to make the legend not overlap the chart data
# too much
program_slugs = ['std::map', 'std::unordered_map', 'google::sparse_hash_map', 'google::dense_hash_map', 'boost::unordered_map', 'boost::flat_map']

chart_data = {}

for i, (benchtype, programs) in enumerate(by_benchtype.items()):
    chart_data[benchtype] = []
    for j, program in enumerate(program_slugs):
        data = programs[program]
        chart_data[benchtype].append({
            'label': proper_names[program],
            'data': [],
        })

        for k, (nkeys, value) in enumerate(data):
            chart_data[benchtype][-1]['data'].append([nkeys, value])

print 'chart_data = ' + json.dumps(chart_data)

## make_html.py
import sys
html_template = file('charts-template.html', 'r').read()
file('charts.html', 'w').write(html_template.replace('__CHART_DATA_GOES_HERE__', sys.stdin.read()))

## Makefile
all: benchmark

benchmark: main.cc
	g++ -std=c++0x -O3 -o benchmark main.cc -lboost_timer -lboost_system
	<html>
	<head>
	<!--[if IE]><script language="javascript" type="text/javascript" src="http://flot.googlecode.com/svn/trunk/excanvas.min.js"></script><![endif]-->
	<script language="javascript" type="text/javascript" src="http://flot.googlecode.com/svn/trunk/jquery.js"></script>
	<script language="javascript" type="text/javascript" src="http://flot.googlecode.com/svn/trunk/jquery.flot.js"></script>
	</head>
	<body>

	<script>
	series_settings = {
	lines: { show: true },
	points: { show: true }
	};

	grid_settings = { tickColor: '#ddd' };

	xaxis_settings = {
	tickSize: 5000000,
	tickFormatter: function(num, obj) { return parseInt(num/1000000) + 'M'; }
	};

	yaxis_runtime_settings = {
	tickSize: 10,
	tickFormatter: function(num, obj) { return num + ' sec.'; }
	};

	yaxis_memory_settings = {
	tickSize: 20010241024,
	tickFormatter: function(num, obj) { return parseInt(num/1024/1024) + 'MiB'; }
	};

	legend_settings = {
	position: 'nw',
	backgroundOpacity: 0
	};

	runtime_settings = {
	series: series_settings,
	grid: grid_settings,
	xaxis: xaxis_settings,
	yaxis: yaxis_runtime_settings,
	legend: legend_settings
	};

	memory_settings = {
	series: series_settings,
	grid: grid_settings,
	xaxis: xaxis_settings,
	yaxis: yaxis_memory_settings,
	legend: legend_settings
	};

	__CHART_DATA_GOES_HERE__

	$(function () {
	$.plot($("#query_random-runtime"), chart_data['query_random-runtime'], runtime_settings);
	$.plot($("#query_ordered-runtime"), chart_data['query_ordered-runtime'], runtime_settings);
	$.plot($("#insert_random-runtime"), chart_data['insert_random-runtime'], runtime_settings);
	$.plot($("#insert_ordered-runtime"), chart_data['insert_ordered-runtime'], runtime_settings);
	});
	</script>

	<style>
	body, * { font-family: sans-serif; }
	div.chart {
	width: 700px;
	height: 230px;
	}
	div.xaxis-title {
	width: 700px;
	text-align: center;
	font-style: italic;
	font-size: small;
	color: #666;
	}
	</style>

	<div class="chart" id="insert_ordered-runtime"></div>
	<div class="xaxis-title">number of entries in hash table</div>

	<div class="chart" id="insert_random-runtime"></div>
	<div class="xaxis-title">number of entries in hash table</div>

	<div class="chart" id="query_ordered-runtime"></div>
	<div class="xaxis-title">number of entries in hash table</div>

	<div class="chart" id="query_random-runtime"></div>
	<div class="xaxis-title">number of entries in hash table</div>

	<div class="chart" id="randomstring-runtime"></div>
	<div class="xaxis-title">number of entries in hash table</div>

	</body>
	</html>
	#include <iostream>
	#include <iomanip>
	#include <locale>
	#include <algorithm>
	#include <cstdlib>
	#include <ctime>
	#include <set>
	#include <vector>
	#include <unordered_map>
	#include <map>
	#include <google/dense_hash_map>
	#include <google/sparse_hash_map>
	#include <boost/unordered_map.hpp>
	#include <boost/container/flat_map.hpp>
	#include <boost/timer/timer.hpp>
	#include <boost/lexical_cast.hpp>

	std::vector<int> keys, random_keys, ordered_keys;
	std::vector<int> queries, random_queries, ordered_queries;

	void generate_random_unique_integers(std::size_t nr_keys,
	std::vector<int>& integers) {
	srand(time(NULL));
	std::set<int> mask;
	while (mask.size() < nr_keys) { mask.insert(rand()); }
	for (std::set<int>::const_iterator i = mask.begin();
	i != mask.end(); ++ i) {
	integers.push_back(*i);
	}
	}

	void generate_random_integers(std::size_t nr_keys,
	std::vector<int>& integers) {
	srand(time(NULL));
	for (auto i = 0; i < nr_keys; ++ i) {
	integers.push_back(rand());
	}
	}

	template <class map_type>
	class Benchmark {
	private:
	std::size_t repeat_times;
	std::string comments;
	public:
	Benchmark(const std::string& _comments,
	std::size_t _repeat_times = 10000): comments(_comments), repeat_times(_repeat_times) {}

	void insert(const std::vector<int>& keys, const std::string& sign) {
	boost::timer::auto_cpu_timer _;
	for (auto i = 0; i < repeat_times; ++ i) { map_type rep; for (int key: keys) { rep[key] = 1024; } }
	std::cout << "insert_" << sign << "," << keys.size() << "," << comments << ",";
	}

	void queries(const std::vector<int>& keys, const std::vector<int> queries, const std::string& sign) {
	map_type rep; for (auto key: keys) { rep[key] = 1024; }
	boost::timer::auto_cpu_timer _;
	for (auto query: queries) { typename map_type::const_iterator itx = rep.find(query); if (itx != rep.end()) {} }
	std::cout << "query_" << sign << "," << keys.size() << "," << comments << ",";
	}
	};

	class BenchmarkGoogleDenseHashMap {
	private:
	std::size_t repeat_times;
	std::string comments;
	typedef google::dense_hash_map<int, double> map_type;
	public:
	BenchmarkGoogleDenseHashMap(const std::string& _comments,
	std::size_t _repeat_times = 10000): comments(_comments), repeat_times(_repeat_times) {}

	void insert(const std::vector<int>& keys, const std::string& sign) {
	boost::timer::auto_cpu_timer _;
	for (auto i = 0; i < repeat_times; ++ i) {map_type rep; rep.set_empty_key(-1); for (int key: keys) { rep[key] = 1024; } }
	std::cout << "insert_" << sign << "," << keys.size() << "," << comments << ",";
	}

	void queries(const std::vector<int>& keys, const std::vector<int> queries, const std::string& sign) {
	map_type rep; rep.set_empty_key(-1); for (auto key: keys) { rep[key] = 1024; }
	boost::timer::auto_cpu_timer _;
	for (auto query: queries) { typename map_type::const_iterator itx = rep.find(query); if (itx != rep.end()) {} }
	std::cout << "query_" << sign << "," << keys.size() << "," << comments << ",";
	}
	};


	template<class map_type>
	void run(const std::string& name, std::size_t nr_tests) {
	Benchmark< map_type > bench(name, nr_tests);
	bench.insert(random_keys, "random");
	bench.insert(ordered_keys, "ordered");
	bench.queries(keys, random_queries, "random");
	bench.queries(keys, ordered_queries, "ordered");
	}

	int main(int argc, char* argv[]) {
	std::size_t nr_keys = boost::lexical_cast<int>(argv[1]);
	std::size_t nr_insertions = boost::lexical_cast<int>(argv[2]);
	std::size_t nr_queries = boost::lexical_cast<int>(argv[3]);
	generate_random_unique_integers(nr_keys, keys);
	random_keys = keys; std::random_shuffle(random_keys.begin(), random_keys.end());
	ordered_keys = keys; std::sort(ordered_keys.begin(), ordered_keys.end());

	generate_random_integers(nr_queries, queries);
	random_queries= queries; std::random_shuffle(random_queries.begin(), random_queries.end());
	ordered_queries = queries; std::sort(ordered_queries.begin(), ordered_queries.end());

	run< std::map<int, double> >("std::map", nr_insertions);
	run< std::unordered_map<int, double> >("std::unordered_map", nr_insertions);
	run< google::sparse_hash_map<int, double> >("google::sparse_hash_map", nr_insertions);
	run< boost::unordered_map<int, double> >("boost::unordered_map", nr_insertions);
	run< boost::container::flat_map<int, double> >("boost::flat_map", nr_insertions);

	{
	BenchmarkGoogleDenseHashMap bench("google::dense_hash_map", nr_insertions);
	bench.insert(random_keys, "random");
	bench.insert(ordered_keys, "ordered");
	bench.queries(keys, random_queries, "random");
	bench.queries(keys, ordered_queries, "ordered");
	}

	return 0;
	}
	import sys, json

	lines = [ line.strip() for line in sys.stdin if line.strip() ]

	by_benchtype = {}

	for line in lines:
	benchtype, nkeys, program, runtime = line.split(',')[:4]
	nkeys = int(nkeys)
	#nbytes = int(nbytes)
	runtime = float(runtime.split()[0].rstrip("s"))

	by_benchtype.setdefault("%s" % benchtype, {}).setdefault(program, []).append([nkeys, runtime])

	proper_names = {
	'std::map': 'GCC 4.8.2 std::map',
	'std::unordered_map': 'GCC 4.8.2 std::unordered_map',
	'google::sparse_hash_map': 'Google sparsehash 2.0 sparse_hash_map',
	'google::dense_hash_map': 'Google sparsehash 2.0 dense_hash_map',
	'boost::unordered_map': 'Boost 1.57 unordered_map',
	'boost::flat_map': 'Boost 1.57 container/flat_map'
	}

	# do them in the desired order to make the legend not overlap the chart data
	# too much
	program_slugs = ['std::map', 'std::unordered_map', 'google::sparse_hash_map', 'google::dense_hash_map', 'boost::unordered_map', 'boost::flat_map']

	chart_data = {}

	for i, (benchtype, programs) in enumerate(by_benchtype.items()):
	chart_data[benchtype] = []
	for j, program in enumerate(program_slugs):
	data = programs[program]
	chart_data[benchtype].append({
	'label': proper_names[program],
	'data': [],
	})

	for k, (nkeys, value) in enumerate(data):
	chart_data[benchtype][-1]['data'].append([nkeys, value])

	print 'chart_data = ' + json.dumps(chart_data)
	import sys
	html_template = file('charts-template.html', 'r').read()
	file('charts.html', 'w').write(html_template.replace('__CHART_DATA_GOES_HERE__', sys.stdin.read()))
	all: benchmark

	benchmark: main.cc
	g++ -std=c++0x -O3 -o benchmark main.cc -lboost_timer -lboost_system