"Anders Thulin" wrote in message
...
Guest wrote:
The only overhead is:
HashIndex = Hash % TableSize;
and later:
All four cases behave the same regardless of table size.
No, there's more to it. You show it yourself when you say:
1) Check one entry.
2) Check two entries.
no further overhead here, true, except that the second may
increase code space, and so cause other kinds of overhead.
If it's implemented as a 1..2 loop, there is obviously
counting overhead.
Say what???
A loop, if you did it that way, would only cost a few cycles. Say 10
cycles.
An access to main memory, which is essentially a random access at full cost,
will cost at least 200 cycles or even up to 400 cycles. Yeah, main memory
is very expensive!
Is an extra 10 cycles really significant?
And that has *nothing* to do whether you are using 32m, 128m or even 1.5g of
memory.
That's an implementation detail of how you choose to implement the hash
table. It will be a constant and will not be influenced by how big the hash
table is. Which is what the original question was.... Which was whether he
should go ahead and use 1536m or stay with 512m.
3) Check one hash line, which may contain two or more entries.
and here you have (I presume) a bucket search, which may be more
Why a bucket search?? Due to cache line sizes (the only reason to do this
kind of hash organization), you'll only have 2 or almost certainly no more
than 4 entries. No need for any fancy search when a straight comparison
will do fine.
Don't go trying to make things more complex than you need to.
or less complex depending on how you implement it. I don't see how
you can claim no overhead in this situation.
I'm not claiming no overhead for how the hash table is implemented. I'm
claiming there would be no additional overhead (or penalty) if you increase
your cache size from 512m to 1.5g, which is what the original question was.
It's even what the thread subject says... "hash table size". Not "hash
table implementation cost".
Go read the original message.
I'll save you the trouble and quote it here...
***
How large should the hash table size be?
The large the better?
Or is 1536 MB wasting hash memory?
And is 512 MB enough?
***
Again, his question wasn't about how to implement it. Whether one method
was better than the other or easier or whatever.
It was how much memory was enough. Whether using his whole 1.5g available
memory was a waste or whether he should cut it back to just 512m.
4) One small table and one large table.
But why stop there? The table is not static -- you don't only
do searches. You also have to insert new stuff, and weed out old.
In the single entry case, it's easy, but in the bucket hash it
tends to get hairy: a fast search usually means a slow insert.
Which will be a constant cost regardless of how big the hash is.
Which is what the original question was.
Now all that adds up: code has to execute to search the table,
code hash to execute to change the table. As long as that code
executes faster than the code the hash replaces, all is fine. But
does it? If the hash table is poorly implemented, you may turn
You are talking more about bugs etc. than what the original question was
about.
out to have a bucket hash with linear searches of the buckets,
and one that resizes by increasing bucket chain length only.
I've seen those in actual use -- and turned out by professional
programmers, too.
It doesn't matter one whit what theory says, if the programmer
didn't do a good job implementing it.
And how is that at all relevant to the original question?
In this particular case, we don't have a single clue to what code
base the question applies to. I assume it applies to code base,
Assuming his hash table isn't out right broken, and assuming he hasn't gone
out of his way to implement it in an idiotic maner, then the cost of the
accessing the hash entry in main memory will be larger than all the other
mainenance costs.
So, as long as his hash table manages to work, and do the job it's designed
for, it will be saving move generation costs, reducing the search bounds,
which makes the tree smaller which cuts out evals and move gens and
q-searches, etc...
So it really all comes down to:
1) Asuming his table isn't broken.
2) Asuming his table wasn't deliberately designed to be inefficient at large
memory sizes
3) the implementation details will effect the performance of the hash table
(ie: hit rate)
4) the cost of actually maintaining the table will be constant (for whatever
method he chooses) regardless of table size.
5) then it all comes down to his original question...
How about that.
Even after going through your totally off subject stuff, it all still comes
down to his original question...
Whether it was a waste of memory to use his full 1.5g of available memory or
just cut it down to 512m.
Unless your next message actually talks about the original subject (which is
also what the subject header says), I wont be replying to any more of your
trolling.
If you want to start a brand new thread that talks about implementation
ideas and methods and the overheads involved with each, and so on, then I
might be willing to read and participate in that discussion. Although
actually, it would be much more convenient to do this over at the TalkChess
forum. That's where the major chess programmers are. That way you could
get the feedback from dozens of chess programmers with 10 or 20 or more
years experience. I don't go there every day, but I'm sure there are many
others that would be willing to immediately discuss implementation issues.
But if you keep trying to change the meaning of the original question in
this thread.... bye.
of course -- if the question is purely theoretical, one of the
standard books on search algorithms will probably be the best source for
a reply.
--
Anders Thulin anders*thulin.name http://www.anders.thulin.name/