Почему unordered_map и карта дают такую ​​же производительность?

Question

Вот мой код, мой unordered_map и карта ведут себя одинаково и принимают одно и то же время для выполнения. Я что-то пропустил об этих структурах данных?

Обновление: я изменил свой код на основе приведенных ниже ответов и комментариев. Я удалил операцию строки, чтобы уменьшить влияние на профилирование. Также теперь я только измеряю find(), который занимает почти 40% процессора в моем коде. Профиль показывает, что unordered_map в 3 раза быстрее, однако, есть ли другой способ сделать этот код быстрее?

#include <map> 
#include <unordered_map> 
#include <stdio.h> 

struct Property { 
    int a; 
}; 

int main() { 
    printf("Performance Summery:\n"); 
    static const unsigned long num_iter = 999999; 

    std::unordered_map<int, Property > myumap; 
    for (int i = 0; i < 10000; i++) { 
     int ind = rand() % 1000; 
     Property p; 
     p.a = i; 
     myumap.insert(std::pair<int, Property> (ind, p)); 
    } 

    clock_t tStart = clock(); 
    for (int i = 0; i < num_iter; i++) { 
     int ind = rand() % 1000; 
     std::unordered_map<int, Property >::iterator itr = myumap.find(ind); 
    } 

    printf("Time taken unordered_map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); 

    std::map<int, Property > mymap; 
    for (int i = 0; i < 10000; i++) { 
     int ind = rand() % 1000; 
     Property p; 
     p.a = i; 
     mymap.insert(std::pair<int, Property> (ind, p)); 
    } 

    tStart = clock(); 
    for (int i = 0; i < num_iter; i++) { 
     int ind = rand() % 1000; 
     std::map<int, Property >::iterator itr = mymap.find(ind); 
    } 

    printf("Time taken map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); 
} 

Выход здесь

Performance Summery: 
Time taken unordered_map: 0.12s 
Time taken map: 0.36s 

Answer 1

Не вдаваясь в код, я хотел бы сделать несколько общих замечаний.

1. Что именно вы измеряете? Ваше профилирование включает в себя как заполнение, так и сканирование структур данных. Учитывая, что (предположительно) заполнение упорядоченной карты займет больше времени, измерение обеих работ противоречит идее выигрыша (или иначе) упорядоченной карты. Выясните, что вы измеряете и просто измеряете это.
2. У вас также много чего происходит в коде, который, вероятно, связан с тем, что вы профилируете: существует много создания объектов, конкатенация строк и т. Д. Это, вероятно, то, что вы на самом деле измеряете. Сосредоточьтесь на профилировании только того, что вы хотите измерить (см. Пункт 1).
3. 10 000 случаев слишком малы. В этом масштабе другие соображения могут подавить то, что вы измеряете, особенно когда вы все измеряете.

Answer 2

Есть причина, по которой нам нравится получать minimal, complete and verifiable примеров. Вот мой код:

#include <map> 
#include <unordered_map> 
#include <stdio.h> 

struct Property { 
    int a; 
}; 

static const unsigned long num_iter = 100000; 
int main() { 
    printf("Performance Summery:\n"); 
    clock_t tStart = clock(); 
    std::unordered_map<int, Property> myumap; 

    for (int i = 0; i < num_iter; i++) { 
     int ind = rand() % 1000; 
     Property p; 
     //p.fileName = "hello" + to_string(i) + "world!"; 
     p.a = i; 
     myumap.insert(std::pair<int, Property> (ind, p)); 
    } 

    for (int i = 0; i < num_iter; i++) { 
     int ind = rand() % 1000; 
     myumap.find(ind); 
    } 

    printf("Time taken unordered_map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); 

    tStart = clock(); 
    std::map<int, Property> mymap; 

    for (int i = 0; i < num_iter; i++) { 
     int ind = rand() % 1000; 
     Property p; 
     //p.fileName = "hello" + to_string(i) + "world!"; 
     p.a = i; 
     mymap.insert(std::pair<int, Property> (ind, p)); 
    } 

    for (int i = 0; i < num_iter; i++) { 
     int ind = rand() % 1000; 
     mymap.find(ind); 
    } 

    printf("Time taken map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); 
} 

Время работы является:

Performance Summery: 
Time taken unordered_map: 0.04s 
Time taken map: 0.07s 

Пожалуйста, обратите внимание, что я бегу в 10 раз число итераций вы были запущены.

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

Answer 3

ли дерево (std::map) или хэш-карта (std::unordered_map) быстрее на самом деле зависит от количества записей и характеристик ключа (вариабельности значений, Сравнение и хеширования функций и т.д.)

Но в теории, дерева медленнее, чем хэш-карта потому, что вставка и поиск внутри двоичного дерева O (log2 (N)) сложности во время вставки и поиск внутри хэш-карты является примерноO (1) сложность.

Ваш тест не показывал, потому что:

1. Вы называете rand() в цикле. Это занимает много времени по сравнению с вставкой карты. И он генерирует разные значения для двух карт, которые вы тестируете, еще больше искажает результаты. Используйте генератор с более легким весом, например. a minstd LCG.

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

3. Вам необходимо убедиться, что компилятор не измените ваш код, поэтому вызовы синхронизации происходят там, где они должны. Это не всегда легко. Запоминание памяти вокруг приуроченного теста обычно помогает решить эту проблему.

4. Ваши звонки find() имеют высокую вероятность того, что вас оптимизируют, так как вы не используете их значение (я просто знаю, что по крайней мере GCC в режиме -O2 этого не делает, поэтому я оставляю его как есть).

5. Строка конкатенации также очень медленная в сравнении.

Вот моя обновленная версия:

#include <atomic> 
#include <chrono> 
#include <iostream> 
#include <map> 
#include <random> 
#include <string> 
#include <unordered_map> 

using namespace std; 
using namespace std::chrono; 

struct Property { 
    string fileName; 
}; 

const int nIter = 1000000; 

template<typename MAP_TYPE> 
long testMap() { 
    std::minstd_rand rnd(12345); 
    std::uniform_int_distribution<int> testDist(0, 1000); 
    auto tm1 = high_resolution_clock::now(); 
    atomic_thread_fence(memory_order_seq_cst); 
    MAP_TYPE mymap; 

    for (int i = 0; i < nIter; i++) { 
    int ind = testDist(rnd); 
    Property p; 
    p.fileName = "hello" + to_string(i) + "world!"; 
    mymap.insert(pair<int, Property>(ind, p)); 
    } 
    atomic_thread_fence(memory_order_seq_cst); 

    for (int i = 0; i < nIter; i++) { 
    int ind = testDist(rnd); 
    mymap.find(ind); 
    } 

    atomic_thread_fence(memory_order_seq_cst); 
    auto tm2 = high_resolution_clock::now(); 
    return (long)duration_cast<milliseconds>(tm2 - tm1).count(); 
} 

int main() 
{ 
    printf("Performance Summary:\n"); 
    printf("Time taken unordered_map: %ldms\n", testMap<unordered_map<int, Property>>()); 
    printf("Time taken map: %ldms\n", testMap<map<int, Property>>()); 
} 

Compiled with -O2, это дает следующие результаты:

Performance Summary: 
Time taken unordered_map: 348ms 
Time taken map: 450ms 

Так, используя unordered_map в этот частный случай быстрее на ~ 20-25 %.

Answer 4

Это не просто поиск быстрее с помощью unordered_map. Этот слегка модифицированный тест также сравнивает время заполнения.

Я сделал пару модификаций:

1. увеличен размер выборки
2. обе карты теперь используют ту же последовательность случайных чисел.

-

#include <map> 
#include <unordered_map> 
#include <vector> 
#include <stdio.h> 

struct Property { 
    int a; 
}; 

struct make_property : std::vector<int>::const_iterator 
{ 
    using base_class = std::vector<int>::const_iterator; 
    using value_type = std::pair<const base_class::value_type, Property>; 
    using base_class::base_class; 

    decltype(auto) get() const { 
     return base_class::operator*(); 
    } 

    value_type operator*() const 
    { 
     return std::pair<const int, Property>(get(), Property()); 
    } 
}; 

int main() { 
    printf("Performance Summary:\n"); 
    static const unsigned long num_iter = 9999999; 

    std::vector<int> keys; 
    keys.reserve(num_iter); 
    std::generate_n(std::back_inserter(keys), num_iter, [](){ return rand()/10000; }); 


    auto time = [](const char* message, auto&& func) 
    { 
     clock_t tStart = clock(); 
     func(); 
     clock_t tEnd = clock(); 
     printf("%s: %.2gs\n", message, double(tEnd - tStart)/CLOCKS_PER_SEC); 
    }; 

    std::unordered_map<int, Property > myumap; 
    time("fill unordered map", [&] 
    { 
     myumap.insert (make_property(keys.cbegin()), 
         make_property(keys.cend())); 
    }); 


    std::map<int, Property > mymap; 
    time("fill ordered map",[&] 
     { 
      mymap.insert(make_property(keys.cbegin()), 
          make_property(keys.cend())); 
     }); 

    time("find in unordered map",[&] 
     { 
      for (auto k : keys) { myumap.find(k); } 
     }); 

    time("find in ordered map", [&] 
     { 
      for (auto k : keys) { mymap.find(k); } 
     }); 
} 

пример вывода:

Performance Summary: 
fill unordered map: 3.5s 
fill ordered map: 7.1s 
find in unordered map: 1.7s 
find in ordered map: 5s