Re: [lc-devel] Compressed caching

[Nitin G. <nit...@gm...>]

John Moser wrote:
>> Just a quick note: We can't have floating point in kernel. So, I doubt
>> how will we have monte-carlo algorithm ported to kernel?
>>
> 
> Nods.  I don't know if it can be rewritten in fixed point; however, it
> is notable that mcarlo is probably not as useful as counting null bytes.
>  Wilson-Kaplan algorithms treat 0 as a special case; think about
> anonymous memory:
> 
> ADDR	DATA
> 0	char a
> 	\0 (pad)
> 	\0 (pad)
> 4	int i
> 	int i
> 	int i
> 	int i
> 8	short j
> 	short j
> 	\0 (pad)
> 	\0 (pad)
> 12	char b
> 	\0 (pad)
> 	\0 (pad)
> 	\0 (pad)
> 16	....
> 
> Data values will often be aligned to 4 bytes; stack frames tend to be
> aligned to 16 bytes I guess (STACK_ROUND() rounds to 16 bytes).
> Executable memory is even worse; loops and small functions and other
> code blocks tend to be aligned to page boundaries, so you have things
> that look like:
> 
> 
> ...;
> ...;
> jmp @a;
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> @a:  /* Aligned to 4096 byte page boundary */
> ...;
> loop;
> ...;
> ret;  /*return*/
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> function foo() { /* Function aligned to a page boundary */
> ........
> 
> And so on.  You get small clumps of zeros here and there that don't
> really compress any better than small clumps of A's or 7's or such; but
> WKdm and WK4x4 expect these so they have a special way to compress them
> with lots more efficiency than LZO.
> 

/* --------------- Frame This One ---------------------------------------- */
> At any rate, just running through with a NULL byte counter is probably
> enough to decide whether to use WK or LZ.
> 
/* ------- Simple, Fast and Reliable ------------------------------------- */

Great suggestion John Moser :-)

And..I think, this NULL byte count can be really optimized to a level that time 
to perform this _each_ time when compressing pages should be far compensated by 
time and space we'll save by having a good hit at selecting right compression 
algorithm.



Cheers,
Nitin Gupta