Create a gist now

Instantly share code, notes, and snippets.

@Oneplus /Makefile
Last active Aug 29, 2015

What would you like to do?
map vs unordered_map vs boost::flat_map
<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>
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment