Why is a std::set slower in traversing all the elements?

Question

We have a code that was originally using a deque as a container. Unfortunately, it wasn't fast enough for our time measurements since it's taking quite some time for it to do a search or sort. So, I recently refactored the code to try and use a set instead. It's definitely faster in terms of searching and sorting than a deque.

One thing I noticed though is that the set was way slower when traversing all the elements. We have a test that basically just traverses the elements from beginning up to the end until it matches the values it is looking for and found out that the set is taking almost 5x the time it takes for the deque to do it.

Can someone provide an explanation as to why the set is slower? I assumed that the time would be around the same since it's simply a traversal of all the elements from start to end, but that's not the case. I already did a lot of searching but can't find anything about a set being slower in traversing its elements.

Update: The set/deque contains a class that basically has two integer member variables.

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

We have a test that basically just traverses the elements from beginning up to the end until it matches the values it is looking for Can you use std::set::find instead? — R Sahu
– R Sahu, Commented May 21, 2018 at 23:01
I am not talking about using std::find. I am talking about using std::set::find. — R Sahu
– R Sahu, Commented May 21, 2018 at 23:06
It's likely that a dequeue stores most of its contents sequentially in memory, making it a very cache-friendly structure (for iteration). A set, OTOH, may well be storing each item in the set at a different/arbitrary location in memory, which would mean that there is little or no locality-of-reference during a set-traversal, and therefore your CPUs' caches are not as effective at hiding the RAM subsystem's inherent latency during a set-traversal as they were during a dequeue-traversal. — Jeremy Friesner
– Jeremy Friesner, Commented May 21, 2018 at 23:10
@thedandyman -- The set's strength is not traversing, it is searching / insertion / deletion. — PaulMcKenzie
– PaulMcKenzie, Commented May 22, 2018 at 1:37

Aki Suihkonen · Accepted Answer · 2018-05-22 03:28:32Z

There are two aspects in set traversal that are more difficult than in list traversal. The cache locality, as explained in the comments and the necessity to store a state to the iterator.

The sets are often implemented as self-balancing trees -- because generating a binary tree from sorted data would produce a degenerate tree, a linked list, which would not allow O(log N) insertions, deletions, or find. The self-balancing property will lead nodes allocated (possibly but not necessarily) from adjacent memory addresses to be accessed in arbitrary order leading to more cache misses.

The other issue is that traversing a tree with an iterator requires a state machine to be encoded in the iterator -- advancing the iterator needs to know, whether to move next to the left child or to the right one, leading to also increased number of branch predictions.

rsy56640 · Accepted Answer · 2018-05-22 02:51:49Z

ADD:
binary tree is indeed anti-cache-friendly, but I guess it is not the main problem.
.........................
dequeue::iterator++ is just (index++)%size (implemented on array), or take its next pointer(implemented on linked list).
set::iterator++ is INORDER TRAVERSAL in a tree. imagine current position is at root's precursor, so the next is root. it should go up and verify whether the current node is a left child, until it is, and the root is parent of the current node.
So travsersal in dequeue is more trivial than traversal in set.
...........................
std::set is implemented based on RB-Tree(a kind of BST).
find() is implemented with awareness of BST, which is O(logn).
If you traverse from the left-most to right-most to find the element, the cost is O(n).
Traversal from begin() to end() is actually the InOrder Traversal of the RB-Tree, while find() just goes down from root and compare key with two children.

find() would, of course, be faster than traversal from beginning to end but that's not the question. The question is why a set is slower in traversing the elements than a deque.
traversal in set is INORDER TRAVERSAL in a tree, but traversal in dequeue is just cursor++(implemented on array) or take its next pointer(implemented on linked list)

Collectives™ on Stack Overflow

Why is a std::set slower in traversing all the elements?

2 Answers 2

Comments

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Related