Как оптимизировать повторное использование большого std :: unordered_map как временного в часто вызываемой функции? - PullRequest
Новая
       5

Как оптимизировать повторное использование большого std :: unordered_map как временного в часто вызываемой функции?

0 голосов
/ 24 января 2019

Упрощенный вопрос с рабочим примером: я хочу многократно использовать std :: unordered_map (назовем его umap), подобно следующему фиктивному коду (который не делает ничего значимого). Как я могу заставить этот код работать быстрее? 

#include <iostream>
#include <unordered_map>
#include <time.h>

unsigned size = 1000000;

void foo(){
    std::unordered_map<int, double> umap;
    umap.reserve(size);
    for (int i = 0; i < size; i++) {
        // in my real program: umap gets filled with meaningful data here
        umap.emplace(i, i * 0.1);
    }
    // ... some code here which does something meaningful with umap
}

int main() {

    clock_t t = clock();

    for(int i = 0; i < 50; i++){
        foo();
    }

    t = clock() - t;
    printf ("%f s\n",((float)t)/CLOCKS_PER_SEC);

    return 0;
}

В моем исходном коде я хочу сохранить матричные записи в umap. При каждом обращении к foo значения ключей начинаются с 0 до N, и N может быть разным при каждом обращении к foo, но для индексов существует верхний предел 10M. Кроме того, значения могут быть разными (в отличие от фиктивного кода, который всегда равен i*0.1).

Я попытался сделать umap нелокальной переменной, чтобы избежать повторного выделения памяти umap.reserve() при каждом вызове. Это требует вызова umap.clear() в конце foo, но это оказалось на самом деле медленнее, чем с использованием локальной переменной (я ее измерил).

Ответы [ 4 ]

0 голосов
/ 26 января 2019

Как я предположил в комментариях, закрытое хеширование было бы лучше для вашего варианта использования. Вот быстрая и грязная закрытая хеш-карта с фиксированным размером хеш-таблицы, с которой вы можете поэкспериментировать: 

template<class Key, class T, size_t size = 1000003, class Hash = std::hash<Key>>
class closed_hash_map {
    typedef std::pair<const Key, T>                     value_type;
    typedef typename std::vector<value_type>::iterator  iterator;
    std::array<int, size>                               hashtable;
    std::vector<value_type>                             data;
 public:
    iterator begin() { return data.begin(); }
    iterator end() { return data.end(); }
    iterator find(const Key &k) {
        size_t h = Hash()(k) % size;
        while (hashtable[h]) {
            if (data[hashtable[h]-1].first == k)
                return data.begin() + (hashtable[h] - 1);
            if (++h == size) h = 0; }
        return data.end(); }
    std::pair<iterator, bool> insert(const value_type& obj) {
        size_t h = Hash()(obj.first) % size;
        while (hashtable[h]) {
            if (data[hashtable[h]-1].first == obj.first)
                return std::make_pair(data.begin() + (hashtable[h] - 1), false);
            if (++h == size) h = 0; }
        data.emplace_back(obj);
        hashtable[h] = data.size();
        return std::make_pair(data.end() - 1, true); }
    void clear() {
        data.clear();
        hashtable.fill(0); }
};

Его можно сделать более гибким за счет динамического изменения размера хэш-таблицы по требованию, когда это необходимо, и более эффективным за счет замены робина-вытяжки.

0 голосов
/ 25 января 2019

Простой и эффективный способ - снова и снова использовать один и тот же контейнер и память с передачей по ссылке следующим образом. В этом методе вы можете избежать их рекурсивного выделения памяти std::unordered_map::reserve и std::unordered_map::~unordered_map, которые оба имеют сложность O (количество элементов): 

void foo(std::unordered_map<int, double>& umap)
{        
    std::size_t N = ...// set N here

    for (int i = 0; i < N; ++i)
    {
        // overwrite umap[0], ..., umap[N-1]
        // If umap does not have key=i, then it is inserted.
        umap[i] = i*0.1;
    }

    // do something and not access to umap[N], ..., umap[size-1] !
}

Сторона вызывающего абонента будет выглядеть следующим образом: 

std::unordered_map<int,double> umap;
umap.reserve(size);

for(int i=0; i<50; ++i){
    foo(umap);
}

Но так как ваш набор ключей всегда представляет собой непрерывные целые числа {1,2,...,N}, я думаю, что std::vector, который позволяет вам избежать вычислений хеш-функции, было бы более предпочтительным для сохранения значений umap[0], ..., umap[N]: 

void foo(std::vector<double>& vec)
{    
    int N = ...// set N here

    for(int i = 0; i<N; ++i)
    {
        // overwrite vec[0], ..., vec[N-1]
        vec[i] = i*0.1;
    }

    // do something and not access to vec[N], ..., vec[size-1] !            
}
0 голосов
/ 25 января 2019

Вы пытались избежать выделения памяти с помощью простого массива? Вы сказали выше, что вы знаете максимальный размер umap для всех вызовов на foo(): 

#include <iostream>
#include <unordered_map>
#include <time.h>

constexpr int size = 1000000;
double af[size];

void foo(int N) {
    // assert(N<=size);
    for (int i = 0; i < N; i++) {
        af[i] = i;
    }
    // ... af
}

int main() {    
    clock_t t = clock();

    for(int i = 0; i < 50; i++){
        foo(size /* or some other N<=size */);
    }

    t = clock() - t;
    printf ("%f s\n",((float)t)/CLOCKS_PER_SEC);

    return 0;
}
0 голосов
/ 24 января 2019

Я не думаю, что есть какой-то хороший способ выполнить то, что вы ищете напрямую - то есть вы не можете очистить карту, не очистив карту.Я предполагаю, что вы могли бы выделить несколько карт заранее и просто использовать каждую из них по одному разу в качестве «одноразовой карты», а затем переходить к использованию следующей карты во время следующего вызова, но я сомневаюсь, что это дастУ вас есть какое-либо общее ускорение, так как в конце всего этого вам нужно будет очистить их все сразу, и в любом случае это будет очень интенсивно использовать ОЗУ и работать с кешем (в современных процессорах доступ к ОЗУ очень частоузкое место в производительности, и, следовательно, минимизация пропусков в кеше - это способ максимизировать эффективность).

Я бы сказал, что если скорость очистки очень важна, вам, возможно, придется отказаться от использования unordered_map полностью,и вместо этого используйте что-то более простое, например, std::vector - в этом случае вы можете просто сохранить целое число числа действительных элементов в векторе, а «очистить» вектор - просто установить обратный отсчетв ноль.(Конечно, это означает, что вы жертвуете свойствами быстрого поиска unordered_map, но, возможно, они вам не нужны на данном этапе ваших вычислений?)

...