crc32: add-slicing-by-8.diff

-----Original Message-----
From: George Spelvin [mailto:[email protected]]
Sent: Tuesday, August 09, 2011 6:21 AM
To: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]
Subject: Re: [patch v3 6/7] crc32: add-slicing-by-8.diff

While writing up some documentation of this algorithm, I came up with a potential speedup. Or, at least, realized why slicing by more than 4 is so much faster than slicing by 4 or less.

Note that the inner loop of the algorithm is as follows:

lib/crc32.c +14 -0

+#  define DO_CRC8a (tab[7][(q) & 255] ^ \
+		tab[6][(q >> 8) & 255] ^ \
+		tab[5][(q >> 16) & 255] ^ \
+		tab[4][(q >> 24) & 255])
+#  define DO_CRC8b (tab[3][(q) & 255] ^ \
+		tab[2][(q >> 8) & 255] ^ \
+		tab[1][(q >> 16) & 255] ^ \
+		tab[0][(q >> 24) & 255])
 
+	for (--b; middle_len; --middle_len) {
+		u32 q;
+		q = crc ^ *++b;
+		crc = DO_CRC8a;
+		q = *++b;
+		crc ^= DO_CRC8b;
 	}

Note the data dependencies: DO_CRC8a depends on the previous crc, which depends on the previous DO_CRC8b. But DO_CRC8b does not depend on anything except the input data at *++b.

It would increase parallelism to schedule DO_CRC8b before DO_CRC8a, to start those loads before the previous crc value is available.

Maybe the compiler and/pr processor can find this parallelism already, but if not, it might be useful to try reordering it:

#  define DO_CRC8a(x) (tab[7][(x) & 255] ^ \
		tab[6][((x) >> 8) & 255] ^ \
		tab[5][((x) >> 16) & 255] ^ \
		tab[4][((x) >> 24) & 255])
#  define DO_CRC8b(x) (tab[3][(x) & 255] ^ \
		tab[2][((x) >> 8) & 255] ^ \
		tab[1][((x) >> 16) & 255] ^ \
		tab[0][((x) >> 24) & 255])

	for ( ; middle_len; --middle_len, b += 2) {
		u32 q = DO_CRC8b(b[1]);
		crc ^= b[0];
		crc = q ^ DO_CRC8a(crc);
	}

add slicing-by-8 algorithm to the existing
slicing-by-4 algorithm. This consists of:

- extend largest BITS size from 32 to 64
- extend table from tab[4][256] to tab[8][256]
- change algorithm to align on 8 byte boundary (it was noted that all that is really required is that the inner loop must comsume 8 bytes. As written it can start on even or odd 4 byte boundary.)

- Add code for inner loop.

Signed-off-by Bob Pearson <[email protected]>

---
 lib/crc32.c          |   58 ++++++++++++++++++++++++++++++++++++++++++---------
 lib/crc32defs.h      |   14 ++++++------
 lib/gen_crc32table.c |   40 +++++++++++++++++++++--------------
 3 files changed, 79 insertions(+), 33 deletions(-)

Index: infiniband/lib/crc32.c
===================================================================

lib/crc32.c +32 -1

@@ -45,6 +45,7 @@ MODULE_LICENSE("GPL");
 
 #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
 
+/* implements slicing-by-4 or slicing-by-8 algorithm */
 static inline u32
 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
 {

@@ -54,41 +55,78 @@ crc32_body(u32 crc, unsigned char const
       tab[2][(crc >> 8) & 255] ^ \
       tab[1][(crc >> 16) & 255] ^ \
       tab[0][(crc >> 24) & 255]
+#  define DO_CRC8a (tab[7][(q) & 255] ^ \
+      tab[6][(q >> 8) & 255] ^ \
+      tab[5][(q >> 16) & 255] ^ \
+      tab[4][(q >> 24) & 255])
+#  define DO_CRC8b (tab[3][(q) & 255] ^ \
+      tab[2][(q >> 8) & 255] ^ \
+      tab[1][(q >> 16) & 255] ^ \
+      tab[0][(q >> 24) & 255])
 # else
 #  define DO_CRC(x) crc = tab[0][((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
 #  define DO_CRC4 crc = tab[0][(crc) & 255] ^ \
       tab[1][(crc >> 8) & 255] ^ \
       tab[2][(crc >> 16) & 255] ^ \
       tab[3][(crc >> 24) & 255]
+#  define DO_CRC8a (tab[4][(q) & 255] ^ \
+      tab[5][(q >> 8) & 255] ^ \
+      tab[6][(q >> 16) & 255] ^ \
+      tab[8][(q >> 24) & 255])
+#  define DO_CRC8b (tab[0][(q) & 255] ^ \
+      tab[1][(q >> 8) & 255] ^ \
+      tab[2][(q >> 16) & 255] ^ \
+      tab[3][(q >> 24) & 255])
 # endif
    const u32 *b;
-   size_t    rem_len;
+   size_t init_len;
+   size_t middle_len;
+   size_t rem_len;
+
+   /* break buf into init_len bytes before and
+    * rem_len bytes after a middle section with
+    * middle_len properly aligned words */
+# if CRC_LE_BITS == 32
+   init_len = min((-((uintptr_t)buf)) & 3, len);
+   middle_len = (len - init_len) >> 2;
+   rem_len = (len - init_len) & 3;
+# else
+   init_len = min((-((uintptr_t)buf)) & 7, len);
+   middle_len = (len - init_len) >> 3;
+   rem_len = (len - init_len) & 7;

lib/crc32.c +13 -7

-   rem_len = len & 3;
-   /* load data 32 bits wide, xor data 32 bits wide. */
-   len = len >> 2;
    b = (const u32 *)buf;
-   for (--b; len; --len) {
+   for (--b; middle_len; --middle_len) {
+# if CRC_LE_BITS == 32
       crc ^= *++b; /* use pre increment for speed */
       DO_CRC4;
+# else
+      u32 q;
+      q = crc ^ *++b;
+      crc = DO_CRC8a;
+      q = *++b;
+      crc ^= DO_CRC8b;
+# endif
    }
-   len = rem_len;
    /* And the last few bytes */
-   if (len) {
+   if (rem_len) {
       u8 *p = (u8 *)(b + 1) - 1;
       do {
          DO_CRC(*++p); /* use pre increment for speed */
-      } while (--len);
+      } while (--rem_len);
    }
    return crc;
 #undef DO_CRC
 #undef DO_CRC4
+#undef DO_CRC8a
+#undef DO_CRC8b
 }
 #endif
 

Index: infiniband/lib/crc32defs.h
===================================================================

lib/crc32defs.h +1 -1

 #endif
 #ifndef CRC_BE_BITS
-# define CRC_BE_BITS 32
+# define CRC_BE_BITS 64
 #endif

lib/crc32defs.h +0 -0

 #endif

Index: infiniband/lib/gen_crc32table.c
===================================================================

lib/gen_crc32table.c +8 -5

@@ -4,20 +4,24 @@
 
 #define ENTRIES_PER_LINE 4
 
-#if CRC_LE_BITS <= 8
-#define LE_TABLE_SIZE (1 << CRC_LE_BITS)
+#if CRC_LE_BITS > 8
+# define LE_TABLE_ROWS (CRC_LE_BITS/8)
+# define LE_TABLE_SIZE 256
 #else
-#define LE_TABLE_SIZE 256
+# define LE_TABLE_ROWS 1
+# define LE_TABLE_SIZE (1 << CRC_LE_BITS)
 #endif
 
-#if CRC_BE_BITS <= 8
-#define BE_TABLE_SIZE (1 << CRC_BE_BITS)
+#if CRC_BE_BITS > 8
+# define BE_TABLE_ROWS (CRC_BE_BITS/8)
+# define BE_TABLE_SIZE 256

lib/gen_crc32table.c +1 -1

 /**
  * crc32init_le() - allocate and initialize LE table data

@@ -40,7 +44,7 @@ static void crc32init_le(void)
    }
    for (i = 0; i < LE_TABLE_SIZE; i++) {
       crc = crc32table_le[0][i];
-      for (j = 1; j < 8; j++) {
+      for (j = 1; j < LE_TABLE_ROWS; j++) {
          crc = crc32table_le[0][crc & 0xff] ^ (crc >> 8);
          crc32table_le[j][i] = crc;
       }

@@ -64,18 +68,18 @@ static void crc32init_be(void)
    }
    for (i = 0; i < BE_TABLE_SIZE; i++) {
       crc = crc32table_be[0][i];

lib/gen_crc32table.c +9 -5

 {
    int i, j;
 
-   for (j = 0 ; j < 8; j++) {
+   for (j = 0 ; j < rows; j++) {
       printf("{");
       for (i = 0; i < len - 1; i++) {
          if (i % ENTRIES_PER_LINE == 0)

@@ -92,15 +96,19 @@ int main(int argc, char** argv)
 
    if (CRC_LE_BITS > 1) {
       crc32init_le();
-      printf("static const u32 crc32table_le[8][256] = {");
-      output_table(crc32table_le, LE_TABLE_SIZE, "tole");
+      printf("static const u32 crc32table_le[%d][%d] = {",
+             LE_TABLE_ROWS, LE_TABLE_SIZE);
+      output_table(crc32table_le, LE_TABLE_ROWS,
+              LE_TABLE_SIZE, "tole");
       printf("};\n");
    }
 
    if (CRC_BE_BITS > 1) {
       crc32init_be();
-      printf("static const u32 crc32table_be[8][256] = {");
-      output_table(crc32table_be, BE_TABLE_SIZE, "tobe");
+      printf("static const u32 crc32table_be[%d][%d] = {",
+             BE_TABLE_ROWS, BE_TABLE_SIZE);
+      output_table(crc32table_be, LE_TABLE_ROWS,
+              BE_TABLE_SIZE, "tobe");
       printf("};\n");
    }
 

Quoted 7 lines

- extend largest BITS size from 32 to 64
- extend table from tab[4][256] to tab[8][256]
- change algorithm to align on 8 byte boundary (it was noted that all that is really required is that the inner loop must comsume 8 bytes. As written it can start on even or odd 4 byte boundary.)

So why not do that in the code too?

From: "Bob Pearson" <[email protected]>
To: "'Joakim Tjernlund'" <[email protected]>
Cc: <[email protected]>, <[email protected]>, <[email protected]>, <[email protected]>
Date: 2011/08/09 22:52
Subject: RE: [patch v3 6/7] crc32: add-slicing-by-8.diff

Quoted 7 lines

Quoted 7 lines

- extend largest BITS size from 32 to 64
- extend table from tab[4][256] to tab[8][256]
- change algorithm to align on 8 byte boundary (it was noted that all that is really required is that the inner loop must comsume 8 bytes. As written it can start on even or odd 4 byte boundary.)

Quoted 2 lines

So why not do that in the code too?

I did the experiment with the random test set and it is a couple of % faster so I made the change. I had thought that it wouldn't make a measurable difference.