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

- Giuseppe Bilotta <giuseppe.bilotta gmail.com> Sep 07 2007
- Daniel Keep <daniel.keep.lists gmail.com> Sep 07 2007
- Giuseppe Bilotta <giuseppe.bilotta gmail.com> Sep 07 2007
- BCS <ao pathlink.com> Sep 07 2007
- Giuseppe Bilotta <giuseppe.bilotta gmail.com> Sep 07 2007
- OF <nospam nospammington.com> Sep 08 2007
- Giuseppe Bilotta <giuseppe.bilotta gmail.com> Sep 08 2007
- OF <nospam nospammington.com> Sep 08 2007
- Jay Norwood <jayn io.com> Sep 10 2007
- Giuseppe Bilotta <giuseppe.bilotta gmail.com> Sep 10 2007
- Don Clugston <dac nospam.com.au> Sep 19 2007

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

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

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

Reply to Giuseppe,Hello all,

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

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

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

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

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

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

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

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