FYI: 12-gary-speedup-hash-resizing.patch

[Gary V. Vaughan]

Index: ChangeLog
from  Gary V. Vaughan  <address@hidden>
        * m4/hash.c (m4_hash_bucket_insert): Symbol shadowing is no longer
        dependant on multiple symbols with the same key, so preserving
        relative symbol order in each bucket during resizing is no longer
        required.  The resize function is considerably faster as a result.

Index: m4/hash.c
===================================================================
RCS file: /cvsroot/m4/m4/m4/hash.c,v
retrieving revision 1.1
diff -u -p -u -r1.1 hash.c
--- m4/hash.c 2001/09/02 09:05:14 1.1
+++ m4/hash.c 2001/09/08 02:12:48
@@ -21,7 +21,6 @@
 /* TODO:
    - Use an obstack to manage the node memory.
    - Implement the macroized magic values with the API.
-   - Have each node be a pushdown stack to eliminate the shadowed flag.
  */
 
 #include "hash.h"
@@ -343,26 +342,25 @@ m4_hash_maybe_grow (m4_hash *hash)
     }
 }
 
-/* Carefully insert each node in BUCKET into HASH.  The nodes are
-   inserted in reverse order to preserve the relative ordering of
-   all sets of nodes with the same key.  */
+/* Insert each node in BUCKET into HASH.  Relative ordering of nodes
+   is not preserved.  */
 void
 m4_hash_bucket_insert (m4_hash *hash, m4_hash_node *bucket)
 {
   assert (hash);
   assert (bucket);
 
-  if (M4_HASH_NODE_NEXT (bucket))
+  do
     {
-      /* Recurse to the end of the list.  */
-      m4_hash_bucket_insert (hash, M4_HASH_NODE_NEXT (bucket));
+      m4_hash_node *next = M4_HASH_NODE_NEXT (bucket);
 
-      /* Break links as the stack unwinds.  */
+      /* Break link to rest of the bucket before reinserting.  */
       M4_HASH_NODE_NEXT (bucket) = 0;
-    }
+      m4_hash_node_insert (hash, bucket);
 
-  /* Insert each node, from last to first, as the stack unwinds.  */
-  m4_hash_node_insert (hash, bucket);
+      bucket = next;
+    }
+  while (bucket);
 }
 
 

-- 
  ())_. Gary V. Vaughan     gary@(oranda.demon.co.uk|gnu.org)
  ( '/  Research Scientist  http://www.oranda.demon.co.uk       ,_())____
  / )=  GNU Hacker          http://www.gnu.org/software/libtool  \'      `&
`(_~)_  Tech' Author        http://sources.redhat.com/autobook   =`---d__/