[Openmcl-devel] Hash Table performance
enderx12 at mac.com
Tue Sep 23 18:09:35 EDT 2008
On Sep 23, 2008, at 5:58 PM, Osei Poku wrote:
> 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
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
More information about the Openmcl-devel