From Pheet
Jump to: navigation, search



Your own set implementation should adhere to the following interface:

// Replace Classname with the name of your Set
template <class Pheet, typename TT>
class Classname {

  bool add(TT const& item);
  bool contains(TT const& item);
  bool remove(TT const& item);

  size_t size(); // Does not have to be exact, but needs to be > 0 if not empty

  static void print_name() {
    // Should also print some relevant configuration parameters if applicable
    std::cout << "Classname"; 
    // Also print name of Mutex used, in case you use locks

Optionally, comparison based sets should have a third template parameter class Comparator = std::less<TT>. Due to limitations of C++ with regard to optional template parameters, such implementations cannot be plugged in directly into the benchmark. This can be worked around using a template alias as follows:

template <class Pheet, typename TT>
using ClassnameX = Classname<Pheet, TT>;

The template alias ClassnameX will provide an alias where there exists no third, optional, template parameter, thus making the compiler happy.

Add to stress test benchmark

Edit the file test/ds_stress/DsStressTests.cpp. Add an include directive to include your newly created data structure.

Add your own implementation to the run_test method by adding this line:


You can also comment out any tests there that you are not interested in.

Running the benchmark

Switch to the stress test benchmark by editing test/settings.h, and setting the macro ACTIVE_TEST to test/test_variants/ds.h. You can change the exact configuration of the test inside ds.h.

The compiler (default: g++), include and library paths can be set in the file To compile, enter the following on the command line:

make test

The output of the benchmarks is in a tab-separated text-format, where each line of data is preceded with a line of headers and can be piped into a file. The output can be converted to a better to process format (csv with one row of headers at the beginning of the file) using the perl-script csvheet in the Pheet main directory.

Header dependencies are not tracked by the Pheet makefile right now, so if you change your lock implementation you might need to run make clean before your changes are applied on a recompile.

Configuration of benchmark and interpretation of results

You can change the configuration of the benchmark by editing test/test_variants/ds.h.

The following line allows to change the number of CPUs used for the experiments. It is recommended to run the tests with different numbers of processors to see scalability trends.

const procs_t ds_stress_test_cpus[] = {1, 2, 4, 8};

So far, Pheet only contains throughput tests. These tests count the number of successful push/pop/peek operations by all threads within one second. To give some intuition on fairness we also store the minimum and maximum number per type of operation by a single thread. Other types of tests (most importantly a test for correctness) will be added in the future.

const int ds_stress_test_types[] = {0};

We allow to explicitly set the random seeds used for the experiments, which adds some determinism to the experiments and thus reproducibility and better comparability between data structure implementations. We also use the random seeds to configure the number of repetitions of the experiments (each random seed is one repetition). For your final measurement, to get statistically significant results, you should run each experiment more than once. (As a rule of thumb, 20 experiments should suffice, unless your results exhibit high variance).

const unsigned int ds_stress_test_seed_first = 0;
const unsigned int ds_stress_test_seed_last = 0;

For the experiments all threads share a single instance of your data structure. Before the start of the experiment this data structure is pre-filled with a configurable amount of data.

const unsigned int ds_stress_test_prefill[] = {10000, 1000000};

The pattern by which the data structure is accessed is also configurable. So far we support the following patterns, with more being added in the future: 0: Each thread will perform either a push or a pop with probability of 25% each, or a contains with probability 50% at each iteration. 1: Each thread is assigned a role and will either push or pop data, or check for data with contains all the time. Out of every 4 threads, one performs push, one pop and the other two contains. 2: Each thread will perform either a push or a pop with probability of 1% each, or a contains with probability 98% at each iteration. 3: One thread will only push data, one will pop data, and all others will only perform contains calls.

const unsigned int ds_stress_test_set_dist[] = {0, 1, 2, 3};

The keys used for each set access are selected uniformly at random. Since the number of keys has a huge impact on the number of key collisions, we allow to configure the maximum key that can be used. The minimum is always 0. The number of values has to be at least double the number of items used for prefilling. Experiments where this is not the case will be automatically skipped.

const unsigned int ds_stress_test_set_max_v[] = {20000, 2000000};
Personal tools