Subject: Re: Symbol lookups.
To: Nathan J. Williams <email@example.com>
From: None <firstname.lastname@example.org>
Date: 05/08/2003 15:56:06
> The speed difference between the kernel lookup and userland lookup
> seems plausable, but I'm not sure how strongly it argues that the
> kernel method is good, rather than that the userlevel method is
> truly lousy.
> I tried fiddling with the kvm.db DB parameters, including trying btree
> (lousy for random searches, but slightly faster than the kernel lookup
> if you happened to be looking everything up in sorted order, forward
> or reverse) and could improve the numbers slightly on my test system,
> but couldn't beat ksyms in general.
> For the time being it seems fine to punt kvm.db, but it's worth
> pondering *why* ksyms is faster.
I don't know how DB works internally, but the simple tree-style lookup
that I used in the kernel uses very few memory referenses to find the
correct string. Some "profiling" on a generic x86 kernel shows:
Loaded 12667 symbols
Shortest path: 2 nodes
Longest path: 24 nodes
Average path length: 16 nodes
Median path length: 16 nodes
This means that the average amount of memory references to find a
given string (among 12667) is 16 + a strcmp() call with the key.
There are a number of optimizations to this that could be done; for
example one ioctl() are called for each symbol, the tree structure
could be compressed to better match cache lines etc... but thinking
of that doing symbol lookups are not in any time-critical path I
don't think it's worth the additional complexity of the code :-)