Re: Where's the bzip2 compressed linux-kernel patch?

From: Rob Landley
Date: Mon Oct 20 2003 - 00:51:40 EST


On Sunday 19 October 2003 23:28, Willy Tarreau wrote:
> I don't know how the tests above were done. But what I know for sure is
> that there are excessive open source zealots who would only download the
> OSS version of UPX which uses the UCL library while the closed source
> version uses the NRV one which is a jewel.

Good for you. And arj beat pkzip for years, no a number of metrics. I
honestly do not care.

> > And no, gzip -9 does not add anything to decompression time, only
> > compression time.
>
> Where did you get this interesting idea ? every decompressor needs
> decompression time.

I mean that the -9 version of gzip does not take any more time to decompress
than the -1 version does, it only affects how many matches are checked in the
dictionary before it stops looking for a shorter match. During decompression
the offsets are all stored, it doesn't matter how they were calculated.

That's where I got the "interesting idea" that the -9 option to the gzip
compressor does not add anything to the decompression time.

> You need the compressed kernel to be in memory, then
> you decompress it, then you boot it. On my old 386sx which was still my
> home firewall 6 months ago, the kernel would take 2-3 seconds to decompress
> with gzip while it was almost unnoticeable with upx (which did it in place,
> BTW).

Interesting. So you're suggesting that your algorithm is optimized for a
processor with no L1 or L2 cache whatsoever? Or are you suggesting that an
algorithm that takes upwards of 3 seconds on a system that maxed out at 16
mhz and had a 16 bit data path, a system with a maximum memory throughput
slower than modern low-end hard drives (16mhz*2 bytes is 32 megabyts per
second, and half for read and half for write is 16 megabytes per second when
copying data without actually PROCESSING any of it, and this glosses over the
fact that with no instruction cache you'll never see even close to that
theoretical throughput on any code snippet longer than "rep movsw")... That
this algorithm is slow enough to be a legitimate optimization target and
worth using closed source software to optimize this bottleneck.

Are you really suggesting that gzip isn't fast enough? (Out of morbid
curiosity, how long did it take the bios code to boot up this straw man to
the point where it loaded the boot sector?)

> Now don't get me wrong, I'm not advertising for upx.

No comment.

> But bzip2 was proposed

No, I posted a link to code. And I offered to use that code to update an
existing kernel patch if I could track it down, which I did. (And I'm
working on a 2.6 port with the new engine, albeit not at a particularly high
priority seeing as we're in the middle of a code freeze...)

You're welcome to code up your own patch to do whatever you darn well please.
I'm not interested.

> and will always be criticized because of its decompression time and cost in
> terms of memory. So I simply suggested to take a look at other solutions
> which seem interesting.

You suggested I spend my free time to code up a patch to support a closed
source compressor I'd never heard of. I've taken it under advisement, and
filed it appropriately.

> An UPX-based implementation seems interesting to me
> only if the decompression code is free and can be put in the kernel.

Good for you. Code up a patch, so I can start ignoring code instead of just
ignoring suggestions.

> Otherwise it is not. If the numbers above come from the UCL lib, then we at
> least know that this one doesn't interest us for this matter.

I presume you're using the editorial "we". Because I, myself, find the
qualifier "for this matter" to be superfluous.

> Some people
> would also suggest taking a look at other compression algorithms which can
> be of interest, but I don't know their sources status (open/close).

If some people code up a patch, then the matter moves out of the realm of pure
philosophical arguments.

> > I can make bunzip work in-place if you'd like
>
> That's very important for low-memory systems.

Really? Wow.

> Regards,
> Willy

Rob
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/