www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Comparison: when operator<() is better than opCmp()

reply Giuseppe Bilotta <giuseppe.bilotta gmail.com> writes:
Hello all,

I'm quite a newbie at D programming, although I have some
programming experience in languages such as C, C++, Ruby.

I've been initially attracted to D by its native support for the
'real' floating point type with the proper native support for nans
and infinities, and I've been thinking about doing some serious
scientific computing stuff in it.

As it happens, my university career has brought me to the field of
'reliable computing', and things such as interval analysis and
affine arithmetic. So I've decided to try my bones at programming
in D by implementing some reliable computing classes (intervals,
affine expressions, and other forms which are the fruit of my
research).

Now, while writing the initial structure of the interval class,
I've come across an interesting consideration: there are some
cases where having to implement comparison operators as the single
opCmp() method is (considerably) less efficient than having to do
it by having to implement the operators <(), <=() >(), >=() as
done in C++.

Let me explain. The class interval is basically a simple wrapper
for a pair of real numbers lo, hi such that lo <= hi; lo is the
lower bound of the interval, and hi is the upper bound.

Now, when comparing such an interval with, say, a real number, the
comparsions would be implemented in C++ as follows:

operator<(double val) { return hi < val ; }
operator<=(double val) { return hi <= val ; }
operator>(double val) { return lo > val ; }
operator>=(double val) { return lo >= val ; }

so that each comparison is actually very fast (a single
comparsion); we can inline it for maximum effect. By contrast, in
D we have

        real opCmp(in real val)
        {
                if (lo >= val)
                        return lo-val ;
                if (hi <= val)
                        return hi-val ;
                return real.nan ;
        }

whose result will be compared with 0 to determine the outcome.
This means that in the best case we have to do two comparisons and
a subtraction, and in the worst case three comparisons and a
subtraction. The subtractions can be eliminated by doing some
extra comparisons (i.e. checking for equality separately from
inequality in the two comparisons).

It is therefore quite obvious that the opCmp() way of doing things
is considerably more inefficient than the C++ way of overloading
each comparison separately: it involves less coding, but results
in slower code.

On the other hand, there are other cases in which opCmp() is more
efficient than implementing the comparison operators one by one.

So what I was wondering was if it was possible to have the
possibility to overload the single comparison operators in D,
while still keeping opCmp(). The way I see it, overloading would
work in a way similar to the way opAdd/opAdd_r work.

Let's say we have opGreater(), opLess(), opGreaterEqual(),
opLessEqual() in addition to opCmp(). When the expression a op b is
encountered, we check for the existence of a.opfunc(b), then of
b.opfunc_reverse(a), then for a.opCmp(b), and finally for
b.opCmp(a) (the result of which is negated before comparison with
0).

This way, the classes implementing opCmp() would still work as
they are, but efficient opfunc() implementations could be written
when necessary.

How does the idea sound?

-- 
Giuseppe "Oblomov" Bilotta
Sep 07 2007
next sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Giuseppe Bilotta wrote:

 Hello all,


Hi.  Excuse me a moment...


 [snip]
 
 How does the idea sound?


I like the idea conceptually, and there have been cases where I've
wished I could make an overload for the particular comparison as opposed
to all of them (especially in cases where one or more of the operators
simply doesn't make sense).

It would probably complicate the rules a bit; but then, currently
there's the overload of "==" using both opCmp and opEquals, so you've
definitely got precedence on your side.

As an aside, does that opCmp returning a real work?  Using a real to
return NaN for an invalid comparison is a nice idea; I might have to use
that.

In any case, glad to see you are otherwise enjoying yourself.  Look
forward to seeing you in #d :)

	-- Daniel
Sep 07 2007
parent Giuseppe Bilotta <giuseppe.bilotta gmail.com> writes:
On Saturday 8 September 2007 04:00, Daniel Keep wrote:


 As an aside, does that opCmp returning a real work?  Using a real to
 return NaN for an invalid comparison is a nice idea; I might have to use
 that.


Well, the unittests don't fail, so it seems to be working :)


 In any case, glad to see you are otherwise enjoying yourself.  Look
 forward to seeing you in #d :)


Actually, #D was the first place where I asked :) the only problem in
IRC being that my nick is tango_ so every time someone talks about the
D Tango I get a ping :P ;)

-- 
Giuseppe "Oblomov" Bilotta
Sep 07 2007
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Giuseppe,


 Hello all,


one nit:
 

 whose result will be compared with 0 to determine the outcome.


IIRC on most systems you can get "cmp to 0" with little more than a jump 
so that one is a freebe.
Sep 07 2007
parent Giuseppe Bilotta <giuseppe.bilotta gmail.com> writes:
On Saturday 8 September 2007 08:19, BCS wrote:


 Reply to Giuseppe,

 whose result will be compared with 0 to determine the outcome.


 
 IIRC on most systems you can get "cmp to 0" with little more than a jump 
 so that one is a freebe.


That's true (assuming it holds for reals (potentially NaNs) too), but
this doesn't really reduce the disadvantage by that much.

-- 
Giuseppe "Oblomov" Bilotta
Sep 07 2007
prev sibling next sibling parent reply OF <nospam nospammington.com> writes:
Giuseppe Bilotta Wrote:


 Hello all,
 [...]
 
 How does the idea sound?
 
 -- 
 Giuseppe "Oblomov" Bilotta


It's sound like it's not worth it. It might be, but you need a better example
to show it. The use of operator overloading in your example isn't very solid.

There's no naturally defined order. This easily makes operator overloading of
compare operators more confusing than helpful. You need to read the documents
or code to fully understand a <= b, and that !(a > b) doesn't equal a <= b even
with correct input.

I'd recommend functions like aboveRange, inRange and belowRange or something
similar for this.
Sep 08 2007
parent reply Giuseppe Bilotta <giuseppe.bilotta gmail.com> writes:
On Saturday 8 September 2007 14:13, OF wrote:


 It's sound like it's not worth it. It might be, but you need a
 better example to show it. The use of operator overloading in
 your example isn't very solid.
 
 There's no naturally defined order. This easily makes operator
 overloading of compare operators more confusing than helpful.
 You need to read the documents or code to fully understand a <=
 b, and that !(a > b) doesn't equal a <= b even with correct
 input.
 
 I'd recommend functions like aboveRange, inRange and belowRange
 or something similar for this.


Sorry, but there *is* a naturally defined ordering of intervals,
although it's (obviously) not a total ordering, in the sense there
may be intervals which are distinct and for which neither i1 < i2
nor i2 < i1 is valid.

Observe that this is no different from the fact that not all reals
are comparable either, if any of them is a real.nan --does this
mean we should use a syntax different from a < b for reals? I
don't think so.

The fact that it's not a total ordering is in no way disturbing or
confusing; on the contrary, it's a pretty standard notion across
pure and applied mathematics that not all orderings are total, and
in particular for interval analysis this definition of < & friends
is pretty standard and universally acknowledged (see e.g. page 6
of the 'red bible' (Interval methods for systems fo equations, by
Arnold Neumaier)).

The package I'm creating is aimed at numerical analysis, and its
target is people which have knowledge in the field, and would
therefore not be surprised by the fact that !(i1 < i2) does not
imply (i2 <= i1). I don't really see why I should cripple the
syntax when the common syntax is perfectly legit.

-- 
Giuseppe "Oblomov" Bilotta
Sep 08 2007
parent OF <nospam nospammington.com> writes:
Giuseppe Bilotta Wrote:


[...]
 Observe that this is no different from the fact that not all reals
 are comparable either, if any of them is a real.nan --does this
 mean we should use a syntax different from a < b for reals? I
 don't think so.
[...]


I consider NaN incorrect input, and that that's why it sets an exception. And
there is different syntax available in D, if one doesn't want exceptions to be
set.

Your other points are good. From my programming point of view I'd still
slightly dislike it, but if your target users wouldn't think it confusing in
any way, then I accept your example.
Sep 08 2007
prev sibling next sibling parent reply Jay Norwood <jayn io.com> writes:
Giuseppe Bilotta Wrote:


 Hello all,
 
 I'm quite a newbie at D programming, although I have some
 programming experience in languages such as C, C++, Ruby.
 
 I've been initially attracted to D by its native support for the
 'real' floating point type with the proper native support for nans
 and infinities, and I've been thinking about doing some serious
 scientific computing stuff in it.
 
 As it happens, my university career has brought me to the field of
 'reliable computing', and things such as interval analysis and
 affine arithmetic. So I've decided to try my bones at programming
 in D by implementing some reliable computing classes (intervals,
 affine expressions, and other forms which are the fruit of my
 research).


I ran across what seems to be a very clearly written C++ arbitrary precision
package at the following link.   It includes integer, float, complex precision
and interval precision.  It might make a nice extension to the current D
built-in capabilities.  I'm attempting a port of this as my first use of D.  

http://www.hvks.com/Numerical/arbitrary_precision.htm


One additional thing I'd be interested in seeing is support for fixed point
arithmetic with N bit, since the dsp applications which I simulate are done on
fixed point processors.  It would be nice to have a general purpose evaluator
that would handle the dsp fixed point expressions accurately, with hooks for
handling overflow and rounding modes.
Sep 10 2007
parent Giuseppe Bilotta <giuseppe.bilotta gmail.com> writes:
On Monday 10 September 2007 13:30, Jay Norwood wrote:


 One additional thing I'd be interested in seeing is support for
 fixed point arithmetic with N bit, since the dsp applications
 which I simulate are done on fixed point processors.  It would
 be nice to have a general purpose evaluator that would handle
 the dsp fixed point expressions accurately, with hooks for
 handling overflow and rounding modes.


There are some excellent fixed-point math algorithms in Donald E.
Knuth's "MetaFont" program. I'm sure they can be readily ported to
D, even though some of the tricks to prevent overflows are based
on the specifics of the MetaFont programming language.

-- 
Giuseppe "Oblomov" Bilotta
Sep 10 2007
prev sibling parent Don Clugston <dac nospam.com.au> writes:
Giuseppe Bilotta wrote:

 Hello all,
 
 I'm quite a newbie at D programming, although I have some
 programming experience in languages such as C, C++, Ruby.
 
 I've been initially attracted to D by its native support for the
 'real' floating point type with the proper native support for nans
 and infinities, and I've been thinking about doing some serious
 scientific computing stuff in it.


My experience was exactly the same. Welcome to D!


 So what I was wondering was if it was possible to have the
 possibility to overload the single comparison operators in D,
 while still keeping opCmp(). The way I see it, overloading would
 work in a way similar to the way opAdd/opAdd_r work.


I'd have another use for the same thing: expression templates don't work with 
opCmp. Expression templates work by encoding information in the return type. 
This is really easy in D, but unfortunately opCmp() must return an int, so you 
can't encode any information in the return type (same thing applies to ==). If 
the simple operators were available, you could do it. .
OTOH, expression templates could well be a technological dead-end.

I also note that there is no way to overload the NCEG operators. a!<>b is not 
possible for user-defined types.
Sep 19 2007