*********** REPLY SEPARATOR ***********
On 4/27/2003 at 7:51 PM Jörn Engel wrote:
>On Sun, 27 April 2003 13:24:37 -0400, rmoser wrote:
>> >int fox_compress(unsigned char *input, unsigned char *output,
>> > uint32_t inlen, uint32_t *outlen);
>> >
>> >int fox_decompress(unsigned char *input, unsigned char *output,
>> > uint32_t inlen, uint32_t *outlen);
>>
>> Ey? uint32_t*? I assume that's a mistake....
>
>Nope. outlen is changed, you need a pointer here.
>
ahh okay, gotcha
>> Anyhow, this wasn't what
>> I was asking. What I was asking was about how to determine how much
>> data to send to compress it. Read the message again, the whole thing
>> this time.
>
>I did. But modularity is the key here. The whole idea may be great or
>plain bullshit, depending on the benchmarks. Which one it is depends
>on the compression algorithm used, among other things. Maybe your
>compression algo is better for some machines, zlib for others, etc.
>
Yeah I know. I really need to get a working user-space version of this
thing so I can bench it against source tarballs and extractions from
/dev/random a bunch of times.
>Why should someone decide on an algorithm before measuring?
>
Erm. You can use any one of the other algos you want, there's a lot
out there. Go ahead and try zlib/gzip/bzip2/7zip/compress if you
want. I just figured, the simplest algo would hopefully be the fastest.
But really we need some finished code to make this work :-)
The real reason I'm working on this is because I favor speed completely
over size in this application. It's all modular; make the interface for the
kernel module flexible enough to push in gzip/bzip2 modules or whatever
else you want:
<M> Swap partition support
____<M> Compressed Swap
________<M> fcomp
____________<M> fcomp-extended support
________<M> zlib
________<M> gzip
________<M> bzip2
________<M> compress
____<M> Swap on RAM
As far as I know, zlib, gzip, and compress use Huffman trees. I am pretty
sure about zlib, not sure about the others. gzip I believe uses 16 bit
backpointers as well, which means you need a 64k processing window
for [de]compression, not to mention that it takes more work. bzip2 we
all know is CPU-intensive, or at least it was last time I checked.
>> >Then the mm code can pick any useful size for compression.
>>
>> Eh? I rather the code alloc space itself and do all its own handling.
>That
>> way you don't have to second-guess the buffer size for decompressed
>> data if you don't do all-at-once decompression (i.e. decompressing x86
>> segments, all-at-once would be to decompress the whole compressed
>> block of N size to 64k, where partial would be to pull in N/n at a time
>and
>> decompress in n sets of N/n, which would give varying sized output).
>
>Segments are old, stupid and x86 only. What you want is a number of
>pages, maybe just one at a time. Always compress chunks of the same
>size and you don't have to guess the decompressed size.
>
Yeah true. But for guessing the decompressed size I meant like when
you don't want to load the WHOLE block into RAM at once. Ahh, so you
swap in pages? Well whatever unit you swap in, that's how you should
compress things. Look I'm confusing myself here, just ignore anything
that sounds retarded--I'm just a kid after all :-p
>> Another thing is that the code isn't made to strictly stick to
>compressing
>> or decompressing a whole input all at once; you may break down the
>> input into smaller pieces. Therefore it does need to think about how
>much
>> it's gonna actually tell you to pull off when you inquire about the size
>to
>> remove from the stream (for compression at least), because you might
>> break it if you pull too much data off midway through compression. The
>> advantage of this method is in when you're A) Compressing files, and
>> B) trying to do this kind of thing on EXTREMELY low RAM systems,
>> where you can't afford to pass whole buffers back and forth. (Think 4
>meg)
>
>a) Even with 4M, two pages of 4k each don't hurt that much. If they
>do, the whole compression trick doesn't pay off at all.
>b) Compression ratios usually suck with small buffers.
>
a)
True, two chunks of 4k don't hurt. But how big are swap pages? Assuming
the page can't be compressed at all, it's [page size / 256] * 3 + [page size]
for the maximum compressed data size. (4144 bytes for 4k of absolutely
non-redundant data within 256 bytes).
b)
Yeah they do. But to find the compression performance (ratio) loss, you
do [max pointer distance]/[block size], meaning like for this one
256/[page size]. If you do a 4k page size, you lose 6.25% of the compression
performance (so if we average 2:1, we'll average 1.875:1). What IS the page
size the kernel uses?
>> You do actually understand the code, right? I have this weird habit of
>> making code and doing such obfuscating comments that people go
>> "WTF is this?" when they see it. Then again, you're probably about
>> 12 classes past me in C programming, so maybe it's just my logic that's
>> flawed. :)
>
>I didn't look that far yet. What you could do, is read through
>/usr/src/linux/Documentation/CodingStyle. It is just so much nicer
>(and faster) to read and sticking to it usually produces better code.
>
Eh, I should just crack open the kernel source and immitate it. But I have
that file on my hard disk, so mebbe I should look. Mebbe I should take a
whack at getting the compression algo to work too, instead of pushing it
on someone else.
>Jörn
>
>--
>Beware of bugs in the above code; I have only proved it correct, but
>not tried it.
>-- Donald Knuth
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Wed Apr 30 2003 - 22:00:27 EST