[PATCH 2/2] (g)unzip: Optimize inflate_codes()

[Rob Landley]

On Monday 15 February 2010 11:52:16 Dan Fandrich wrote:
> On Mon, Feb 15, 2010 at 04:34:20AM -0600, Rob Landley wrote:
> > Wow, you've quite thoroughly missed the entire point of busybox.
>
> Wow, you've quite thoroughly missed the entire point of my question.

No, I think my point stands.

> > There is no "the goal", there are multiple goals that get balanced
> > against each other.  Reducing size is a goal, reducing complexity is a
> > goal, reducing external dependencies is a goal, reducing the number of
> > separate executables in the system (and thus the ELF overhead, filesystem
> > block granularity, mmap page granularity, and so on) is a goal...
>
> I'm not asking for the rationale for some arbitrary BusyBox attribute that
> you pulled out of your head, I'm asking about the use of small, widely-
> available library.

On ubuntu 9.10 for x86-64, /lib/libz.so.1.2.3.3 is 96,768 bytes (stripped).  I 
just built busybox with both gzip and gunzip, and it was 30,824 bytes.  Our 
version, both compression and decompresson, is less than 1/3 the size of the 
basic zlib library that comes with the system.  (And yes both files are 
stripped according to the "file" command.)

You too could have checked this.

That's on _top_ of the point that minimizing environmental dependencies is 
part of the nature of busybox.

> > Busybox doesn't depend on any external libraries (except libc and
> > friends), and never has.  We emit raw ansi escape sequences rather than
> > depend on ncurses, implement our own command line history in the shell
> > rather than getline, and so on.
>
> I thought I saw a loaded BusyBox binary linking to OpenSSL, but may have
> just been libcrypt.

Part of the standard C library.  Both glibc and uClibc packages supply it.  It 
handles the /etc/passwd cryptography.

The C library is not a single file.  For one thing, you can't use any shared 
libraries without the shared library loader, which is provided by your C 
library package.  (That would be the /lib/ld-*.so.* file/files.)  You also get 
libm, librt, libutil, libresolv, libdl, libcrypt, and libpthread.  Those are 
all provided by the same package as libc, and built from the same source 
tarball.

By the way, look up CONFIG_USE_BB_PWD_GRP in menuconfig.  Busybox implemented 
its own built-in versions even of libcrypt.  (Our versions are really small, 
but if you need network logins and such the C library versions.)

> But lots of BusyBox systems already supply things like
> zlib as well as other libraries that are reimplemented in BusyBox, and
> since "reducing size is a goal", it's not unreasonable to expect BusyBox
> to use their availability to reduce its size even further.

As I said, we've discussed exporting our own implementations to that busybox 
can provide zlib bindings to other programs that need it, but haven't found it 
worth the complexity yet.

Busybox has never required external library dependencies beyond what comes 
with libc.  Requiring external libraries increases complexity, and there are 
plenty of other things out there that already provide big and complicated 
implementations of all this stuff.

> > Keeping "old inefficient code around as a fallback" goes against
> > everything busybox stands for.  I personally re-implemented mount at
> > least three times trying to get it to do more in less code, and it's
> > since been redone another couple times since I left.  I didn't rewrite
> > bunzip because it didn't _work_, but because I thought I could do better.
>
> Maybe you weren't reading this thread carefully enough.  It's about
> patching the decompress code because it's old and inefficient.

Actually it was a specific bugfix and a specific optimization.  Not because it 
stopped working, but because it could be improved.

My suggestion was grabbing the implementations from the Linux kernel, which 
might (or might not) be a further improvement.  I may get around to poking at 
it this weekend if nobody else does.

Rob
-- 
Latency is more important than throughput. It's that simple. - Linus Torvalds