HAT-trie benchmark

bench.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
#include <chrono>

#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>
#include <string.h>

#include <city.h>
struct str_hash {
    std::size_t operator()(const char* key, std::size_t key_size) const {
        return CityHash64(key, key_size);
    }
    
    std::size_t operator()(const std::string& key) const {
        return CityHash64(key.c_str(), key.size());
    }
};

using value_type = int;


#ifdef BENCH_STD_UNORDERED_MAP

#include <unordered_map>
using map_type = std::unordered_map<std::string, value_type, str_hash>;

map_type construct() {
    return map_type();
}

void reserve(map_type& map, std::size_t nb_elements) {
    map.reserve(nb_elements);
}

void insert(map_type& map, const std::string& str, value_type value) {
    map.insert({str, value});
}

bool find(const map_type& map, const std::string& str) {
    return map.find(str) != map.end();
}

void destroy(map_type& /*map*/) {
}


#elif BENCH_TSL_HOPSCOTCH_MAP

#include <hopscotch_map.h>
using map_type = tsl::hopscotch_map<std::string, value_type, str_hash>;

map_type construct() {
    return map_type();
}

void reserve(map_type& map, std::size_t nb_elements) {
    map.reserve(nb_elements);
}

void insert(map_type& map, const std::string& str, value_type value) {
    map.insert({str, value});
}

bool find(const map_type& map, const std::string& str) {
    return map.find(str) != map.end();
}

void destroy(map_type& /*map*/) {
}



#elif BENCH_GOOGLE_DENSE_MAP

#include <google/dense_hash_map>
using map_type = google::dense_hash_map<std::string, value_type, str_hash>;

map_type construct() {
    map_type map;
    map.set_empty_key("");
    
    return map;
}

void reserve(map_type& map, std::size_t nb_elements) {
    /*
     * There is no reserve function.
     * 
     * The following doesn't work well either, it reserves too much buckets 
     * (much more than the closest power of 2).
     * 
     * map.rehash(std::size_t(std::ceil(float(nb_elements)/map.max_load_factor()))); 
     * 
     * So use the constructor which take the number of elements to reserve in parameters.
     */
    map_type map_tmp(nb_elements);
    map_tmp.set_empty_key("");

    map.swap(map_tmp);
}

void insert(map_type& map, const std::string& str, value_type value) {
    map.insert({str, value});
}

bool find(const map_type& map, const std::string& str) {
    return map.find(str) != map.end();
}

void destroy(map_type& /*map*/) {
}



#elif BENCH_SPP_SPARSE_HASH_MAP

#include <sparsepp/spp.h>
using map_type = spp::sparse_hash_map<std::string, value_type, str_hash>;

map_type construct() {
    return map_type();
}

void reserve(map_type& map, std::size_t nb_elements) {
    map.reserve(nb_elements);
}

void insert(map_type& map, const std::string& str, value_type value) {
    map.insert({str, value});
}

bool find(const map_type& map, const std::string& str) {
    return map.find(str) != map.end();
}

void destroy(map_type& /*map*/) {
}



#elif BENCH_TSL_ARRAY_MAP

#include <array_map.h>
using map_type = tsl::array_map<char, value_type, str_hash, tsl::str_equal_ah<char>, false>;

map_type construct() {
    return map_type();
}

void reserve(map_type& map, std::size_t nb_elements) {
    map.reserve(nb_elements);
}

void insert(map_type& map, const std::string& str, value_type value) {
    map.insert(str, value);
}

bool find(const map_type& map, const std::string& str) {
    return map.find(str) != map.end();
}

void destroy(map_type& /*map*/) {
}



#elif (BENCH_TSL_HTRIE_MAP || BENCH_TSL_HTRIE_MAP_LF_4 || BENCH_TSL_HTRIE_MAP_LF_2 || BENCH_TSL_HTRIE_MAP_LF_1)

#include <htrie_map.h>
using map_type = tsl::htrie_map<char, value_type, str_hash>;

map_type construct() {
    map_type map;
    
#ifdef BENCH_TSL_HTRIE_MAP_LF_4   
    map.max_load_factor(4.0f);
#elif BENCH_TSL_HTRIE_MAP_LF_2
    map.max_load_factor(2.0f);
#elif BENCH_TSL_HTRIE_MAP_LF_1
    map.max_load_factor(1.0f);
#endif    
    
    return map;
}

void insert(map_type& map, const std::string& str, value_type value) {
    map.insert(str, value);
}

bool find(const map_type& map, const std::string& str) {
    return map.find(str) != map.end();
}

void destroy(map_type& /*map*/) {
}



#elif BENCH_DC_HAT_TRIE

#include <hat-trie/hat-trie.h>
using map_type = hattrie_t*;

map_type construct() {
    return hattrie_create();
}

void insert(map_type& map, const std::string& str, value_type value) {
    value_t* map_value = hattrie_get(map, str.c_str(), str.size());
    *map_value = value;
}

bool find(const map_type& map, const std::string& str) {
    value_t* map_value = hattrie_tryget(map, str.c_str(), str.size());
    return map_value != nullptr;
}

void destroy(map_type& map) {
    hattrie_free(map);
}



#elif BENCH_CEDAR

#include <cedar.h>
using map_type = cedar::da<value_type, -1, -2, true>;

#define NO_CONSTRUCT_METHOD

void insert(map_type& map, const std::string& str, value_type value) {
    map.update(str.c_str(), str.size(), value);
}

bool find(const map_type& map, const std::string& str) {
    return map.exactMatchSearch<value_type>(str.c_str(), str.size()) != -1;
}

void destroy(map_type& /*map*/) {
}



#elif BENCH_CEDAR_UNORDERED

#include <cedar.h>
using map_type = cedar::da<value_type, -1, -2, false>;

#define NO_CONSTRUCT_METHOD

void insert(map_type& map, const std::string& str, value_type value) {
    map.update(str.c_str(), str.size(), value);
}

bool find(const map_type& map, const std::string& str) {
    return map.exactMatchSearch<value_type>(str.c_str(), str.size()) != -1;
}

void destroy(map_type& /*map*/) {
}



#elif BENCH_CEDARPP

#include <cedarpp.h>
using map_type = cedar::da<value_type, -1, -2, true>;

#define NO_CONSTRUCT_METHOD

void insert(map_type& map, const std::string& str, value_type value) {
    map.update(str.c_str(), str.size(), value);
}

bool find(const map_type& map, const std::string& str) {
    return map.exactMatchSearch<value_type>(str.c_str(), str.size()) != -1;
}

void destroy(map_type& /*map*/) {
}



#elif BENCH_CEDARPP_UNORDERED

#include <cedarpp.h>
using map_type = cedar::da<value_type, -1, -2, false>;

#define NO_CONSTRUCT_METHOD

void insert(map_type& map, const std::string& str, value_type value) {
    map.update(str.c_str(), str.size(), value);
}

bool find(const map_type& map, const std::string& str) {
    return map.exactMatchSearch<value_type>(str.c_str(), str.size()) != -1;
}

void destroy(map_type& /*map*/) {
}



#elif BENCH_JUDY_SL

#include <Judy.h>
using map_type = Pvoid_t;

map_type construct() {
    return nullptr;
}

void insert(map_type& map, const std::string& str, value_type value) {
    PWord_t value_ptr;
    JSLI(value_ptr, map, (const uint8_t*) str.c_str());
    *value_ptr = value;
}

bool find(const map_type& map, const std::string& str) {
    PWord_t value_ptr = 0; 
    JSLG(value_ptr, map, (const uint8_t*) str.c_str()); 
    
    return value_ptr != nullptr;
}

void destroy(map_type& map) {
    Word_t size;
    JSLFA(size, map);
}



#elif BENCH_JUDY_HS

#include <Judy.h>
using map_type = Pvoid_t;

map_type construct() {
    return nullptr;
}

void insert(map_type& map, std::string& str, value_type value) {
    PWord_t value_ptr;
    JHSI(value_ptr, map, (uint8_t*) str.c_str(), str.size());
    *value_ptr = value;
}

bool find(const map_type& map, std::string& str) {
    PWord_t value_ptr = 0; 
    JHSG(value_ptr, map, (uint8_t*) str.c_str(), str.size()); 
    
    return value_ptr != nullptr;
}

void destroy(map_type& map) {
    Word_t size;
    JHSFA(size, map);
}



#elif (BENCH_QP_TRIE || BENCH_CRITBIT_TRIE)

#include <Tbl.h>

using map_type = Tbl*;

map_type construct() {
    return nullptr;
}

void insert(map_type& map, const std::string& str, value_type value) {
    // As the API of qp trie behaves quite differently than the other implementations,
    // two ugly hacks are done to do a fair comparison.
    
    /**
     * The qp trie library doesn't make a copy of the string passed in parameter.
     * It only stores the pointer to the key contrary to all the other implementations
     * which do a copy of the string. 
     * 
     * The str parameter is only a temporary value, so we also do a manual copy.
     * We store the copy pointer directly into the qp trie to avoid an additional structure 
     * (which would require sizeof(void*) extra bytes for each string), we need
     * to call free() on the keys manually on destruction.
     */
    char* str_copy = strndup(str.c_str(), str.size());
    
    /**
     * We can't store the int directly into the qp trie as it only take a 
     * void* parameter. We could allocate an int in the heap but it would require
     * an extra allocation and take an extra sizeof(void*) bytes.
     * 
     * As this would be unfair compared to the other structures, we store
     * the value itself as an invalid pointer (with +1 to avoid a NULL value and 
     * a shift to avoid the alignement check). To retrieve the real value,
     * we just have to do the opposite operation.
     */
    void* value_as_ptr = (void*) (((uint64_t) value + 1) << 2);
    
    map_type new_map_root = Tsetl(map, str_copy, str.size(), value_as_ptr);
    if(new_map_root == nullptr) {
        free(str_copy);
        throw std::runtime_error("Couldn't perform insert in qp or critbit trie.");
    }
    
    map = new_map_root;
}

bool find(const map_type& map, const std::string& str) {
    return Tgetl(map, str.c_str(), str.size()) != NULL;
}

void destroy(map_type& map) {
    char* key = NULL;
    std::size_t key_length = 0;
    void* value = NULL;
    
    while(Tnextl(map, &key, &key_length, &value)) {
        map = Tdell(map, key, key_length);
        
        free(key);
        
        key = NULL;
        key_length = 0;
        value = NULL;
    }
}
#else

#error "No defined test"

#endif














std::size_t get_memory_usage_bytes() {
    std::ifstream file("/proc/self/statm");
    std::size_t memory;
    file >> memory; // Ignore first
    file >> memory;
    
    return memory * getpagesize();
}



template<typename T>
void bench_insert(T& map, const std::string& file_words_insert) {
    std::ifstream file(file_words_insert);
    if(!file.is_open()) {
        throw std::runtime_error("Couldn't read " + file_words_insert + ".");
    }
    
    std::vector<std::string> lines;
    std::copy(std::istream_iterator<std::string>(file), std::istream_iterator<std::string>(), 
                std::back_inserter(lines));
    
    
    const size_t mem_start = get_memory_usage_bytes();
    const auto chrono_start = std::chrono::high_resolution_clock::now();
    
#ifdef BENCH_RESERVE
    reserve(map, lines.size());
#endif    
    
    int i = 0;
    for(auto& line: lines) {
        insert(map, line, i);
        i++;
    }
    
    const auto chrono_end = std::chrono::high_resolution_clock::now();
    const size_t mem_end = get_memory_usage_bytes();
    
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(chrono_end - chrono_start).count()
                 / double(lines.size()) << " ns/key" << std::endl;
    std::cout << double(mem_end - mem_start)/double(1024*1024) << " MiB (" << (mem_end - mem_start) << " bytes)." << std::endl;
}

template<typename T>
void bench_read(const T& map, const std::string& file_words_read) {
    std::ifstream file(file_words_read);
    if(!file.is_open()) {
        throw std::runtime_error("Couldn't read " + file_words_read + ".");
    }
    
    std::vector<std::string> lines;
    std::copy(std::istream_iterator<std::string>(file), std::istream_iterator<std::string>(), 
                std::back_inserter(lines));
    
    
    const auto chrono_start = std::chrono::high_resolution_clock::now();
    
    std::size_t nb_found = 0;
    for(auto& line: lines) {
        if(find(map, line)) {
            nb_found++;
        }
    }

    const auto chrono_end = std::chrono::high_resolution_clock::now();
    
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(chrono_end - chrono_start).count()
                 / double(lines.size()) << " ns/key" << std::endl;
              
    std::cout << "Found " << nb_found << " of " << lines.size() << " elements." << std::endl;
}

void bench(const std::string& file_words_insert, const std::string& file_words_read) {
#ifdef NO_CONSTRUCT_METHOD
    map_type map;
#else
    auto map = construct();
#endif    
    
    bench_insert(map, file_words_insert);
    bench_read(map, file_words_read);
    
    destroy(map);
}

void insert_no_measure(const std::string& file_words_insert) {
#ifdef NO_CONSTRUCT_METHOD
    map_type map;
#else
    auto map = construct();
#endif 
    
    std::ifstream file(file_words_insert);
    if(!file.is_open()) {
        throw std::runtime_error("Couldn't read " + file_words_insert + ".");
    }
    
#ifdef BENCH_RESERVE
    reserve(map, std::distance(std::istream_iterator<std::string>(file), std::istream_iterator<std::string>()));
    file.clear();
    file.seekg(0);
#endif
    
    int i = 0;
    std::string line;
    while(file >> line) {
        insert(map, line, i);
        i++;
    }
    
    destroy(map);
}


int main(int argc, char** argv) {
    if(argc == 2) {
        insert_no_measure(argv[1]);
    }
    else if(argc == 3) {
        bench(argv[1], argv[2]);
    }
    else {
        std::cout << "Usage: " << argv[0] << " words_file_insert" << std::endl;
        std::cout << "Usage: " << argv[0] << " words_file_insert words_file_read" << std::endl;
        exit(1);
    }
}

Makefile

CXX=g++
CXXFLAGS=-lcityhash -std=c++11 -march=native -DNDEBUG -O3
WORDS_INSERT_FILE="./enwiki-20170320-all-titles-in-ns0"
WORDS_READ_FILE="./enwiki-20170320-all-titles-in-ns0"

QP_TRIE_LIB_PATH="./qp/"

all: compile run run_peak

compile:
	$(CXX) $(CXXFLAGS) -o std_unordered_map          -DBENCH_STD_UNORDERED_MAP bench.cpp
	$(CXX) $(CXXFLAGS) -o std_unordered_map_reserve  -DBENCH_STD_UNORDERED_MAP -DBENCH_RESERVE bench.cpp
	$(CXX) $(CXXFLAGS) -o tsl_hopscotch_map          -DBENCH_TSL_HOPSCOTCH_MAP bench.cpp
	$(CXX) $(CXXFLAGS) -o tsl_hopscotch_map_reserve  -DBENCH_TSL_HOPSCOTCH_MAP -DBENCH_RESERVE bench.cpp
	$(CXX) $(CXXFLAGS) -o google_dense_map           -DBENCH_GOOGLE_DENSE_MAP bench.cpp	
	$(CXX) $(CXXFLAGS) -o google_dense_map_reserve   -DBENCH_GOOGLE_DENSE_MAP -DBENCH_RESERVE bench.cpp	
	$(CXX) $(CXXFLAGS) -o spp_sparsepp               -DBENCH_SPP_SPARSE_HASH_MAP bench.cpp
	$(CXX) $(CXXFLAGS) -o spp_sparsepp_reserve       -DBENCH_SPP_SPARSE_HASH_MAP -DBENCH_RESERVE bench.cpp
	$(CXX) $(CXXFLAGS) -o tsl_array_hash             -DBENCH_TSL_ARRAY_MAP bench.cpp
	$(CXX) $(CXXFLAGS) -o tsl_array_hash_reserve     -DBENCH_TSL_ARRAY_MAP -DBENCH_RESERVE bench.cpp
	$(CXX) $(CXXFLAGS) -o tsl_htrie_map              -DBENCH_TSL_HTRIE_MAP  bench.cpp
	$(CXX) $(CXXFLAGS) -o tsl_htrie_map_lf_4         -DBENCH_TSL_HTRIE_MAP_LF_4 bench.cpp
	$(CXX) $(CXXFLAGS) -o tsl_htrie_map_lf_2         -DBENCH_TSL_HTRIE_MAP_LF_2 bench.cpp
	$(CXX) $(CXXFLAGS) -o tsl_htrie_map_lf_1         -DBENCH_TSL_HTRIE_MAP_LF_1 bench.cpp
	$(CXX) $(CXXFLAGS) -o judy_sl                    -DBENCH_JUDY_SL -fpermissive -lJudy bench.cpp 
	$(CXX) $(CXXFLAGS) -o judy_hs                    -DBENCH_JUDY_HS -fpermissive -lJudy bench.cpp 
	$(CXX) $(CXXFLAGS) -o dc_hat_trie                -DBENCH_DC_HAT_TRIE -fpermissive -lhat-trie bench.cpp 
	$(CXX) $(CXXFLAGS) -o cedar                      -DBENCH_CEDAR bench.cpp 
	$(CXX) $(CXXFLAGS) -o cedar_unordered            -DBENCH_CEDAR_UNORDERED bench.cpp 
	$(CXX) $(CXXFLAGS) -o cedar_reduced              -DBENCH_CEDAR -DUSE_REDUCED_TRIE bench.cpp 
	$(CXX) $(CXXFLAGS) -o cedar_unordered_reduced    -DBENCH_CEDAR_UNORDERED -DUSE_REDUCED_TRIE bench.cpp 
	$(CXX) $(CXXFLAGS) -o cedarpp                    -DBENCH_CEDARPP bench.cpp 
	$(CXX) $(CXXFLAGS) -o cedarpp_unordered          -DBENCH_CEDARPP_UNORDERED bench.cpp
	$(CXX) $(CXXFLAGS) -o qp_trie                    -DBENCH_QP_TRIE -fpermissive $(QP_TRIE_LIB_PATH)/qp.c $(QP_TRIE_LIB_PATH)/Tbl.c bench.cpp 
	$(CXX) $(CXXFLAGS) -o critbit_trie               -DBENCH_CRITBIT_TRIE -fpermissive $(QP_TRIE_LIB_PATH)/cb.c $(QP_TRIE_LIB_PATH)/Tbl.c bench.cpp 


run:
	./std_unordered_map          $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./std_unordered_map_reserve  $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./tsl_hopscotch_map          $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./tsl_hopscotch_map_reserve  $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./google_dense_map           $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./google_dense_map_reserve   $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./spp_sparsepp               $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./spp_sparsepp_reserve       $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./tsl_array_hash             $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./tsl_array_hash_reserve     $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./tsl_htrie_map              $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./tsl_htrie_map_lf_4         $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./tsl_htrie_map_lf_2         $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./tsl_htrie_map_lf_1         $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./judy_sl                    $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./judy_hs                    $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./dc_hat_trie                $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./cedar                      $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./cedar_unordered            $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./cedar_reduced              $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./cedar_unordered_reduced    $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./cedarpp                    $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./cedarpp_unordered          $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./qp_trie                    $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)
	./critbit_trie               $(WORDS_INSERT_FILE) $(WORDS_READ_FILE)

run_peak:
	/usr/bin/time -f "%M" ./std_unordered_map          $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./std_unordered_map_reserve  $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./tsl_hopscotch_map          $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./tsl_hopscotch_map_reserve  $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./google_dense_map           $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./google_dense_map_reserve   $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./spp_sparsepp               $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./spp_sparsepp_reserve       $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./tsl_array_hash             $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./tsl_array_hash_reserve     $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./tsl_htrie_map              $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./tsl_htrie_map_lf_4         $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./tsl_htrie_map_lf_2         $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./tsl_htrie_map_lf_1         $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./judy_sl                    $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./judy_hs                    $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./dc_hat_trie                $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./cedar                      $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./cedar_unordered            $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./cedar_reduced              $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./cedar_unordered_reduced    $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./cedarpp                    $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./cedarpp_unordered          $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./qp_trie                    $(WORDS_INSERT_FILE)
	/usr/bin/time -f "%M" ./critbit_trie               $(WORDS_INSERT_FILE)