std::set: gratuitous comparisons?

[Paul Brettschneider]

Hi,

I wrote a little code snippet (see end of posting) to see what kind of
comparisons are made when inserting into a std::set container. The members
are a class wrapped around std::string with an internal counter to
differentiate between multiple instantiations of the class (but only the
string value is compared). For the insertion
sequence "A", "B", "C", "B", "A" I get the following comparisons (on g++
4.1):

A1
B2
lt:B2 vs. A1:0
lt:A1 vs. B2:1
lt:B2 vs. A1:0

Huh? This is strange for two reasons: first of all, if "A" < "B" == true,
then "B" < "A" *must* be false. And secondly, "B" < "A" was already tested
before.

C3
lt:C3 vs. A1:0
lt:C3 vs. B2:0
lt:B2 vs. C3:1
lt:C3 vs. B2:0

Same weirdness.

B4
lt:B4 vs. B2:0
lt:B4 vs. C3:1
lt:B2 vs. B4:0

This makes sense.

A5
lt:A5 vs. B2:1
lt:A5 vs. A1:0
lt:A1 vs. A5:0

This makes sense too.

So what happened in the first two cases? The only explanation I can come up
with is that some tree balancing (AVL or red/black?) code kicked in...

Thanks,
Paul

Testcode:
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>

class Item {
friend std:stream &operator<<(std:stream &out, const Item &i);
protected:
std::string s;
int num;
public:
Item(const char *s_) : s(s_) {
static int count = 0;
num = ++count;
std::cout << s << num << '\n';
};
bool operator<(const Item &i) const {
std::cout << "lt:"
<< *this << " vs. " << i << ":"
<< (s < i.s) << '\n';
return s < i.s;
};
};

std:stream &operator<<(std:stream &out, const Item &i)
{
return out << i.s << i.num;
}

int main()
{
std::set<Item> set;
set.insert(Item("A"));
set.insert(Item("B"));
set.insert(Item("C"));
set.insert(Item("B"));
set.insert(Item("A"));
std::cout << "------\n";
std::copy(set.begin(), set.end(),
std:stream_iterator<const Item>(std::cout, "\n"));
return 0;
}

 

[Victor Bazarov]

I wrote a little code snippet (see end of posting) to see what kind of
comparisons are made when inserting into a std::set container. The
members are a class wrapped around std::string with an internal
counter to differentiate between multiple instantiations of the class
(but only the string value is compared). For the insertion
sequence "A", "B", "C", "B", "A" I get the following comparisons (on
g++
4.1):


Huh? This is strange for two reasons: first of all, if "A" < "B" ==
true, then "B" < "A" *must* be false. And secondly, "B" < "A" was
already tested before.

If you do it in debug, it could be verifying that your 'less than'
operator is actually providing the correct strict weak ordering.
Beyond that, I don't know, could be a QoI issue.

[..]

V

 

[red floyd]

Hi,

I wrote a little code snippet (see end of posting) to see what kind of
comparisons are made when inserting into a std::set container. The members
are a class wrapped around std::string with an internal counter to
differentiate between multiple instantiations of the class (but only the
string value is compared). For the insertion
sequence "A", "B", "C", "B", "A" I get the following comparisons (on g++
4.1):


Huh? This is strange for two reasons: first of all, if "A" < "B" == true,
then "B" < "A" *must* be false. And secondly, "B" < "A" was already tested
before.

Perhaps it's an equality comparison ( !(a < b) && !(b < a) ) followed by
an ordering comparison??

 

[Paul Brettschneider]

If you do it in debug, it could be verifying that your 'less than'
operator is actually providing the correct strict weak ordering.
Beyond that, I don't know, could be a QoI issue.

No debugging options AFAIK. I compiled with "g++ -Wall -O3 test.C".
A guess of mine is that the standard defines some worst-case behaviour which
implies a balanced tree structure. (A non-balanced binary tree can degrade
to a list.)

Thanks,
Paul

 

[Greg Herlihy]

I wrote a little code snippet (see end of posting) to see what kind of
comparisons are made when inserting into a std::set container. The members
are a class wrapped around std::string with an internal counter to
differentiate between multiple instantiations of the class (but only the
string value is compared). For the insertion
sequence "A", "B", "C", "B", "A" I get the following comparisons (on g++
4.1):


Huh? This is strange for two reasons: first of all, if "A" < "B" == true,
then "B" < "A" *must* be false. And secondly, "B" < "A" was already tested
before.

The set's insertion routine performs a binary search of the set's
contents in order to find the proper insertion point for the item
being inserted. So the comparisons observed above - match the
comparisons performed by a binary search. In particular, the results
of the last two comparisons (true and false) are exactly the results
expected when the search has found the two elements (one higher, one
lower) between which the item will be inserted. Naturally, when
performing a binary search in a set with only one or two elements, it
is quite likely that same object will be involved in more than one of
the search's comparisons.

So, when performing a binary search in a set that contains only one or
two objects, it would in fact be possible to eliminate one of these
redundant comparisons. But there would be little point in doing so -
because this optimization is so small and so infrequent - that merely
testing for small sets would add more overhead (and complexity) to the
set's insertion routine in all cases - than could possibly be
recouped by applying the optimization in the two special cases.

Greg

 

[James Kanze]

I wrote a little code snippet (see end of posting) to see what
kind of comparisons are made when inserting into a std::set
container. The members are a class wrapped around std::string
with an internal counter to differentiate between multiple
instantiations of the class (but only the string value is
compared). For the insertion sequence "A", "B", "C", "B", "A"
I get the following comparisons (on g++ 4.1):

Huh? This is strange for two reasons: first of all, if "A" <
"B" == true, then "B" < "A" *must* be false. And secondly, "B"
< "A" was already tested before.

Since you've got g++, it's pretty simple to look at the g++
source code and see what is happening. (In the libstdc++ tree,
the actual code is in _M_insert_unique in bits/stl_tree.h.)
Basically, when insert is called, the tree consists of a single
node, with A1 in it. The first comparison tells the code that
the new node goes to the right (or is equal---you can't forget
that). The algorithm then checks the right node, and finds that
it is null. It then does the reverse comparision, to check for
equality---if both return false, then no insertion takes place.
It then calls the function which does the actual insertion,
which does an extra check to determine whether the insertion is
to the left or to the right. (Given the way we arrive here, we
know that it can only be to the right, but the function which
does the insertion may be called from other places as well. But
it's true that it probably could have been spared, at the cost
of some additional code complexity. Or I've possibly misread
the code.)

Same weirdness.

This makes sense.

Here, the first two checks find the potential position---the
third tells us that we are equal, so no insertion takes place.

This makes sense too.

So what happened in the first two cases? The only explanation
I can come up with is that some tree balancing (AVL or
red/black?) code kicked in...

The standard requires the tree to be balanced (since it requires
logrithmic complexity), but once you've found the exact postion
of insertion, there's no need for any additional comparisons for
the balancing (and in fact, the balancing code doesn't seem to
be present in the template sources---which makes me think that
it isn't even a template).

There does seem to be one extra comparison in there, that
possibly could be avoided. But don't forget that you do have to
check for equality, and not insert in such cases.

 

[Paul Brettschneider]

Since you've got g++, it's pretty simple to look at the g++
source code and see what is happening. (In the libstdc++ tree,
the actual code is in _M_insert_unique in bits/stl_tree.h.)
Basically, when insert is called, the tree consists of a single
node, with A1 in it. The first comparison tells the code that
the new node goes to the right (or is equal---you can't forget
that). The algorithm then checks the right node, and finds that
it is null. It then does the reverse comparision, to check for
equality---if both return false, then no insertion takes place.
It then calls the function which does the actual insertion,
which does an extra check to determine whether the insertion is
to the left or to the right. (Given the way we arrive here, we
know that it can only be to the right, but the function which
does the insertion may be called from other places as well. But
it's true that it probably could have been spared, at the cost
of some additional code complexity. Or I've possibly misread
the code.)

Thanks a lot!
You are absolutely right: _M_insert_unique calls _M_insert, which does
another comparison. Strange, I would have thought that something as
fundamental as the standard containers would be "optimised to death". But
apparently not so.

Here, the first two checks find the potential position---the
third tells us that we are equal, so no insertion takes place.



The standard requires the tree to be balanced (since it requires
logrithmic complexity), but once you've found the exact postion
of insertion, there's no need for any additional comparisons for
the balancing (and in fact, the balancing code doesn't seem to
be present in the template sources---which makes me think that
it isn't even a template).

I think you're right again: On my system _Rb_tree_insert_and_rebalance is a
library object:

$ objdump --dynamic-syms libstdc++.so.6.0.9 | grep
_Rb_tree_insert_and_rebalance
0005b270 g DF .text 00000176 GLIBCXX_3.4
_ZSt29_Rb_tree_insert_and_rebalancebPSt18_Rb_tree_node_baseS0_RS_

Thanks,
Paul

 

[Daniel Dearlove]

Other items to note:

1) Your program leaks memory like a sieve. I see many instances of
"new char" (which probably should be "new char[MAX_LENGTH + 1]"), but
I don't ever see a call to "delete" (or delete[] if you fix the
allocations).
2) This gets a whole lot easier if you change to
std::strings. All of the dynamic memory stuff related to "strings"
goes away.
3) If you're trying to read an entire line into a
std::string, look up std::getline() (and not the getline() that is a
member of a stream).
4) I'm assuming it's part of the assignment that
you can't use the rest of the standard C++ library (like std::list, or
some other container)?

I also assume you can't use the std::string or STL features.

1. You might find it easier, more OO, to nest your linked list
implementation in another class. An incomplete definition might be:

class LinkedList
{
public:
LinkedList();
~LinkedList();

void insert( cdData* item );

private:
cdData* head;
};

This way you can do proper deletion in the destructor and it nicely
separates your intention from implementation detail. As a user of
LinkedList, you don't need to know how it is implemented under the hood
even though, in reality, you are coding LinkedList too.

2. When you read a string from std::cin, try encapsulating it in it's own
function that returns a char* with the string you just read. The function
prototype might be something like:

namespace My
{
char* getLine( std::istream& is ); // normally getLine( std::cin )
}

And now you can do a getName() function as:

namespace My
{
char* getName( std::istream& is )
{
std::cout << "Name of CD: " << std::flush;
return My::getLine( is );
}
}

This should neaten up those loops and functions a little bit. It should
also reduce the number of points where you can mishandle dynamic memory
allocation by reducing the number of points where you have to do it.

3. There are a few shortcomings in the way cdData is being implemented but
I am assuming that class has been handed to you to use. A parameterized
constructor and delete[]'s in the destructor would go a long way to
improving things when you have to delete things in your LinkedList class
if you are allowed to change the implementation.

4. Your current implementation assumes no removal of items from the linked
list and relies on the OS to do memory clean-up after your app exits. You
need to consider the destruction of objects, particularly when the
LinkedList class destructs. For the moment, I would assume your
LinkedList never removes an item except at destruction where it deletes
all of the items.

5. Hopefully this will guide you in the ways of C++ without giving you too
much in the way of actual code.

 

[Gerhard Fiedler]

Strange, I would have thought that something as fundamental as the
standard containers would be "optimised to death". But apparently not
so.

Maybe this behavior /is/ the optimal way to treat the problem?

Gerhard

 

[Paul Brettschneider]

Maybe this behavior /is/ the optimal way to treat the problem?

How could making a useless comparison be the optimal way? I doubt it makes
the code shorter, so there isn't even an instruction-cache argument. And
don't forget that we're talking about templates, so compares might be quite
expensive. All in all I must admit that I'm not following you..

 

[Gerhard Fiedler]

How could making a useless comparison be the optimal way? I doubt it
makes the code shorter, so there isn't even an instruction-cache
argument. And don't forget that we're talking about templates, so
compares might be quite expensive. All in all I must admit that I'm not
following you..

I haven't looked at this particular code to be able to say how it is in
this case (note the "maybe"), but what I'm saying is that including special
treatment for one case often adds code that needs to be run in all other
cases, too. And that can invert the effect.

Imagine a function that is called in different circumstances (like the case
you were discussing: the "circumstance" in this case is the number of
elements in the set). Let's say you optimize away 10 us of runtime in one
case, but the change adds 0.1 us of runtime to all cases. If that one, now
optimized case makes up less than 1% of the actual calls, the overall
runtime is increased after this "optimization", not reduced.

In order to see how this is with a particular case, one would have to
suggest an optimization and analyze how much it optimized in the now better
optimized cases and how much overhead it added to other cases. In order to
judge whether this is an improvement, one has to apply a reasonable
distribution for the different cases to the modification and calculate the
improvement distribution. Depending on the characteristics, it may have
areas where the improvement is negative.

Gerhard

 

[James Kanze]

On 2008-03-17 16:52:42, Paul Brettschneider wrote:

It's not.

I haven't looked at this particular code to be able to say how
it is in this case (note the "maybe"), but what I'm saying is
that including special treatment for one case often adds code
that needs to be run in all other cases, too. And that can
invert the effect.

That's not the case here. The function which does the extra
comparison is (in this case) called from a function in a way
where the extra comparison will always have the same results.
The function itself is doubtlessly called from elsewhere, as
well, where the comparison is necessary, but it's short enough
that it could have been provided in two versions, one which
makes the comparison, and one which doesn't. (I suspect,
although I've not verified, that in the case of std::set and
std::map, the comparison is always superfluous; that it is only
necessary in the case of std::multiset and std::multimap.)

Whether it's worth it or not is another matter. If comparisons
are very expensive, and there are a lot of insertions, it
doubtless is. But if comparisons are very expensive, you'd
probably want to use a different data structure (maybe a hash
table) anyway. Still, at first glance, it didn't seem like a
difficult optimization.