RE: [PATCH v7 00/11] kallsyms: Optimizes the performance of lookup symbols

[David Laight <David.Laight@ACULAB.COM>]

> >> On 2022/10/27 3:03, Luis Chamberlain wrote:
> >>> On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
> >>>> On 2022/10/26 1:53, Luis Chamberlain wrote:
> >>>>> This answers how we don't use a hash table, the question was *should* we
> >>>>> use one?

(Probably brainfart) thought...

Is the current table (effectively) a sorted list of strings?
So the lookup is a binary chop - so O(log(n)).

But your hashes are having 'trouble' stopping one chain
being very long?
So a linear search of that hash chain is slow.
In fact that sort of hashed lookup in O(n).

What if the symbols were sorted by hash then name?
(Without putting the hash into each entry.)
Then the code could do a binary chop search over
the symbols with the same hash value.
The additional data is then an array of symbol numbers
indexed by the hash - 32 bits for each bucket.

If the hash table has 0x1000 entries it saves 12 compares.
(All of which are likely to be data cache misses.)

If you add the hash to each table entry then you can do
a binary chop search for the hash itself.
While this is the same search as is done for the strings
the comparison (just a number) will be faster than a
string compare.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)