Ingo Molnar wrote: >... > >>With binary search you would need to backward search to find the stem >>for the stem compression. It's probably doable, but would be a bit >>ugly I guess. > > > yeah. Maybe someone will find the time to improve the algorithm. But > it's not a highprio thing. Well, I found some time and decided to give it a go :) I first built a small test program that could provide the same symbol data to the lookup function, so that I could test using a user space app. This way I could benchmark both the original algorithm and any improvement I could make, and do it confortably from user space. The original algorithm took, on average, 1340us per lookup on my P4 2.8GHz. The compile settings for the test are not the same on the kernel, so this can be only compared against other results from the same setup. With the attached patch it takes 14us per lookup. This is almost a 100x improvement. The largest portion of the time it took to do a lookup, was the decompression of the symbol names. It seemed a waste of time to keep strcpy'ing over the result lots of names that would probably not contribute to the final name. With the strcpy's out, the speed-up was around 5x, but even then, looking sequentially for the symbol name was still slow. The final algorithm pre-calculates markers on the compressed symbols so that the search time is almost divided by the number of markers. There are still a few issues with this approach. The biggest issue is that this is clearly a speed/space trade-off, and maybe we don't want to waste the space on a code path that is not supposed to be "hot". If this is the case, I can make a smaller patch, that fixes just the name "decompression" strcpy's. As always, any comments will be greatly appreciated. Just one side note: gcc gives a warning about 2 variables that might be used before initialization. I know they are not, and it didn't seem a good idea to put extra code just to shut up gcc. What is the standard way to convince gcc that those vars are ok? -- Paulo Marques - www.grupopie.com "In a world without walls and fences who needs windows and gates?"