Переход с boost::unordered_map и boost::unordered_set на std::unordered_map и std::unordered_set
С того времени, как мы перешли на Visual C++ 2015, прошло больше года. До сих пор мы использовали boost::unordered_map и boost::unordered_set, и они себя вполне хорошо зарекомендовали. Однако, наконец-то, дошли руки протестировать их реализацию из стандартной библиотеки нового компилятора.
Самый распространенный случай использования ключей для этих контейнеров в нашей системе — это либо std::string, либо какой-то интегральный тип, либо что-то, приводящее к нему (например, enum). При этом размеры контейнеров не очень большие, в пределах от единиц до нескольких десятков, реже сотен элементов. Сначала заполним элементы значениями, определим ключи так, чтобы был равномерный разброс по диапазону. Затем для выбранных ключей прогоним тест в цикле и измерим время. Как обычно, тесты делаем с использованием Boost.Test.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
BOOST_AUTO_TEST_CASE(unordered_set_str_test) { std::unordered_set s_set = { "MCXS.AVAZ", "MCXS.AVAZP", "MCXS.BANE", "MCXS.BANEP", "MCXS.CHMF", "MCXS.FEES", "MCXS.GAZP", "MCXS.GMKN", "MCXS.HYDR", "MCXS.IRAO", "MCXS.LKOH", "MCXS.MAGN", "MCXS.MGNT", "MCXS.RSTI", "MCXS.RSTIP", "MCXS.MTLR", "MCXS.MTLRP", "MCXS.MSNG", "MCXS.MTSS", "MCXS.NLMK", "MCXS.NVTK", "MCXS.OGKB", "MCXS.RASP", "MCXS.ROSN", "MCXS.RTKM", "MCXS.RTKMP", "MCXS.RUALR", "MCXS.SBER", "MCXS.SBERP", "MCXS.SIBN", "MCXS.SNGS", "MCXS.SNGSP", "MCXS.TATN", "MCXS.TATNP", "MCXS.TRNFP", "MCXS.URKA", "MCXS.VTBR", "MCXS.MICEX", "MCXS.MICEX10", "MCXS.MICEXSC", "MCXS.MICEXOG", "MCXS.MICEXFNL", "MCXS.MICEXMM", "MCXS.MICEXPWR", "MCXS.RTSI", "MCXS.RTS2", "MCXS.RTSog", "MCXS.RTSfn", "MCXS.RTSmm", "MCXS.RTSeu", "MCXF.BR", "MCXF.CHMF", "MCXF.Eu", "MCXF.FEES", "MCXF.GAZR", "MCXF.GMKR", "MCXF.GOLD", "MCXF.HYDR", "MCXF.LKOH", "MCXF.MGNT", "MCXF.MIX", "MCXF.MXI", "MCXF.MTSI", "MCXF.ROSN", "MCXF.RTKM", "MCXF.RTS", "MCXF.SNGR", "MCXF.SNGP", "MCXF.SBPR", "MCXF.SBRF", "MCXF.Si", "MCXF.SILV", "MCXF.TATN", "MCXF.URKA", "MCXF.VTBR" }; boost::unordered_set b_set = { "MCXS.AVAZ", "MCXS.AVAZP", "MCXS.BANE", "MCXS.BANEP", "MCXS.CHMF", "MCXS.FEES", "MCXS.GAZP", "MCXS.GMKN", "MCXS.HYDR", "MCXS.IRAO", "MCXS.LKOH", "MCXS.MAGN", "MCXS.MGNT", "MCXS.RSTI", "MCXS.RSTIP", "MCXS.MTLR", "MCXS.MTLRP", "MCXS.MSNG", "MCXS.MTSS", "MCXS.NLMK", "MCXS.NVTK", "MCXS.OGKB", "MCXS.RASP", "MCXS.ROSN", "MCXS.RTKM", "MCXS.RTKMP", "MCXS.RUALR", "MCXS.SBER", "MCXS.SBERP", "MCXS.SIBN", "MCXS.SNGS", "MCXS.SNGSP", "MCXS.TATN", "MCXS.TATNP", "MCXS.TRNFP", "MCXS.URKA", "MCXS.VTBR", "MCXS.MICEX", "MCXS.MICEX10", "MCXS.MICEXSC", "MCXS.MICEXOG", "MCXS.MICEXFNL", "MCXS.MICEXMM", "MCXS.MICEXPWR", "MCXS.RTSI", "MCXS.RTS2", "MCXS.RTSog", "MCXS.RTSfn", "MCXS.RTSmm", "MCXS.RTSeu", "MCXF.BR", "MCXF.CHMF", "MCXF.Eu", "MCXF.FEES", "MCXF.GAZR", "MCXF.GMKR", "MCXF.GOLD", "MCXF.HYDR", "MCXF.LKOH", "MCXF.MGNT", "MCXF.MIX", "MCXF.MXI", "MCXF.MTSI", "MCXF.ROSN", "MCXF.RTKM", "MCXF.RTS", "MCXF.SNGR", "MCXF.SNGP", "MCXF.SBPR", "MCXF.SBRF", "MCXF.Si", "MCXF.SILV", "MCXF.TATN", "MCXF.URKA", "MCXF.VTBR" }; size_t const count = 100000000; std::vector<std::string> search_keys = { "MCXS.AVAZ", "MCXS.MCXS.RTKM", "MCXS.MICEXPWR", "MCXF.MIX", "MCXF.URKA" }; DateTime dt; dt = DateTime::now(); std::cout << "std::unordered_set " << count << " times search: "; for(int i = 0; i < count; i++) { for(std::string const& key : search_keys) s_set.find(key); } std::cout << DateTime::now() - dt << std::endl; dt = DateTime::now(); std::cout << "boost::unordered_set " << count << " times search: "; for(int i = 0; i < count; i++) { for(std::string const& key : search_keys) b_set.find(key); } std::cout << DateTime::now() - dt << std::endl; } |
Теперь сделаем то же самое для интегральных типов.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
BOOST_AUTO_TEST_CASE(unordered_set_enum_test) { std::unordered_set s_set = { OrderStateEnum::INITIALIZED, OrderStateEnum::PENDING_FOR_OPEN, OrderStateEnum::PLACED_FOR_OPEN, OrderStateEnum::PARTIALLY_OPENED, OrderStateEnum::OPENED, OrderStateEnum::PENDING_FOR_CLOSE, OrderStateEnum::PLACED_FOR_CLOSE, OrderStateEnum::PARTIALLY_CLOSED, OrderStateEnum::CLOSED, OrderStateEnum::CANCELLED, OrderStateEnum::FAILED }; boost::unordered_set b_set = { OrderStateEnum::INITIALIZED, OrderStateEnum::PENDING_FOR_OPEN, OrderStateEnum::PLACED_FOR_OPEN, OrderStateEnum::PARTIALLY_OPENED, OrderStateEnum::OPENED, OrderStateEnum::PENDING_FOR_CLOSE, OrderStateEnum::PLACED_FOR_CLOSE, OrderStateEnum::PARTIALLY_CLOSED, OrderStateEnum::CLOSED, OrderStateEnum::CANCELLED, OrderStateEnum::FAILED }; size_t const count = 1000000000; std::vector search_keys = { OrderStateEnum::INITIALIZED, OrderStateEnum::PARTIALLY_CLOSED, OrderStateEnum::PLACED_FOR_CLOSE, OrderStateEnum::PENDING_FOR_OPEN, OrderStateEnum::FAILED }; DateTime dt; dt = DateTime::now(); std::cout << "std::unordered_set " << count << " times search: "; for(int i = 0; i < count; i++) { for(OrderStateEnum const& key : search_keys) s_set.find(key); } std::cout << DateTime::now() - dt << std::endl; dt = DateTime::now(); std::cout << "boost::unordered_set " << count << " times search: "; for(int i = 0; i < count; i++) { for(OrderStateEnum const& key : search_keys) b_set.find(key); } std::cout << DateTime::now() - dt << std::endl; } |
Результат вывода теста:
|
1 2 3 4 5 6 7 |
Running 2 test cases... std::unordered_set 100000000 times search: 00:00:12.571686 boost::unordered_set 100000000 times search: 00:00:17.412110 std::unordered_set 1000000000 times search: 00:00:31.595703 boost::unordered_set 1000000000 times search: 00:00:34.313476 *** No errors detected |
Как видно, результат для std::unordered_set для данных условий отличается в лучшую сторону.
В тестах использован класс DateTime, использующийся в нашей кодовой базе, но это по сути boost::posix_time::ptime с набором дополнительных сервисных методов. OrderStateEnum — класс-обертка энумератора состояний ордеров, также использующийся в платформе. Для того, чтобы его можно было использовать в качестве ключа в unordered_set, необходимо переопределить оператор == и специализировать boost::hash_value() и std::hash.
Должен заметить, что тест может показать и другие результаты в иных условиях, например, про большом количестве элементов или при других типах ключей. Однако, это тестирование было проведено конкретно для нашего случая и показало хороший результат. Соответственно, мы пришли к выводу, что избавление от лишней зависимости в данном случае оправданно.
