Re: [lc-devel] Compressed caching

[John M. <joh...@gm...>]

Nitin Gupta wrote:
> John Moser wrote:
>> Nitin Gupta wrote:
>>> John Moser wrote:
>>>> It may even be possible to find an algorithm that does strict analysis
>>>> but not compression (like a hash) that spits out a value correlating to
>>>> the redundancy and encodability of the stream; but that would take a
>>>> lot
>>>> of research to come up with.  A really fast, really light compressor
>>>> would be easier.
>>> your hash idea is a real nice topic for MS...but I've not yet planned
>>> for that :)
>>> (btw...I searched for something like this on citeseer but no luck)
>>>
>>> WKdm is lightest I know...something lighter is maybe dear ol'
>>> memcpy() ;)
>>> ..and still WKdm can't give you an idea of how well others(LZO) will
>>> compress it.
>>>
>>
>> In general there is a correlation.  Remember compression is a
>> characteristic of the algorithm and the data.  It is computationally
>> impossible to compress truly random data beyond a specific average
>> ratio; however, small isolated blocks may encode well.
>>
>> In general we say one algorithm performs better than another because of
>> this.  7zip gets smaller output than RAR or ZIP, consistantly, on
>> various input datas; this is not a coincidence, the LZMA algorithm is
>> actually better at redundancy elimination.  The fact that an algorithm
>> compresses a set of data more than the next shows that algorithm is
>> better at eliminating redundancy; while the fact that a given algorithm
>> compresses one piece of data better than the next shows that that data
>> is more redundant.
>>
>> Think of it in terms of a punett square with the crossed values giving
>> the output data size of compressing a 32K block of data:
>>
>>   Algorithms:            Data sets:
>>   X = weak compression        A = minimal redundancy
>>   Y = strong compression    B = much redundancy
>>
>>    A    B
>> X 30 | 25
>>  ----+----
>> Y 25 | 15
>>
>> A weak algorithm with non-redundant data will produce a block only
>> slightly smaller (if not bigger) than the input; while the same
>> algorithm on more redundant data will produce a block that's a little
>> smaller than that.  In contrast, a strong algorithm on non-redundant
>> data will produce a block that's somewhat smaller, and on redundant data
>> will produce a block that's much smaller.
>>
>> You are correct in assuming that it's not a mathematical fact that any
>> given algorithm can be used to predict how other algorithms will perform
>> with the data; however, compression algorithms are basically analysis of
>> data, and they do happen to as a side effect of their nature expose a
>> property of the data.  We can use this to conjecture that in most cases
>> a compression algorithm will effectively describe how well other
>> algorithms will perform, just not in a 1:1 manner; it will produce an
>> approximate general trend.
> 
> This seems very logical and we can confirm this at least for particular
> cases of  WKdm, WK4x4 and LZO.
> 
> If you have some time, it would be awesome if you take 'compress-test'
> kernel module:
> 
> http://linux-mm.org/CompressedCaching/Code?action=AttachFile&do=get&target=compress-test.tar.gz
> 

bluefox@iceslab:~/compress-test$ sudo ./testscript.sh
==== LIBRARY FILE TEST ====
Block 1 of /lib/libc.so.6 (4096 in)
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000241 seconds, 17.0 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 1000 (0 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000443 seconds, 9.2 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 952 (0 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000432 seconds, 9.5 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 1593 (1 kB)



Block 2 of /lib/libc.so.6 (8192 in)
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 6.1e-05 seconds, 67.1 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 1676 (1 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000197 seconds, 20.8 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 1592 (1 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000177 seconds, 23.1 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2620 (2 kB)



Block 3 of /lib/libc.so.6 (12288 in)
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 9.6e-05 seconds, 42.7 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2512 (2 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000162 seconds, 25.3 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2328 (2 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000241 seconds, 17.0 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2877 (2 kB)



Block 4 of /lib/libc.so.6 (16384 in)
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000104 seconds, 39.4 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2692 (2 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000158 seconds, 25.9 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2528 (2 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000223 seconds, 18.4 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2854 (2 kB)



Block 5 of /lib/libc.so.6 (20480 in)
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.0001 seconds, 41 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2764 (2 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000257 seconds, 15.9 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2580 (2 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.00028 seconds, 14.6 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 2854 (2 kB)



==== RANDOM DATA TEST ====
Block 1 of /dev/urandom
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001142 seconds, 3.6 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4368 (4 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001151 seconds, 3.6 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4352 (4 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001132 seconds, 3.6 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4116 (4 kB)



Block 2 of /dev/urandom
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001079 seconds, 3.8 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4368 (4 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.00115 seconds, 3.6 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4352 (4 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001254 seconds, 3.3 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4116 (4 kB)



Block 3 of /dev/urandom
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001086 seconds, 3.8 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4368 (4 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001187 seconds, 3.5 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4352 (4 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001262 seconds, 3.2 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4116 (4 kB)



Block 4 of /dev/urandom
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001074 seconds, 3.8 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4368 (4 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.00117 seconds, 3.5 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4352 (4 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001276 seconds, 3.2 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4116 (4 kB)



Block 5 of /dev/urandom
   Algorithm index:  0 = WKdm
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.000997 seconds, 4.1 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4368 (4 kB)

   Algorithm index:  1 = WK4x4
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.00101 seconds, 4.1 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4352 (4 kB)

   Algorithm index:  2 = LZO
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.001118 seconds, 3.7 MB/s
Data size given: 4096 (4 kB) -- padded to 4kB
Compressed size: 4116 (4 kB)


(interesting results with random data)

It looks like on libc, WKdm and WK4x4 do well but LZO fails to perform;
while more random data squeezes down tighter with LZO.  It's interesting
that the random data sizes are consistent; I used /dev/urandom to
calculate pi once, it's VERY good at producing random data, I am
assuming thus that we are probably looking at the theoretical limits of
compression on 4096 bytes of data (i.e. they get bigger).

It does appear that there is a correlation here.  For libc, WKdm and
WK4x4 compress better than LZO; but in general, if a piece of data A
compresses smaller than a piece of data B under one algorithm, then it
also compresses smaller under the other algorithms.  Side by side:

/lib/libc.so.6
Block	WKdm	WK4x4	LZO
1	1000	952	1593
2	1676	1592	2620
3	2512	2328	2877

Notice as the output size of WKdm grows, so does the output size of
WK4x4 and LZO.

I have made note that for library data it seems in terms of output size
LZO > WKdm > WK4x4; whereas for random data it seems to progress WKdm >
WK4x4 > LZO.  It is probably possible to write a small period analysis
program to determine which to use; a simple monte-carlo  could detect
more random data, but counting the 0 bytes is also significant (WKdm and
WK4x4 treat 0 as a special case, due to C memory alignment and unused
bytes of memory pages tending to be filled with 0's).

A quick test on the first 4096 bytes of each of /dev/urandom and
/lib/libc.so.6 gives:

bluefox@icebox:/tmp/x$ ./mcarlo
hits = 1607, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  3.423745e+02    <--- Very random (high quality entropy)
        Nulls:  15

hits = 1595, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  3.793874e+01
        Nulls:  13

hits = 1593, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  3.304198e+01
        Nulls:  16

hits = 1592, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  3.103888e+01
        Nulls:  17

hits = 1606, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  2.051743e+02
        Nulls:  18

hits = 1570, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  1.330028e+01
        Nulls:  19

hits = 1612, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  1.460953e+02
        Nulls:  9

hits = 1578, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  1.678940e+01
        Nulls:  13

hits = 1600, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  6.026764e+01
        Nulls:  14

hits = 1621, shots = 2048
Final Calculations for /dev/urandom:
        Q.Idx:  4.094506e+01
        Nulls:  19

hits = 2038, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.192071e+00    <--- Very not random (low quality)
        Nulls:  2341

hits = 2046, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.170274e+00
        Nulls:  3448            <---  Lots of '\0' (WK-friendly!)

hits = 2047, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.167605e+00
        Nulls:  2646

hits = 2011, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.272035e+00
        Nulls:  2194

hits = 1994, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.328130e+00
        Nulls:  2022

hits = 1989, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.345582e+00
        Nulls:  2032

hits = 1990, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.342055e+00
        Nulls:  2019

hits = 1990, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.342055e+00
        Nulls:  2029

hits = 1980, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.378180e+00
        Nulls:  2025

hits = 1988, shots = 2048
Final Calculations for /lib/libc.so.6:
        Q.Idx:  1.349127e+00
        Nulls:  2008


> 
> and feed all three algos (included with this module), data from /lib
> (binary files), normal text files and other kind of data you can think
> of, and compare how effectively each compresses the data. This thing can
> be easily automated and  lots of data on this will allow us to see if we
> can really conjecture how well performance of WKdm (lightest) describes
> performance of other two.
> 
> If you are interested in doing this, I can send you all the details for
> this module. In fact, all you need to do is feed some data (in single
> pages) to /proc/compress_test/compress and then read this same file to
> see compressed size. You can dynamically switch algos by writing 0, 1,
> or 2 to /proc/compress_test/algo_idx.
> 
> ---------------------------
> [couldn't now think of a reply for rest of your mail]
> ---------------------------
> 
> Also, I have some doubts on page grouping you mentioned earlier:
> 
> AFAIK, Rodrigo's patch never compressed pages in groups - all pages were
> compressed individually. The page grouping you were mentioning about was
> the size of 'cells'. So, what is the meaning of grouping of pages w.r.t
> 'chunked' structure?


+Double Page Size
+CONFIG_COMP_DOUBLE_PAGE
+
+  Select this option to make compressed cache use double sized pages
+  (two pages contiguos) instead of single memory pages. That increases
+  the effect of the compressed cache use even when the compression
+  ratio isn't very good. On i386, compressed cache pages will have
+  8KiB instead of the regular 4KiB.
+
+  The size of the compressed cache page is listed in the output of
+  /proc/comp_cache_stat.
+
+  If unsure, say Y here.

Not sure.  I can't tell at a glance how the logic works (I have
difficulty figuring out the mm/ code), you may be right.

> 
> Though we can compression more than one page together and then store
> them in chunks but this was not you were mentioning about...right?
> 

Yeah I was thinking crunch together multiple pages at once...

> 
> Cheers,
> Nitin Gupta
>