Comparison operator performance <= against !=

Question

Lets start out with stating code-readability beats micro-optimizations and we should rather leave that to the compiler. This was just a weird case where the specifics seemed interesting against general recommendation

So was messing about with a Prime number generator function, and came up with a weird behavior where "!=" which people recommend to be the most efficient actually the least efficient and "<=" which is the worst as the best option.

C#

private static void Main(string[] args) {
  long totalTicks = 0;
  for (int i = 0; i < 100; ++i) {
    var stopWatch = Stopwatch.StartNew();
    PrintPrimes(15000);
    totalTicks += stopWatch.ElapsedTicks;
  }
  Console.WriteLine("\n\n\n\nTick Average: {0}", totalTicks / 100);
  Console.Read();
}

private static void PrintPrimes(int numberRequired) {
  if (numberRequired < 1)
    return;
  Console.Write("{0}\t", 2);
  int primeTest = 3;
  /****** UPDATE NEXT TWO LINES TO TEST FOR != *****/
  int numPrimes = 2;  // set numPrimes = 1 for !=
  while (numPrimes <= numberRequired) {  // switch <= to !=
    if (IsPrime(primeTest)) {
      Console.Write("{0}\t", primeTest);
      ++numPrimes;
    }
    primeTest += 2;
  }
}

private static bool IsPrime(int test) {
  for (int i = 3; i * i <= test; i = 2 + i)
    if (test % i == 0)
      return false;
  return true;
}

Output:

<= 1319991
!= 1321251

Similarly In C++(On a different machine)

include <cstddef>
#include <limits>

int main() {
  for(size_t i(0) ; i <= 10000000000 ; ++i);
}

Output:

<=

real        0m16.538s
user        0m16.460s
sys        0m0.000s
~ [master] $ vim d.cc

!=

real        0m16.860s
user        0m16.780s
sys        0m0.000s

The loops run the same amount of times. Are there any optimizations for <= which does not apply for != or is it some weird cpu behavior?

Answer 1

It doesn't make sense that there would be a difference, assuming the result is the same number of iterations.

If we assume it's an x86 processor, != turns into jne (or je, depending on which side of the "it is" or "it is not" jumps [1]). A <= will do jle or jgt depending on which way the loop goes. Whilst the instructions are different, other processors have the same sort of instructions.

I suspect you have measurement errors. A difference of less than 0.2 seconds out of 16s is not a huge difference, and you may simply have had a few more network packets, hard disk interrupts or some background process running that time.

[1] A for loop that has a fixed set of iterations, for example, will typically just have a "if not true, jump to beginning of loop", and the same applies to while loops.

I just ran this on my machine:

bool IsPrime(int test) {
  for (int i = 3; i * i <= test; i = 2 + i)
    if (test % i == 0)
      return false;
  return true;
}

void PrintPrimes(int numberRequired) {
  if (numberRequired < 1)
    return;
  int primeTest = 3;
  /****** UPDATE NEXT TWO LINES TO TEST FOR != *****/
  int numPrimes = 2;  // set numPrimes = 1 for !=
  while (numPrimes != numberRequired) {  // switch <= to !=
    if (IsPrime(primeTest)) {
      ++numPrimes;
    }
    primeTest += 2;
  }
}

int  main() 
{
  long totalTicks = 0;
  for (int i = 0; i < 100; ++i) {
    PrintPrimes(15000);
  }
}

Compiled with g++ -O3 primes.cpp. The difference between using != and <= in the main loop is not noticeable. The fastest time for != is 3.326s, for <= 3.329, the slowest for != is 3.332 and with <= it is 3.335s. Having run many benchmarks on my machine before, I know that there is no significance in the millisecond digit, so I would say that it takes 3.33 seconds for both.

And just to confirm:

--- primesne.s  2013-04-30 23:52:10.840513380 +0100
+++ primesle.s  2013-04-30 23:52:35.457639603 +0100
@@ -46,7 +46,7 @@
 .L3:
    addl    $2, %esi
    cmpl    $15000, %edi
-   jne .L10
+   jle .L10
    subl    $1, %r9d
    jne .L2
    xorl    %eax, %eax

The entire difference between the "not equal" and "less or equal" is the jne vs jle instructions - this is the assembler output from g++ of the two variants of the code - and that is the ENTIRE output from diff.