Efficient integer compare function

Question

The compare function is a function that takes two arguments a and b and returns an integer describing their order. If a is smaller than b, the result is some negative integer. If a is bigger than b, the result is some positive integer. Otherwise, a and b are equal, and the result is zero.

This function is often used to parameterize sorting and searching algorithms from standard libraries.

Implementing the compare function for characters is quite easy; you simply subtract the arguments:

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

This works because the difference between two characters is generally assumed to fit into an integer. (Note that this assumption does not hold for systems where sizeof(char) == sizeof(int).)

This trick cannot work to compare integers, because the difference between two integers generally does not fit into an integer. For example, INT_MAX - (-1) = INT_MIN suggests that INT_MAX is smaller than -1 (technically, the overflow leads to undefined behavior, but let's assume modulo arithmetic).

So how can we implement the compare function efficiently for integers? Here is my first attempt:

int compare_int(int a, int b) {     int temp;     int result;     __asm__ __volatile__ (         "cmp %3, %2 \n\t"         "mov $0, %1 \n\t"          "mov $1, %0 \n\t"         "cmovg %0, %1 \n\t"          "mov $-1, %0 \n\t"         "cmovl %0, %1 \n\t"     : "=r"(temp), "=r"(result)     : "r"(a), "r"(b)     : "cc");     return result; } 

Can it be done in less than 6 instructions? Is there a less straightforward way that is more efficient?

Answer 1

This one has no branches, and doesn't suffer from overflow or underflow:

return (a > b) - (a < b); 

With gcc -O2 -S, this compiles down to the following six instructions:

xorl    %eax, %eax cmpl    %esi, %edi setl    %dl setg    %al movzbl  %dl, %edx subl    %edx, %eax 

Here's some code to benchmark various compare implementations:

#include <stdio.h> #include <stdlib.h>  #define COUNT 1024 #define LOOPS 500 #define COMPARE compare2 #define USE_RAND 1  int arr[COUNT];  int compare1 (int a, int b) {     if (a < b) return -1;     if (a > b) return 1;     return 0; }  int compare2 (int a, int b) {     return (a > b) - (a < b); }  int compare3 (int a, int b) {     return (a < b) ? -1 : (a > b); }  int compare4 (int a, int b) {     __asm__ __volatile__ (         "sub %1, %0 \n\t"         "jno 1f \n\t"         "cmc \n\t"         "rcr %0 \n\t"         "1: "     : "+r"(a)     : "r"(b)     : "cc");     return a; }  int main () {     for (int i = 0; i < COUNT; i++) { #if USE_RAND         arr[i] = rand(); #else         for (int b = 0; b < sizeof(arr[i]); b++) {             *((unsigned char *)&arr[i] + b) = rand();         } #endif     }      int sum = 0;      for (int l = 0; l < LOOPS; l++) {         for (int i = 0; i < COUNT; i++) {             for (int j = 0; j < COUNT; j++) {                 sum += COMPARE(arr[i], arr[j]);             }         }     }      printf("%d=0\n", sum);      return 0; } 

The results on my 64-bit system, compiled with gcc -std=c99 -O2, for positive integers (USE_RAND=1):

compare1: 0m1.118s compare2: 0m0.756s compare3: 0m1.101s compare4: 0m0.561s 

Out of C-only solutions, the one I suggested was the fastest. user315052's solution was slower despite compiling to only 5 instructions. The slowdown is likely because, despite having one less instruction, there is a conditional instruction (cmovge).

Overall, FredOverflow's 4-instruction assembly implementation was the fastest when used with positive integers. However, this code only benchmarked the integer range RAND_MAX, so the 4-instuction test is biased, because it handles overflows separately, and these don't occur in the test; the speed may be due to successful branch prediction.

With a full range of integers (USE_RAND=0), the 4-instruction solution is in fact very slow (others are the same):

compare4: 0m1.897s