Speed up code based on map with vectors as values

Question

Following is the piece of code which represents the bottleneck of my application:

#include <iostream>
#include <chrono>
#include <unordered_map>
#include <vector>
#include <memory>
#include <cassert>
#include <thread>
#include <random>
#include <utility>
using namespace std;
using namespace chrono;


static const size_t len = 30;
static const size_t nGraphics = 0xfffff;
static const size_t nIndexes = 600000;

static default_random_engine generator;
static normal_distribution<float> distribution(len / 2.f, 2);


struct Graphic
{
    Graphic()
        : lnum ((short)distribution(generator))
    {
        // common scenario
        // most of my graphics elements belong to few layers
        assert(lnum < len);
    }

    short lnum;
    unsigned char data[200];
};


static vector<short> order;
static vector<unique_ptr<Graphic>> graphics;
static vector<size_t> indexes;


static void init()
{
    order.reserve(len);
    for (short i = 0; i < len; i++)
        order.push_back(i);

    graphics.reserve(nGraphics);
    for (size_t i = 0; i < nGraphics; i++)
        graphics.emplace_back(new Graphic);

    assert(nGraphics >= nIndexes);

    indexes.reserve(nIndexes);
    for (size_t i = 0; i < nIndexes; i++)
        indexes.push_back(i);
}

static bool is_selected(short lnum)
{
    // worst case scenario (everything has been selected)
    return true;
}

static bool is_valid(Graphic* g)
{
    // worst case scenario (everything is valid)
    return (g != nullptr);
}

static void benchmarks()
{
    unordered_map<short, vector<Graphic*>> selected;
    selected.reserve(len);

    for (size_t i = 0; i < len; i++)
    {
        const auto lnum = order[i];

        if (!is_selected(lnum))
            continue;

        selected.emplace(lnum, vector<Graphic*>());
    }

    for (const auto idx : indexes)
    {
        assert(idx < graphics.size());
        const auto g = graphics[idx].get();

        if (!is_valid(g))
            continue;

        const auto it = selected.find(g->lnum);

        if (it != selected.end())
            it->second.emplace_back(g);
    }

    for (size_t i = 0; i < len; i++)
    {
        const auto lnum = order[i];

        if (!is_selected(lnum))
            continue;

        assert(selected.find(lnum) != selected.end());

        for (const auto g : selected[lnum])
        {
            assert(g);

            if (g->lnum != lnum)
                throw runtime_error("error");

            // perform slow operation on g (third party library)...
            // must follow a specific order
        }

        // simulate operations
        this_thread::sleep_for(microseconds{ selected[lnum].size() });
    }
}

int main()
{
    init();

    const auto t0 = high_resolution_clock::now();
    benchmarks();
    const auto t1 = high_resolution_clock::now();
    const auto elapsed = duration_cast<milliseconds>(t1 - t0).count();
    cout << "Elapsed: " << elapsed << endl;
    cin.get();

    return 0;
}

Most of the work is done inside the third party library (the elapsed time well represents the actual application), but my code, used to prepare the data structure, last more than 50ms on my machine.

Is there any way to reduce this time?

Answer 1

1. You can use std::iota for the sequential order vector. If it doesnt increase speed it is prettier:

   std::vector<short> order(len);
   std::iota(order.begin(), order.end(), 0);
   

   The same obviously goes for indexes

2. Given that you emplace in sequential order here selected.emplace(lnum, vector<Graphic*>()) you might want to switch to emplace_back

3. If you do not care about memory you can reserve the memory for your graphics vector with a guess during initialization and then call shrink_to_fit afterwards. That way you avoid possibly costly reallocations. However depending on the size of your guess this might significantly increase the memory burden.