Составной контейнер из std::set быстрее, чем сам std::set?

Я сделал составной контейнер Range, который принимает либо минимальный/максимальный диапазон как std::pair, либо набор целых чисел как std::set.

внутренне копия ввода сохраняется как void *

Этот контейнер поддерживает iterators, и мне было любопытно, насколько быстро этот контейнер по сравнению с итерацией только по набору std::set.

Я убедился, что пишу каждый цикл итерации в своем тесте со следующими политиками:

  • без постинкремента (медленнее)
  • убедитесь, что компилятор не может полностью оптимизировать циклы
  • сравнивать одни и те же вещи

У меня есть следующие тайминги: тест производительности

Тест скорости
ВРЕМЯ ВЫПОЛНЕНИЯ диапазона: [Pair] : 13,0522 мс
ВРЕМЯ ВЫПОЛНЕНИЯ диапазона: [Set]: 272,54 мс
ВРЕМЯ ВЫПОЛНЕНИЯ std::set: 438,239 мс
ВРЕМЯ ВЫПОЛНЕНИЯ диапазона: Обычный цикл For: 0,000175 мс

Во-первых я был удивлен, и я надеюсь, что вы тоже, потому что почему мой контейнер Range должен быть быстрее, поскольку итераторы Range содержат бот итератор для std::pair (просто целое число) и для std::set. И моя реализация Range::iterator фактически перенаправляет все операторы в std::set, если Range является std::set.

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


performance iterator c++11 stl stdset
person Gabriel    schedule 05.06.2014    source источник
comment
Этот вопрос лучше подходит для codereview.stackexchange.com.   -  person Ali    schedule 05.06.2014
comment
Обратите внимание, что ваша программа всегда работает на MSVC2013. Это потому, что его RAND_MAX равен 32767, но вы пытаетесь вставить в набор 1E5 (уникальных) элементов.   -  person dyp    schedule 05.06.2014
comment
Я думаю, это связано с копией, которую вы выполняете в Range<Type> range(s);. Если я скопирую набор после вставки, например. вставьте в некоторые set<Type> s2;, затем после вставки auto s = s2;, тогда цикл std::set будет быстрее. Это может быть связано с локальностью, поскольку копия набора будет копировать элементы, как правило, в порядке обхода, в то время как вставка создает соседей, которые были выделены в очень разное время.   -  person dyp    schedule 05.06.2014
comment
@dyp: хорошо =) Я думаю, это правильно:   -  person Gabriel    schedule 05.06.2014

Ответы (1)


arrow_upward
0
arrow_downward

С комментарием dyp: std::set работает быстрее!

Тест скорости =============================
ВРЕМЯ РАБОТЫ диапазона: [Пара] : 8,69353 мс
ВРЕМЯ РАБОТЫ диапазона: [Set]: 281,202 мс
ВРЕМЯ ВЫПОЛНЕНИЯ std::set: 220,367 мс // Повторно скопировано ВРЕМЯ ВЫПОЛНЕНИЯ std::set
диапазона: Normal For Loop: 0,000196 мс

person Gabriel    schedule 05.06.2014