population count test

population_count_test.c

/*
$ gcc -std=c99 a.c
$ ./a.out  10000000
10000000 bits...
precmp8:   11ms (1250001)
 POPCNT:    6ms (1250001)
$ ./a.out  100000000
100000000 bits...
precmp8:  111ms (12500001)
 POPCNT:   62ms (12500001)
$ ./a.out  1000000000
1000000000 bits...
precmp8: 1115ms (125000001)
 POPCNT:  629ms (125000001)
*/
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define NUM_TESTS 10

static int COUNT_TABLE[] = {
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

static int count_precmp8(unsigned char* buffer, int len)
{
  int count = 0;
  for (int i=0; i<len; i++) {
    count += COUNT_TABLE[buffer[i]];
  }
  return count;
}

#ifdef __GNUC__
static int count_popcnt(unsigned char* buffer, int len)
{
  int count = 0;
  unsigned int* p = (unsigned int*)buffer;
  for (int i=0; i<len/4; i++) {
    unsigned int x = p[i];
    count += __builtin_popcount(x);
  }
  if (len % 4) {
    unsigned int x = 0;
    for (int i=0; i<len%4; i++) {
      x += p[i + len/4];
      x <<= 1;
    }
    count += __builtin_popcount(x);
  }
  return count;
}
#endif

static int test(char* name, int (*fn)(unsigned char*, int), unsigned char* buffer, int len)
{
  struct timeval t1, t2;
  int count;

  gettimeofday(&t1, 0);
  for (int i=NUM_TESTS; i; i--) count = (*fn)(buffer, len);
  gettimeofday(&t2, 0);

  t2.tv_sec -= t1.tv_sec;
  t2.tv_usec -= t1.tv_usec;
  if (t2.tv_usec < 0) {
    t2.tv_sec--;
    t2.tv_usec += 1000000;
  }
  if (t2.tv_usec >= 1000000) {
    t2.tv_sec++;
    t2.tv_usec -= 1000000;
  }
  int ms = t2.tv_sec * 1000 + t2.tv_usec / 1000;
  printf("%s: %4dms (%d)\n", name, ms/NUM_TESTS, count);
}

int main(int argc, char** argv)
{
  unsigned int bits = argc > 1 ? atoi(argv[1]) : 1000000000;
  printf("%u bits...\n", bits);
  bits = bits / 8 + 1;
  unsigned char* buffer = malloc(bits);
  for (int i=0; i<bits; i++) {
    buffer[i] = 1;
  }
  test("precmp8", count_precmp8, buffer, bits);
  test(" POPCNT", count_popcnt, buffer, bits);

  free(buffer);
  return 0;
}