<div dir="ltr">Hi Gary,<div><br></div><div> Thanks for your info. I understand (I think) about rehashing caused by the hash-table becoming "full". </div><div>I don't think that is the case for the "hash-table shrinking" I'm observing.</div><div><br></div><div>I wasn't aware that GC changing addresses of keys might cause rehashing, but I guess that makes sense.</div><div>In my searches, I'm using hash-tables with :test #'equal, and my keys are all byte-vectors (make-array 16 :element-type '(unsigned-byte 8)).</div><div>My model of behavior for equalp hashing is that the addresses of keys shouldn't matter. Am I mistaken?</div><div><br></div><div>So as far as I can tell, neither of the cases (1 or 2) that you mention seems to be a cause for rehashing.</div><div><br></div><div>What I'm suspecting is that perhaps heap space is getting exhausted, and somehow the GC is aggressively</div><div>looking for space to reclaim, and decides to reduce the size of my hash-table in order to get more space.</div><div>My question is whether this could really be what's happening, or if my speculation is wrong.</div><div>NOTE: Raymond produced a code snippet that demonstrated that CLRHASH could result in a reduced hash-table size.</div><div>This experiment shows a difference in behavior between CCL and alternatives like LispWorks and SBCL.</div><div>Here is a reproduction of his (Raymond Wiker's) experiment (from earlier in this thread):</div><div>***begin quote***</div><div><span style="font-size:13px">It looks like repeatedly clrhashing the table may cause it to be rehashed down to a smaller size. The following code snippet replicates what you’re seeing (I think): </span><div style="font-size:13px"><br></div><div style="font-size:13px"><div>(let ((h (make-hash-table :size 100000)))</div><div><span style="white-space:pre-wrap"> </span> (dotimes (i (truncate (hash-table-size h) 2))</div><div><span style="white-space:pre-wrap"> </span> (setf (gethash i h) i))</div><div><span style="white-space:pre-wrap"> </span> (clrhash h)</div><div><span style="white-space:pre-wrap"> </span> (dotimes (i (truncate (hash-table-size h) 2))</div><div><span style="white-space:pre-wrap"> </span> (setf (gethash i h) i))</div><div><span style="white-space:pre-wrap"> </span> (hash-table-size h))</div></div><div style="font-size:13px"><br></div><div style="font-size:13px">In ccl, this returns 75001. Lispworks 6.1 32-bit returns 100003, while sbcl returns 100000 (all on Mac OS X). This may or may not be a bug in ccl; no doubt people better qualified to judge will provide an answer to that.</div><div style="font-size:13px"><br></div><div style="font-size:13px">It may be better to simply allocate a new hash table rather than using clrhash.</div></div><div style="font-size:13px">***end quote***</div><div style="font-size:13px"><br></div><div style="font-size:13px">Note that this experiment uses EQL hash-tables, not EQUALP like I'm using, but still shows evidence of hash-table shrinking.</div><div style="font-size:13px"><br></div><div style="font-size:13px">Here's a slight modification I made to Raymond's experiment:</div><div style="font-size:13px"><div>(let ((h (make-hash-table :size 100000)))</div><div><span class="" style="white-space:pre"> </span> (dotimes (i (truncate (hash-table-size h) 2))</div><div><span class="" style="white-space:pre"> </span> (setf (gethash i h) i))</div><div><span class="" style="white-space:pre"> </span> (format t "~%before CLRHASH, hash-table-size = ~a" (hash-table-size h))</div><div><span class="" style="white-space:pre"> </span> (clrhash h)</div><div><span class="" style="white-space:pre"> </span> (format t "~%after CLRHASH, hash-table-size = ~a" (hash-table-size h))</div><div><span class="" style="white-space:pre"> </span> (dotimes (i (truncate (hash-table-size h) 2))</div><div><span class="" style="white-space:pre"> </span> (setf (gethash i h) i))</div><div><span class="" style="white-space:pre"> </span> (hash-table-size h))</div><div>CCL results:</div><div><div>before CLRHASH, hash-table-size = 100005<br></div><div>after CLRHASH, hash-table-size = 100005</div><div>75001</div></div><div><br></div><div>LispWorks results:</div><div><div>before CLRHASH, hash-table-size = 100003</div><div>after CLRHASH, hash-table-size = 100003</div><div>100003</div></div><div><br></div><div>So it seems that AFTER a CLRHASH, merely filling the hash-table approximately 1/2 full will</div><div>cause the hash-table-size to decrease in CCL, but not in LispWorks.</div></div><div style="font-size:13px"><br></div><div style="font-size:13px">Because the size of the hash-tables in these experiments is relatively small,</div><div style="font-size:13px">and because the tables are only filled 1/2 way, I'm thinking this can't be due to</div><div style="font-size:13px">heap-exhaustion. It does look like CLRHASH may be doing something possibly buggy. </div><div style="font-size:13px">What do you think?</div><div style="font-size:13px"><br></div><div style="font-size:13px">Meanwhile, for my search purposes:</div><div style="font-size:13px">Is there any way in CCL to specify a Minimum size for a hash-table??</div><div style="font-size:13px">It seems pretty annoying (to put it mildly) that rehashing might reduce the size of the table. </div><div style="font-size:13px">And the :rehash-size and :rehash-threshold don't help, and should only matter when rehashing</div><div style="font-size:13px">due to the hash-table becoming full (which it isn't in my case).</div><div style="font-size:13px"><br></div><div style="font-size:13px">Apologies for this longish post, and</div><div style="font-size:13px"><br></div><div style="font-size:13px">Thanks in advance for any light you can shed on my ignorance,</div><div style="font-size:13px"><br></div><div style="font-size:13px">--Glenn</div><div style="font-size:13px"><br></div><div style="font-size:13px"><br></div><div style="font-size:13px"><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jan 4, 2015 at 1:37 PM, Gary Byers <span dir="ltr"><<a href="mailto:gb@clozure.com" target="_blank">gb@clozure.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 01/03/2015 07:10:35 AM, Glenn Iba wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Raymond,<br>
<br>
Thanks for the quick response. Is it definitely the case, then, that a<br>
GC can trigger rehashing?<br>
</blockquote>
<br></span>
A hash table can need to be rehashed for either of two distinct reasons:<br>
1) it's "full" - the number of key/value pairs that have been added to the table exceeds some threshold that's related to the size of the table.<br>
2) some of the keys in the table are hashed by address and the GC has changed the address of one or more keys in the table, This is not related to the size of the table; it is related to the hash table's :TEST function and to the types of objects used as keys in the table.<br>
<br>
The value of the :size parameter to MAKE-HASH-TABLE doesn't have much to do with the "size" of the table after it's been rehashed (for either reason); the values of the :REHASH-SIZE and :REHASH-THRESHOLD should (and AFAIK they do.)<br>
<br>
There's a lot more that could and should be said about this, but if you're thinking that making larger hash tables will avoid rehashing because of key movement (case (2)) you're mistaken.<br>
<br>
</blockquote></div><br></div>