ColinDeWitBenchmarks.cpp

// http://coliru.stacked-crooked.com/a/661e096db956eca7
// Timing on my computer (with larger benchmarks)
// 0s 907ms 747us (benchmark_16_2048000_FULL_BUILD)
// 0s 919ms 263us (benchmark_16_2048000_SPTR_BUILD)
// 0s 620ms 877us (benchmark_16_2048000_FULL_PROBE)
// 0s 697ms 964us (benchmark_16_2048000_SPTR_PROBE)
// 
// 0s 578ms 693us (benchmark_64_1024000_FULL_BUILD)
// 0s 527ms 744us (benchmark_64_1024000_SPTR_BUILD)
// 0s 440ms 486us (benchmark_64_1024000_FULL_PROBE)
// 0s 514ms 416us (benchmark_64_1024000_SPTR_PROBE)
// 
// 0s 513ms 15us (benchmark_256_512000_FULL_BUILD)
// 0s 417ms 839us (benchmark_256_512000_SPTR_BUILD)
// 0s 449ms 808us (benchmark_256_512000_FULL_PROBE)
// 0s 490ms 8us (benchmark_256_512000_SPTR_PROBE)
// 
// 0s 747ms 143us (benchmark_1024_256000_FULL_BUILD)
// 0s 556ms 250us (benchmark_1024_256000_SPTR_BUILD)
// 0s 682ms 652us (benchmark_1024_256000_FULL_PROBE)
// 0s 689ms 313us (benchmark_1024_256000_SPTR_PROBE)

#include <unordered_set>
#include <string_view>
#include <algorithm>
#include <iostream>
#include <utility>
#include <random>
#include <memory>
#include <chrono>
#include <array>

class ScopedChrono
{
    
public:

    ScopedChrono(const std::string_view name) :
        _start{std::chrono::steady_clock::now()},
        _name{name}
    {}

    ~ScopedChrono()
    {
        auto end = std::chrono::steady_clock::now();

        auto diff = end - _start;

        std::cout << std::chrono::duration_cast<std::chrono::seconds     >(diff).count()        << "s "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(diff).count() % 1000 << "ms "
                  << std::chrono::duration_cast<std::chrono::microseconds>(diff).count() % 1000 << "us "
                  << "(" << _name << ")" << std::endl;
    }

private:

    std::chrono::time_point<std::chrono::steady_clock> _start;
    const std::string_view _name;
};

#define CHRONO(name) ScopedChrono scopedChrono{name};

template <std::size_t SIZE>
struct Key
{
    Key()
    {
        for (auto& byte : data)
        {
            byte = UNIFORM_DISTRIB(RANDOM_ENGINE);  
        }
    }

    std::array<uint8_t, SIZE> data;
    
    static std::default_random_engine             RANDOM_ENGINE;
    static std::uniform_int_distribution<uint8_t> UNIFORM_DISTRIB;
};

template <std::size_t SIZE>
std::default_random_engine             Key<SIZE>::RANDOM_ENGINE{std::random_device{}()};

template <std::size_t SIZE>
std::uniform_int_distribution<uint8_t> Key<SIZE>::UNIFORM_DISTRIB{};

template <std::size_t SIZE>
struct KeyEquals
{
    bool operator()(const Key<SIZE>& lhs,
                    const Key<SIZE>& rhs) const
    {
        for (std::size_t i = 0; i < SIZE; i++)
        {
            if (lhs.data[i] != rhs.data[i])
            {
                return false;    
            }
        }
        
        return true;
    }
};

template <std::size_t SIZE>
struct KeyHasher
{
    // See https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1_hash
    static constexpr std::size_t FNV1A_BASE = 0xcbf29ce484222325;
    static constexpr std::size_t FNV1A_PRIM = 0x100000001b3;
    
    std::size_t operator()(const Key<SIZE>& key) const
    {
        std::size_t hash = FNV1A_BASE;
        
        for (const auto byte : key.data)
        {
            hash ^= byte;
            hash *= FNV1A_PRIM;
        }
        
        return hash;
    }
};

template <std::size_t SIZE>
using KeySPtr = std::shared_ptr<Key<SIZE>>;

template <std::size_t SIZE>
struct KeySPtrEquals
{
    bool operator()(const KeySPtr<SIZE>& lhs,
                    const KeySPtr<SIZE>& rhs) const
    {
        return KeyEquals<SIZE>{}(*lhs,
                                 *rhs); // don't check for nullptr
    }
};

template <std::size_t SIZE>
struct KeySPtrHasher
{
    std::size_t operator()(const KeySPtr<SIZE>& keySPtr) const
    {
        return KeyHasher<SIZE>{}(*keySPtr); // don't check for nullptr
    }
};

template <std::size_t SIZE>
using SetOfKeys = std::unordered_set<Key       <SIZE>,
                                     KeyHasher <SIZE>,
                                     KeyEquals <SIZE>>; 
template <std::size_t SIZE>
using SetOfKeySPtrs = std::unordered_set<KeySPtr       <SIZE>,
                                         KeySPtrHasher <SIZE>,
                                         KeySPtrEquals <SIZE>>;
template <std::size_t SIZE>
using VectorOfKeys = std::vector<Key<SIZE>>;

template <std::size_t SIZE>
using VectorOfKeySPtrs = std::vector<KeySPtr<SIZE>>;

template <std::size_t SIZE>
VectorOfKeys<SIZE> makeVectorOfKeys(const std::size_t numberOfKeys)
{
    VectorOfKeys<SIZE> vectorOfKeys;
    
    for (std::size_t i = 0; i < numberOfKeys; i++)
    {
        vectorOfKeys.emplace_back();
    }
    
    return std::move(vectorOfKeys);
}

template <std::size_t SIZE>
VectorOfKeySPtrs<SIZE> makeVectorOfKeySPtrs(const std::size_t numberOfKeySPtrs)
{
    VectorOfKeySPtrs<SIZE> vectorOfKeySPtrs;
    
    for (std::size_t i = 0; i < numberOfKeySPtrs; i++)
    {
        vectorOfKeySPtrs.emplace_back(std::make_shared<Key<SIZE>>());
    }
    
    return std::move(vectorOfKeySPtrs);
}

template <std::size_t SIZE>
SetOfKeys<SIZE> makeSetOfKeys(const VectorOfKeys<SIZE>& vectorOfKeys)
{
    SetOfKeys<SIZE> setOfKeys;
    
    for (const auto& key : vectorOfKeys)
    {
        setOfKeys.emplace(key);
    }
    
    return std::move(setOfKeys);
}

template <class SetType, class VectorType>
SetType makeSet(const VectorType& vector)
{
    SetType set;
    
    for (const auto& key : vector)
    {
        set.emplace(key);    
    }
    
    return std::move(set);
}

template <class VectorType>
void shuffleVector(VectorType& vector)
{
    std::default_random_engine randomEngine{std::random_device{}()};
    
    std::shuffle(vector.begin(),
                 vector.end(),
                 randomEngine);
}

template <class SetType, class VectorType>
std::size_t probeSet(const VectorType& vector,
                     const    SetType& set)
{
    std::size_t numberOfMatches = 0; // to prevent any optim
    
    for (const auto& key : vector)
    {   
        numberOfMatches += (set.find(key) != set.end());   
    }
    
    return numberOfMatches;
}

template <std::size_t KEY_SIZE, std::size_t NUMBER_OF_KEYS>
constexpr auto makeBenchmark(const std::string_view benchmarkNameFullBuild,
                             const std::string_view benchmarkNameSPtrBuild,
                             const std::string_view benchmarkNameFullProbe,
                             const std::string_view benchmarkNameSPtrProbe)
{
    return [benchmarkNameFullBuild,
            benchmarkNameSPtrBuild,
            benchmarkNameFullProbe,
            benchmarkNameSPtrProbe]()
        {
            auto&& vectorOfKeys     = makeVectorOfKeys     <KEY_SIZE>(NUMBER_OF_KEYS);
            auto&& vectorOfKeySPtrs = makeVectorOfKeySPtrs <KEY_SIZE>(NUMBER_OF_KEYS);

            SetOfKeys     <KEY_SIZE> setOfKeys;
            SetOfKeySPtrs <KEY_SIZE> setOfKeySPtrs;
    
            {
                CHRONO(benchmarkNameFullBuild);
                
                setOfKeys = std::move(makeSet<SetOfKeys<KEY_SIZE>>(vectorOfKeys));
            }
            
            {
                CHRONO(benchmarkNameSPtrBuild);
                
                setOfKeySPtrs = std::move(makeSet<SetOfKeySPtrs<KEY_SIZE>>(vectorOfKeySPtrs));
            }
            
            shuffleVector(vectorOfKeys     );
            shuffleVector(vectorOfKeySPtrs );
            
            std::size_t sum = 0;
            
            {
                CHRONO(benchmarkNameFullProbe);
            
                sum += probeSet(vectorOfKeys, setOfKeys);
            }
            
            {
                CHRONO(benchmarkNameSPtrProbe);
            
                sum += probeSet(vectorOfKeySPtrs, setOfKeySPtrs);
            }
            
            std::cout << std::endl;
            
            return sum;
        };
}

#define MAKE_BENCHMARK(keySize, numberOfKeys) static constexpr auto benchmark_ ## keySize ## _ ## numberOfKeys = makeBenchmark<keySize, numberOfKeys>("benchmark_"#keySize"_"#numberOfKeys"_FULL_BUILD", \
                                                                                                                                                      "benchmark_"#keySize"_"#numberOfKeys"_SPTR_BUILD", \
                                                                                                                                                      "benchmark_"#keySize"_"#numberOfKeys"_FULL_PROBE", \
                                                                                                                                                      "benchmark_"#keySize"_"#numberOfKeys"_SPTR_PROBE");
MAKE_BENCHMARK(16   , 204800);
MAKE_BENCHMARK(64   , 102400);
MAKE_BENCHMARK(256  ,  51200);
MAKE_BENCHMARK(1024 ,  25600);

int main()
{
    std::size_t sum = 0;
    
    sum += benchmark_16_204800();
    sum += benchmark_64_102400();
    sum += benchmark_256_51200();
    sum += benchmark_1024_25600();

    return sum;
}