Bench Sorted Vs Unsorted Vector

Last updated on 2020-12-22

People love their polymorphic types, but usually don’t realize that a sorted array iterates faster than an unsorted array due to code cache misses.

/* sorted */

auto begin = std::chrono::high_resolution_clock::now();
for(const auto &i : sorted) {
        i->hello();
}
auto end = std::chrono::high_resolution_clock::now();

auto diff = end - begin;
auto time = std::chrono::duration_cast<std::chrono::nanoseconds>(diff).count();
printf("Sorted: %d\n", (int)(time));        

/* unsorted */

begin = std::chrono::high_resolution_clock::now();
for(const auto &i : unsorted) {
        i->hello();
}
end = std::chrono::high_resolution_clock::now();

diff = end - begin;
time = std::chrono::duration_cast<std::chrono::nanoseconds>(diff).count();
printf("Unsorted: %d\n", (int)(time));

Results

In milliseconds.

Array	Time
Sorted	3074528
Unsorted	13887083

Quite a big difference between the two.

Full Code

#include <vector>
#include <memory>
#include <random>
#include <algorithm>
#include <iostream>
#include <chrono>


struct foo {
        virtual void hello() = 0;
        virtual ~foo() {}
};


struct bar : public foo {
        void hello() override{
                x += 123;
        }

        int x = 123;
};


struct baz : public foo {
        void hello() override{
                x += 12;
                y *= 34;
        }

        int x = 123;
        int y = 234;
};


struct boo : public foo {
        void hello() override{
                z *= 10.123f;
        }

        float z = 345.f;
};


struct bin : public foo {
        void hello() override{
                x = y + z;
        }

        float x = 123.f;
        float y = 234.f;
        float z = 345.f;
};


int
main() {
        /* count */
        constexpr unsigned count = 1 << 18;
        constexpr unsigned quart = count / 4;

        /* data */
        std::vector<std::unique_ptr<foo>> sorted;
        std::vector<std::unique_ptr<foo>> unsorted;

        /* create with dummy data */
        for(int i = 0; i < quart; ++i) {
                sorted.emplace_back(std::make_unique<bar>());
                unsorted.emplace_back(std::make_unique<bar>());
        }

        for(int i = 0; i < quart; ++i) {
                sorted.emplace_back(std::make_unique<baz>());
                unsorted.emplace_back(std::make_unique<baz>());
        }

        for(int i = 0; i < quart; ++i) {
                sorted.emplace_back(std::make_unique<boo>());
                unsorted.emplace_back(std::make_unique<boo>());
        }

        for(int i = 0; i < quart; ++i) {
                sorted.emplace_back(std::make_unique<bin>());
                unsorted.emplace_back(std::make_unique<bin>());
        }

        std::random_device rd;
        std::mt19937 g(rd());

        std::shuffle(unsorted.begin(), unsorted.end(), g);

        /* sorted */

        auto begin = std::chrono::high_resolution_clock::now();
        for(const auto &i : sorted) {
                i->hello();
        }
        auto end = std::chrono::high_resolution_clock::now();

        auto diff = end - begin;
        auto time = std::chrono::duration_cast<std::chrono::nanoseconds>(diff).count();
        printf("Sorted: %d\n", (int)(time));

        /* unsorted */

        begin = std::chrono::high_resolution_clock::now();
        for(const auto &i : unsorted) {
                i->hello();
        }
        end = std::chrono::high_resolution_clock::now();

        diff = end - begin;
        time = std::chrono::duration_cast<std::chrono::nanoseconds>(diff).count();
        printf("Unsorted: %d\n", (int)(time));
}