[Openmcl-devel] Hash Table performance

[Chris Curtis]

On Sep 23, 2008, at 5:58 PM, Osei Poku wrote:

> Hi,
>
> CCL extensively uses the ENUMERATE-HASH-KEYS-AND-VALUES function
> underneath most of hash table functions (MAPHASH, WITH-HASH-TABLE-
> ITERATOR).  This causes a great deal of waste when iterating through a
> very large hash table (like I have now ~10^8 entries).  The way I

If you need to iterate through 10^8 entries, a hash table is simply  
not the right data structure. For that matter, if you need to iterate  
through any number of entries, a hashtable is generally a Bad Idea.

> understand the code from briefly looking at l0-hash.lisp and
> hash.lisp, the contents of the hash table are first stored in a pair
> of vectors, then the vectors are iterated through.
>
> WITH-HASH-TABLE-ITERATOR is used everywhere like in the expansion of
> the LOOP macro.  There is simply no standard way in CCL to iterate
> through the contents of a hash table without doing this double work.
> Is there some fundamental limitation of the way hash tables are
> implemented in CCL that prevent iterating through its contents only
> once?

I don't think this has anything to do with CCL. Hashtables get their  
insert and lookup performance at the expense of iterability. Linked  
lists get their iteration performance at the expense of insert and  
lookup performance. Trees of various types spread the expense around  
differently.

--chris