implementing "complete" comparison 
Author Message
 implementing "complete" comparison

Frequently one runs into situations where a "complete"
comparison, is needed, that is,

  a TEST b

requires different actions for <,==, and >.  As far
as I know this can be coded in C only with two separate
comparison operations, as in:

  if      (a < b){   /* less than code */    }
  else if (a == b){  /* equals code */       }
  else {            /* greater than code */ }
  }

Since this comes up so often I've always found it odd that
no processors (that I know of) have a machine code
instruction to handle the full comparison explicitly.  That is,
while the above would reduce to:

  blt LTDest
  beq EQDest

there is no:

  bfull EQDest GTDest  #branch == to EQDEST, > to GTDEST

Many of you may be asking "why bother"?  Well, consider what
happens if this sort of comparison is nested several layers deep.
Assume each outcome of the comparison is equally likely then
each level requires 1.5 comparisons, on average for the current
"two test" method, but only 1 comparison (ever) for the "full compare"
operation. Bury this in a large fast loop and the speed difference
should be significant.   For optimization purposes it would probably
also be helpful to know that the speed through the full compare
nested operations is constant.

Assuming for the moment that such an instruction ever
exists on some platform would there be any way in C to
instruct the compiler to take advantage of it?  Inline
assembler and "pray that the optimizer recognizes the
structure" don't count.  All the C comparisons that I know
of except "switch" choose between only two blocks of code,
and switch can't be used here because it requires fixed
values to select each block of code, other than the
default block.

Perhaps this is a "chicken and the egg" situation.  The
processors don't have it because the languages don't
require it, and the languages don't require it because
the processors don't have it!

Thanks,

David Mathog

Manager, Sequence Analysis Facility, Biology Division, Caltech



Sat, 27 Aug 2005 01:10:09 GMT  
 implementing "complete" comparison


Quote:
> Frequently one runs into situations where a "complete" comparison, is
> needed, that is,

>   a TEST b
> requires different actions for <,==, and >.  As far as I know this can
> be coded in C only with two separate comparison operations, as in:

>   if      (a < b){   /* less than code */    } else if (a == b){  /*
>   equals code */       } else {            /* greater than code */ } }

Which is perfectly readable, standard C. And is ontopic for this
newsgroup.

Quote:
> Since this comes up so often I've always found it odd that no processors
> (that I know of) have a machine code instruction to handle the full
> comparison explicitly.  That is, while the above would reduce to:

None of the above is ontopic here. Precious little of the below is,
either.

Quote:
>   bfull EQDest GTDest  #branch == to EQDEST, > to GTDEST

fortran had a computed GOTO structure that had a syntax similar to that,
IIRC. But that is completely off-topic here.

I've snipped the rest because here we discuss the standard C programming
language, not proposed modifications to the standard or proposed assembly
languages. Learn this and you will do well here.

(Just out of curiosity, why did you post this here instead of, say,
comp.lang.ada? What makes you think C programmers would be any more
receptive to your ideas than anyone else?)

--
Microsoft made Windows,
 A crufty hack of DOS,
And everywhere that OS went
 It was a total loss.



Sat, 27 Aug 2005 01:26:52 GMT  
 implementing "complete" comparison

Quote:


> > Frequently one runs into situations where a "complete"
> > comparison, is needed, that is,

> >   a TEST b
> > requires different actions for <,==, and >.  As far as I know
> > this can be coded in C only with two separate comparison
> > operations, as in:

> >  if        (a < b)  {  /* less than code */
> >  } else if (a == b) {  /* equals code */  
> >  } else {              /* greater than code */
> >  }

> Which is perfectly readable, standard C. And is ontopic for
> this newsgroup.

> > Since this comes up so often I've always found it odd that no
> > processors (that I know of) have a machine code instruction to
> > handle the full comparison explicitly.  That is, while the above
> > would reduce to:  ... snip ...

And the code generator is perfectly free to perform such an
optimization.  The machine almost certainly has a comparison
instruction that leave appropriate flags set.  How it is used is
off-topic here.

--

   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!



Sat, 27 Aug 2005 02:06:51 GMT  
 implementing "complete" comparison
On Mon, 10 Mar 2003 10:26:52 -0700

Quote:

> (Just out of curiosity, why did you post this here instead of, say,
> comp.lang.ada? What makes you think C programmers would be any more
> receptive to your ideas than anyone else?)

Because an Ada programmer was unlikely to be able to
tell me if there was an (obscure) "complete" comparison
syntax already in C.  It's not completely irrational
that such a syntax might exist in C since strcmp(), for
instance, returns an integer value which is the
state of exactly this type of "complete" comparison.

For all I know C99 might have added something like this:

  (void) fprintf(stdout,"%s\n",(a-b ?? "A<B" : "A==B" : "A>B"));

as a functional equivalent to this:

  (void) fprintf(stdout,"%s\n",(a<b  ? "A<B" : (a==b ? "A==B" : "A>B") ));

Regards,

David Mathog

Manager, Sequence Analysis Facility, Biology Division, Caltech



Sat, 27 Aug 2005 02:09:56 GMT  
 implementing "complete" comparison

Quote:

> Frequently one runs into situations where a "complete"
> comparison, is needed, that is,

>  a TEST b

> requires different actions for <,==, and >.  As far
> as I know this can be coded in C only with two separate
> comparison operations, as in:

>  if      (a < b){   /* less than code */    }
>  else if (a == b){  /* equals code */       }
>  else {            /* greater than code */ }
>  }

If you want to use a switch, you can:

switch ((a > b) - (a < b)) {
    case 1:
        /* a > b */
        break;
    case 0:
        /* a == b */
        break;
    case -1:
        /* a < b */

Quote:
}

I think the optimiser has more chance of spotting the first one though
(by the way, I think it has a reasonably good chance of doing so).

        - Kevin.



Sat, 27 Aug 2005 05:51:24 GMT  
 implementing "complete" comparison

Quote:

> Frequently one runs into situations where a "complete"
> comparison, is needed, that is,

>   a TEST b

> requires different actions for <,==, and >.  As far
> as I know this can be coded in C only with two separate
> comparison operations, as in:

>   if      (a < b){   /* less than code */    }
>   else if (a == b){  /* equals code */       }
>   else {            /* greater than code */ }
>   }
> Perhaps this is a "chicken and the egg" situation.  The
> processors don't have it because the languages don't
> require it, and the languages don't require it because
> the processors don't have it!

Another part of the reason, I think, is that the syntax required for
this statement would be even more of an exception than that for ?:. One
possible solution is

  compare (a; b) {
    less:     /*code*/
    equal:    /*code*/
    greather: /*code*/
  }

but I'm not sure I like the look of that. Possibly more generic, but
requiring even more extra syntax, is something like

  triple (a<=>b)
    nega {
    /*code*/
  } zero {
    /*code*/
  } posi {
    /*code*/
  }

The requirement for two different new constructs does mean that one
could also use these for

  triple (temperature)
    nega
      puts("It's freezing.");
    zero
      puts("We're at freezing point.");
    posi
      puts("It's thawing.");

and, less usefully,

  compare_two= x<=>y;
  /* Code that uses compare_two several times, for example for a couple
     of separate triple statements. */

However, most of this is, IMO, slightly clumsy, and easily implemented
using what C already has.

Richard



Sat, 27 Aug 2005 20:23:34 GMT  
 implementing "complete" comparison


Quote:
>"pray that the optimizer recognizes the
>structure" don't count

Why? If you insist that the language correspond to the machine
instructions and the compiler be able to generate optimal code without
recognizing structures which can be optimized, you're talking about
assembly language.

--
Al Balmer
Balmer Consulting



Sun, 28 Aug 2005 00:00:28 GMT  
 implementing "complete" comparison

Quote:


> > Frequently one runs into situations where a "complete" comparison, is
> > needed, that is,

> >   a TEST b
> > requires different actions for <,==, and >.  ...
> > Since this comes up so often I've always found it odd that no processors
> > (that I know of) have a machine code instruction to handle the full
> > comparison explicitly.  That is, while the above would reduce to:

Actually, *most* architectures, except some rigidly RISC ones,
have the *comparison* set flags (often called condition-code) to
all three states, and some (e.g. S/360) to a fourth for unordered
(e.g. floating-point NAN).  What is rare is to have (subsequent)
conditional branches that are other than two-way.

Quote:
> >   bfull EQDest GTDest  #branch == to EQDEST, > to GTDEST

> FORTRAN had a computed GOTO structure that had a syntax similar to that,
> IIRC. But that is completely off-topic here.

It's arithmetic IF that was almost like that, and still is, though
now deprecated.  Computed GOTO is more like switch,
and assigned GOTO was almost like GNU C label variable.

--
- David.Thompson 1 now at worldnet.att.net



Fri, 02 Sep 2005 15:04:48 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. FS: "Oracle8: The Complete Reference"

2. Comparisons with value returned from "signal".

3. implementing "ls eli*"

4. Implement a "var.Add(...)"?

5. implementing "trace" in c

6. Question on implementing "repeat...until keypress"?

7. Rules for "implements" in VB

8. "Implement Connection Point..." option is missing

9. implement a "kill" with signals

10. How to implement "autometic statement completion"?

11. Implementing "cp" shell command

12. How to implement "Multiway Serch Tree"?

 

 
Powered by phpBB® Forum Software