std::map performance

[Dave Moore]

Oops, I was wrong and you are right. However my basic point remains.
The actual loop in lower_bound from my implementation (GNU libstdc++3)
is

while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);

return iterator(__y);

While you are right that the loop does not call strcmp() twice on each
node, it pays a cost for doing so by going deeper into the tree
unnecessarily even when _S_key(__x)==k (where an optimal
implementation would have returned) and calling strcmp() on the deeper
nodes. Either way the inefficiency lies in throwing away the
information contained in the three-valued (-ve,0,+ve) strcmp() by
converting it to the two-valued (true,false) predicate key_compare().

Hmm .. what if you "roll your own" predicate for text key comparison
instead of using strcmp? Can you do better on performance? You can
fairly easily write one that obeys strict weak ordering to use with
the std::map implementation. Something like:

// for NTBS
bool mylexcmp(const char *a, const char *b) {
bool result=true; // single return value for strong exception safety
while (a!='\0') {
if (b=='\0') result=false;
else if (a++ > b++) result=false;
}
return result;
}

and similar for std::string ... of course there is no guarantee that
my naive version above won't be slower that strcmp, but I expect there
is a way to write it that would be faster, since the comparison
criterion is less strict.

AFAICS this is more consistent with the "you don't pay for what you
don't use" philosophy underlying C++ (and C). OTOH, it may be that
the performance gain with the strict weak version is negligible, since
you only save the explicit check for equality (and the conversion of
the return value). However, if your test case is in English (or
another language), most of the repeated values (which are the source
of the performance difference IIUC) will likely be short words (a,
the, and, of, etc.), which will have the highest performance gain
using the above technique, so it might make a significant difference
after all for this particular case.

As you can perhaps tell, I don't have much experience with these kind
of performance issues (I deal mostly with numerical code), so it is
hard for me to guess at the effect ... I was just thinking (always
dangerous 8*).

Dave Moore

 

[Howard Hinnant]

You need to make both tests at most once per search, and then only
for a container that requires unique keys. So the deeper the tree,
the less extra overhead -- log(N)+1 vs. log(N) ain't no thang.

I don't think so. When you are traversing a tree with unique keys to
find a particular key, if you do both the tests you can terminate the
traversal early when you find an exact match. The cost of not doing so
will be higher for a deeper tree. This cost is zero for two corner
cases: an input consisting entirely of distinct words and an input
consisting entirely of repetitions of a single word. The worst case
will lie somewhere in between. Though I have not done a formal
analysis I think that the extra cost in the worst case will not be an
additive but a multiplicative one.
In short: not log(N)+1 but C.log(N) [my guess][/QUOTE]

Consider a perfectly balanced (and full) binary tree with L levels. It
will contain N elements with N and L related by:

N = 2^L - 1

The typical std::map/set implementation of find will do L+1 comparison
tests when searching for each element in the tree (as previously
described).

Your algorithm can also be analyzed in this context by finding the
"average depth" of each element. That is, if each element in the tree
is searched for, the average number of comparisons can be found by
finding the average depth in the tree.

The average depth of each element in the tree can be found by summing
the depth of each element and dividing by the total number of elements:

Sum[i*2^(i-1), {i, 1, L}] / (2^L - 1)

which simplifies to:

(2^L * (L - 1) + 1) / (2^L - 1)

As L grows large (doesn't have to be that large), the above formula for
average depth becomes approximately:

L - 1

That is, on average, when searching for an element that exists in the
tree, you will find it on the second-to-deepest level.

So the comparison is L+1 vs L-1, or in the earlier notation: log(N)+1 vs
log(N)-1.

-Howard

 

[Siemel Naran]

I think this case is quite general. First, this is the case for all
fundamental types. As my example shows, this is also the case for
strings, and they are quite frequently used as keys. Moreover, this is
even the case when comparison for a complicated type is based on
lexicographic ordering and comparison of simple types: for example
comparing two names by comparing the strings representing the last
names and if they are equal then comparing the strings representing
the first names. The last I think is by far the most general case:
even the comparison of strings is just lexicographic ordering of
arrays of characters.

Yes, I think std::map<std::string, Something> is quite common.

Anyway, perhaps the ternary tree is better for your purposes. Someone
posted an implementation of this to this newsgroup some months ago. You can
search on google. I have to get to work now, and can search for it later if
you can't find it.

 

[Siemel Naran]

Anyway, perhaps the ternary tree is better for your purposes. Someone
posted an implementation of this to this newsgroup some months ago. You can
search on google. I have to get to work now, and can search for it later if
you can't find it.

Actually it was in comp.lang.c++.moderated

Go to groups.google.com and search for

insubject:"Ternary search tree" group:comp.lang.c++.moderated

 

[jmoy]

You need to make both tests at most once per search, and then only
for a container that requires unique keys. So the deeper the tree,
the less extra overhead -- log(N)+1 vs. log(N) ain't no thang.

I don't think so. ... Though I have not done a formal
analysis I think that the extra cost in the worst case will not be an
additive but a multiplicative one.
In short: not log(N)+1 but C.log(N) [my guess]

Consider a perfectly balanced (and full) binary tree with L levels. It
will contain N elements with N and L related by:

N = 2^L - 1

The typical std::map/set implementation of find will do L+1 comparison
tests when searching for each element in the tree (as previously
described).

Your algorithm can also be analyzed in this context by finding the
"average depth" of each element.
...
The average depth of each element in the tree can be found by summing
the depth of each element and dividing by the total number of elements:
...
That is, on average, when searching for an element that exists in the
tree, you will find it on the second-to-deepest level.

So the comparison is L+1 vs L-1, or in the earlier notation: log(N)+1 vs
log(N)-1.

-Howard[/QUOTE]

Thanks a lot---I should have been paying more attention to my books.