On 2022/10/29 20:49, David Laight wrote:

quoted

quoted

quoted

On 2022/10/27 3:03, Luis Chamberlain wrote:

quoted

On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:

quoted

On 2022/10/26 1:53, Luis Chamberlain wrote:

quoted

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)).

Currently not sorted.

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).

You've analyzed it very well. The hash method is not good for sorting names
and then searching in binary mode. I figured it out when I was working on
the design these days.

Current Implementation:
---------------------------------------
| idx | addresses | markers |  names  |
---------------------------------------
|  0  |    addr0  |         |  name0  |
|  1  |    addr1  |         |  name1  |
| ... |    addrx  |   [0]   |  namex  |
| 255 |    addrx  |         |  name255|
---------------------------------------
| 256 |  addr256  |         |  name256|
| ... |    addrx  |   [1]   |  namex  |
| 511 |  addr511  |         |  name511|
---------------------------------------

markers[0] = offset_of(name0)
markers[1] = offset_of(name256)

1. Find name by address
   binary search addresses[], get idx, traverse names[] from  markers[idx>>8] to markers[(idx>>8) + 1], return name

2. Find address by name
   traverse names[], get idx, return addresses[idx]

Hash Implementation:
Add two new arrays: hash_table[] and names_offsets[]

-----------------------------------------------------------------
| key |      hash_table       |         names_offsets           |
|---------------------------------------------------------------|
|  0  |  names_offsets[key=0] | offsets of all names with key=0 |
|  1  |  names_offsets[key=1] | offsets of all names with key=1 |
| ... |          ...          | offsets of all names with key=k |
|---------------------------------------------------------------|

hash_table[0] = 0
hash_table[1] = hash_table[0] + sizeof(names_offsets[0]) * number_of_names(key=0)
hash_table[2] = hash_table[1] + sizeof(names_offsets[0]) * number_of_names(key=1)

1. Find address by name
   hash name, get key, traverse names_offsets[] from index=hash_table[key] to
   index=hash_table[key+1], get the offset of name in names[]. binary search markers[],
   get index, then traverse names[] from  markers[index] to markers[index + 1], until
   match the offset of name, return addresses[idx].
2. Find address by name
   No change.

Sorted names Implementation:
Add two new arrays: offsets_of_addr_to_name[] and offsets_of_name[]

offsets_of_addr_to_name[i] = offset of name i in names[]
offsets_of_name[i]         = offset of sorted name i in names[]

1. Find name by address
   binary search addresses[], get idx, return names[offsets_of_addr_to_name[idx]]

2. Find address by name
   binary search offsets_of_name[], get idx, return addresses[idx]

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)

-- 
Regards,
  Zhen Lei