Bug hunting or How many bits is enough?

[Michael Sherwin]

Doesn't sound entirely wrong. Previously entry A mapped to the same location as entries B, C and D (etc), but now it has to fight against being replaced by positions B', C' and D'. Depending on the overload factor, this leads to completely different hash contents.

How big was the table?

#define POSMASK 0x1ffffe

[Michael Sherwin]

Okay guys, sofar my testing indicates:

* increasing hash size has no effect on performance

* using a good 64 bit random function and generating the 64 bit hash values all at once is not better than using a bad random function and generating the bits one by one

* using either good or bad random methods to fill the hash values while also increasing the number of bits to 96 did increase performance equally and noticeably.

*going to 96 bits does not increase the storage requirement of the hash very much and barely effects the node rate.

So unless I can actually find a bug in my code somewhere, I am staying with 96 bits for now as it hardly has a cost.

Thanks everyone!

[Tony Thomas]

Okay guys, sofar my testing indicates:

* increasing hash size has no effect on performance

* using a good 64 bit random function and generating the 64 bit hash values all at once is not better than using a bad random function and generating the bits one by one

* using either good or bad random methods to fill the hash values while also increasing the number of bits to 96 did increase performance equally and noticeably.

*going to 96 bits does not increase the storage requirement of the hash very much and barely effects the node rate.

So unless I can actually find a bug in my code somewhere, I am staying with 96 bits for now as it hardly has a cost.

Thanks everyone!

The hash size increase doesnt show improvements on your computer (or mine) probably because some people here have Grandmas who got faster computers. I think you should let the user adjust the hashsize via a commandline of some sort..May I suggest -h64 ??

[Harald Johnsen]

*going to 96 bits does not increase the storage requirement of the hash very much and barely effects the node rate.

So unless I can actually find a bug in my code somewhere, I am staying with 96 bits for now as it hardly has a cost.

Thanks everyone!

This is not serious. You did not even count your number of collisions.

You showed no correlation between the number of bits in your hash key and the results of your engine, so why is 96 better than 64 or 32 ?

HJ.

[Michael Sherwin]

*going to 96 bits does not increase the storage requirement of the hash very much and barely effects the node rate.

So unless I can actually find a bug in my code somewhere, I am staying with 96 bits for now as it hardly has a cost.

Thanks everyone!

This is not serious. You did not even count your number of collisions.

You showed no correlation between the number of bits in your hash key and the results of your engine, so why is 96 better than 64 or 32 ?

HJ.

I was just deciding for myself based on results that I am getting. I leave the serious investigation to the scientist. I am just a lay person that taught himself how to program by writing a chess program. And I did say that it was just "for now" that I would stay with 96 bits, didn't I? Your criticism is unwarented.

We need to split this programming forum into two. One for smart people like you and one for idiots like me!

[Harald Johnsen]

I was perhaps a bit abrupt in my post and I'm sorry for that but my question was honest because I'm interested in the answer.

Hash tables is not an easy subject (at least for me) so I think that I'm in the idiot category too

HJ.

[Michael Sherwin]

I was perhaps a bit abrupt in my post and I'm sorry for that but my question was honest because I'm interested in the answer.

Hash tables is not an easy subject (at least for me) so I think that I'm in the idiot category too

HJ.

Hi Harald,

Thanks!

I wish that I had the time to be a scientist. But right now, I have to leave that for others. My testing shows that there is no downside to going to 96 bits, so I might as well.

[Fritz Grau]

For example, if you have 4 million hash table entries then you have 24+32 = 56 bits (because the low 24 bits are totally redundant -> only a value with those 24 bits matching would have been stored in that slot). The odds of a hash collision are therefore one in 2^56=72,057,594,037,927,936
If you search 10 million NPS then you will have one collision every 7205759403.8 seconds = one collision every 83400 days = one every 228 years.

I guess that something else was the problem.

Your first statement is correct: The odds of one hash collision is only 2^(-56). However, if you search more nodes, the expected number of collisions does not grow linearly in the number of nodes searched, but (for small numbers of nodes) roughly quadratic because collisions can occur between any pair of hashed positions. This somewhat counterintuitive effect is explained in the Wikipedia article http://en.wikipedia.org/wiki/Birthday_problem.

[H.G.Muller]

The easiest way to correctlly treat the problem is to note that in any slot there will be 4 entries waiting, and each of them will offer you a 1:2^32 probability for a false hir if you store a 32-bit signature. So you get a mixup evry 1G probes, i.e. once every 1000 sec if you run at 1M nps.