Очень низкая производительность моего пользовательского использования std :: unordered_map - PullRequest
Новая
       29

Очень низкая производительность моего пользовательского использования std :: unordered_map

3 голосов
/ 10 января 2020

Я пытаюсь сохранить некоторую информацию о графике в unordered_map. Каждое ребро имеет несколько параметров. Имеется 120 ребер, и каждое ребро имеет 90 * 2 различных параметров.

У меня есть следующая реализация std::unordered_map<>

typedef std::tuple<int, int, int, int> metric_tuple_key; // metric  tuple key


// define a hash function for this metric_tuple_key tuple
struct m_KeyHash : public std::unary_function<metric_tuple_key, std::size_t> {
        std::size_t operator()(const metric_tuple_key& k) const {
            // the magic operation below makes collisions less likely than just the standard XOR
            std::size_t seed = std::hash<int>()(std::get<0>(k));
            seed ^= std::hash<int>()(std::get<1>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
            seed ^= std::hash<int>()(std::get<2>(k)) + 0x9e3779b97f4a7c15 + (seed << 6) + (seed >> 2);
            return seed ^ (std::hash<char>()(std::get<3>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
        }
    };

// define the comparison operator for this  metric_tuple_key tuple
struct m_KeyEqual : public std::binary_function<metric_tuple_key, metric_tuple_key, bool> {
        bool operator()(const metric_tuple_key& v0, const metric_tuple_key& v1) const {
            return (std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1) &&
                    std::get<2>(v0) == std::get<2>(v1) && std::get<3>(v0) == std::get<3>(v1));
        }
    };

std::unordered_map<metric_tuple_key, double, m_KeyHash, m_KeyEqual>           _metrics;

Я смог вставить значения в _metrics путем создания ключа кортежа.

Теперь я хочу получить некоторые значения из _metrics, когда указан ключ. 

//Retrieve around 120  double values. Total number of entries in _metrics is 21600
double k = _metrics.at((std::make_tuple(m, k, edge.first, edge.second))). //do this 120 times

Это оказывается очень медленным (почти 400 мс ). Я надеялся, что это займет около миллисекунды или меньше.

Я делаю что-то не так или std :: unordered_map не подходит для моего варианта использования. Ранее я использовал python словари для решения этой же проблемы, и получение значений практически мгновенно в python dicts

edit: некоторые unordered_map stats: 

 max_load_factor: 1

 size: 21600

 bucket_count: 25717

 load_factor: 0.839911

Edit: Timer Code : 

#include <chrono>
#include <iostream>
#include <iomanip>

class Timer {
private:
    std::chrono::time_point<std::chrono::steady_clock> start , stop;;

public:

    void startClock();
    void stopClock();
    void elapsedTime(std::string &message);

};
#include "Timer.hpp"

void Timer::startClock() {
    start = std::chrono::steady_clock::now();
}

void Timer::stopClock() {
    stop = std::chrono::steady_clock::now();
}


void Timer::elapsedTime(std::string &message) {
    auto diff = stop - start;
    std::cout << "Elapsed time for " <<message<< " " << std::setprecision(13) <<std::chrono::duration <double, std::milli> (diff).count() << " ms" << std::endl;
}

и измерение времени 

T_met.startClock();
for (const auto& edges: list_of_arcs())
{
    double k = _metrics.at((std::make_tuple(m, k, edge.first, edge.second)))
}
T_met.stopClock();

1 Ответ

2 голосов
/ 10 января 2020

Продолжительность поиска зависит от качества вашего га sh. Для теста можно использовать «карту» - она ​​имеет стабильную продолжительность поиска. Если карта быстрее неупорядоченной карты - ваш ха sh плохой.

...