ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

how to measure frequency of hash collisions.
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Daniel Shawul



Joined: 14 Mar 2006
Posts: 2186
Location: Ethiopia
PostPost subject: Some tests: Attn Don    Posted: Sat Jun 16, 2012 6:25 pm Reply to topic Reply with quote
marcelk wrote:
Daniel Shawul wrote:
Is there a way to directly measure the number of hash collisions (not its effect). I was thinking of storing the fen along with the hash key in transposition table entry, so that if the signatures match but the fens don't it would be collision. Is there a better way ?
Edit: Right after I write this I realized storing _two_ hash keys is better than this (one could be a string hash of the fen). If the primary keys match but the second one don't it is a collision.


You can get a good estimate by measuring the number of near-collisions.
For example, each time you have a miss, count how many of the left-most bits match (xor and look for the highest bit set, call that index 'b'). Then do count[b]++. Then make a histogram with b on one axis, and log(count[b]) on the other. You should get a linear plot once you have enough measurements. The number of false hits would be approximately count[0]/2.

There are variants on this that are essentially the same (instead of xor use substraction, or count hamming distance, or count right-most match etc)

Thanks for the suggestion. I think that will be a good way to measure for PRNG generated hash keys when collisions are very rare. Because of that it may better to test for similarity of keys...

I did a quick test over the forumulas we have been examining and the collision rate is embarassing :(The keys differ in a subtle way and they look good visually but there are many collisions.
FNV-1 => 25000 collisions/sec
FNV-1a => 15 collisions/sec
The one I suggested with a rotate & multiply => 1600 collisions/sec !!
Code:

const U64 C1 = U64(0x109951162821a737);
   U64 h = U64(0xeadf018b615d3be8);
   h = (h << sq) ^ (h >> (64 - sq));
   h *= C1;
   h = (h << cp) ^ (h >> (64 - cp));
   return h;

I changed the third line to
Code:
h += C1

and collions dropped to => 0 collions/second so far...
Visual inspection is definately misleading. And the power of additions is revealed again Wink

More later
_________________
https://sites.google.com/site/dshawul/
https://github.com/dshawul
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
Display posts from previous:   
Subject Author Date/Time
how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 4:45 pm
      Re: how to measure frequency of hash collisions. Marcel van Kervinck Sat Jun 16, 2012 5:25 pm
            Some tests: Attn Don Daniel Shawul Sat Jun 16, 2012 6:25 pm
                  Re: Some tests: Attn Don Daniel Shawul Sat Jun 16, 2012 7:15 pm
      Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 9:17 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:05 pm
                  Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 10:23 pm
                        Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 10:29 pm
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 11:06 pm
                              Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 11:39 pm
                                    Re: how to measure frequency of hash collisions. Kevin Hearn Sat Jun 16, 2012 11:50 pm
                                          Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 12:08 am
                                          Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 12:40 am
                                    Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 11:54 pm
                                          Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 12:23 am
                                    Re: how to measure frequency of hash collisions. Marcel van Kervinck Sun Jun 17, 2012 7:55 am
                  Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 1:26 am
      Re: how to measure frequency of hash collisions. Ed Schroder Sat Jun 16, 2012 9:36 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:01 pm
      Re: how to measure frequency of hash collisions. H.G.Muller Sat Jun 16, 2012 10:12 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:31 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 2:00 am
                  Re: how to measure frequency of hash collisions. Rémi Coulom Sun Jun 17, 2012 8:30 am
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 10:49 am
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 2:58 pm
                              Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 3:41 pm
                                    Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 5:58 pm
                                          Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 9:06 pm
                                                Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 9:57 pm
      Re: how to measure frequency of hash collisions. Lucas Braesch Sun Jun 17, 2012 3:02 am
            Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 3:08 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 6:12 pm
                  Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 9:14 pm
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 10:01 pm
      Re: how to measure frequency of hash collisions. Joshua Shriver Wed Jun 20, 2012 8:45 pm
            Re: how to measure frequency of hash collisions. Ronald de Man Wed Jun 20, 2012 10:44 pm
                  Re: how to measure frequency of hash collisions. Joshua Shriver Thu Jun 21, 2012 1:51 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads