316 lines
9.9 KiB
C++
316 lines
9.9 KiB
C++
#include <functional>
|
|
#include <iomanip>
|
|
#include <iostream>
|
|
#include <locale.h>
|
|
#include <map>
|
|
#include <stdint.h>
|
|
#include <sys/time.h>
|
|
#include <unistd.h>
|
|
#include <unordered_map>
|
|
#include <vector>
|
|
|
|
#include <boost/thread.hpp>
|
|
#include <boost/thread/mutex.hpp>
|
|
#include <boost/unordered_map.hpp>
|
|
|
|
#include <boost/container/flat_map.hpp>
|
|
|
|
#include <boost/pool/pool_alloc.hpp>
|
|
#include <boost/pool/singleton_pool.hpp>
|
|
|
|
#include "../fastnetmon_types.h"
|
|
|
|
// apt-get install -y libtbb-dev libsparsehash-dev
|
|
// g++ -O3 traffic_structures_performance_tests.cpp -std=c++11 -lboost_system -lboost_thread -ltbb -I/opt/local/include -L/opt/local/lib
|
|
// clang traffic_structures_performance_tests.cpp -std=c++11 -lboost_system -lboost_thread -ltbb -I/opt/local/include -L/opt/local/lib -lstdc++ -lm
|
|
// Mac OS:
|
|
// g++ traffic_structures_performance_tests.cpp -std=c++11 -lboost_system_mt -lboost_thread_mt -ltbb -I/opt/local/include -L/opt/local/lib -g -pg
|
|
|
|
#ifndef __APPLE__
|
|
#include "tbb/concurrent_unordered_map.h"
|
|
#endif
|
|
|
|
#include <sparsehash/dense_hash_map>
|
|
|
|
// No speed benefits
|
|
// std::map<uint32_t, map_element, std::less<uint32_t>, boost::fast_pool_allocator<std::pair<const uint32_t, map_element>>
|
|
std::map<uint32_t, map_element> DataCounter;
|
|
boost::mutex data_counter_mutex;
|
|
|
|
std::unordered_map<uint32_t, map_element> DataCounterUnordered;
|
|
|
|
std::unordered_map<uint32_t, map_element> DataCounterUnorderedPreallocated;
|
|
|
|
boost::unordered_map<uint32_t, map_element> DataCounterBoostUnordered;
|
|
|
|
boost::container::flat_map<uint32_t, map_element> DataCounterBoostFlatMap;
|
|
|
|
struct eqint {
|
|
bool operator()(uint32_t a, uint32_t b) const {
|
|
return a == b;
|
|
}
|
|
};
|
|
|
|
google::dense_hash_map<uint32_t, map_element, std::hash<uint32_t>, eqint> DataCounterGoogleDensehashMapPreallocated;
|
|
|
|
google::dense_hash_map<uint32_t, map_element, std::hash<uint32_t>, eqint> DataCounterGoogleDensehashMap;
|
|
|
|
#ifndef __APPLE__
|
|
tbb::concurrent_unordered_map<uint32_t, map_element> DataCounterUnorderedConcurrent;
|
|
#endif
|
|
|
|
std::vector<map_element> DataCounterVector;
|
|
|
|
using namespace std;
|
|
|
|
int number_of_ips = 10 * 1000 * 1000;
|
|
int number_of_retries = 1;
|
|
|
|
// #define enable_mutexex_in_test
|
|
unsigned int number_of_threads = 1;
|
|
|
|
// 83 seconds
|
|
// without mutexes segmentation fault
|
|
void packet_collector_thread_std_map() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.lock();
|
|
#endif
|
|
DataCounter[i].udp_in_bytes++;
|
|
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.unlock();
|
|
#endif
|
|
}
|
|
}
|
|
}
|
|
|
|
void packet_collector_thread_boost_unordered_map() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.lock();
|
|
#endif
|
|
DataCounterBoostUnordered[i].udp_in_bytes++;
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.unlock();
|
|
#endif
|
|
}
|
|
}
|
|
}
|
|
|
|
void packet_collector_thread_unordered_map() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.lock();
|
|
#endif
|
|
DataCounterUnordered[i].udp_in_bytes++;
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.unlock();
|
|
#endif
|
|
}
|
|
}
|
|
}
|
|
|
|
void packet_collector_thread_google_dense_hash_map_preallocated() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.lock();
|
|
#endif
|
|
DataCounterGoogleDensehashMapPreallocated[i].udp_in_bytes++;
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.unlock();
|
|
#endif
|
|
}
|
|
}
|
|
}
|
|
|
|
void packet_collector_thread_google_dense_hash_map() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.lock();
|
|
#endif
|
|
DataCounterGoogleDensehashMap[i].udp_in_bytes++;
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.unlock();
|
|
#endif
|
|
}
|
|
}
|
|
}
|
|
|
|
void packet_collector_thread_unordered_map_preallocated() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.lock();
|
|
#endif
|
|
DataCounterUnordered[i].udp_in_bytes++;
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.unlock();
|
|
#endif
|
|
}
|
|
}
|
|
}
|
|
|
|
void packet_collector_thread_flat_map_preallocated() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.lock();
|
|
#endif
|
|
DataCounterBoostFlatMap[i].udp_in_bytes++;
|
|
#ifdef enable_mutexex_in_test
|
|
data_counter_mutex.unlock();
|
|
#endif
|
|
}
|
|
}
|
|
}
|
|
|
|
void packet_collector_thread_vector() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
DataCounterVector[i].udp_in_bytes++;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
#ifndef __APPLE__
|
|
void packet_collector_thread_unordered_concurrent_map() {
|
|
for (int iteration = 0; iteration < number_of_retries; iteration++) {
|
|
for (uint32_t i = 0; i < number_of_ips; i++) {
|
|
DataCounterUnorderedConcurrent[i].udp_in_bytes++;
|
|
}
|
|
}
|
|
}
|
|
#endif
|
|
|
|
// http://www.gnu.org/software/libc/manual/html_node/Elapsed-Time.html
|
|
int timeval_subtract(struct timeval* result, struct timeval* x, struct timeval* y) {
|
|
/* Perform the carry for the later subtraction by updating y. */
|
|
if (x->tv_usec < y->tv_usec) {
|
|
int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
|
|
y->tv_usec -= 1000000 * nsec;
|
|
y->tv_sec += nsec;
|
|
}
|
|
|
|
if (x->tv_usec - y->tv_usec > 1000000) {
|
|
int nsec = (x->tv_usec - y->tv_usec) / 1000000;
|
|
y->tv_usec += 1000000 * nsec;
|
|
y->tv_sec -= nsec;
|
|
}
|
|
|
|
/* Compute the time remaining to wait. tv_usec is certainly positive. */
|
|
result->tv_sec = x->tv_sec - y->tv_sec;
|
|
result->tv_usec = x->tv_usec - y->tv_usec;
|
|
|
|
/* Return 1 if result is negative. */
|
|
return x->tv_sec < y->tv_sec;
|
|
}
|
|
|
|
|
|
int run_tests(void (*tested_function)(void)) {
|
|
timeval start_time;
|
|
gettimeofday(&start_time, NULL);
|
|
|
|
// std::cout << "Run "<< number_of_threads <<" threads" << endl;
|
|
boost::thread* threads[number_of_threads];
|
|
for (int i = 0; i < number_of_threads; i++) {
|
|
threads[i] = new boost::thread(tested_function);
|
|
}
|
|
|
|
// std::cout << "All threads started" << endl;
|
|
|
|
// std::cout << "Wait for finishing" << endl;
|
|
for (int i = 0; i < number_of_threads; i++) {
|
|
threads[i]->join();
|
|
}
|
|
|
|
// cout << "All threads finished" << endl;
|
|
|
|
timeval finish_time;
|
|
gettimeofday(&finish_time, NULL);
|
|
|
|
double total_operations = number_of_ips * number_of_retries * number_of_threads;
|
|
|
|
// We use ' for pretty print of long numbers
|
|
// http://stackoverflow.com/questions/1499156/convert-astronomically-large-numbers-into-human-readable-form-in-c-c
|
|
setlocale(LC_NUMERIC, "en_US.utf-8"); /* important */
|
|
|
|
timeval interval;
|
|
timeval_subtract(&interval, &finish_time, &start_time);
|
|
|
|
// Build time with float part
|
|
double used_time = (double)interval.tv_sec + (double)interval.tv_usec / 1000000;
|
|
// printf("We spent %f seconds\n", used_time);
|
|
|
|
double ops_per_second = total_operations / used_time;
|
|
;
|
|
double mega_ops_per_second = ops_per_second / 1000 / 1000;
|
|
|
|
printf("%'.1f mega ops per second\n", mega_ops_per_second);
|
|
|
|
return 0;
|
|
}
|
|
|
|
bool enabled_slow_data_structures_test = true;
|
|
|
|
int main() {
|
|
std::cout << "Element size: " << sizeof(map_element) << std::endl;
|
|
|
|
if (enabled_slow_data_structures_test) {
|
|
std::cout << "std::map: ";
|
|
run_tests(packet_collector_thread_std_map);
|
|
DataCounter.clear();
|
|
|
|
#ifndef __APPLE__
|
|
std::cout << "tbb::concurrent_unordered_map: ";
|
|
run_tests(packet_collector_thread_unordered_concurrent_map);
|
|
DataCounterUnorderedConcurrent.clear();
|
|
#endif
|
|
|
|
// Boost unordered map
|
|
std::cout << "boost::unordered_map: ";
|
|
run_tests(packet_collector_thread_boost_unordered_map);
|
|
DataCounterBoostUnordered.clear();
|
|
|
|
// Boost flat_map
|
|
DataCounterBoostFlatMap.reserve(number_of_ips);
|
|
std::cout << "boost::container::flat_map with preallocated elements: ";
|
|
run_tests(packet_collector_thread_flat_map_preallocated);
|
|
DataCounterBoostFlatMap.clear();
|
|
}
|
|
|
|
std::cout << "std::unordered_map C++11: ";
|
|
run_tests(packet_collector_thread_unordered_map);
|
|
DataCounterUnordered.clear();
|
|
|
|
// Preallocate hash buckets
|
|
DataCounterUnorderedPreallocated.reserve(number_of_ips);
|
|
std::cout << "std::unordered_map C++11 preallocated buckets: ";
|
|
run_tests(packet_collector_thread_unordered_map_preallocated);
|
|
DataCounterUnorderedPreallocated.clear();
|
|
|
|
std::cout << "google:dense_hashmap without preallocation: ";
|
|
DataCounterGoogleDensehashMap.set_empty_key(UINT32_MAX); // We will got assert without it!
|
|
run_tests(packet_collector_thread_google_dense_hash_map);
|
|
DataCounterGoogleDensehashMap.clear();
|
|
|
|
std::cout << "google:dense_hashmap preallocated buckets: ";
|
|
// We use UINT32_MAX as "empty" here, not a good idea but OK for tests
|
|
DataCounterGoogleDensehashMapPreallocated.set_empty_key(UINT32_MAX); // We will got assert without it!
|
|
DataCounterGoogleDensehashMapPreallocated.resize(number_of_ips);
|
|
run_tests(packet_collector_thread_google_dense_hash_map_preallocated);
|
|
DataCounterGoogleDensehashMapPreallocated.clear();
|
|
|
|
// Preallocate vector
|
|
DataCounterVector.reserve(number_of_ips);
|
|
std::cout << "std::vector preallocated: ";
|
|
run_tests(packet_collector_thread_vector);
|
|
DataCounterVector.clear();
|
|
}
|