sorted/unsorted small vector search

main.cpp

#include <nanobench.h>

#include <iostream>
#include <array>
#include <set>
#include <algorithm>

/*************************************************************************************************/

int main(int argc, char **argv) {
    std::array<unsigned short, 32> unsorted_rand{
         62393, 20099, 44739, 37156, 27773
        ,16020, 24855,  9603, 56765, 43928
        ,4680 , 40108, 30722, 33851, 27499
        ,33913, 35599, 58345, 37432, 61116
        ,61580, 39450, 20738, 39393, 61609
        ,14793, 50430, 52451, 42279, 24039
        ,4545 , 50248};
    static_assert(sizeof(unsorted_rand) == 64);

    std::array<unsigned short, 32> sorted_asc{
         4545 , 4680 , 9603 , 14793, 16020
        ,20099, 20738, 24039, 24855, 27499
        ,27773, 30722, 33851, 33913, 35599
        ,37156, 37432, 39393, 39450, 40108
        ,42279, 43928, 44739, 50248, 50430
        ,52451, 56765, 58345, 61116, 61580
        ,61609,62393};
    static_assert(sizeof(sorted_asc) == 64);

    std::array<unsigned short, 32> sorted_desc{
         62393, 61609, 61580, 61116, 58345
        ,56765, 52451, 50430, 50248, 44739
        ,43928, 42279, 40108, 39450, 39393
        ,37432, 37156, 35599, 33913, 33851
        ,30722, 27773, 27499, 24855, 24039
        ,20738, 20099, 16020, 14793, 9603
        ,4680 , 4545};
    static_assert(sizeof(sorted_desc) == 64);

    // test for equality of arrays
    {
        const std::set<unsigned short> rand{unsorted_rand.begin(), unsorted_rand.end()};
        const std::set<unsigned short> asc{sorted_asc.begin(), sorted_asc.end()};
        const std::set<unsigned short> desc{sorted_desc.begin(), sorted_desc.end()};
        if ( rand != asc || rand != desc ) {
            std::cout << "the arrays contains the different values" << std::endl;

            return EXIT_FAILURE;
        }
    }

    if ( argc == 1 ) {
        for ( const auto &it: sorted_asc )
            std::cout << it << ' ';
        std::cout << std::endl;

        return EXIT_SUCCESS;
    }
    if ( argc != 2 ) {
        std::cout << "usage: ./test number" << std::endl;

        return EXIT_FAILURE;
    }

    auto val = std::strtoul(argv[1], nullptr, 10);
    auto found = 0u;

    // linear
    // 0
    ankerl::nanobench::Bench().run("unsorted linear", [&]() {
        for ( const auto &it: unsorted_rand ) {
            if ( it == val ) { found = it; break; }
        }
        ankerl::nanobench::doNotOptimizeAway(found);
    });
    // 1
    ankerl::nanobench::Bench().run("sorted linear ASC", [&]() {
        for ( const auto &it: sorted_asc ) {
            if ( it == val ) { found = it; break; }
        }
        ankerl::nanobench::doNotOptimizeAway(found);
    });
    // 2
    ankerl::nanobench::Bench().run("sorted linear DESC", [&]() {
        for ( const auto &it: sorted_desc ) {
            if ( it == val ) { found = it; break; }
        }
        ankerl::nanobench::doNotOptimizeAway(found);
    });

    // binary
    // 3
    ankerl::nanobench::Bench().run("unsorted binary", [&]() {
        std::sort(unsorted_rand.begin(), unsorted_rand.end());
        auto it = std::lower_bound(unsorted_rand.begin(), unsorted_rand.end(), val);
        found = (it != unsorted_rand.end() && *it == val);
        ankerl::nanobench::doNotOptimizeAway(found);
    });
    // 4
    ankerl::nanobench::Bench().run("sorted binary ASC", [&]() {
        auto it = std::lower_bound(sorted_asc.begin(), sorted_asc.end(), val);
        found = (it != sorted_asc.end() && *it == val);
        ankerl::nanobench::doNotOptimizeAway(found);
    });
    // 5
    ankerl::nanobench::Bench().run("sorted binary DESC", [&]() {
        auto it = std::lower_bound(sorted_desc.begin(), sorted_desc.end(), val);
        found = (it != sorted_desc.end() && *it == val);
        ankerl::nanobench::doNotOptimizeAway(found);
    });

    return EXIT_SUCCESS;
}

/*
    |               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
    |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
0 - |                8.54 |      117,088,898.41 |    0.7% |          233.00 |           39.00 |  5.974 |          66.00 |    0.0% |      0.01 | `unsorted linear`
1 - |                8.59 |      116,421,281.14 |    0.4% |          233.00 |           39.00 |  5.974 |          66.00 |    0.0% |      0.01 | `sorted linear ASC`
2 - |                8.73 |      114,528,910.20 |    0.3% |          233.00 |           39.00 |  5.974 |          66.00 |    0.0% |      0.01 | `sorted linear DESC`
3 - |               46.90 |       21,323,859.12 |    0.1% |          818.00 |          208.16 |  3.930 |         200.00 |    0.0% |      0.01 | `unsorted binary`
4 - |                4.48 |      223,029,784.31 |    0.4% |           87.00 |           20.00 |  4.350 |          20.00 |    0.0% |      0.01 | `sorted binary ASC`
5 - |                4.51 |      221,560,699.47 |    0.3% |           87.00 |           20.00 |  4.350 |          20.00 |    0.0% |      0.01 | `sorted binary DESC`
*/