VirtualBox

Changeset 1829 in kBuild for trunk/src/kmk/variable.c


Ignore:
Timestamp:
Oct 11, 2008 10:09:43 AM (16 years ago)
Author:
bird
Message:

kmk: variable hash hacking. (yet again)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/kmk/variable.c

    r1827 r1829  
    110110#  define inline _inline
    111111typedef signed int int32_t;
    112 typedef signed short int int16_t;
    113112# endif
    114113static inline unsigned long variable_hash_2i(register const char *var, register int length)
    … …  
    340339}
    341340
     341#ifndef VARIABLE_HASH
    342342static int
    343343variable_hash_cmp (const void *xv, const void *yv)
    … …  
    348348  if (result)
    349349    return result;
    350 #ifdef VARIABLE_HASH
    351 #ifdef VARIABLE_HASH_STRICT /* bird */
     350  return_STRING_N_COMPARE (x->name, y->name, x->length);
     351}
     352#else /* VARIABLE_HASH */
     353
     354# ifdef __GNUC__
     355#  define PREDICT_TRUE(expr)  __builtin_expect(!!(expr), 1)
     356#  define PREDICT_FALSE(expr) __builtin_expect(!!(expr), 0)
     357# else
     358#  define PREDICT_TRUE(expr)  (expr)
     359#  define PREDICT_FALSE(expr) (expr)
     360# endif
     361
     362inline static int
     363variable_hash_cmp_2_memcmp (const char *xs, const char *ys, unsigned int length)
     364{
     365  /* short string compare - ~50% of the kBuild calls. */
     366  assert ( !((size_t)ys & 3) );
     367  if (!((size_t)xs & 3))
     368    {
     369      /* aligned */
     370      int result;
     371      switch (length)
     372        {
     373          case 8:
     374              result  = *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
     375              result |= *(int32_t*)xs - *(int32_t*)ys;
     376              return result;
     377          case 7:
     378              result  = xs[6] - ys[6];
     379              result |= xs[5] - ys[5];
     380              result |= xs[4] - ys[4];
     381              result |= *(int32_t*)xs - *(int32_t*)ys;
     382              return result;
     383          case 6:
     384              result  = xs[5] - ys[5];
     385              result |= xs[4] - ys[4];
     386              result |= *(int32_t*)xs - *(int32_t*)ys;
     387              return result;
     388          case 5:
     389              result  = xs[4] - ys[4];
     390              result |= *(int32_t*)xs - *(int32_t*)ys;
     391              return result;
     392          case 4:
     393              return *(int32_t*)xs - *(int32_t*)ys;
     394          case 3:
     395              result  = xs[2] - ys[2];
     396              result |= xs[1] - ys[1];
     397              result |= xs[0] - ys[0];
     398              return result;
     399          case 2:
     400              result  = xs[1] - ys[1];
     401              result |= xs[0] - ys[0];
     402              return result;
     403          case 1:
     404              return *xs - *ys;
     405          case 0:
     406              return 0;
     407        }
     408    }
     409  else
     410    {
     411      /* unaligned */
     412      int result = 0;
     413      switch (length)
     414        {
     415          case 8: result |= xs[7] - ys[7];
     416          case 7: result |= xs[6] - ys[6];
     417          case 6: result |= xs[5] - ys[5];
     418          case 5: result |= xs[4] - ys[4];
     419          case 4: result |= xs[3] - ys[3];
     420          case 3: result |= xs[2] - ys[2];
     421          case 2: result |= xs[1] - ys[1];
     422          case 1: result |= xs[0] - ys[0];
     423          case 0:
     424              return result;
     425        }
     426    }
     427
     428  /* memcmp for longer strings */
     429# ifdef __GNUC__
     430  return __builtin_memcmp (xs, ys, length);
     431# else
     432  return memcmp (xs, ys, length);
     433# endif
     434}
     435
     436inline static int
     437variable_hash_cmp_2_inlined (const char *xs, const char *ys, unsigned int length)
     438{
     439  assert ( !((size_t)ys & 3) );
     440  if (!((size_t)xs & 3))
     441    {
     442      int result;
     443      /* aligned */
     444      while (length >= 8)
     445        {
     446          result  = *(int32_t*)xs - *(int32_t*)ys;
     447          result |= *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
     448          if (PREDICT_FALSE(result))
     449            return result;
     450          xs += 8;
     451          ys += 8;
     452          length -= 8;
     453        }
     454      switch (length)
     455        {
     456          case 7:
     457              result  = *(int32_t*)xs - *(int32_t*)ys;
     458              result |= xs[6] - ys[6];
     459              result |= xs[5] - ys[5];
     460              result |= xs[4] - ys[4];
     461              return result;
     462          case 6:
     463              result  = *(int32_t*)xs - *(int32_t*)ys;
     464              result |= xs[5] - ys[5];
     465              result |= xs[4] - ys[4];
     466              return result;
     467          case 5:
     468              result  = *(int32_t*)xs - *(int32_t*)ys;
     469              result |= xs[4] - ys[4];
     470              return result;
     471          case 4:
     472              return *(int32_t*)xs - *(int32_t*)ys;
     473          case 3:
     474              result  = xs[2] - ys[2];
     475              result |= xs[1] - ys[1];
     476              result |= xs[0] - ys[0];
     477              return result;
     478          case 2:
     479              result  = xs[1] - ys[1];
     480              result |= xs[0] - ys[0];
     481              return result;
     482          case 1:
     483              return *xs - *ys;
     484          default:
     485          case 0:
     486              return 0;
     487        }
     488    }
     489  else
     490    {
     491      /* unaligned */
     492      int result;
     493      while (length >= 8)
     494        {
     495#if defined(__i386__) || defined(__x86_64__)
     496          result  = (  ((int32_t)xs[3] << 24)
     497                     | ((int32_t)xs[2] << 16)
     498                     | ((int32_t)xs[1] <<  8)
     499                     |           xs[0]       )
     500                  - *(int32_t*)ys;
     501          result |= (  ((int32_t)xs[7] << 24)
     502                     | ((int32_t)xs[6] << 16)
     503                     | ((int32_t)xs[5] <<  8)
     504                     |           xs[4]       )
     505                  - *(int32_t*)(ys + 4);
     506#else
     507          result  = xs[3] - ys[3];
     508          result |= xs[2] - ys[2];
     509          result |= xs[1] - ys[1];
     510          result |= xs[0] - ys[0];
     511          result |= xs[7] - ys[7];
     512          result |= xs[6] - ys[6];
     513          result |= xs[5] - ys[5];
     514          result |= xs[4] - ys[4];
     515#endif
     516          if (PREDICT_FALSE(result))
     517            return result;
     518          xs += 8;
     519          ys += 8;
     520          length -= 8;
     521        }
     522      result = 0;
     523      switch (length)
     524        {
     525          case 7: result |= xs[6] - ys[6];
     526          case 6: result |= xs[5] - ys[5];
     527          case 5: result |= xs[4] - ys[4];
     528          case 4: result |= xs[3] - ys[3];
     529          case 3: result |= xs[2] - ys[2];
     530          case 2: result |= xs[1] - ys[1];
     531          case 1: result |= xs[0] - ys[0];
     532              return result;
     533          default:
     534          case 0:
     535              return 0;
     536        }
     537    }
     538}
     539
     540inline static int
     541variable_hash_cmp (const void *xv, const void *yv)
     542{
     543  struct variable const *x = (struct variable const *) xv;
     544  struct variable const *y = (struct variable const *) yv;
     545  int result;
     546
     547# ifdef VARIABLE_HASH_STRICT
    352548  if (x->hash1 != variable_hash_1i (x->name, x->length))
    353549    __asm__("int3");
    … …  
    358554  if (y->hash2 && y->hash2 != variable_hash_2i (y->name, y->length))
    359555    __asm__("int3");
    360 #endif
    361   /* hash 1 */
    362   result = x->hash1 - y->hash1;
    363   if (result)
     556# endif /* VARIABLE_HASH_STRICT */
     557
     558  /* hash 1 & length */
     559  result = (x->hash1 - y->hash1)
     560         | (x->length - y->length);
     561  if (PREDICT_TRUE(result))
    364562    return result;
    365 #endif
    366 #ifdef CONFIG_WITH_OPTIMIZATION_HACKS /* bird: speed */
    367   {
    368     const char *xs = x->name;
    369     const char *ys = y->name;
    370     switch (x->length)
    371       {
    372         case 8:
    373             result = *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
    374             if (result)
    375               return result;
    376             return *(int32_t*)xs - *(int32_t*)ys;
    377         case 7:
    378             result = xs[6] - ys[6];
    379             if (result)
    380                 return result;
    381         case 6:
    382             result = *(int32_t*)xs - *(int32_t*)ys;
    383             if (result)
    384                 return result;
    385             return *(int16_t*)(xs + 4) - *(int16_t*)(ys + 4);
    386         case 5:
    387             result = xs[4] - ys[4];
    388             if (result)
    389                 return result;
    390         case 4:
    391             return *(int32_t*)xs - *(int32_t*)ys;
    392         case 3:
    393             result = xs[2] - ys[2];
    394             if (result)
    395                 return result;
    396         case 2:
    397             return *(int16_t*)xs - *(int16_t*)ys;
    398         case 1:
    399             return *xs - *ys;
    400         case 0:
    401             return 0;
    402       }
    403   }
    404 #endif /* CONFIG_WITH_OPTIMIZATION_HACKS */
    405 #ifdef VARIABLE_HASH
    406   /* hash 2 */
    407   if (!x->hash2)
    408     ((struct variable *)x)->hash2 = variable_hash_2i (x->name, x->length);
    409   if (!y->hash2)
    410     ((struct variable *)y)->hash2 = variable_hash_2i (y->name, y->length);
    411   result = x->hash2 - y->hash2;
    412   if (result)
    413     return result;
    414 #endif
    415 #ifdef CONFIG_WITH_OPTIMIZATION_HACKS
    416   return memcmp (x->name, y->name, x->length);
    417 #else
    418   return_STRING_N_COMPARE (x->name, y->name, x->length);
    419 #endif
    420 }
     563
     564# if 0 /* too few hits at this point. */
     565  /* hash 2, but only if X has it since lookup_variable will give us an X
     566     which resides on the stack and which result will be lost to us. */
     567  if (x->hash2)
     568    {
     569      if (!y->hash2)
     570        ((struct variable *)y)->hash2 = variable_hash_2i (y->name, y->length);
     571      result = x->hash2 - y->hash2;
     572      if (result)
     573        return result;
     574    }
     575# endif
     576
     577# if 0
     578  return variable_hash_cmp_2_memcmp(x->name, y->name, x->length);
     579# else
     580  return variable_hash_cmp_2_inlined(x->name, y->name, x->length);
     581# endif
     582}
     583#endif /* VARIABLE_HASH */
    421584
    422585#ifndef VARIABLE_BUCKETS
    … …  
    740903# ifdef VARIABLE_HASH_STRICT /* bird */
    741904                  struct variable *v2 = (struct variable *) hash_find_item ((struct hash_table *) &setlist->set->table, &var_key);
    742                   assert(v2 == v);
     905                  assert (v2 == v);
    743906# endif
    744907                  return v->special ? handle_special_var (v) : v;
Note: See TracChangeset for help on using the changeset viewer.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette