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

From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>
Date: Fri, 16 Oct 2009 01:36:14 +1100
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
Received on Thu Oct 15 2009 - 14:36:32 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET