Creation of generic less than function in C

Question

I am looking to implement something similar to

int memcmp ( const void * ptr1, const void * ptr2, size_t num );

For comparison of numerical types such as floats, doubles and integers but with distinguishing between two case (1) < and (2) =,> rather than <between 3 cases (1)<, ==(2)==, and >(3)>. My aim is to reduce the number of the used instructions, assuming running on a standard laptop (x86 architecture).

Answer 1

The solution to the problem is likely just #define less(a,b,n) (memcmp(a,b,n) < 0).

There's a bunch of advantages with using memcmp since the compiler is likely to highly optimize the use of it. It may look at what you use as input and inline memcmp accordingly, giving the most efficient code.

For example memcmp has the requirement to cast each byte to unsigned char internally and work on misaligned data. But if you provide lets say two chunks of 8 byte aligned data on a x86_64, there's probably no reason for the machine code to chew through it byte by byte.

Here's an example where I hacked together a semi-naive version of a "less" function working similar to memcmp:

#include <string.h>
#include <stdio.h>

bool lesscmp (const void* obj1, const void* obj2, size_t size)
{
  const unsigned char* o1 = (const unsigned char*)obj1;
  const unsigned char* o2 = (const unsigned char*)obj2;

  for(size_t i=0; i<size; i++)
  {
    if(o1[i] != o2[i])
    {
      return o1[i] < o2[i];
    }
  }
  return 0;
}

int main (void)
{
  char s1[] = "This is some data";
  char s2[] = "This is some other data";

  printf("%d\n", memcmp(s1,s2,sizeof s1) < 0);
  printf("%d\n", memcmp(s2,s1,sizeof s1) < 0);
  printf("%d\n", memcmp(s1,s1,sizeof s1) < 0);
  printf("%d\n", lesscmp(s1,s2,sizeof s1));
  printf("%d\n", lesscmp(s2,s1,sizeof s1));
  printf("%d\n", lesscmp(s1,s1,sizeof s1));
}

When implementing it, I soon recognized the problem that although we are looking for the < result, we have to keep looping while the bytes are equal. And when they aren't, that's when we can start looking for <, with the cost of additional comparisons.

Because C has no operator working like "use <= but store the less or equal statuses separately, so we can loop based on the equal flag but return the less flag". On the assembler level we can likely do that however, making this function a good candidate for inline assembler in case we care deeply about performance. And yet unless we happen to be some x86 assembler guru, we can probably not hope to beat the compiler even with hand-crafted assembler.

Looking at the generated code (gcc -O3 x86) in Compiler Explorer, we can conclude that my home-made function is a mess:

lesscmp:
        test    rdx, rdx
        je      .L5
        xor     eax, eax
        jmp     .L4
.L3:
        add     rax, 1
        cmp     rdx, rax
        je      .L5
.L4:
        movzx   ecx, BYTE PTR [rsi+rax]
        cmp     BYTE PTR [rdi+rax], cl
        je      .L3
        setb    al
        ret
.L5:
        xor     eax, eax
        ret

cmp all over the place - it has more branches than a Christmas tree! This will not perform well at all.

Whereas the equivalent memcmp calls are sometimes inlined, resulting in various fancy x86 intrinsics, hard-coded "magic numbers" etc and very few if any branches. Way more efficient.

As so the conclusion is that "pre-mature optimization" remains the root of all evil, and memcmp(...) < 0 is likely the best solution for this purpose no matter the target.