Skip to contentSkip to conversation

zlib: Optimize decompression

RFC PATCH New Joakim Tjernlund 3 participants 5 messages Nov 19, 2009 – Dec 5, 2009

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 zlib: Optimize decompression

This patch optimizes 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. No speed test has been performed in u-boot.

Size increase on ppc: 484 bytes

---

I have the same optimization queued for linux. Figured it would be useful for u-boot too.

Testing and feedback welcome.

 lib_generic/zlib.c |   56 ++++++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 44 insertions(+), 12 deletions(-)
lib_generic/zlib.c +44 -12
index 8fe3bd0..5721968 100644
@@ -26,8 +26,10 @@
 #define ZUTIL_H
 #define ZLIB_INTERNAL
 
-#include "u-boot/zlib.h"
 #include <common.h>
+#include <compiler.h>
+#include <asm/unaligned.h>
+#include "u-boot/zlib.h"
 /* To avoid a build time warning */
 #ifdef STDC
 #include <malloc.h>
@@ -400,6 +402,7 @@ void inflate_fast OF((z_streamp strm, unsigned start));
  */
 #define OFF 1
 #define PUP(a) *++(a)
+#define UP_UNALIGNED(a) get_unaligned(++(a))
 
 /*
    Decode literal, length, and distance codes and write out the resulting
@@ -616,18 +619,47 @@ unsigned start;         /* inflate()'s starting value for strm->avail_out */
                     }
                 }
                 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)
+#if defined(__BIG_ENDIAN)
+			    pat16 = (pat16 & 0xff) | ((pat16 & 0xff ) << 8);
+#elif defined(__LITTLE_ENDIAN)
+			    pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00 ) >> 8);
+#else
+#error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined
+#endif
+			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 */
Signature · 1 line
1.6.4.4
#1 lore raw

RFC PATCH 1/1 zlib: Optimize decompression

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

"Joakim" == Joakim Tjernlund <[email protected]> writes:

Joakim> This patch optimizes the direct copy procedure. Joakim> Uses get_unaligned() but only in one place.
Joakim> The copy loop just above this one can also use this Joakim> optimization, but I havn't done so as I have not tested if it Joakim> is a win there too.
Joakim> On my MPC8321 this is about 17% faster on my JFFS2 root FS Joakim> than the original. No speed test has been performed in u-boot.

On a mpc8347 board it's ~12% faster at decompressing the uImage (165ms).

Joakim> Signed-off-by: Joakim Tjernlund <[email protected]>

Signature · 1 line
Bye, Peter Korsgaard
#2 lore raw

RFC PATCH 1/1 zlib: Optimize decompression

Peter Korsgaard <[email protected]> wrote on 19/11/2009 15:07:12:

Quoted 11 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

"Joakim" == Joakim Tjernlund <[email protected]> writes:

Joakim> This patch optimizes the direct copy procedure. Joakim> Uses get_unaligned() but only in one place.
Joakim> The copy loop just above this one can also use this Joakim> optimization, but I havn't done so as I have not tested if it Joakim> is a win there too.
Joakim> On my MPC8321 this is about 17% faster on my JFFS2 root FS Joakim> than the original. No speed test has been performed in u-boot.

Quoted 5 lines

On a mpc8347 board it's ~12% faster at decompressing the uImage (165ms).

Joakim> Signed-off-by: Joakim Tjernlund <[email protected]>

Thanks, question: How does this compare with your lzo uncompress?

Jocke

#3 lore raw

RFC PATCH 1/1 zlib: Optimize decompression

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

"Joakim" == Joakim Tjernlund <[email protected]> writes:

Hi,

Quoted 2 lines
Quoted 2 lines

On a mpc8347 board it's ~12% faster at decompressing the uImage (165ms).

Joakim> Signed-off-by: Joakim Tjernlund <[email protected]>

Quoted 2 lines
Quoted 2 lines

Joakim> Thanks, question: How does this compare with your lzo uncompress?

Lzo is still slightly faster, but it only about ~5% (60ms). This is at 400MHz with very slow flash. With slower cpu/faster flash the difference would probably be bigger (it certainly was when I compared with zlib before your optimization).

I can rerun that test, but first I need to figure out why 2009.11-rc1 is more than 1 second slower than 2009.08.

Signature · 1 line
Bye, Peter Korsgaard
#4 lore raw

RFC PATCH 1/1 zlib: Optimize decompression

In reply to Joakim Tjernlund

Dear Joakim Tjernlund,

Quoted 13 lines · In message <[email protected]>…

This patch optimizes 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. No speed test has been performed in u-boot.

Size increase on ppc: 484 bytes

---

Quoted 7 lines

I have the same optimization queued for linux. Figured it would be useful for u-boot too.

Testing and feedback welcome.

 lib_generic/zlib.c |   56 ++++++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 44 insertions(+), 12 deletions(-)

Applied to "next", thanks.

Best regards,

Wolfgang Denk

Signature · 7 lines
DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
I don't mind criticism. You know me. I've  never  been  one  to  take
offence  at  criticism. No one could say I'm the sort to take offence
at criticism -- Not twice, anyway. Not without blowing bubbles.
                                  - Terry Pratchett, _Witches Abroad_