Re: [patch] Latency Tracer, voluntary-preempt-2.6.8-rc4-O6

[Paulo Marques <pmarques@grupopie.com>]

Ingo Molnar wrote:
> * Sam Ravnborg <sam@ravnborg.org> wrote:
> 
> 
>>That said do not put too much effort moving kode from the kernel to
>>kallsyms.c. kallsyms support can be deselected, and users will not
>>care about the little extra overhead (down in noise compared with the
>>symbols).

I know I'm probably putting to much effort on a low priority task 
(understatement of the year), but I was having fun doing it, so I saw no 
reason to stop :)

The new algorithm that I was thinking about is quite simple from the 
kernel point of view. It takes advantage of the fact that not all 
characters are allowed on symbols.

It uses these extra chars to feed a table that maps "special unused 
char"->"small string". For instance, it can say char \x85 is in fact 
"write_". Interesting enough the best string on my test data is "acpi_", 
and saves about 3kb of data to map it to just one char :)

So the work in the kernel is quite easy, and I believe it will in fact 
be faster than now, using less code.

The real problem is that the algorithm has to give the best strings to 
use in the table fast enough as to not be noticed in the total kernel 
compile time. Selecting the best strings is a really interesting problem 
from a mathematical point of view, and I was trying to solve it just for 
the fun of doing it :)

> distributions tend to enable it though, so saving 64K of kernel RAM is 
> good indeed. Good compression of the symbols increases the applicability 
> of kallsyms.

I'm glad you also found this scheme to be useful.

The code might be useful on other situations where we need to compress 
english text (or something like that) in a way that uncompressing a 
small string is quite fast. (I remember a thread a long time ago about 
compressing all the printk texts in the kernel, so maybe this could be 
useful there too)

-- 
Paulo Marques - www.grupopie.com