Seungbeom Kim wrote:
.
> A better example is std::binary_search, which IS one of them.
"Returns:
> true if there is an iterator i in the range [first, last) that
satisfies
> the corresponding conditions: !(*i < value) && !(value < *i) or
comp(*i,
> value) == false && comp(value, *i) == false." Here you can see that
the
> comparator is called twice to test for equality. I can certainly
imagine
> that a 3-way comparison would have made it much more efficient.

I'm curious: how would you achieve that? The typical binary search
requires on the order of log2(N) evaluations of the two-way comparison
operator; only at the very end of the search, when the target range has
been completely bracketed, does the difference between two-way and
three-way comparisons matter, and then it only saves you a couple of
comparisons to use the three-way comparison. If the three-way
comparison is slightly slower than the two-way one (as is often the
case), that speed difference may be more important than the lower
operation count, particularly if the comparisons can be in-lined.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Seungbeom Kim wrote:

> ... A better example is std::binary_search ... I can certainly
imagine
> that a 3-way comparison would have made it much more efficient.

If the "typical" use of binary search is over 1e6 elements, where at
most one element matches, a 3-way compare drops the number of
comparison calls from about 21 to 20, roughly a 5% improvement,
probably not enough to qualify as "much more efficient".

OTOH, if you frequently call  binary search on ranges with a single
element, you'd get to cut the number of comparisons in half ;-).

In the following example, if I search for 7, the three-way compare is
about 10% faster on my machine (MSVC7.1 optimized on a Pentium4).  If I
search for -7, the less() version is about 20% faster.

template<class RANIT, class TYPE, class LESS>
bool bsl(RANIT first, RANIT last, TYPE value, LESS less)
{
  iter left = first;  // Invariant [first, left) elements are < value
  iter right = last;  // Invariant [right, last) elements are >= value
  while(left < right)
  {
    ITER mid = left + (right-left)/2;
    if(less(*mid, value))
      left = mid+1;
    else
      right = mid;
  }
  return right != last && !less(value, *right);
}

template<class RANIT, class TYPE, class COMPARE>
bool bsc(RANIT first, RANIT last, TYPE value, COMPARE cmp)
{
  iter left = first;  // Invariant [first, left) elements are < value
  iter right = last;  // Invariant [right, last) elements are > value
  while(left < right)
  {
    ITER mid = left + (right-left)/2;
    int test = cmp(*mid, value);
    if(test < 0)
      left = mid+1;
    else if(test > 0)
      right = mid;
    else
      return true;
  }
  return false;
}

inline bool lessint(int a, int b){ return a < b; }
inline int compareint(int a, int b){ return a < b ? -1 : a > b; }

int main()
{
  vector<int> vec(1000000);
  clock_t t = clock();
  for(int i = 0; i < 10000000; ++i)
    bsl(vec.begin(), vec.end(), -7, lessint);
  cout << "less: " << clock() - t << endl;

  t = clock();
  for(int j = 0; j < 10000000; ++j)
    bsc(vec.begin(), vec.end(), -7, compareint);
  cout << "comp: " << clock() - t << endl;

  return 0;
}

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Max T. Woodbury wrote:
> Thomas Mang wrote:
..
>> Maybe I am missing something, but the new way, you make - inside
comp
>> - only
>> one comparison.
>>
>> E.g. for ints:
>>
>> bool operator()(int a, int b)
>> { return a < b;}
>>
>> Whereas for the C-style - way, you'd need to make (potentially) a
second
>> comparison. That's an additional cost!
>
>
> a C style comparison is typically done with a subtraction:
>
> int cmpbyte( char a, char b) { return (int)a - b; }

That works correctly for types where the maximum difference fits in an
'int'. For other types (in particular, for 'int' itself), it can
overflow.

..
> On the hardware level most comparisons return a three, sometimes four
> value result (<, ==, >, and not comparable).  Those results are then
> converted into binary actions; you either change the instruction
pointer
> value or let it continue to the next sequential instruction.  Usually
> the comparison instruction takes more resources than the action
> instruction but the branch instruction may trash the contents of the
> prefetch pipeline.  However all this is minor compared to the cost of
> a real subroutine call.

Note that comparison functions are typically inline, except when
they're so somplex that the subroutine call overhead is minor.

> The STL style comparisons have the advantage of being analytically
> simpler and easier to document, but they are typically slower in
> execution because they have to be called twice.

One of the points that was made earlier in this thread is that most of
the relevant algorithms don't require many equality comparisons;
inequality comparisons are all that's needed, and an algorith that uses
a C-style comparison function to perform those inequality comparisons
can easily be less efficient.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Dave Harris wrote:

> max.teneyck.woodbury@verizon.net ("Max T. Woodbury") wrote (abridged):
>
>>a C style comparison is typically done with a subtraction:
>>
>>int cmpbyte( char a, char b) { return (int)a - b; }
>
> That's how I think of it, but as an actual implementation it often doesn't
> work because of overflow. If the arguments are ints or doubles, for
> example, the difference between them may be too big to fit in an int.

Actually it should be (int)b - a.  You should also notice the
cast to a wider type would avoid the overflow issue unless char
and int are the same size.  For wider types you need to encode
the result to avoid overflow, but even that overhead is going to
be swamped by the cost of doing the function call.  The fact that
the STL allows inlining of the comparison is in fact one of its
more important attributes.

However this does not answer the original question.  The STL
comparison specification is based on extensibility and proof
of correctness criteria rather than on performance criteria.
The older C comparison specification put more emphasis on
performance.  Which is 'better' depends on how you define
'better'.

>>The STL style comparisons have the advantage of being analytically
>>simpler and easier to document, but they are typically slower in
>>execution because they have to be called twice.
>
> "Typically"? For at least some important algorithms, they only have to be
> called once.
>
> For example, you are apparently expecting lower_bound to be written like:
>
>     T *lower_bound( T *first, T *last, T target ) {
>         while (first < last) {
>             T *mid = first + (last - first) / 2;
>             if (*mid < target)
>                 first = mid + 1;
>             else if (*mid == target)
>                 return mid;
>             else
>                 last = mid;
>         }
>         return last;
>     }
>
> but it can also be written like:
>
>     T *lower_bound( T *first, T *last, T target ) {
>         while (first < last) {
>             T *mid = first + (last - first)/2;
>             if (*mid < target)
>                 first = mid + 1;
>             else
>                 last = mid;
>         }
>         return last;
>     }
>
> The second version will make more iterations of the loop, but the work
> done in each iteration is smaller. If you think about the shape of a
> binary tree, half the items are leaf nodes so the equality test usually
> fails and usually saves very little even when it succeeds. And if the
> target is absent it will always fail. That equality test is a very dubious
> attempt at optimisation.

OK.  'Typically' was not the best way to express what I meant.

You have chosen an example where an equality condition actually
complicates the algorithm.  In other algorithms where equality is
a requirement, not a complication, the analysis would yield different
results.

As I said above, the criteria used to design comparisons in
the STL are different from those used in the original C library.
Your example illustrates that clearly.  However it is only part
of the answer to the original question.  A proper answer, if there
is ever a proper answer to any 'why' question, requires a larger
perspective and a different point of view.

max@mtew.isa-geek.net

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Max T. Woodbury wrote:
>
> A well optimized C style comparison function would typically do one
> comparison and then a sequence of two conditional branches to sort
> out the three cases.  In at least some cases no action is needed
> because the result of a simple subtraction of two values has the
> correct form.
>
> The STL style comparisons have the advantage of being analytically
> simpler and easier to document, but they are typically slower in
> execution because they have to be called twice.  That makes them
> cheaper from the implementer's manager's point of view, but more
> expensive from the user's point of view.  The manager usually wins.
>

Having spent a reasonable amount of time with the STL algorithms, I
would say that in most of the algorithms, having a 3-way comparison
function wouldn't help in most cases. Also you are assuming that the STL
algorithms are only used on built-in types, remember lots of people use
STL algorithms on vectors of vectors, and such structures.

It comes down to the question of could you implement a more efficent
sort / lexicographic compare / etc. if you had a 3-way comparison
function. I reckon it would actually be slower, although I'd be more
than happy to be proved wrong.

Chris

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Max T. Woodbury wrote:
.
> OK.  'Typically' was not the best way to express what I meant.
>
> You have chosen an example where an equality condition actually
> complicates the algorithm.  In other algorithms where equality is
> a requirement, not a complication, the analysis would yield different
> results.

Would you care to identify an algorithm where, when the size of the
ranges operated on is large, the implementation would be significantly
speeded up by use of three-way comparisons rather than two-way, even if
the three-way one is 50% more expensive.? Make sure that you're
comparing with an algorithm actually optimized for use of the two-way
comparison.

I'm not saying there aren't any; but I suspect there are fewer of them
than you think.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

max.teneyck.woodbury@verizon.net ("Max T. Woodbury") wrote (abridged):
> >>a C style comparison is typically done with a subtraction:
> >>
> >>int cmpbyte( char a, char b) { return (int)a - b; }
> >
> > That's how I think of it, ...
>
> Actually it should be (int)b - a.

Not if you want to sort in ascending order. strcmp( a, b ) returns < 0 if
a should come before b, and similarly for the other cmp() functions. These
expressions:
    cmp( a, b ) < 0
    a - b < 0
    a < b

should all yield the same result, ignoring overflow. Notice that a and b
always appear in the same order, and the "<" always points the same way.


> > ... but as an actual implementation it often doesn't work because
> > of overflow. If the arguments are ints or doubles, for example,
> > the difference between them may be too big to fit in an int.
>
> You should also notice the cast to a wider type would avoid the
> overflow issue unless char and int are the same size.

I did notice that, but I also noticed you said "typically", so I thought
you were suggesting it worked more generally than that. We agree it
doesn't work for int, and to my mind that makes it rather a special case.


> For wider types you need to encode the result to avoid overflow,
> but even that overhead is going to be swamped by the cost of doing
> the function call.  The fact that the STL allows inlining of
> the comparison is in fact one of its more important attributes.

Indeed. And it means that the most efficient design for C may not be most
efficient for C++.


> The STL comparison specification is based on extensibility and proof
> of correctness criteria rather than on performance criteria.

I'm not convinced. I don't see why using less() is more extensible than
using cmp(). Nor do I see much difference in the proof of correctness,
whether we write "less(a,b)" or "cmp(a,b)<0". My impression is that
Stepanov was driven by a desire for performance (albeit a fairly academic
notion of it). That's why there is so much emphasis on compile-time
dispatch. I believe less() was chosen because it is faster, because it
does the minimum work needed by the algorithm.


> You have chosen an example where an equality condition actually
> complicates the algorithm. In other algorithms where equality is
> a requirement, not a complication, the analysis would yield
> different results.

Which algorithms?

Generally std algorithms which need equality use equality - for example,
std::find. Can you give some examples of std algorithms which are
significantly slower because they synthesise equality from a 3-way cmp() ?

(By "significantly", I mean they do it in their inner loop.)

-- Dave Harris, Nottingham, UK

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Dave Harris wrote:

> max.teneyck.woodbury@verizon.net ("Max T. Woodbury") wrote (abridged):
>
>>>>a C style comparison is typically done with a subtraction:
>>>>
>>>>int cmpbyte( char a, char b) { return (int)a - b; }
>>>
>>>That's how I think of it, ...
>>
>>Actually it should be (int)b - a.
>
>
> Not if you want to sort in ascending order. strcmp( a, b ) returns < 0 if
> a should come before b, and similarly for the other cmp() functions. These
> expressions:
>     cmp( a, b ) < 0
>     a - b < 0
>     a < b
>
> should all yield the same result, ignoring overflow. Notice that a and b
> always appear in the same order, and the "<" always points the same way.

You're right. That's how I've been thinking of it, and I've never been
confused.

>>The STL comparison specification is based on extensibility and proof
>>of correctness criteria rather than on performance criteria.
>
> I'm not convinced. I don't see why using less() is more extensible than
> using cmp(). Nor do I see much difference in the proof of correctness,
> whether we write "less(a,b)" or "cmp(a,b)<0".

My initial claim was that less() is actually less extensible than cmp().
Combining comparisons of several members into one comparison in a
lexicographic order is a disaster, as I have shown previously. Yes,
mainly because you need the equality to go to the next member.

>>You have chosen an example where an equality condition actually
>>complicates the algorithm. In other algorithms where equality is
>>a requirement, not a complication, the analysis would yield
>>different results.
>
> Which algorithms?
>
> Generally std algorithms which need equality use equality - for example,
> std::find. Can you give some examples of std algorithms which are
> significantly slower because they synthesise equality from a 3-way cmp() ?

Unfortunately, the 2-way comparison applies to the algorithms described
in 25.3 "Sorting and related operations", and std::find is not one of
them. Std::find takes a predicate that returns true for equality, and
false for inequality.

A better example is std::binary_search, which IS one of them. "Returns:
true if there is an iterator i in the range [first, last) that satisfies
the corresponding conditions: !(*i < value) && !(value < *i) or comp(*i,
value) == false && comp(value, *i) == false." Here you can see that the
comparator is called twice to test for equality. I can certainly imagine
that a 3-way comparison would have made it much more efficient.

--
Seungbeom Kim

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

musiphil@bawi.org (Seungbeom Kim) wrote (abridged):
> My initial claim was that less() is actually less extensible than
> cmp(). Combining comparisons of several members into one comparison in
> a lexicographic order is a disaster, as I have shown previously. Yes,
> mainly because you need the equality to go to the next member.

Well, you claimed it. You need half as many calls to cmp() than to less(),
but if each call does twice as much work, the net benefit isn't clear.

Equals() is also simpler than cmp() (sometimes much simpler). So its worth
implementing equals() directly if you want maximum efficiency. And then
you can implement less(M,M) in terms of equals(A,A) and less(A,A). I have
generally found that doing everything in terms of cmp() means doing more
work than necessary.

Still, if it turns out that you can implement less(M,M) more efficiently
in terms of cmp(A,A) than equals(A,A) and less(A,A) then go ahead and do
that.


> > Can you give some examples of std algorithms which are
> > significantly slower because they synthesise equality from
> > a 3-way cmp() ?
>
> [...]
> A better example is std::binary_search

But std::binary_search can be defined in terms of std::lower_bound:

    bool binary_search( const T *first, const T *last, const T &target ) {
        const T *i = lower_bound( first, last, target );
        return i != last && !(target < *i);
    }

And I've already shown that std::lower_bound is not, in general, slower
for using less() rather than cmp(), and it may be faster because its inner
loop is simpler. So binary_search doesn't suffer either. It just adds an
extra test at the end, which is O(1), so it too may be faster.

I think you need to do some benchmarks against a good implementation of
the std library.

-- Dave Harris, Nottingham, UK

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Dave Harris wrote:
> max.teneyck.woodbury@verizon.net ("Max T. Woodbury") wrote (abridged):
>
>>>>a C style comparison is typically done with a subtraction:
>>>>
>>>>int cmpbyte( char a, char b) { return (int)a - b; }
>>>
>>>That's how I think of it, ...
>>
>>Actually it should be (int)b - a.
>
>
> Not if you want to sort in ascending order. strcmp( a, b ) returns < 0 if
> a should come before b, and similarly for the other cmp() functions. These
> expressions:
>     cmp( a, b ) < 0
>     a - b < 0
>     a < b
>
> should all yield the same result, ignoring overflow. Notice that a and b
> always appear in the same order, and the "<" always points the same way.

You're right.  I need more sleep...

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

The comparison function used by bsearch and qsort from C is supposed to
return <0, =0, >0 when a<b, a=b, a>b respectively when called with (a,b).

On the other hand, the Compare object used by C++ standard library (25.3)
is supposed to return bool, indicating only whether a<b. This seems to be
worse than the old C way because we need two calls to the function to
test for equality: !comp(a, b) && !comp(b, a), which takes about twice
the time needed with the old 3-way comparison semantics.

The 2-way comparison also makes it difficult to combine multiple
comparisons into a single one; e.g.

struct A;
struct B;
struct C;
struct M { A a; B b; C c; };

// C way
int M_compare(const M& x, const M& y)
{
     int c;
     if ((c = A_compare(x.a, y.a)) != 0) return c;
     if ((c = B_compare(x.b, y.b)) != 0) return c;
          c = C_compare(x.c, y.c);       return c;
}

// C++ way
bool M_compare(const M& x, const M& y)
{
     if (A_compare(x.a, y.a)) return true;
     if (A_compare(y.a, x.a)) return false;
     if (B_compare(x.b, y.b)) return true;
     if (B_compare(y.b, x.b)) return false;
     return C_compare(x.a, y.a);
};

(And imagine what we would happen if we want to compare two M objects for
equality.. how many calls to A_compare?)

Why was this new-style 2-way comparison adopted instead of the good old
C-style 3-way comparison?

--
Seungbeom Kim

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Seungbeom Kim wrote:
> The comparison function used by bsearch and qsort from C is supposed to
> return <0, =0, >0 when a<b, a=b, a>b respectively when called with (a,b).
>
> On the other hand, the Compare object used by C++ standard library (25.3)
> is supposed to return bool, indicating only whether a<b. This seems to be
> worse than the old C way because we need two calls to the function to
> test for equality: !comp(a, b) && !comp(b, a), which takes about twice
> the time needed with the old 3-way comparison semantics.

I *think* (but am not sure) that binary searching with an order
predicate only requires 1 more comparison than binary searching with a
3-way comparator, on average.  Since 3-way comparisons tend to take
marginally longer, order predicates may actually result in faster
searching.  But do try comparing actual speeds, if you're concerned
about this.

As evidence, see the implementations of lower_bound, upper_bound and
binary_search for random-access iterators in
<http://groups.google.co.uk/groups?selm=slrnc27eek.1g0.do-not-spam-benh%40tin.bwsint.com>
(or <http://tinyurl.com/6gxve>).  (These are not quite correct; read
the follow-up too.)

> The 2-way comparison also makes it difficult to combine multiple
> comparisons into a single one; e.g.
>
> struct A;
> struct B;
> struct C;
> struct M { A a; B b; C c; };
>
> // C way
> int M_compare(const M& x, const M& y)
> {
>      int c;
>      if ((c = A_compare(x.a, y.a)) != 0) return c;
>      if ((c = B_compare(x.b, y.b)) != 0) return c;
>           c = C_compare(x.c, y.c);       return c;
> }
>
> // C++ way
> bool M_compare(const M& x, const M& y)
> {
>      if (A_compare(x.a, y.a)) return true;
>      if (A_compare(y.a, x.a)) return false;
>      if (B_compare(x.b, y.b)) return true;
>      if (B_compare(y.b, x.b)) return false;
>      return C_compare(x.a, y.a);
> };

The C++ way is to overload equality and inequality operators, so you
can just write:

    return x.a < y.a || (x.a == y.a
       && (x.b < y.b || (x.b == y.b
       &&  x.c < y.c)));

> (And imagine what we would happen if we want to compare two M objects for
> equality.. how many calls to A_compare?)

Yes, I can see how this could get inefficient for complex types
(though probably not for std::complex types!).

> Why was this new-style 2-way comparison adopted instead of the good old
> C-style 3-way comparison?

I couldn't say, but one point in their favour is that the mathematics
of ordering relations are better understood.

--
Ben Hutchings
It is easier to write an incorrect program than to understand a correct one.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Seungbeom Kim wrote:
> On the other hand, the Compare object used by C++ standard library (25.3)
> is supposed to return bool, indicating only whether a<b. This seems to be
> worse than the old C way because we need two calls to the function to
> test for equality: !comp(a, b) && !comp(b, a), which takes about twice
> the time needed with the old 3-way comparison semantics.

Have you measured the effect? I can imagine that there are types which are
faster with 2-way comparison and ones which are faster with 3-way
comparison. That is, I doubt that it is a universal trait that 3-way
comparison is always faster.

> The 2-way comparison also makes it difficult to combine multiple
> comparisons into a single one;

On the other hand, it is more difficult to take advantage of the 3-way
result (unless you call the comparison function twice). I don't buy
any argument in this direction either.

> (And imagine what we would happen if we want to compare two M objects for
> equality.. how many calls to A_compare?)

Two. How many would you imagine?

> Why was this new-style 2-way comparison adopted instead of the good old
> C-style 3-way comparison?

Personally, I think the 2-way comparison is much clearer: I always need
to look up what 1 and -1 mean if I call comp(a, b): is a smaller or b
if the result is 1? (I think b because you might implement the comparator
to return "a - b" but this actually shows that you need to compare the
result against something anyway).
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Seungbeom Kim" <musiphil@bawi.org> schrieb im Newsbeitrag
news:cvdf6s$och$1@news.Stanford.EDU...
> The comparison function used by bsearch and qsort from C is supposed to
> return <0, =0, >0 when a<b, a=b, a>b respectively when called with (a,b).
>
> On the other hand, the Compare object used by C++ standard library (25.3)
> is supposed to return bool, indicating only whether a<b. This seems to be
> worse than the old C way because we need two calls to the function to
> test for equality: !comp(a, b) && !comp(b, a), which takes about twice
> the time needed with the old 3-way comparison semantics.


Maybe I am missing something, but the new way, you make - inside comp - only
one comparison.

E.g. for ints:

bool operator()(int a, int b)
{ return a < b;}


Whereas for the C-style - way, you'd need to make (potentially) a second
comparison. That's an additional cost!
But for ordererd containers, this second comparison is usually useless,
since operator<() == true already suffices to travel forward one node.

I can easily imagine the C-style way costing more than the C++-style under
certain - probably quite common - circumstances.


Thomas


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On 2005-02-23 02:58, Dietmar Kuehl wrote:
:
> Personally, I think the 2-way comparison is much clearer: I always need
> to look up what 1 and -1 mean if I call comp(a, b): is a smaller or b
> if the result is 1?

I find it quite intuitive: a is </=/> b iff comp(a, b) is </=/> zero,
respectively.

-- Niklas Matthies

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Thomas Mang wrote:
> "Seungbeom Kim" <musiphil@bawi.org> schrieb im Newsbeitrag
> news:cvdf6s$och$1@news.Stanford.EDU...
>
>>The comparison function used by bsearch and qsort from C is supposed to
>>return <0, =0, >0 when a<b, a=b, a>b respectively when called with (a,b).
>>
>>On the other hand, the Compare object used by C++ standard library (25.3)
>>is supposed to return bool, indicating only whether a<b. This seems to be
>>worse than the old C way because we need two calls to the function to
>>test for equality: !comp(a, b) && !comp(b, a), which takes about twice
>>the time needed with the old 3-way comparison semantics.
>
> Maybe I am missing something, but the new way, you make - inside comp - only
> one comparison.
>
> E.g. for ints:
>
> bool operator()(int a, int b)
> { return a < b;}
>
> Whereas for the C-style - way, you'd need to make (potentially) a second
> comparison. That's an additional cost!

a C style comparison is typically done with a subtraction:

int cmpbyte( char a, char b) { return (int)a - b; }

[or is it (int)b - a?  Always build a unit tester to make sure you
meet your specification!]

> But for ordererd containers, this second comparison is usually useless,
> since operator<() == true already suffices to travel forward one node.
>
> I can easily imagine the C-style way costing more than the C++-style under
> certain - probably quite common - circumstances.

Your imagination has failed you...

On the hardware level most comparisons return a three, sometimes four
value result (<, ==, >, and not comparable).  Those results are then
converted into binary actions; you either change the instruction pointer
value or let it continue to the next sequential instruction.  Usually
the comparison instruction takes more resources than the action
instruction but the branch instruction may trash the contents of the
prefetch pipeline.  However all this is minor compared to the cost of
a real subroutine call.

A well optimized C style comparison function would typically do one
comparison and then a sequence of two conditional branches to sort
out the three cases.  In at least some cases no action is needed
because the result of a simple subtraction of two values has the
correct form.

The STL style comparisons have the advantage of being analytically
simpler and easier to document, but they are typically slower in
execution because they have to be called twice.  That makes them
cheaper from the implementer's manager's point of view, but more
expensive from the user's point of view.  The manager usually wins.

max@mtew.isa-geek.net

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Max T. Woodbury" <max.teneyck.woodbury@verizon.net> wrote:

>
> The STL style comparisons have the advantage of being analytically
> simpler and easier to document, but they are typically slower in
> execution because they have to be called twice.  That makes them
> cheaper from the implementer's manager's point of view, but more
> expensive from the user's point of view.  The manager usually wins.
  Typically slower?? I don't think so, possibly slower yes, but then
a fine tuned implimentation of a mathematical algorithm is often better
than a generic one, the question becomes is it SIGNIFIGANTLY better?

 Now a threw compare requires a function/functor inlined or not to
create the three way result and a compare against zero.  If you write
your three way compare and provide simple inline functions operator <(),
operator == () that do this compare to zero then what is the loss in the
algorithem assuming a complier will inline something as simple as a one
line compare to zero?

 My route is if a three way is easy or more efficient than a direct
two way compare is to provide both and be done with the problem:)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Max T. Woodbury wrote:

> a C style comparison is typically done with a subtraction:
>
> int cmpbyte( char a, char b) { return (int)a - b; }

Is it? Guess what this program prints:

#include <iostream>
#include <climits>

int main() {
     int a=INT_MAX, b=-INT_MAX;
     // if (a > b) ...
     if (a-b > 0) {
 std::cout << a << " > " << b << std::endl;
     } else {
 std::cout << a << " <= " << b << std::endl;
     }
     return 0;
}

Answer:

2147483647 <= -2147483647

Now what do you think would happen to code that relied on the sign of
that subtraction?

Hardware might indeed yield three-way flags, but most types are compound
objects, and the simpleminded tests don't work.

--
Ron House     house@usq.edu.au
               http://www.sci.usq.edu.au/staff/house

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

max.teneyck.woodbury@verizon.net ("Max T. Woodbury") wrote (abridged):
> a C style comparison is typically done with a subtraction:
>
> int cmpbyte( char a, char b) { return (int)a - b; }

That's how I think of it, but as an actual implementation it often doesn't
work because of overflow. If the arguments are ints or doubles, for
example, the difference between them may be too big to fit in an int.


> The STL style comparisons have the advantage of being analytically
> simpler and easier to document, but they are typically slower in
> execution because they have to be called twice.

"Typically"? For at least some important algorithms, they only have to be
called once.

For example, you are apparently expecting lower_bound to be written like:

    T *lower_bound( T *first, T *last, T target ) {
        while (first < last) {
            T *mid = first + (last - first) / 2;
            if (*mid < target)
                first = mid + 1;
            else if (*mid == target)
                return mid;
            else
                last = mid;
        }
        return last;
    }

but it can also be written like:

    T *lower_bound( T *first, T *last, T target ) {
        while (first < last) {
            T *mid = first + (last - first)/2;
            if (*mid < target)
                first = mid + 1;
            else
                last = mid;
        }
        return last;
    }

The second version will make more iterations of the loop, but the work
done in each iteration is smaller. If you think about the shape of a
binary tree, half the items are leaf nodes so the equality test usually
fails and usually saves very little even when it succeeds. And if the
target is absent it will always fail. That equality test is a very dubious
attempt at optimisation.

-- Dave Harris, Nottingham, UK

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Max T. Woodbury"" <max.teneyck.woodbury@verizon.net> schrieb im
Newsbeitrag news:_e3Ud.62381$wc.47045@trnddc07...
> Thomas Mang wrote:
> > "Seungbeom Kim" <musiphil@bawi.org> schrieb im Newsbeitrag
> > news:cvdf6s$och$1@news.Stanford.EDU...
> >
> >>The comparison function used by bsearch and qsort from C is supposed to
> >>return <0, =0, >0 when a<b, a=b, a>b respectively when called with
(a,b).
> >>
> >>On the other hand, the Compare object used by C++ standard library
(25.3)
> >>is supposed to return bool, indicating only whether a<b. This seems to
be
> >>worse than the old C way because we need two calls to the function to
> >>test for equality: !comp(a, b) && !comp(b, a), which takes about twice
> >>the time needed with the old 3-way comparison semantics.
> >
> > Maybe I am missing something, but the new way, you make - inside comp -
only
> > one comparison.
> >
> > E.g. for ints:
> >
> > bool operator()(int a, int b)
> > { return a < b;}
> >
> > Whereas for the C-style - way, you'd need to make (potentially) a second
> > comparison. That's an additional cost!
>
> a C style comparison is typically done with a subtraction:
>
> int cmpbyte( char a, char b) { return (int)a - b; }
>
> [or is it (int)b - a?  Always build a unit tester to make sure you
> meet your specification!]
>
> > But for ordererd containers, this second comparison is usually useless,
> > since operator<() == true already suffices to travel forward one node.
> >
> > I can easily imagine the C-style way costing more than the C++-style
under
> > certain - probably quite common - circumstances.
>
> Your imagination has failed you...
>
> On the hardware level most comparisons return a three, sometimes four
> value result (<, ==, >, and not comparable).  Those results are then
> converted into binary actions; you either change the instruction pointer
> value or let it continue to the next sequential instruction.  Usually
> the comparison instruction takes more resources than the action
> instruction but the branch instruction may trash the contents of the
> prefetch pipeline.  However all this is minor compared to the cost of
> a real subroutine call.


How do you want to access the hardware-level in portable C++?

The Standard Library could, of course, add new "predicates" that yield
either negative, zero, or positive values and specialize that for built-in
types that take advantage of the hardware level. For UDTs, once could then
call these specializations (if the subobjects are built-in). If not, one
needs to use plain ordinary < and ==. Looks expensive to me if the result of
operator< suffices to make a decision.


Thomas


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]