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

From: Paulo Marques
Date: Tue Aug 17 2004 - 13:19:32 EST


Ingo Molnar wrote:
* Sam Ravnborg <sam@xxxxxxxxxxxx> 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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/