Key benchmark

gistfile1.txt

******************** O2 ********************


$ clang++ -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 -O2 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 17635698 nsec
  elapsed: 16047390 nsec
  elapsed: 15367448 nsec
  elapsed: 15024112 nsec
  elapsed: 14848860 nsec
AVG elapsed: 15784701 nsec

$ clang++ -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 -O2 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 16166163 nsec
  elapsed: 16021412 nsec
  elapsed: 15178050 nsec
  elapsed: 14949183 nsec
  elapsed: 15038880 nsec
AVG elapsed: 15470737 nsec

$ clang++ -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 -O2 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 16000001 nsec
  elapsed: 15783501 nsec
  elapsed: 15794351 nsec
  elapsed: 15357366 nsec
  elapsed: 14931581 nsec
AVG elapsed: 15573360 nsec

$ clang++ -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 -O2 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 17329851 nsec
  elapsed: 16180315 nsec
  elapsed: 16110431 nsec
  elapsed: 15384101 nsec
  elapsed: 15225452 nsec
AVG elapsed: 16046030 nsec

***** 32-bit *****

$ clang++ -m32 -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 -O2 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 258789682 nsec
  elapsed: 261010512 nsec
  elapsed: 263154738 nsec
  elapsed: 265544351 nsec
  elapsed: 263192497 nsec
AVG elapsed: 262338356 nsec

$ clang++ -m32 -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 -O2 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 255666555 nsec
  elapsed: 263908974 nsec
  elapsed: 263781960 nsec
  elapsed: 264886364 nsec
  elapsed: 263818597 nsec
AVG elapsed: 262412490 nsec

$ clang++ -m32 -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 -O2 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 240767135 nsec
  elapsed: 237454537 nsec
  elapsed: 242372096 nsec
  elapsed: 237389515 nsec
  elapsed: 243831225 nsec
AVG elapsed: 240362901 nsec

$ clang++ -m32 -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 -O2 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 251107846 nsec
  elapsed: 242395698 nsec
  elapsed: 239625547 nsec
  elapsed: 243703082 nsec
  elapsed: 244085761 nsec
AVG elapsed: 244183586 nsec


******************** O1 ********************


$ clang++ -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 -O1 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 237632513 nsec
  elapsed: 226977382 nsec
  elapsed: 224705747 nsec
  elapsed: 225022323 nsec
  elapsed: 224296873 nsec
AVG elapsed: 227726967 nsec

$ clang++ -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 -O1 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 238691548 nsec
  elapsed: 223927628 nsec
  elapsed: 223760368 nsec
  elapsed: 223817706 nsec
  elapsed: 223409729 nsec
AVG elapsed: 226721395 nsec

$ clang++ -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 -O1 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 206730813 nsec
  elapsed: 192223744 nsec
  elapsed: 193088650 nsec
  elapsed: 193171352 nsec
  elapsed: 192980623 nsec
AVG elapsed: 195639036 nsec

$ clang++ -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 -O1 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 204628567 nsec
  elapsed: 192931069 nsec
  elapsed: 194734472 nsec
  elapsed: 191824135 nsec
  elapsed: 193043613 nsec
AVG elapsed: 195432371 nsec

***** 32-bit *****

$ clang++ -m32 -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 -O1 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 424143259 nsec
  elapsed: 416349065 nsec
  elapsed: 420375333 nsec
  elapsed: 418157602 nsec
  elapsed: 424201082 nsec
AVG elapsed: 420645268 nsec

$ clang++ -m32 -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 -O1 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 422504339 nsec
  elapsed: 413055227 nsec
  elapsed: 413120127 nsec
  elapsed: 414948168 nsec
  elapsed: 413605212 nsec
AVG elapsed: 415446614 nsec

$ clang++ -m32 -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 -O1 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 400676454 nsec
  elapsed: 383671096 nsec
  elapsed: 396497077 nsec
  elapsed: 384700797 nsec
  elapsed: 386510506 nsec
AVG elapsed: 390411186 nsec

$ clang++ -m32 -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 -O1 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 411025862 nsec
  elapsed: 386614649 nsec
  elapsed: 390537981 nsec
  elapsed: 385325660 nsec
  elapsed: 386640747 nsec
AVG elapsed: 392028979 nsec


******************** NO -O ********************


$ clang++ -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 382066899 nsec
  elapsed: 390875894 nsec
  elapsed: 383717492 nsec
  elapsed: 392078167 nsec
  elapsed: 387637253 nsec
AVG elapsed: 387275141 nsec

$ clang++ -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 389843607 nsec
  elapsed: 382754558 nsec
  elapsed: 383572639 nsec
  elapsed: 383336675 nsec
  elapsed: 381276047 nsec
AVG elapsed: 384156705 nsec

$ clang++ -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 326811086 nsec
  elapsed: 316323486 nsec
  elapsed: 317208269 nsec
  elapsed: 316155907 nsec
  elapsed: 319499224 nsec
AVG elapsed: 319199594 nsec

$ clang++ -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 326875673 nsec
  elapsed: 316579971 nsec
  elapsed: 315567797 nsec
  elapsed: 318787478 nsec
  elapsed: 316267024 nsec
AVG elapsed: 318815588 nsec

***** 32-bit *****

$ clang++ -m32 -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 598451794 nsec
  elapsed: 589719045 nsec
  elapsed: 589523285 nsec
  elapsed: 589894706 nsec
  elapsed: 588236503 nsec
AVG elapsed: 591165066 nsec

$ clang++ -m32 -DDUMB_KEY -Wall -stdlib=libstdc++ -std=c++11 keybench.cpp && ./a.out
sizeof(Key) = 16
5 iterations:
  elapsed: 595750819 nsec
  elapsed: 591613788 nsec
  elapsed: 592672100 nsec
  elapsed: 589292332 nsec
  elapsed: 591900556 nsec
AVG elapsed: 592245919 nsec

$ clang++ -m32 -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 580269503 nsec
  elapsed: 573207124 nsec
  elapsed: 571265357 nsec
  elapsed: 580592733 nsec
  elapsed: 578721064 nsec
AVG elapsed: 576811156 nsec

$ clang++ -m32 -DDUMB_KEY_NOT -Wall -stdlib=libstdc++ -std=c++11 keybench.cpp && ./a.out
sizeof(Key) = 8
5 iterations:
  elapsed: 579145158 nsec
  elapsed: 574894190 nsec
  elapsed: 575563469 nsec
  elapsed: 575704343 nsec
  elapsed: 574823909 nsec
AVG elapsed: 576026213 nsec

keybench.cpp

#include <map>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum A { LastA = 10 };
enum B { LastB = 70 };
enum C { LastC = 33 };

int Random(int max) {
    return rand() % max;
}

#ifdef DUMB_KEY

struct Key {
    A a;
    B b;
    C c;
    uint8_t data1;
    uint8_t data2;

    bool operator < (const Key& other) const {
    bool operator < (const Key& other) const {
        if (a < other.a) {
            return true;
        }
        if (a == other.a) {
            if (b < other.b) {
                return true;
            }
            if (b == other.b) {
                if (c < other.c) {
                    return true;
                }
                if (c == other.c) {
                    if (data1 < other.data1) {
                        return true;
                    }
                    if (data1 == other.data1) {
                        if (data2 < other.data2) {
                            return true;
                        }
                        if (data2 == other.data2) {
                            return false;
                        }
                    }
                }
            }
        }
        return false;
    }
};

Key RandomKey() {
    Key key = {
        (A)Random(LastA),
        (B)Random(LastB),
        (C)Random(LastC),
        (uint8_t)Random(256),
        (uint8_t)Random(256)
    };
    return key;
}

#else // !DUMB_KEY

union Key {
    struct {
        uint8_t a;
        uint8_t b;
        uint8_t c;
        uint8_t data1;
        uint8_t data2;
    } values;
    uint64_t packed;

    bool operator < (const Key& other) const {
        return packed < other.packed;
    }
};

Key RandomKey() {
    Key key;
    key.packed = 0;
    key.values.a = (uint8_t)Random(LastA);
    key.values.b = (uint8_t)Random(LastB);
    key.values.c = (uint8_t)Random(LastC);
    key.values.data1 = (uint8_t)Random(256);
    key.values.data2 = (uint8_t)Random(256);
    return key;
}

#endif // DUMB_KEY

typedef unsigned long long Timestamp;
Timestamp timestamp() {
    struct timespec time = {0};
    clock_gettime(CLOCK_MONOTONIC, &time);
    return Timestamp(time.tv_sec) * 1000000000 + time.tv_nsec;
}

Timestamp bench() {
    std::map<Key, const void*> cache;

    for (size_t i = 0; i != 10000; ++i) {
        cache.insert(std::make_pair(RandomKey(), ""));
    }

    Timestamp elapsed = 0;
    for (size_t i = 0; i != 1000000; ++i) {
        Key key = RandomKey();

        Timestamp startTime = timestamp();
        cache.find(key);
        elapsed += (timestamp() - startTime);
    }

    printf("  elapsed: %llu nsec\n", elapsed);

    return elapsed;
}

int main() {
    srand(0x1234567);

    printf("sizeof(Key) = %zu\n", sizeof(Key));

    Timestamp totalElapsed = 0;
    const size_t iterations = 5;

    printf("%zu iterations:\n", iterations);
    for (size_t i = 0; i != iterations; ++i) {
        totalElapsed += bench();
    }

    printf("AVG elapsed: %llu nsec\n", totalElapsed / iterations);

    if (Random(RAND_MAX) != 1950179113) {
        printf("OOPS, invalid random value at the end!\n");
    }

    return 0;
}