[BusyBox] Re: [PATCH] Re: Sigh... this time i attached the file (bunzip-4.c)

Jörn Engel joern at wohnheim.fh-wedel.de
Fri Oct 24 17:32:31 UTC 2003

On Fri, 24 October 2003 08:09:00 -0500, Rob Landley wrote:
> On Friday 24 October 2003 04:45, Jörn Engel wrote:
> >
> > Not sure then.  It might be an idea to change interface slightly,
> > letting the user provide a read function.
> It will still read more data than it needs from their supplied function, so 
> how does this help?  (Sure the user can snapshot the data somehow as it goes 
> through their input function, but unless they go back and query the 
> compression library for how MUCH extra data it read, this will do them no 
> good.  If you're querying the library, the library can be made to cough up 
> not just the length but also the extra data it read, so why reinvent the 
> wheel?)  They can either reinvent stdio, or they can ask for the extra data 
> back at the end, but either way it's going to be a bit funky...

As are the uses, agreed.  99% will live happily without this.

> Actually, the n*log(n) shell sort you suggested earlier works well enough for 
> my purposes.  Sorting one 900k block of data (which will be after run length 
> compression, so it's usually rather a lot more data than that) takes a little 
> over 13 seconds of user time (worst case, all zeroes) and 8.15 seconds tested 
> with random data.  (This is on a 900 mhz celeron laptop; not unreasonably far 
> off from the times bzip itself is getting, although I haven't torn apart and 
> instrmented bzip's block sorting stuff yet...)

Mine takes .4 seconds for random data, much better.  With all zeros,
it takes forever, >10m or worse.  This can be improved. :)

Can you send me your code?  I am not (yet) allowed to send you mine in
return, but I can sure comment on it, after fixing my speed problem.

> The shell sort uses no more data than the 900k of charcters and the index 
> array.  I also whipped up a couple of GET_IDX and SET_IDX functions that only 
> use 20 bits for each index array entry instead of 32 (bringing the total 
> block sorting memory usage down to 3125000 bytes), but all the extra anding, 
> oring, and bit-shifting bloated the worst-case sort time to 22 seconds for a 
> 900k block of zeroes...

I've already thought about using 64k blocks for things like jffs2,
swap compression etc.  16 bits are not much slower.  You could try
using 24 bits and see how much speed you gain/lose vs. 20/32 bits.

> My first pass at bzip compression may not work as fast as jseward's, but it'll
> have a heck of a lot less code, and I can bolt the special-case-optimized 
> sorting functions onto it later, after I get it to work...

Actually, you are impressively fast already, sounds almost as if you
were cheating.  Without cheating, this is a great basis.


There's nothing better for promoting creativity in a medium than
making an audience feel "Hmm ­ I could do better than that!"
-- Douglas Adams in a slashdot interview

More information about the busybox mailing list