popcount() optimization for speed.

We run the array by 32 bit words instead of processing it byte per byte.
If the code is compiled using GCC __builtin_popcount() builtin function
is used instead.

diff --git a/src/bitop.c b/src/bitop.c
index 2b26265d7be4860a7b5b2b776571fb1c4b54947e..053db02b5cf51451ef0010cc8fb8a0ec6b54170b 100644 (file)
--- a/src/bitop.c
+++ b/src/bitop.c
@@ -30,10 +30,26 @@ static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) {
  * work with a input string length up to 512 MB. */
 long popcount(void *s, long count) {
     long bits = 0;
-    unsigned char *p = s;
+    unsigned char *p;
+    uint32_t *p4 = s;
     static const unsigned char bitsinbyte[256] = {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};
 
-    /* We can finally count bits. */
+    /* Count bits four bytes at a time */
+    while(count>=4) {
+        uint32_t aux = *p4++;
+        count -= 4;
+#ifdef __GNUC__
+        /* Unsigned int is always >= 4 bytes if compiler is GCC */
+        bits += __builtin_popcount(aux);
+#else
+        bits += bitsinbyte[aux&0xff] +
+                bitsinbyte[(aux>>8)&0xff] +
+                bitsinbyte[(aux>>16)&0xff] +
+                bitsinbyte[(aux>>24)&0xff];
+#endif
+    }
+    /* Count the remaining bytes */
+    p = (unsigned char*)p4;
     while(count--) bits += bitsinbyte[*p++];
     return bits;
 }