Patch: Faster module processing

[Brad Spencer]

Hi...

This patch for modules.c rev 1.62 introduces the notion of module
memory to the module processing system.  The intent is to remember
which modules have been processed already and to use that information
to prune the "tree" when processing further modules.  The module
processing is highly recursive, and we add a module name cache as a
secondary recursive out.  Basically this stops cvs from trying to do
silly things like check out a module every time it is referenced.
The effect is a _great_ performance improvement when using deep
modules (i.e. modules aliasing modules aliasing modules) where the
leaves are referenced a lot.  This is common within a large source
tree with a lot of libraries.

We've run this locally and found it to work fine in practice.  We've
also thought about it a lot and it seems to be correct.  That is, it
doesn't look like we'll ever _miss_ doing anything.  The whole concept
is based on the assumption:

  Processing a module n times is equivalent to processing a module
  once.

This holds true (as far as we can tell) _unless_ you write an evil
checkout, checkin, or other script.  _But_ if you write such an evil
script (one that has different effects each time it is run) , you're
asking for trouble because you can't reasonably predict how often a
module is referenced with existing cvs (without our patch), and
therefore, you can't predict how many times that script would be run.

Anyway, here's the patch.

Brad Spencer and David Benoit

-- 
-----------------------------------------------------------------
Brad Spencer - spencer@infointeractive.com - "It's quite nice..."
"S.M.A.K.I.B.B.F.B." - A.J. Rimmer | http://infointeractive.com/

*** modules.c.orig      Thu May 10 11:28:41 2001
--- modules.c   Fri May 11 14:20:11 2001
***************
*** 53,60 ****
--- 53,170 ----
  static int sort_order PROTO((const PTR l, const PTR r));
  static void save_d PROTO((char *k, int ks, char *d, int ds));
  
+ /*
+  * Remember what modules we've processed before so we don't duplicate a _lot_
+  * of effort.  This saves an amazing amount of time with highly recursive
+  * module definitions.  This should perhaps be a hash of some form, but
+  * writing complex data structures in C is just too quaint.
+  *
+  * GOTCHA: This assumes that only one (top-level) do_module is called per
+  * instance.  If this isn't true, reset the table first.  FIXME: It leaks.
+  */
  
+ /* Extra diagnostics */
+ #define CVSMODULE_PRINT_MODULE_MEMORY 1
+ 
+ /* Right now, it's just a linked list. */
+ struct MemoryNode {
+   struct MemoryNode *next;
+   char data[1];
+ };
+ static struct MemoryNode *st_list = NULL;
+ static unsigned int st_memoryHits = 0;
+ 
  /*
+  * Ask if the specified module is in module memory or not.
+  */
+ static int
+ module_memory_hit(char *mname)
+ {
+   /* The current list */
+   struct MemoryNode *start = st_list;
+ 
+   /* Start at the front and see if it's there.  If not, add it. */
+   while(start != NULL) {
+     if(strcmp(start->data, mname) == 0) {
+       /* Found it. */
+       st_memoryHits++;
+       return 1;
+     }
+     start = start->next;
+   }
+   return 0;
+ }
+ 
+ /*
+  * Add a specified module to module memory.  Returns 1 if it was already 
there,
+  * or 0 if it wasn't.
+  */
+ static int
+ module_memory(char *mname)
+ {
+   /* The current list */
+   struct MemoryNode *node;
+ 
+   if(module_memory_hit(mname) == 1) {
+     return 1;
+   }
+   
+   /*
+    * Make a new node that will go on the front of the list.  We've got the +1
+    * in the data[1].
+   */ 
+   node = (struct MemoryNode *)xmalloc(sizeof(struct MemoryNode)
+                                      + strlen(mname));
+   node->next = st_list;
+   strcpy(node->data, mname);
+   st_list = node;
+ 
+ #if CVSMODULE_PRINT_MODULE_MEMORY
+   if(trace) {
+     cvs_outerr(CLIENT_SERVER_STR, 0);
+     cvs_outerr("-> Added module `", 0);
+     cvs_outerr(mname, 0);
+     cvs_outerr("' to module memory\n", 0);
+   }
+ #endif /* CVSMODULE_PRINT_MODULE_MEMORY */      
+   
+   /* We added it, so it wasn't there */
+   return 0;
+ }
+ 
+ /*
+  * Forget all current module memory
+  */
+ 
+ static void
+ module_memory_forget(void)
+ {
+   struct MemoryNode *node = st_list;
+   struct MemoryNode *next;
+ 
+   /* Delete all nodes */
+   while(node != NULL) {
+     next = node->next;
+     free(node);
+     node = next;
+   }
+   /* Mark the list as empty */
+   st_list = NULL;
+   st_memoryHits = 0;
+ 
+ #if CVSMODULE_PRINT_MODULE_MEMORY
+   if(trace) {
+     char buff[17];
+     cvs_outerr(CLIENT_SERVER_STR, 0);
+     cvs_outerr("-> Cleared module memory (", 0);
+     sprintf(buff, "%u", st_memoryHits);
+     cvs_outerr(buff, 0);
+     cvs_outerr(" hits)\n", 0);
+   }
+ #endif /* CVSMODULE_PRINT_MODULE_MEMORY */      
+ }
+ 
+ /*
   * Open the modules file, and die if the CVSROOT environment variable
   * was not set.  If the modules file does not exist, that's fine, and
   * a warning message is displayed and a NULL is returned.
***************
*** 89,94 ****
--- 199,207 ----
  {
      if (db != NULL)
        dbm_close (db);
+ 
+     /* Forget all memorized modules */
+     module_memory_forget();
  }
  
  /*
***************
*** 295,305 ****
            if (save_cwd (&cwd))
                error_exit ();
            cwd_saved = 1;
  
-           err += callback_proc (modargc, modargv, where, mwhere, mfile,
-                                 shorten,
-                                 local_specified, mname, msg);
- 
            free_names (&modargc, modargv);
  
            /* cd back to where we started.  */
--- 408,420 ----
            if (save_cwd (&cwd))
                error_exit ();
            cwd_saved = 1;
+           
+           if(module_memory(mname) == 0) {
+             err += callback_proc (modargc, modargv, where, mwhere, mfile,
+                                   shorten, 
+                                   local_specified, mname, msg);
+           }
  
            free_names (&modargc, modargv);
  
            /* cd back to where we started.  */
***************
*** 503,512 ****
                error (0, 0,
                       "module `%s' in modules file contains infinite loop",
                       mname);
!           else
                err += do_module (db, modargv[i], m_type, msg, callback_proc,
                                  where, shorten, local_specified,
                                  run_module_prog, build_dirs, extra_arg);
        }
        goto do_module_return;
      }
--- 618,628 ----
                error (0, 0,
                       "module `%s' in modules file contains infinite loop",
                       mname);
!           else if(module_memory_hit(modargv[i]) == 0) {
                err += do_module (db, modargv[i], m_type, msg, callback_proc,
                                  where, shorten, local_specified,
                                  run_module_prog, build_dirs, extra_arg);
+           }
        }
        goto do_module_return;
      }
***************
*** 523,530 ****
      /* otherwise, process this module */
      if (modargc > 0)
      {
!       err += callback_proc (modargc, modargv, where, mwhere, mfile, shorten,
!                             local_specified, mname, msg);
      }
      else
      {
--- 639,648 ----
      /* otherwise, process this module */
      if (modargc > 0)
      {
!       if(module_memory(mname) == 0) {
!       err += callback_proc(modargc, modargv, where, mwhere, mfile, shorten,
!                            local_specified, mname, msg);
!       }
      }
      else
      {