Why is a vector find faster than a set with find()?

[James Kanze]

On 11/08/2012 19:16, James Kanze wrote:

You can improve the locality of the node based containers by using a
custom allocator; I got significant speed increases doing it this way
(but how much was down to improved locality and how much was down to not
using a general purpose allocator is unclear).

That would certainly help, but you'll still not get the locality of
std::vector, because each node is larger than an entry in a vector. And
of course, there's no way of telling the allocator where the element
being allocated will end up in the set, so that if you're iterating
through sequentially, you could still end up with relatively poor
locality. (If you had some way of telling the allocator the depth, you
could really win by regrouping the top nodes. Binary search on a vector
has poor locality at the beginning, since it's jumping all over the
place.)

In the end, there is no one perfect solution. If the abstraction is
fundamental to your application, define a class for it yourself; use
std::vector or std::set or whatever is simplest for you to implement it.
But provide it with a minimal interface (e.g. forward iterators, if
that's all that's needed, even if the implementation is std::vector), so
that you can easily switch implementation later, when you know where the
performance bottlenecks are.

 

[Juha Nieminen]

Are you sure?

Yes, I'm sure.

Think about the amount of steps required *per node* for a full traversal
from beginning to end. If you think about it, you'll see that the amount
of steps required per node is fixed, ie. O(1). (Thus for the entire tree
the total amount of steps is O(n).)

(If you still can't figure it out, the steps are, roughly: "Arrive at node,
go left, arrive from left, go right, arrive from right, go to parent." This
exact procedure is repeated for each node, and the amount of operations per
node does not depend on the size of the tree.)