[armedbear-devel] Performance of eq hash tables

[Alan Ruttenberg]

Hi,

Has anyone looked at this? I'm traversing a large structure and using an eq
(tried eql too) hash table to record where I've been so that I don't get
caught in circularities. There are about 1.5M nodes, but what I see is that
adding entries to the hash table slows down (a lot) over time, even when I
give an initial size of 4,000,000. That would be max occupancy of 30%,
lower than anyone would typically rehash.

What I see is that it rapidly starts to fill. At 300k entries I'm getting
about 2.5K new entries per second. By the time I get to 600k entries it is
down to 750 new entries/sec. At 900k (where it stands now) it's about 500
entries/sec.

That makes me suspect that the hash isn't distributing well over the size
of the underlying vector and that the slowdown is due to buckets getting
long.

I'm not sure how to probe this - any ideas?
Or to fix it. I suppose I could look for an alternative hash
implementation, but I thought I would check first with the list to see if
anyone else can shed some light.

Thanks,
Alan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/armedbear-devel/attachments/20130522/4e5ee318/attachment.html>