LZ4 linear search versus binary search

main.cpp

#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <array>
#include <random>
#include <frozen/map.h>

#include <plf/plf_nanotimer.h>


int table_lookup ( char s_ ) noexcept {
    struct KeyValue { const char key, value; };
    static constexpr std::array<const KeyValue, 22> table { {
        { '0',  0 }, { '1',  1 }, { '2',  2 }, { '3',  3 }, { '4',  4 }, { '5',  5 }, { '6',  6 }, { '7',  7 },
        { '8',  8 }, { '9',  9 }, { 'A', 10 }, { 'B', 11 }, { 'C', 12 }, { 'D', 13 }, { 'E', 14 }, { 'F', 15 },
        { 'a', 10 }, { 'b', 11 }, { 'c', 12 }, { 'd', 13 }, { 'e', 14 }, { 'f', 15 }
    } };
    for ( auto [ k, v ] : table )
        if ( k == s_ )
            return v;
    return -1;
}

__attribute__ ( ( noinline ) ) // we do not want the compiler to rewrite the problem
uint32_t hex_table_lookup ( const uint8_t *src ) {
    uint32_t v1 = table_lookup ( src [ 0 ] );
    uint32_t v2 = table_lookup ( src [ 1 ] );
    uint32_t v3 = table_lookup ( src [ 2 ] );
    uint32_t v4 = table_lookup ( src [ 3 ] );
    return static_cast< uint32_t >( v1 << 12 | v2 << 8 | v3 << 4 | v4 );
}


frozen::map<char, char, 22> map_lookup {
    { '0',  0 }, { '1',  1 }, { '2',  2 }, { '3',  3 }, { '4',  4 }, { '5',  5 }, { '6',  6 }, { '7',  7 }, { '8',  8 },
    { '9',  9 }, { 'A', 10 }, { 'B', 11 }, { 'C', 12 }, { 'D', 13 }, { 'E', 14 }, { 'F', 15 }, { 'a', 10 }, { 'b', 11 },
    { 'c', 12 }, { 'd', 13 }, { 'e', 14 }, { 'f', 15 }
};

__attribute__ ( ( noinline ) ) // we do not want the compiler to rewrite the problem
uint32_t hex_frozen_map ( const uint8_t *src ) {
    uint32_t v1 = map_lookup.at ( src [ 0 ] );
    uint32_t v2 = map_lookup.at ( src [ 1 ] );
    uint32_t v3 = map_lookup.at ( src [ 2 ] );
    uint32_t v4 = map_lookup.at ( src [ 3 ] );
    return static_cast< uint32_t >( v1 << 12 | v2 << 8 | v3 << 4 | v4 );
}


template <uint32_t ( *F )( const uint8_t *src )> void test ( size_t N ) {
    uint8_t *x = ( uint8_t * ) malloc ( sizeof ( uint8_t ) * ( N + 3 ) );
    srand ( 1235 );
    for ( size_t i = 0; i < N + 3; i++ ) {
        int digit = ( rand ( ) % 16 );
        if ( digit < 10 )
            x [ i ] = 48 + digit;
        else
            x [ i ] = 65 + digit - 10;
    }
    for ( size_t i = 0; i < N; i++ ) {
        assert ( hex_to_u32_lookup ( x + i ) == hex_to_u32_math ( x + i ) );
    }
    size_t iterations = 50;
    std::random_device rd;
    std::mt19937 gen ( rd ( ) );
    std::uniform_int_distribution<> dis ( 0, 0xFFFF );
    plf::nanotimer timer;
    timer.start ( );
    uint64_t sum = 0;
    for ( uint32_t i = 0; i < iterations; i++ ) {
        for ( size_t i = 0; i < N; i++ ) {
            sum += F ( x + i );
        }
    }
    uint64_t end = timer.get_elapsed_ms ( );
    free ( x );
    printf ( "sum  = %zu \n", ( size_t ) sum );
    printf ( "time = %zu \n", ( uint64_t ) end );
}

int main ( ) {
    size_t N = 1000 * 1000;
    printf ( "table_lookup:\n" );
    test<hex_table_lookup> ( N );
    printf ( "frozen_map:\n" );
    test<hex_frozen_map> ( N );
}