Changeset 430 for trunk/src/gmake

Timestamp:

Mar 26, 2006, 2:40:00 PM (19 years ago)

Author:

bird

Message:

better hashing, more inline string stuff. (still optimizing libc)

Location:

trunk/src/gmake

Files:

• Makefile.kmk (modified) (1 diff)
• make.h (modified) (1 diff)
• variable.c (modified) (9 diffs)
• variable.h (modified) (1 diff)

trunk/src/gmake/Makefile.kmk

@@ -21 +21 @@
         CONFIG_NO_DEFAULT_SUFFIX_RULES \
         CONFIG_NO_DEFAULT_VARIABLES \
-        KMK
+        KMK \
+        VARIABLE_HASH
         
         

trunk/src/gmake/make.h

@@ -606 +606 @@
                                while (((_v)=_c)==0 && errno==EINTR); }while(0)
 
+#ifdef __EMX__ /* saves 40-100ms on libc. */
+#undef strchr
+#define strchr(s, c) \
+  (__extension__ (__builtin_constant_p (c)                                    \
+                  ? ((c) == '\0'                                              \
+                     ? (char *) __rawmemchr ((s), (c))                        \
+                     : __strchr_c ((s), ((c) & 0xff) << 8))                   \
+                  : __strchr_g ((s), (c))))
+static inline char *__strchr_c (const char *__s, int __c)
+{
+  register unsigned long int __d0;
+  register char *__res;
+  __asm__ __volatile__
+    ("1:\n\t"
+     "movb      (%0),%%al\n\t"
+     "cmpb      %%ah,%%al\n\t"
+     "je        2f\n\t"
+     "leal      1(%0),%0\n\t"
+     "testb     %%al,%%al\n\t"
+     "jne       1b\n\t"
+     "xorl      %0,%0\n"
+     "2:"
+     : "=r" (__res), "=&a" (__d0)
+     : "0" (__s), "1" (__c),
+       "m" ( *(struct { char __x[0xfffffff]; } *)__s)
+     : "cc");
+  return __res;
+}
+
+static inline char *__strchr_g (__const char *__s, int __c)
+{
+  register unsigned long int __d0;
+  register char *__res;
+  __asm__ __volatile__
+    ("movb      %%al,%%ah\n"
+     "1:\n\t"
+     "movb      (%0),%%al\n\t"
+     "cmpb      %%ah,%%al\n\t"
+     "je        2f\n\t"
+     "leal      1(%0),%0\n\t"
+     "testb     %%al,%%al\n\t"
+     "jne       1b\n\t"
+     "xorl      %0,%0\n"
+     "2:"
+     : "=r" (__res), "=&a" (__d0)
+     : "0" (__s), "1" (__c),
+       "m" ( *(struct { char __x[0xfffffff]; } *)__s)
+     : "cc");
+  return __res;
+}
+
+static inline void *__rawmemchr (const void *__s, int __c)
+{
+  register unsigned long int __d0;
+  register unsigned char *__res;
+  __asm__ __volatile__
+    ("cld\n\t"
+     "repne; scasb\n\t"
+     : "=D" (__res), "=&c" (__d0)
+     : "a" (__c), "0" (__s), "1" (0xffffffff),
+       "m" ( *(struct { char __x[0xfffffff]; } *)__s)
+     : "cc");
+  return __res - 1;
+}
+
+#undef memchr
+#define memchr(a,b,c) __memchr((a),(b),(c))
+static inline void *__memchr (__const void *__s, int __c, size_t __n)
+{
+  register unsigned long int __d0;
+  register unsigned char *__res;
+  if (__n == 0)
+    return NULL;
+  __asm__ __volatile__
+    ("repne; scasb\n\t"
+     "je        1f\n\t"
+     "movl      $1,%0\n"
+     "1:"
+     : "=D" (__res), "=&c" (__d0)
+     : "a" (__c), "0" (__s), "1" (__n),
+       "m" ( *(struct { __extension__ char __x[__n]; } *)__s)
+     : "cc");
+  return __res - 1;
+}
+
+#endif

trunk/src/gmake/variable.c

@@ -103 +103 @@
 /* Hash table of all global variable definitions.  */
 
+#ifdef KMK
+static inline unsigned long variable_hash_b(register const unsigned char *var, register int length)
+{
+    register unsigned long hash = 0;
+    for (;;)
+    {
+        switch (length)
+        {
+            default:
+            case 16: hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 15: hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 14: hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 13: hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 12: hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 11: hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 10: hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 9:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 8:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 7:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 6:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 5:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 4:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 3:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 2:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 1:  hash = *var++ + (hash << 6) + (hash << 16) - hash;
+            case 0:
+                break;
+        }
+        if (length <= 16)
+            break;
+        length -= 16;
+    }
+    return hash;
+}
+
+static inline unsigned long variable_hash_a(register const unsigned char *var, register int length)
+{
+    register unsigned long hash = ((5381 << 5) + 5381) + *var;
+    switch (length)
+    {
+        default:
+        case 8: hash = ((hash << 5) + hash) + var[7];
+        case 7: hash = ((hash << 5) + hash) + var[6];
+        case 6: hash = ((hash << 5) + hash) + var[5];
+        case 5: hash = ((hash << 5) + hash) + var[4];
+        case 4: hash = ((hash << 5) + hash) + var[3];
+        case 3: hash = ((hash << 5) + hash) + var[2];
+        case 2: hash = ((hash << 5) + hash) + var[1];
+        case 1: return hash;
+        case 0: return 5381; /* shouldn't happen */
+    }
+}
+#endif /* KMK */
+
 static unsigned long
 variable_hash_1 (const void *keyv)
 {
   struct variable const *key = (struct variable const *) keyv;
+#ifdef VARIABLE_HASH
+#ifdef VARIABLE_HASH_STRICT
+  if (key->hash1 != variable_hash_a (key->name, key->length))
+    __asm__("int3");
+  if (key->hash2 && key->hash2 != variable_hash_b (key->name, key->length))
+    __asm__("int3");
+#endif
+  return key->hash1;
+#else
+#ifdef KMK
+  return variable_hash_a (key->name, key->length);
+#else
   return_STRING_N_HASH_1 (key->name, key->length);
+#endif
+#endif
 }
 
@@ -113 +181 @@
 variable_hash_2 (const void *keyv)
 {
+#ifdef VARIABLE_HASH
+  struct variable *key = (struct variable *) keyv;
+  if (!key->hash2)
+    key->hash2 = variable_hash_b (key->name, key->length);
+  return key->hash2;
+#else
   struct variable const *key = (struct variable const *) keyv;
+#ifdef KMK
+  return variable_hash_b (key->name, key->length);
+#else
   return_STRING_N_HASH_2 (key->name, key->length);
+#endif
+#endif
 }
 
@@ -125 +204 @@
   if (result)
     return result;
+#ifdef KMK /* speed */
+  {
+    const char *xs = x->name;
+    const char *ys = y->name;
+    switch (x->length)
+      {
+        case 8:
+            result = *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
+            if (result)
+              return result;
+            return *(int32_t*)xs - *(int32_t*)ys;
+        case 7:
+            result = xs[6] - ys[6];
+            if (result)
+                return result;
+        case 6:
+            result = *(int32_t*)xs - *(int32_t*)ys;
+            if (result)
+                return result;
+            return *(int16_t*)(xs + 4) - *(int16_t*)(ys + 4);
+        case 5:
+            result = xs[4] - ys[4];
+            if (result)
+                return result;
+        case 4:
+            return *(int32_t*)xs - *(int32_t*)ys;
+        case 3:
+            result = xs[2] - ys[2];
+            if (result)
+                return result;
+        case 2:
+            return *(int16_t*)xs - *(int16_t*)ys;
+        case 1:
+            return *xs - *ys;
+        case 0:
+            return 0;
+      }
+  }
+#endif /* KMK */
+#ifdef VARIABLE_HASH_STRICT
+  if (x->hash1 != variable_hash_a (x->name, x->length))
+    __asm__("int3");
+  if (x->hash2 && x->hash2 != variable_hash_b (x->name, x->length))
+    __asm__("int3");
+  if (y->hash1 != variable_hash_a (y->name, y->length))
+    __asm__("int3");
+  if (y->hash2 && y->hash2 != variable_hash_b (y->name, y->length))
+    __asm__("int3");
+#endif
+#ifdef VARIABLE_HASH
+
+  /* hash 1 */
+  result = (int)x->hash1 - (int)y->hash1;
+  if (result)
+    return result;
+
+  /* hash 2 */
+  if (x->hash2 && y->hash2)
+    {
+      result = (int)x->hash2 - (int)y->hash2;
+      if (result)
+        return result;
+    }
+#endif
+#ifdef KMK
+  return memcmp (x->name, y->name, x->length);
+#else
   return_STRING_N_COMPARE (x->name, y->name, x->length);
+#endif
 }
 
@@ -151 +298 @@
   hash_init (&global_variable_set.table,
 #ifdef KMK
-             8192,
+             8191,
 #else
              VARIABLE_BUCKETS,
@@ -180 +327 @@
   var_key.name = (char *) name;
   var_key.length = length;
+#ifdef VARIABLE_HASH
+  var_key.hash1 = variable_hash_a (name, length);
+  var_key.hash2 = 0;
+#endif
   var_slot = (struct variable **) hash_find_slot (&set->table, &var_key);
 
@@ -216 +367 @@
   v->name = savestring (name, length);
   v->length = length;
+#ifdef VARIABLE_HASH
+  v->hash1 = variable_hash_a (name, length);
+  v->hash2 = 0;
+#endif
   hash_insert_at (&set->table, v, var_slot);
   v->value = xstrdup (value);
@@ -353 +508 @@
   var_key.name = (char *) name;
   var_key.length = length;
+#ifdef VARIABLE_HASH
+  var_key.hash1 = variable_hash_a (name, length);
+  var_key.hash2 = 0;
+#endif
 
   for (setlist = current_variable_set_list;
@@ -438 +597 @@
   var_key.name = (char *) name;
   var_key.length = length;
+#ifdef VARIABLE_HASH
+  var_key.hash1 = variable_hash_a (name, length);
+  var_key.hash2 = 0;
+#endif
 
   return (struct variable *) hash_find_item ((struct hash_table *) &set->table, &var_key);
@@ -914 +1077 @@
   makelevel_key.name = MAKELEVEL_NAME;
   makelevel_key.length = MAKELEVEL_LENGTH;
+#ifdef VARIABLE_HASH
+  makelevel_key.hash1 = variable_hash_a (MAKELEVEL_NAME, MAKELEVEL_LENGTH);
+  makelevel_key.hash2 = 0;
+#endif
   hash_delete (&table, &makelevel_key);
 

trunk/src/gmake/variable.h

@@ -54 +54 @@
     char *name;                 /* Variable name.  */
     int length;                 /* strlen (name) */
+#ifdef VARIABLE_HASH
+    long hash1;                 /* the primary hash */
+    long hash2;                 /* the secondary hash */
+#endif
     char *value;                /* Variable value.  */
     struct floc fileinfo;       /* Where the variable was defined.  */