[PATCH] zlib: Optimize inffast when copying direct from output

[PATCH] zlib: Optimize inffast when copying direct from output

[Joakim Tjernlund]

JFFS2 uses lesser compression ratio and inflate always
ends up in "copy direct from output" case.
This patch tries to optimize the direct copy procedure.
Uses get_unaligned() but only in one place.
The copy loop just above this one can also use this
optimization, but I havn't done so as I have not tested if it
is a win there too.
On my MPC8321 this is about 17% faster on my JFFS2 root FS
than the original.
---

 Would like some testing of the PowerPC boot wrapper and
 a LE target before sending it upstream.

 arch/powerpc/boot/Makefile |    4 ++-
 lib/zlib_inflate/inffast.c |   48 +++++++++++++++++++++++++++++++++----------
 2 files changed, 40 insertions(+), 12 deletions(-)

diff --git a/arch/powerpc/boot/Makefile b/arch/powerpc/boot/Makefile
index 9ae7b7e..98e4c4f 100644
--- a/arch/powerpc/boot/Makefile
+++ b/arch/powerpc/boot/Makefile
@@ -20,7 +20,7 @@
 all: $(obj)/zImage
 
 BOOTCFLAGS    := -Wall -Wundef -Wstrict-prototypes -Wno-trigraphs \
-		 -fno-strict-aliasing -Os -msoft-float -pipe \
+		 -fno-strict-aliasing -Os -msoft-float -pipe -D__KERNEL__\
 		 -fomit-frame-pointer -fno-builtin -fPIC -nostdinc \
 		 -isystem $(shell $(CROSS32CC) -print-file-name=include)
 BOOTAFLAGS	:= -D__ASSEMBLY__ $(BOOTCFLAGS) -traditional -nostdinc
@@ -34,6 +34,8 @@ BOOTCFLAGS	+= -fno-stack-protector
 endif
 
 BOOTCFLAGS	+= -I$(obj) -I$(srctree)/$(obj)
+BOOTCFLAGS	+= -include include/linux/autoconf.h -Iarch/powerpc/include
+BOOTCFLAGS	+= -Iinclude
 
 DTS_FLAGS	?= -p 1024
 
diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c
index 8550b0c..0c7fa3d 100644
--- a/lib/zlib_inflate/inffast.c
+++ b/lib/zlib_inflate/inffast.c
@@ -4,6 +4,7 @@
  */
 
 #include <linux/zutil.h>
+#include <asm/unaligned.h>
 #include "inftrees.h"
 #include "inflate.h"
 #include "inffast.h"
@@ -24,9 +25,11 @@
 #ifdef POSTINC
 #  define OFF 0
 #  define PUP(a) *(a)++
+#  define UP_UNALIGNED(a) get_unaligned((a)++)
 #else
 #  define OFF 1
 #  define PUP(a) *++(a)
+#  define UP_UNALIGNED(a) get_unaligned(++(a))
 #endif
 
 /*
@@ -239,18 +242,41 @@ void inflate_fast(z_streamp strm, unsigned start)
                     }
                 }
                 else {
+		    unsigned short *sout;
+		    unsigned long loops;
+
                     from = out - dist;          /* copy direct from output */
-                    do {                        /* minimum length is three */
-                        PUP(out) = PUP(from);
-                        PUP(out) = PUP(from);
-                        PUP(out) = PUP(from);
-                        len -= 3;
-                    } while (len > 2);
-                    if (len) {
-                        PUP(out) = PUP(from);
-                        if (len > 1)
-                            PUP(out) = PUP(from);
-                    }
+                    /* minimum length is three */
+		    /* Align out addr */
+		    if (!((long)(out - 1 + OFF)) & 1) {
+			PUP(out) = PUP(from);
+			len--;
+		    }
+		    sout = (unsigned short *)(out - OFF);
+		    if (dist > 2 ) {
+			unsigned short *sfrom;
+
+			sfrom = (unsigned short *)(from - OFF);
+			loops = len >> 1;
+			do
+			    PUP(sout) = UP_UNALIGNED(sfrom);
+			while (--loops);
+			out = (unsigned char *)sout + OFF;
+			from = (unsigned char *)sfrom + OFF;
+		    } else { /* dist == 1 or dist == 2 */
+			unsigned short pat16;
+
+			pat16 = *(sout-2+2*OFF);
+			if (dist == 1)
+			    pat16 = (pat16 & 0xff) | ((pat16 & 0xff ) << 8);
+			loops = len >> 1;
+			do
+			    PUP(sout) = pat16;
+			while (--loops);
+			out = (unsigned char *)sout + OFF;
+		    }
+		    if (len & 1)
+			PUP(out) = PUP(from);
                 }
             }
             else if ((op & 64) == 0) {          /* 2nd level distance code */
-- 
1.6.4.4

Re: [PATCH] zlib: Optimize inffast when copying direct from output

[Benjamin Herrenschmidt]

On Tue, 2009-11-10 at 10:00 +0100, Joakim Tjernlund wrote:
> JFFS2 uses lesser compression ratio and inflate always
> ends up in "copy direct from output" case.
> This patch tries to optimize the direct copy procedure.
> Uses get_unaligned() but only in one place.
> The copy loop just above this one can also use this
> optimization, but I havn't done so as I have not tested if it
> is a win there too.
> On my MPC8321 this is about 17% faster on my JFFS2 root FS
> than the original.
> ---
> 
>  Would like some testing of the PowerPC boot wrapper and
>  a LE target before sending it upstream.

Well, you should probably submit that patch to lkml then :-)

I'm not sure its going to work to use get_unaligned() like that on all
archs .. it might be definitely something to discuss on some more
appropriate mailing list.

Cheers,
Ben.

>  arch/powerpc/boot/Makefile |    4 ++-
>  lib/zlib_inflate/inffast.c |   48 +++++++++++++++++++++++++++++++++----------
>  2 files changed, 40 insertions(+), 12 deletions(-)
> 
> diff --git a/arch/powerpc/boot/Makefile b/arch/powerpc/boot/Makefile
> index 9ae7b7e..98e4c4f 100644
> --- a/arch/powerpc/boot/Makefile
> +++ b/arch/powerpc/boot/Makefile
> @@ -20,7 +20,7 @@
>  all: $(obj)/zImage
>  
>  BOOTCFLAGS    := -Wall -Wundef -Wstrict-prototypes -Wno-trigraphs \
> -		 -fno-strict-aliasing -Os -msoft-float -pipe \
> +		 -fno-strict-aliasing -Os -msoft-float -pipe -D__KERNEL__\
>  		 -fomit-frame-pointer -fno-builtin -fPIC -nostdinc \
>  		 -isystem $(shell $(CROSS32CC) -print-file-name=include)
>  BOOTAFLAGS	:= -D__ASSEMBLY__ $(BOOTCFLAGS) -traditional -nostdinc
> @@ -34,6 +34,8 @@ BOOTCFLAGS	+= -fno-stack-protector
>  endif
>  
>  BOOTCFLAGS	+= -I$(obj) -I$(srctree)/$(obj)
> +BOOTCFLAGS	+= -include include/linux/autoconf.h -Iarch/powerpc/include
> +BOOTCFLAGS	+= -Iinclude
>  
>  DTS_FLAGS	?= -p 1024
>  
> diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c
> index 8550b0c..0c7fa3d 100644
> --- a/lib/zlib_inflate/inffast.c
> +++ b/lib/zlib_inflate/inffast.c
> @@ -4,6 +4,7 @@
>   */
>  
>  #include <linux/zutil.h>
> +#include <asm/unaligned.h>
>  #include "inftrees.h"
>  #include "inflate.h"
>  #include "inffast.h"
> @@ -24,9 +25,11 @@
>  #ifdef POSTINC
>  #  define OFF 0
>  #  define PUP(a) *(a)++
> +#  define UP_UNALIGNED(a) get_unaligned((a)++)
>  #else
>  #  define OFF 1
>  #  define PUP(a) *++(a)
> +#  define UP_UNALIGNED(a) get_unaligned(++(a))
>  #endif
>  
>  /*
> @@ -239,18 +242,41 @@ void inflate_fast(z_streamp strm, unsigned start)
>                      }
>                  }
>                  else {
> +		    unsigned short *sout;
> +		    unsigned long loops;
> +
>                      from = out - dist;          /* copy direct from output */
> -                    do {                        /* minimum length is three */
> -                        PUP(out) = PUP(from);
> -                        PUP(out) = PUP(from);
> -                        PUP(out) = PUP(from);
> -                        len -= 3;
> -                    } while (len > 2);
> -                    if (len) {
> -                        PUP(out) = PUP(from);
> -                        if (len > 1)
> -                            PUP(out) = PUP(from);
> -                    }
> +                    /* minimum length is three */
> +		    /* Align out addr */
> +		    if (!((long)(out - 1 + OFF)) & 1) {
> +			PUP(out) = PUP(from);
> +			len--;
> +		    }
> +		    sout = (unsigned short *)(out - OFF);
> +		    if (dist > 2 ) {
> +			unsigned short *sfrom;
> +
> +			sfrom = (unsigned short *)(from - OFF);
> +			loops = len >> 1;
> +			do
> +			    PUP(sout) = UP_UNALIGNED(sfrom);
> +			while (--loops);
> +			out = (unsigned char *)sout + OFF;
> +			from = (unsigned char *)sfrom + OFF;
> +		    } else { /* dist == 1 or dist == 2 */
> +			unsigned short pat16;
> +
> +			pat16 = *(sout-2+2*OFF);
> +			if (dist == 1)
> +			    pat16 = (pat16 & 0xff) | ((pat16 & 0xff ) << 8);
> +			loops = len >> 1;
> +			do
> +			    PUP(sout) = pat16;
> +			while (--loops);
> +			out = (unsigned char *)sout + OFF;
> +		    }
> +		    if (len & 1)
> +			PUP(out) = PUP(from);
>                  }
>              }
>              else if ((op & 64) == 0) {          /* 2nd level distance code */

Re: [PATCH] zlib: Optimize inffast when copying direct from output

[Joakim Tjernlund]

Benjamin Herrenschmidt <benh@kernel.crashing.org> wrote on 24/11/2009 04:12:43:
>
> On Tue, 2009-11-10 at 10:00 +0100, Joakim Tjernlund wrote:
> > JFFS2 uses lesser compression ratio and inflate always
> > ends up in "copy direct from output" case.
> > This patch tries to optimize the direct copy procedure.
> > Uses get_unaligned() but only in one place.
> > The copy loop just above this one can also use this
> > optimization, but I havn't done so as I have not tested if it
> > is a win there too.
> > On my MPC8321 this is about 17% faster on my JFFS2 root FS
> > than the original.
> > ---
> >
> >  Would like some testing of the PowerPC boot wrapper and
> >  a LE target before sending it upstream.
>
> Well, you should probably submit that patch to lkml then :-)

I have(with LE fixes), Andrew Morton has it.

>
> I'm not sure its going to work to use get_unaligned() like that on all
> archs .. it might be definitely something to discuss on some more
> appropriate mailing list.

Oh, why not? Is that because I am using it wrongly or because xx_unaligned
is impl. incorrectly on some archs?

      Jocke

Re: [PATCH] zlib: Optimize inffast when copying direct from output

[Benjamin Herrenschmidt]

On Thu, 2009-11-26 at 09:30 +0100, Joakim Tjernlund wrote:
> > I'm not sure its going to work to use get_unaligned() like that on all
> > archs .. it might be definitely something to discuss on some more
> > appropriate mailing list.
> 
> Oh, why not? Is that because I am using it wrongly or because xx_unaligned
> is impl. incorrectly on some archs? 

I'm just not sure it works in boot wrappers in case archs ... I suppose
it does but I haven't actually checked :-)

Cheers,
Ben.

Re: [PATCH] zlib: Optimize inffast when copying direct from output

[Joakim Tjernlund]

Benjamin Herrenschmidt <benh@kernel.crashing.org> wrote on 26/11/2009 09:46:58:
>
> On Thu, 2009-11-26 at 09:30 +0100, Joakim Tjernlund wrote:
> > > I'm not sure its going to work to use get_unaligned() like that on all
> > > archs .. it might be definitely something to discuss on some more
> > > appropriate mailing list.
> >
> > Oh, why not? Is that because I am using it wrongly or because xx_unaligned
> > is impl. incorrectly on some archs?
>
> I'm just not sure it works in boot wrappers in case archs ... I suppose
> it does but I haven't actually checked :-)

I am not aware of other boot wrappers than PowerPC and I believe ppc
should handle it as unaligned accesses aren't a problem there.

      Jocke