[PATCH] crc32: Optimize inner loop.

[PATCH] crc32: Optimize inner loop.

[Joakim Tjernlund]

taking a pointer reference to each row in the crc table matrix,
one can reduce the inner loop with a few insn's

Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
---

 As the slice by 8 CRC32 optimizations seems stalled, I figured
 I send in this generic one.

 lib/crc32.c |   21 +++++++++++----------
 1 files changed, 11 insertions(+), 10 deletions(-)

diff --git a/lib/crc32.c b/lib/crc32.c
index 4855995..b06d1e7 100644
--- a/lib/crc32.c
+++ b/lib/crc32.c
@@ -51,20 +51,21 @@ static inline u32
 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
 {
 # ifdef __LITTLE_ENDIAN
-#  define DO_CRC(x) crc = tab[0][(crc ^ (x)) & 255] ^ (crc >> 8)
-#  define DO_CRC4 crc = tab[3][(crc) & 255] ^ \
-		tab[2][(crc >> 8) & 255] ^ \
-		tab[1][(crc >> 16) & 255] ^ \
-		tab[0][(crc >> 24) & 255]
+#  define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
+#  define DO_CRC4 crc = t3[(crc) & 255] ^ \
+		t2[(crc >> 8) & 255] ^ \
+		t1[(crc >> 16) & 255] ^ \
+		t0[(crc >> 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_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
+#  define DO_CRC4 crc = t0[(crc) & 255] ^ \
+		t1[(crc >> 8) & 255] ^  \
+		t2[(crc >> 16) & 255] ^	\
+		t3[(crc >> 24) & 255]
 # endif
 	const u32 *b;
 	size_t    rem_len;
+	const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
 
 	/* Align it */
 	if (unlikely((long)buf & 3 && len)) {
-- 
1.7.3.4

Re: [PATCH] crc32: Optimize inner loop.

[Andrew Morton]

On Thu, 3 Nov 2011 10:28:25 +0100
Joakim Tjernlund <Joakim.Tjernlund@transmode.se> wrote:

> taking a pointer reference to each row in the crc table matrix,
> one can reduce the inner loop with a few insn's
> 
> Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>

As we have other developers who have previously shown an interest in
the crc32 code it is a good idea to cc them on future patches to get a
bit more review and perhaps testing input.

This patch seems fairly harmless.  Some runtime testing results would
have been appropriate.

Also, something like "reduce a few insns" is extremely easy to
substantiate, so why not do it?  With my compiler, the patch reduces
the crc32.o text by 22 bytes.

>  As the slice by 8 CRC32 optimizations seems stalled, I figured
>  I send in this generic one.

I meant to ask about that.  The discussion was fairly long and complex
and I'm now unsure whether the patch I have is a still up-to-date,
whether it is a good one, whether it has additional testing results,
etc.

So probably the best thing to do now is for me to drop it.  Please
resend when convenient.  Be sure to cc all previous reviewers and also
update the changelog to cover any important issues which were
brought up in the review.  This is to show what the issues were, how
they were addressed, etc.

Thanks.

> index 4855995..b06d1e7 100644
> --- a/lib/crc32.c
> +++ b/lib/crc32.c
> @@ -51,20 +51,21 @@ static inline u32
>  crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
>  {
>  # ifdef __LITTLE_ENDIAN
> -#  define DO_CRC(x) crc = tab[0][(crc ^ (x)) & 255] ^ (crc >> 8)
> -#  define DO_CRC4 crc = tab[3][(crc) & 255] ^ \
> -		tab[2][(crc >> 8) & 255] ^ \
> -		tab[1][(crc >> 16) & 255] ^ \
> -		tab[0][(crc >> 24) & 255]
> +#  define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
> +#  define DO_CRC4 crc = t3[(crc) & 255] ^ \
> +		t2[(crc >> 8) & 255] ^ \
> +		t1[(crc >> 16) & 255] ^ \
> +		t0[(crc >> 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_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
> +#  define DO_CRC4 crc = t0[(crc) & 255] ^ \
> +		t1[(crc >> 8) & 255] ^  \
> +		t2[(crc >> 16) & 255] ^	\
> +		t3[(crc >> 24) & 255]
>  # endif
>  	const u32 *b;
>  	size_t    rem_len;
> +	const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
>  
>  	/* Align it */
>  	if (unlikely((long)buf & 3 && len)) {

RE: [PATCH] crc32: Optimize inner loop.

[Bob Pearson]

> 
> I meant to ask about that.  The discussion was fairly long and complex
> and I'm now unsure whether the patch I have is a still up-to-date,
> whether it is a good one, whether it has additional testing results,
> etc.

The original patch that went into your mm tree was replaced by a cleaner one
over time but the review process went on and on and I had to spend more time
with my day job. Eventually I just couldn't figure out how to get everyone
any happier. I was really reluctant to give up performance on the Intel
platform
but we were mostly arguing about 2-3% give or take.

It seems that the folks that wanted the same algorithm for crc32c may have
figured out how to reach a compromise.

RE: [PATCH] crc32: Optimize inner loop.

[Joakim Tjernlund]

"Bob Pearson" <rpearson@systemfabricworks.com> wrote on 2011/11/10 06:58:35:
>
> >
> > I meant to ask about that.  The discussion was fairly long and complex
> > and I'm now unsure whether the patch I have is a still up-to-date,
> > whether it is a good one, whether it has additional testing results,
> > etc.
>
> The original patch that went into your mm tree was replaced by a cleaner one
> over time but the review process went on and on and I had to spend more time
> with my day job. Eventually I just couldn't figure out how to get everyone
> any happier. I was really reluctant to give up performance on the Intel
> platform
> but we were mostly arguing about 2-3% give or take.

As I recall I was happy with your last round(possibly some minor nits) and
you were going to submit a final round to be included by Andrew.

>
> It seems that the folks that wanted the same algorithm for crc32c may have
> figured out how to reach a compromise.

crc32c are based on your patches and can't move on until your work
is applied.

 Jocke

RE: [PATCH] crc32: Optimize inner loop.

[Bob Pearson]

> 
> crc32c are based on your patches and can't move on until your work
> is applied.
> 
Ahhhh. I've been heads down for a month on Portals4 over InfiniBand for
Sandia and
haven't been paying much attention. Please let me know what I can do to help
unstick
things. I want to help.
>  Jocke