Почему std :: set работает медленнее при обходе всех элементов?

Question

У нас есть код, который изначально использовал deque в качестве контейнера.К сожалению, это не было достаточно быстро для наших измерений времени, так как для поиска или сортировки уходит довольно много времени.Итак, я недавно реорганизовал код, чтобы попытаться использовать набор вместо этого.Это определенно быстрее с точки зрения поиска и сортировки, чем deque.

Одна вещь, которую я заметил, это то, что набор был намного медленнее при обходе всех элементов.У нас есть тест, который в основном просто обходит элементы от начала до конца, пока он не совпадает со значениями, которые он ищет, и обнаружил, что набор занимает почти 5 раз больше времени, которое требуется для того, чтобы deque это сделал.

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

Обновление: set / deque содержит класс, который в основном имеет две целочисленные переменные-члены.

class Element
{
    uint32_t id;
    uint32_t time;
};

Compile options:
-g -pipe -funit-at-a-time
-O3 --param inline-unit-growth=10000 --param large-function-growth=10000 --param max-inline-insns-single=10000
-Wall -Wextra -Wno-aggregate-return -Wno-padded -Wno-reorder -Wno-sign-compare -Wno-unused-parameter -Wcast-align -Wcast-qual -Wdisabled-optimization -Wfloat-equal -Wno-inline -Wlarger-than-10000 -Wmissing-format-attribute -Wpointer-arith -Wredundant-decls -Wno-unknown-pragmas

Answer 1

В обходе множества есть два аспекта, которые сложнее, чем в обходе списка.Местонахождение кэша, как объяснено в комментариях, и необходимость сохранять состояние для итератора.

Множества часто реализуются в виде самобалансирующихся деревьев - потому что генерация двоичного дерева из отсортированных данных приведет к вырождениюдерево, связанный список, который не позволяет O (log N) вставки, удаления или поиска.Свойство самобалансировки приведет к тому, что узлы, выделенные (возможно, но не обязательно) из соседних адресов памяти, будут доступны в произвольном порядке, что приведет к большему количеству пропусков кэша.

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

Answer 2

ADD:
бинарное дерево действительно защищено от кеширования, но я думаю, что это не главная проблема.
.........................
dequeue :: iterator ++ имеет размер (index ++)% (реализован в массиве) или использует следующий указатель (реализован в связанном списке).
set :: iterator ++ является INORDER TRAVERSAL вдерево.Представьте, что текущая позиция находится у предшественника root, поэтому следующая - root.он должен подняться и проверить, является ли текущий узел левым потомком, пока он не будет, и корень является родительским для текущего узла.
Таким образом, travsersal в очереди более тривиален, чем обход в наборе.
...........................
std :: set реализован на основе RB-Tree (разновидность BST).
find () реализовано с учетом BST, то есть O (logn).
Если вы переместитесь от крайнего левого к крайнему правому углу, чтобы найти элемент, стоимость составит O (n).
Обход с начала () to end () на самом деле является обходом InOrder RB-дерева, тогда как find () просто спускается от корня и сравнивает ключ с двумя дочерними элементами.