Author: Robert Hyatt
Date: 09:35:20 12/03/05
Go up one level in this thread
On December 03, 2005 at 09:52:21, Rolf Tueschen wrote: >On December 02, 2005 at 23:27:41, Robert Hyatt wrote: > >>On December 02, 2005 at 17:47:00, Tony Nichols wrote: >> >>>On December 02, 2005 at 17:21:59, Robert Hyatt wrote: >>> >>>>It is time to stop this now. The above is utter nonsense. We don't "search" >>>>hash tables. Larger hash tables do not take longer to search, because we just >>>>don't search them. We randomly probe into them and either hit or miss, so the >>>>size has absolutely no effect other than larger sizes hold more information >>>>without requiring that older data be overwritten sooner. >>>> >>>>You are quoting nonsense... >>> >>> >>>Hello, >>> >>> Is it safe to assume that you can't have too much hash? I mean, as long as you >>>have the ram. >>>Regards >>>Tony >> >> >>pretty much. Beyond some point additional hash will not help. But to see how >>it helps, set it to something like 384K (yes 384 k bytes) and run a position for >>say 10 minutes. Record the highest depth reached and the time to reach that >>depth. Double the hash and re-run. Keep doing this until it doesn't get any >>faster. You just reached the max needed for the 10 minute search time (10 >>minutes was just a number, pick anything you want). You will see significant >>speed improvements at first, but they begin to flatten out and eventually >>doubling the hash doesn't change a thing any further. >> >>If a program clears hash between moves (most do not) then this can be a bigger >>issue with large hashes since they do take time to clear should that be >>needed... > > >Bob, excuse me that I ask, but Chan came into CTF with the links again. I know >that if anybody you are the one for explaining the very basics of all CC >problems. I think we should seperate the verbal terminology and the underlying >tech. If you say above, I quote: > >"We randomly probe into them and either hit or miss, so the >size has absolutely no effect other than larger sizes hold more information >without requiring that older data be overwritten sooner." > >That is the key part for misunderstandings IMO. I repeat: I dont doubt what you >are having in mind when saying this but I doubt that you see what one could >interprete into that what you wrote. > >Is this your last word, I say it with my own understanding, that a small hash >doesnt take _shorter_ time to "probe" including the neccessary deletion for new >"data" than larger hash tables who as you said yourself take much longer time to >delete and? or? overwrite? The point is that we do a single probe to some point in the table. If we find something useful there, we use it, if we don't, we are done with hashing and we continue searching normally. When we finish a search at some node, we want to store the result in the hash table. We again probe to one particular entry and decide whether to overwrite that entry with our current info, of we decide the existing entry has better information than our current info and we then throw our current info away and leave the existing info. Either way, the size of the table has absolutely no impact on the speed of those two operations. What a larger table does, is allow us to keep more information, so that we don't have to make that "overwrite/discard" decision above as frequently. Because when we make such a decision, we are obviously losing what gets overwritten or discarded, and we might could use that later to speed up the search by avoiding doing the same sub-tree search again... > >The second point is the meaning of "search" vs "probe". Is it perhaps just a >misunderstanding from every day speech to tech speech. Of course it's inexact to >say "search" when you just work with a defined key definition but to say that a >program "searches" in its hash in seperating that from the calculations etc then >this is not totally wrong tto say so. But ten search here is NOT the same as >what it means when a program really "searches". - Could you please make a couple >of clarifying remarks for this general problem of two sides of the same medal, >tech speech and then average language vocabulary? I hope that then also Chan has >the feeling of having not only useless ideas. Thanks. Some think we somehow "search" through the hash table looking for a "match" of some sort. This would kill performance, and is the main point to "hashing" anyway. A probe is simply a single memory read and we either use that data or not, but we don't probe a second time... A "probe" is therefore different from a "search" (when applied to a hash table) because a search implies looking in more than one place for useful information, while in a hash table we don't do that at all for performance reasons.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.