On 2022/10/29 20:49, David Laight wrote: >>>> 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)). 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
