bzip2 very slow

I recently started using bzip2 to compress my kernel, I made the necessary changes in u-boot-1.1.2 to include bzip2 and increase the malloc size to 4MB. The decompression for the bzip2 image is over 10 times slower compared to the gzip image.

version: U-Boot-1.1.2 - 5338372 Feb 25 10:47 u-boot-1.1.2.tar.bz2
cpu: at91rm9200

from at91rm9200dk.h:
#define CONFIG_BZIP2 1
#define CFG_MALLOC_LEN (0x410000)

Here is a comparison of gzip vs bzip2 on the same 2.6.x kernel:

== gzip ==

$ gzip -v9 linux.bin
$ /usr/local/uboot/mkimage -A arm -O linux -C gzip -a 0x20008000 -e 0x20008000
-d linux.bin.gz uImage-2.6-dk

compressed file size: 877kB
decompression time: about 3 seconds

== bzip2 ==

$ bzip2 --best linux.bin
$ /usr/local/uboot/mkimage -A arm -O linux -C bzip2 -a 0x20008000 -e 0x20008000
-d linux.bin.bz2 uImage-2.6-dk

compressed file size: 813kB
decompression time: about 30 seconds

bzip2 is taking over 10 times longer to decompress for a 64K smaller file size. Is this normal?

regards,

Aras Vaichas