[freetype2-demos] master ecaa799: [graph] Count the number of hash clashes.

[Werner Lemberg]

branch: master
commit ecaa7996f0aeb40618e4fc83d70858d631561d50
Author: Alexei Podtelezhnikov <apodtele@gmail.com>
Commit: Alexei Podtelezhnikov <apodtele@gmail.com>

    [graph] Count the number of hash clashes.
    
    The hash table lookups take very noticeable time when rendering is
    complex like in `ftgrid`.  This can help optimize the hash function.
    
    * graph/gblender.h (GBLENDER_STATS): New field for clashes.
    * graph/gblender.c (gblender_init, gblender_lookup{,_channel},
    gblender_dump_stats): Initialize, collect, and report clashes.
---
 graph/gblender.c | 8 ++++++++
 graph/gblender.h | 1 +
 2 files changed, 9 insertions(+)

diff --git a/graph/gblender.c b/graph/gblender.c
index 1ce404b..a26fb83 100644
--- a/graph/gblender.c
+++ b/graph/gblender.c
@@ -167,6 +167,7 @@ gblender_init( GBlender   blender,
 #ifdef GBLENDER_STATS
   blender->stat_hits    = 0;
   blender->stat_lookups = 0;
+  blender->stat_clashes = 0;
   blender->stat_keys    = 0;
   blender->stat_clears  = 0;
 #endif
@@ -308,6 +309,9 @@ NewNode:
 #endif
 
 Exit:
+#ifdef GBLENDER_STATS
+  blender->stat_clashes += ( idx - idx0 ) & (GBLENDER_KEY_COUNT-1);
+#endif
   return  key->cells;
 }
 
@@ -399,6 +403,9 @@ NewNode:
 #endif
 
 Exit:
+#ifdef GBLENDER_STATS
+  blender->stat_clashes += ( idx - idx0 ) & (GBLENDER_KEY_COUNT-1);
+#endif
   return  (unsigned char*)blender->cells + key->index;
 }
 
@@ -421,6 +428,7 @@ gblender_dump_stats( GBlender  blender )
                    blender->stat_lookups,
           blender->stat_lookups - blender->stat_keys,
           blender->stat_lookups );
+  printf( "  Clashes:     %ld\n", blender->stat_clashes );
   printf( "  Keys used:   %ld\n  Caches full: %ld\n",
           blender->stat_keys, blender->stat_clears );
 }
diff --git a/graph/gblender.h b/graph/gblender.h
index 1dd72b6..941f992 100644
--- a/graph/gblender.h
+++ b/graph/gblender.h
@@ -107,6 +107,7 @@
 #ifdef GBLENDER_STATS
     long                  stat_hits;    /* number of direct hits             */
     long                  stat_lookups; /* number of table lookups           */
+    long                  stat_clashes; /* number of table clashes           */
     long                  stat_keys;    /* number of table key recomputation */
     long                  stat_clears;  /* number of table clears            */
 #endif