freetype-commit
[Top][All Lists]
Advanced
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Git][freetype/freetype][ftc_resize] [cache] Revise the dynamic hash tab

From: Alexei Podtelezhnikov (@apodtele)
Subject: [Git][freetype/freetype][ftc_resize] [cache] Revise the dynamic hash table accounting.
Date: Thu, 11 May 2023 03:27:59 +0000

Alexei Podtelezhnikov pushed to branch ftc_resize at FreeType / FreeType

Commits:

  • af7a92d0
    by Alexei Podtelezhnikov at 2023-05-10T23:26:01-04:00 
    [cache] Revise the dynamic hash table accounting.

Instead of counting entries relative to the middle of the hash table,
this switches to the absolute counter with the full index range mask.
As a result, some calculations become a bit simpler.

* src/cache/ftccache.h (FTC_NODE_TOP_FOR_HASH): Revised.
* src/cache/ftccache.c (ftc_get_top_node_for_hash): Ditto.
(ftc_cache_resize): Simplify the flow.
(ftc_cache_init): Stop over-allocating initially.
(FTC_Cache_Clear, FTC_Cache_RemoveFaceID): Updated accordingly.

2 changed files:

Changes:

  • src/cache/ftccache.c
    ... ... @@ -94,8 +94,8 @@
    94 94
    95 95
    96 96 
         idx = hash & cache->mask;
    97 
    -    if ( idx < cache->p )
    98 
    -      idx = hash & ( 2 * cache->mask + 1 );
    97 
    +    if ( idx >= cache->p )
    98 
    +      idx = hash & ( cache->mask >> 1 );
    99 99
    100 100 
         return cache->buckets + idx;
    101 101 
       }
    ... ... @@ -113,9 +113,9 @@
    113 113 
         for (;;)
    114 114 
         {
    115 115 
           FTC_Node  node, *pnode;
    116 
    -      FT_UFast  p     = cache->p;
    117 
    -      FT_UFast  mask  = cache->mask;
    118 
    -      FT_UFast  count = mask + p + 1;    /* number of buckets */
    116 
    +      FT_UFast  p    = cache->p;
    117 
    +      FT_UFast  size = cache->mask + 1;  /* available size */
    118 
    +      FT_UFast  half = size >> 1;
    119 119
    120 120
    121 121 
           /* do we need to expand the buckets array? */
    ... ... @@ -127,20 +127,22 @@
    127 127 
             /* try to expand the buckets array _before_ splitting
    128 128 
              * the bucket lists
    129 129 
              */
    130 
    -        if ( p >= mask )
    130 
    +        if ( p == size )
    131 131 
             {
    132 132 
               FT_Memory  memory = cache->memory;
    133 133 
               FT_Error   error;
    134 134
    135 135
    136 136 
               /* if we can't expand the array, leave immediately */
    137 
    -          if ( FT_RENEW_ARRAY( cache->buckets,
    138 
    -                               ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) )
    137 
    +          if ( FT_QRENEW_ARRAY( cache->buckets, size, size * 2 ) )
    139 138 
                 break;
    139 
    +
    140 
    +          cache->mask = 2 * size - 1;
    141 
    +          half        = size;
    140 142 
             }
    141 143
    142 
    -        /* split a single bucket */
    143 
    -        pnode = cache->buckets + p;
    144 
    +        /* the bucket to split */
    145 
    +        pnode = cache->buckets + p - half;
    144 146
    145 147 
             for (;;)
    146 148 
             {
    ... ... @@ -148,7 +150,7 @@
    148 150 
               if ( !node )
    149 151 
                 break;
    150 152
    151 
    -          if ( node->hash & ( mask + 1 ) )
    153 
    +          if ( node->hash & half )
    152 154 
               {
    153 155 
                 *pnode     = node->link;
    154 156 
                 node->link = new_list;
    ... ... @@ -158,56 +160,50 @@
    158 160 
                 pnode = &node->link;
    159 161 
             }
    160 162
    161 
    -        cache->buckets[p + mask + 1] = new_list;
    163 
    +        cache->buckets[p] = new_list;
    162 164
    163 165 
             cache->slack += FTC_HASH_MAX_LOAD;
    166 
    +        cache->p      = p + 1;
    164 167
    165 
    -        if ( p >= mask )
    166 
    -        {
    167 
    -          cache->mask = 2 * mask + 1;
    168 
    -          cache->p    = 0;
    169 
    -        }
    170 
    -        else
    171 
    -          cache->p = p + 1;
    168 
    +        FT_TRACE2(( "ftc_cache_resize: cache %u increased to %u hashes\n",
    169 
    +                    cache->index, cache->p ));
    172 170 
           }
    173 171
    174 172 
           /* do we need to shrink the buckets array? */
    175 
    -      else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
    173 
    +      else if ( cache->slack > (FT_Long)p * FTC_HASH_SUB_LOAD )
    176 174 
           {
    177 
    -        FT_UFast   old_index = p + mask;
    178 
    -        FTC_Node*  pold;
    175 
    +        FTC_Node  old_list = cache->buckets[--p];
    179 176
    180 177
    181 
    -        if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
    178 
    +        if ( p < FTC_HASH_INITIAL_SIZE )
    182 179 
               break;
    183 180
    184 
    -        if ( p == 0 )
    181 
    +        if ( p == half )
    185 182 
             {
    186 183 
               FT_Memory  memory = cache->memory;
    187 184 
               FT_Error   error;
    188 185
    189 186
    190 187 
               /* if we can't shrink the array, leave immediately */
    191 
    -          if ( FT_QRENEW_ARRAY( cache->buckets,
    192 
    -                               ( mask + 1 ) * 2, mask + 1 ) )
    188 
    +          if ( FT_QRENEW_ARRAY( cache->buckets, size, half ) )
    193 189 
                 break;
    194 190
    195 
    -          cache->mask >>= 1;
    196 
    -          p             = cache->mask;
    191 
    +          cache->mask = half - 1;
    197 192 
             }
    198 
    -        else
    199 
    -          p--;
    200 193
    201 
    -        pnode = cache->buckets + p;
    194 
    +        /* the bucket to merge */
    195 
    +        pnode = cache->buckets + p - half;
    196 
    +
    202 197 
             while ( *pnode )
    203 198 
               pnode = &(*pnode)->link;
    204 199
    205 
    -        pold   = cache->buckets + old_index;
    206 
    -        *pnode = *pold;
    207 
    -        *pold  = NULL;
    200 
    +        *pnode = old_list;
    208 201
    209 202 
             cache->slack -= FTC_HASH_MAX_LOAD;
    210 203 
             cache->p      = p;
    204 
    +
    205 
    +        FT_TRACE2(( "ftc_cache_resize: cache %u decreased to %u hashes\n",
    206 
    +                    cache->index, cache->p ));
    211 207 
           }
    212 208
    213 209 
           /* otherwise, the hash table is balanced */
    ... ... @@ -336,11 +332,11 @@
    336 332 
         FT_Error   error;
    337 333
    338 334
    339 
    -    cache->p     = 0;
    335 
    +    cache->p     = FTC_HASH_INITIAL_SIZE;
    340 336 
         cache->mask  = FTC_HASH_INITIAL_SIZE - 1;
    341 337 
         cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;
    342 338
    343 
    -    FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 );
    339 
    +    FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE );
    344 340 
         return error;
    345 341 
       }
    346 342
    ... ... @@ -351,11 +347,9 @@
    351 347 
         if ( cache && cache->buckets )
    352 348 
         {
    353 349 
           FTC_Manager  manager = cache->manager;
    350 
    +      FT_UFast     count   = cache->p;
    354 351 
           FT_UFast     i;
    355 
    -      FT_UFast     count;
    356 
    -
    357 352
    358 
    -      count = cache->p + cache->mask + 1;
    359 353
    360 354 
           for ( i = 0; i < count; i++ )
    361 355 
           {
    ... ... @@ -562,12 +556,12 @@
    562 556 
       FTC_Cache_RemoveFaceID( FTC_Cache   cache,
    563 557 
                               FTC_FaceID  face_id )
    564 558 
       {
    565 
    -    FT_UFast     i, count;
    566 559 
         FTC_Manager  manager = cache->manager;
    567 560 
         FTC_Node     frees   = NULL;
    561 
    +    FT_UFast     count   = cache->p;
    562 
    +    FT_UFast     i;
    568 563
    569 564
    570 
    -    count = cache->p + cache->mask + 1;
    571 565 
         for ( i = 0; i < count; i++ )
    572 566 
         {
    573 567 
           FTC_Node*  pnode = cache->buckets + i;

  • src/cache/ftccache.h
    ... ... @@ -73,10 +73,10 @@ FT_BEGIN_HEADER
    73 73 
     #define FTC_NODE_PREV( x )  FTC_NODE( (x)->mru.prev )
    74 74
    75 75 
     #ifdef FTC_INLINE
    76 
    -#define FTC_NODE_TOP_FOR_HASH( cache, hash )                      \
    77 
    -        ( ( cache )->buckets +                                    \
    78 
    -            ( ( ( ( hash ) &   ( cache )->mask ) < ( cache )->p ) \
    79 
    -              ? ( ( hash ) & ( ( cache )->mask * 2 + 1 ) )        \
    76 
    +#define FTC_NODE_TOP_FOR_HASH( cache, hash )                       \
    77 
    +        ( ( cache )->buckets +                                     \
    78 
    +            ( ( ( ( hash ) &   ( cache )->mask ) >= ( cache )->p ) \
    79 
    +              ? ( ( hash ) & ( ( cache )->mask >> 1 ) )            \
    80 80 
                   : ( ( hash ) &   ( cache )->mask ) ) )
    81 81 
     #else
    82 82 
       FT_LOCAL( FTC_Node* )
    ... ... @@ -142,8 +142,8 @@ FT_BEGIN_HEADER
    142 142 
       /* each cache really implements a dynamic hash table to manage its nodes */
    143 143 
       typedef struct  FTC_CacheRec_
    144 144 
       {
    145 
    -    FT_UFast           p;
    146 
    -    FT_UFast           mask;
    145 
    +    FT_UFast           p;           /* hash table counter     */
    146 
    +    FT_UFast           mask;        /* hash table index range */
    147 147 
         FT_Long            slack;
    148 148 
         FTC_Node*          buckets;
    149 149

    • —
    View it on GitLab.
    You're receiving this email because of your account on gitlab.freedesktop.org. Manage all notifications · Help

    reply via email to
    [Prev in Thread] Current Thread [Next in Thread]