Re: [eclipse-clp-users] dictionary hash collisions

Joachim Schimpf wrote:
> Stephan Schiffel wrote:
>> Hi all,
>>
>> I have a rather large program with a lot of predicates and other symbols which 
>> fill the dictionary:
>>
>> dictionary_entries:     20666
>> dict_hash_usage:        6816 / 8192
>> dict_hash_collisions:   7917 / 6816
>>
>> I worry about the last line and the negative performance impact these 
>> collisions may have. What happens if there are a lot of hash collisions in 
>> the dictionary? Can this have a negative influence on the performance of a 
>> program?
> 
> You have here on average 3 (20666/6813) entries per collision list, which
> should not be a problem (of course, some can be longer).
> 
> The other point is that not many operations need to do a hash lookup
> in the dictionary.  The system usually passes pointers to the entries
> directly.  Only operations that make new atoms or functors, e.g. read
> predicates, atom_string/2 etc do name lookups.  The one operation that
> may be critical is functor/3, which could be slowed down by long
> collision chains.
> 
> -- Joachim
> 
The last line is more alarming than it actually is, because of an error 
in the documentation for statistics/2 -- which incorrectly states that 
the 7917 in the dict_hash_collisions line is the length of the longest 
list in a hash-table slot, but it is not, and is supposed to be the 
total number of collisions, although Joachim have noticed a problem with 
it and the count is incorrect, so it is pretty non-informative right now.

Cheers,

Kish

-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.