[freetype2-demos] master 60552081 2/2: [graph] Rework cache management.

[Werner Lemberg]

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

    [graph] Rework cache management.
    
    With more complex rendering in `ftgrid`, the old cache management
    resulted in excessive clashes and slow `gblender_lookup`.  It is
    better to replace the clashing entries than to preserve them and
    search for an available spot in the table.  This saves about 10%
    of execution time in `ftgrid` without much effect on the others.
    
    * graph/gblender.c (gblender_lookup): Replace old clashing entries
    and hash function.
    (gblender_lookup_channel): Ditto.
    * graph/gblender.h (GBlenderRec): Remove `stat_clears`.
---
 graph/gblender.c | 64 +++++++++++++++++---------------------------------------
 graph/gblender.h |  1 -
 2 files changed, 19 insertions(+), 46 deletions(-)

diff --git a/graph/gblender.c b/graph/gblender.c
index 8184a494..df393797 100644
--- a/graph/gblender.c
+++ b/graph/gblender.c
@@ -169,7 +169,6 @@ gblender_init( GBlender   blender,
   blender->stat_lookups = 0;
   blender->stat_clashes = 0;
   blender->stat_keys    = 0;
-  blender->stat_clears  = 0;
 #endif
 }
 
@@ -264,40 +263,28 @@ gblender_lookup( GBlender       blender,
                  GBlenderPixel  background,
                  GBlenderPixel  foreground )
 {
-  int          idx, idx0;
-  GBlenderKey  key;
+  unsigned int  idx;
+  GBlenderKey   key;
 
 #ifdef GBLENDER_STATS
   blender->stat_hits--;
   blender->stat_lookups++;
 #endif
 
-  idx0 = ( background + foreground*63 ) & (GBLENDER_KEY_COUNT-1);
-  idx  = idx0;
-  do
-  {
-    key = blender->keys + idx;
+  idx = ( background ^ foreground * 7 ) % (GBLENDER_KEY_COUNT-1);
 
-    if ( key->cells == NULL )
-      goto NewNode;
+  key = blender->keys + idx;
 
-    if ( key->background == background &&
-         key->foreground == foreground )
-      goto Exit;
+  if ( key->cells == NULL )
+    goto NewNode;
 
-#ifdef GBLENDER_STATS
-    blender->stat_clashes++;
-#endif
-    idx = (idx+1) & (GBLENDER_KEY_COUNT-1);
-  }
-  while ( idx != idx0 );
+  if ( key->background == background &&
+       key->foreground == foreground )
+    goto Exit;
 
- /* the cache is full, clear it completely
-  */
 #ifdef GBLENDER_STATS
-  blender->stat_clears++;
+  blender->stat_clashes++;
 #endif
-  gblender_clear( blender );
 
 NewNode:
   key->background = background;
@@ -360,7 +347,7 @@ gblender_lookup_channel( GBlender      blender,
                          unsigned int  background,
                          unsigned int  foreground )
 {
-  int              idx, idx0;
+  unsigned         idx;
   unsigned short   backfore = (unsigned short)((foreground << 8) | background);
   GBlenderChanKey  key;
 
@@ -369,31 +356,19 @@ gblender_lookup_channel( GBlender      blender,
   blender->stat_lookups++;
 #endif
 
-  idx0 = ( background + foreground*17 ) & (GBLENDER_KEY_COUNT-1);
-  idx  = idx0;
-  do
-  {
-    key = (GBlenderChanKey)blender->keys + idx;
+  idx = ( background ^ foreground * 7 ) % (GBLENDER_KEY_COUNT-1);
 
-    if ( key->index < 0 )
-      goto NewNode;
+  key = (GBlenderChanKey)blender->keys + idx;
 
-    if ( key->backfore == backfore )
-      goto Exit;
+  if ( key->index < 0 )
+    goto NewNode;
 
-#ifdef GBLENDER_STATS
-    blender->stat_clashes++;
-#endif
-    idx = (idx+1) & (GBLENDER_KEY_COUNT-1);
-  }
-  while ( idx != idx0 );
+  if ( key->backfore == backfore )
+    goto Exit;
 
- /* the cache is full, clear it completely
-  */
 #ifdef GBLENDER_STATS
-  blender->stat_clears++;
+  blender->stat_clashes++;
 #endif
-  gblender_clear( blender );
 
 NewNode:
   key->backfore   = backfore;
@@ -429,7 +404,6 @@ gblender_dump_stats( GBlender  blender )
           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 );
+  printf( "  Keys used:   %ld\n", blender->stat_keys );
 }
 #endif
diff --git a/graph/gblender.h b/graph/gblender.h
index 941f9925..f5d27b69 100644
--- a/graph/gblender.h
+++ b/graph/gblender.h
@@ -109,7 +109,6 @@
     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
 
   } GBlenderRec, *GBlender;