hashcomp.cc

// Copyright © 2014 Nate rosenblum <flander@gmail.com>
// This work is free. You can redistribute it and/or modify it under the
// terms of the Do What The Fuck You Want To Public License, Version 2,
// as published by Sam Hocevar. See http://www.wtfpl.net/ for more details.

#include <inttypes.h>
#include <stdio.h>

#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/function.hpp>
#include <boost/unordered_set.hpp>

// Prevent loop elision
#define TOTES_USED(var) asm volatile("" : "+r" (var));

void timeit(std::string const& name, boost::function<void()> const& work) {
    boost::posix_time::ptime start(
        boost::posix_time::microsec_clock::universal_time());
    work();
    boost::posix_time::ptime end(
        boost::posix_time::microsec_clock::universal_time());
    int64_t duration = (end - start).total_microseconds();
    printf("%-30s: %10" PRId64" us\n", name.c_str(), duration);
}

void test(int align) {
    char buf[32];
    snprintf(buf, sizeof(buf), "(%d)", align);
    const std::string kAlign(buf);

    // Preallocating to avoid rehash. Note that for the wrong policy,
    // rehashing will also be quite expensive.
    boost::unordered_set<uint64_t> ids(1E8);

    timeit("insert " + kAlign, [&ids, align]() {
            for (size_t i = 0; i < 1E8; ++i) {
                ids.insert(i << align);
            }
        });

    timeit("query " + kAlign, [&ids, align]() {
            for (size_t i = 0; i < 1E8; ++i) {
                bool foo = ids.find(i << align) != ids.end();
                TOTES_USED(foo);
            }
        });
}

int main (int argc, char **argv) {
    printf("Running unorderd_set integral benchmarks for various alignments\n"
           "Please be (possibly quite) patient...\n");

    test(1);
    test(2);
    test(3);
    test(4);
    test(5);
    // Consecutive inserts certainly cross cache lines for prime policy or for
    // power-two policy without mixing; possibly before depending on the
    // size & alignment of the table entries, which I haven't checked.
    test(6);
    return 0;
}