Ticket #8509: uuid_operators.cpp

#include <time.h>
#include <cstring>
#include <memory>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <boost/config.hpp>
#include <boost/uuid/uuid.hpp>
#include <boost/uuid/uuid_generators.hpp>
#if defined(BOOST_WINDOWS)
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#endif
#if defined(_MSC_VER)
// MSVC does not always have immintrin.h (at least, not up to MSVC 10), and we cannot detect the target higher than SSE2 anyway, so just include this header
#include <emmintrin.h>
#else
#include <immintrin.h>
#endif

using boost::uuids::uuid;

bool stock_equal(uuid const& left, uuid const& right)
{
        return std::equal(left.begin(), left.end(), right.begin());
}

bool mem_equal(uuid const& left, uuid const& right)
{
        return std::memcmp(left.data, right.data, 16) == 0;
}

bool simd_equal(uuid const& left, uuid const& right)
{
#if defined(__SSE3__)
        __m128i mm_left = _mm_lddqu_si128(reinterpret_cast< const __m128i* >(left.data));
        __m128i mm_right = _mm_lddqu_si128(reinterpret_cast< const __m128i* >(right.data));
#else
        __m128i mm_left = _mm_loadu_si128(reinterpret_cast< const __m128i* >(left.data));
        __m128i mm_right = _mm_loadu_si128(reinterpret_cast< const __m128i* >(right.data));
#endif
        __m128i mm_cmp = _mm_cmpeq_epi32(mm_left, mm_right);
#if defined(__SSE4_1__)
        return _mm_test_all_ones(mm_cmp);
#else
        return _mm_movemask_epi8(mm_cmp) == 0xFFFF;
#endif
}


bool stock_less(uuid const& left, uuid const& right)
{
        return std::lexicographical_compare(left.begin(), left.end(), right.begin(), right.end());
}

bool mem_less(uuid const& left, uuid const& right)
{
        return std::memcmp(left.data, right.data, 16) < 0;
}

bool simd_less(uuid const& left, uuid const& right)
{
#if defined(__SSE3__)
        __m128i mm_left = _mm_lddqu_si128(reinterpret_cast< const __m128i* >(left.data));
        __m128i mm_right = _mm_lddqu_si128(reinterpret_cast< const __m128i* >(right.data));
#else
        __m128i mm_left = _mm_loadu_si128(reinterpret_cast< const __m128i* >(left.data));
        __m128i mm_right = _mm_loadu_si128(reinterpret_cast< const __m128i* >(right.data));
#endif

        // To emulate lexicographical_compare behavior we have to perform two comparisons - the forward and reverse one.
        // Then we know which bytes are equivalent and which ones are different, and for those different the comparison results
        // will be opposite. Then we'll be able to find the first differing comparison result (for both forward and reverse ways),
        // and depending on which way it is for, this will be the result of the operation. There are a few notes to consider:
        //
        // 1. Due to little endian byte order the first bytes go into the lower part of the xmm registers,
        //    so the comparison results in the least significant bits will actually be the most signigicant for the final operation result.
        //    This means we have to determine which of the comparison results have the least significant bit on, and this is achieved with
        //    the "(x - 1) ^ x" trick.
        // 2. Because there is only signed comparison in SSE/AVX, we have to operate on 16 bit integers. We zero-extend bytes to 16 bit words
        //    before comparison and then pack the comparison results back to 8 bits. For AVX2 we can still do the comparison in one instruction though.
        // 3. pcmpgtw compares for "greater" relation, so we swap the arguments to get what we need.
        const __m128i mm_0 = _mm_setzero_si128();
        __m128i mm_left_lo = _mm_unpacklo_epi8(mm_left, mm_0), mm_right_lo = _mm_unpacklo_epi8(mm_right, mm_0);
        __m128i mm_left_hi = _mm_unpackhi_epi8(mm_left, mm_0), mm_right_hi = _mm_unpackhi_epi8(mm_right, mm_0);

        __m128i mm_cmp_lo = _mm_cmpgt_epi16(mm_right_lo, mm_left_lo), mm_cmp_hi = _mm_cmpgt_epi16(mm_right_hi, mm_left_hi);
        __m128i mm_rcmp_lo = _mm_cmpgt_epi16(mm_left_lo, mm_right_lo), mm_rcmp_hi = _mm_cmpgt_epi16(mm_left_hi, mm_right_hi);
        __m128i mm_cmp = _mm_packs_epi16(mm_cmp_lo, mm_cmp_hi);
        __m128i mm_rcmp = _mm_packs_epi16(mm_rcmp_lo, mm_rcmp_hi);

        boost::uint32_t cmp = _mm_movemask_epi8(mm_cmp), rcmp = _mm_movemask_epi8(mm_rcmp);
        cmp = (cmp - 1u) ^ cmp;
        rcmp = (rcmp - 1u) ^ rcmp;

        return static_cast< boost::uint16_t >(cmp) < static_cast< boost::uint16_t >(rcmp);
}

typedef bool equal_t(uuid const& left, uuid const& right);

const unsigned int iterations = 100000000u;

void test_performance(uuid const& left, uuid const& right, const char* name, equal_t* eq)
{
#if !defined(BOOST_WINDOWS)
        struct timespec start = {}, end = {};
        clock_gettime(CLOCK_REALTIME, &start);
#else
        LARGE_INTEGER start = {}, end = {};
        QueryPerformanceCounter(&start);
#endif

        for (volatile unsigned int i = 0; i < iterations; ++i)
        {
                eq(left, right);
        }

#if !defined(BOOST_WINDOWS)
        clock_gettime(CLOCK_REALTIME, &end);

        boost::uint64_t duration = (end.tv_sec - start.tv_sec) * 1000000000ull + (end.tv_nsec - start.tv_nsec);
#else
        QueryPerformanceCounter(&end);
        LARGE_INTEGER freq = {};
        QueryPerformanceFrequency(&freq);

        boost::uint64_t duration = (end.QuadPart - start.QuadPart) * 1000000000ull / freq.QuadPart;
#endif

        std::cout << name << " duration: " << duration << " ns" << std::endl;
}

void run_tests(uuid const& left, uuid const& right)
{
        test_performance(left, right, "stock_equal", &stock_equal);
        test_performance(left, right, "mem_equal", &mem_equal);
        test_performance(left, right, "simd_equal", &simd_equal);

        test_performance(left, right, "stock_less", &stock_less);
        test_performance(left, right, "mem_less", &mem_less);
        test_performance(left, right, "simd_less", &simd_less);
}

int main(int, char*[])
{
        boost::uuids::random_generator gen;

        {
                std::cout << "Values placed on stack:" << std::endl;
                uuid left = gen();
                uuid right = gen();
                run_tests(left, right);
        }
        {
                std::cout << "\nValues placed on heap:" << std::endl;
                std::auto_ptr< uuid > pleft(new uuid(gen()));
                std::auto_ptr< uuid > pright(new uuid(gen()));
                run_tests(*pleft, *pright);
        }

        return 0;
}