🚀 go-pugleaf

A customer reported serious performance problems with GNU Make,
including needing 9MB of virtual memory to run and 20 CPU-seconds to
start up.  They were compiling a large application that builds sources
from twenty or thirty directories.

The main problems were that hashing parameters were chosen poorly.
Directory names are hashed based on a single table, which only had 23
buckets.  In this run, 1800 directories were used (of which 558
actually existed), meaning that long chains had to be searched (more
than a million calls to strcmp were done).  I increased to using 199
buckets, for a negligible cost in space.

File names within a directory are hashed based on a table that is
replicated per directory.  This table had 1007 buckets.  Each bucket
needed 16 bytes of space, so each directory took 16kbytes.  With 558
real directories, this was about 9MB.  I reduced the file hash table
size to 107 entries -- which should still allow files in an average
directory to be found without any indirections.  I also fixed a real
bug which allocated 16 bytes for each bucket rather than 4.  Together,
these reduced the space for file names by a factor of 40, to a few
hundred kbytes.

The third problem is that make is not tracking which directory paths
are actually the same directory.  Since both "vpath" with relative
paths, and specific dependencies that specify relative file paths,
were in use, make would search all elements of vpath for all the
relative file names -- finding most of them.  This produced 558
directories out of only twenty or thirty; here is a sample, as
reported by print_dir_data_base():

# ../xxx/../loader: 102 files, no impossibilities.
# ../bbb/../loader: 102 files, no impossibilities.
# ../ccc/../loader: 102 files, no impossibilities.
# ../ddd/../loader: 102 files, no impossibilities.
# ../eee/../loader: 102 files, no impossibilities.
# ../fff/../loader: 102 files, no impossibilities.
# ../ggg/../loader: 102 files, no impossibilities.
# ../hhh/../loader: 102 files, no impossibilities.
# ../iii/../loader: 102 files, no impossibilities.
# ../kkk/../loader: 102 files, no impossibilities.
# ../loader: 102 files, no impossibilities.
# ../mmm/../loader: 102 files, no impossibilities.
# ../nnn/../loader: 102 files, no impossibilities.
# ../ppp/../loader: 102 files, no impossibilities.
# ../sss/../loader: 102 files, no impossibilities.
# ../ttt/../loader: 102 files, no impossibilities.
# ../uuu/../loader: 102 files, no impossibilities.
# ../vvv/../loader: 102 files, no impossibilities.
# ../www/../loader: 102 files, no impossibilities.

I didn't see an easy way for make to notice that these are all the
same directory, so I didn't do anything about this.  However, removing
the vpath commands from the makefile halved the startup time without
affecting the builds (and reduced the number of total directories to
129, and known directories to 42).

The final change was to eliminate some useless calls.  find_directory
calls dir_file_exists_p, passing it a directory name;
dir_file_exists_p immediately calls back to find_directory to locate
the directory struct that matches that name.  Now it calls
dir_struct_file_exists_p and passes it the struct pointer directly.

Another useless call was in selective_vpath_search; it called
dir_file_exists_p to see if the directory exists, and then immediately
called it again to see if a file exists.  The first call is useless
because if the directory doesn't exist, the file won't either, and it
saved no time or space in selective_vpath_search.

With these changes (and the vpath commands removed), it's down to
1.5MB virtual and about 9 CPU seconds to start -- still not very
good, but much more usable.

	John Gilmore
	gnu@cygnus.com

diff -u make-3.62/dir.c make-new/dir.c
--- make-3.62/dir.c	Fri Oct 18 12:26:24 1991
+++ make-new/dir.c	Fri Sep 25 14:00:21 1992
@@ -61,7 +61,7 @@
   };
 
 #ifndef	DIRECTORY_BUCKETS
-#define DIRECTORY_BUCKETS 23
+#define DIRECTORY_BUCKETS 199
 #endif
 
 static struct directory *directories[DIRECTORY_BUCKETS];
@@ -84,8 +84,9 @@
   };
 
 #ifndef	DIRFILE_BUCKETS
-#define DIRFILE_BUCKETS 1007
+#define DIRFILE_BUCKETS 107
 #endif
+
 
 /* Find the directory named NAME and return its `struct directory'.  */
 
@@ -122,15 +123,15 @@
 	{
 	  /* Allocate an array of hash buckets for files and zero it.  */
 	  dir->files = (struct dirfile **)
-	    xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS);
+	    xmalloc (sizeof (struct dirfile *) * DIRFILE_BUCKETS);
 	  bzero ((char *) dir->files,
-		 sizeof (struct dirfile) * DIRFILE_BUCKETS);
+		 sizeof (struct dirfile *) * DIRFILE_BUCKETS);
 
 	  /* Keep track of how many directories are open.  */
 	  ++open_directories;
 	  if (open_directories == MAX_OPEN_DIRECTORIES)
 	    /* Read the entire directory and then close it.  */
-	    (void) dir_file_exists_p (dir->name, (char *) 0);
+	    (void) dir_struct_file_exists_p (dir, (char *) 0);
 	}
     }
 
@@ -137,21 +138,19 @@
   return dir;
 }
 
-/* Return 1 if the name FILENAME in directory DIRNAME
+/* Return 1 if the name FILENAME in directory struct *DIR
    is entered in the dir hash table.
    FILENAME must contain no slashes.  */
 
 int
-dir_file_exists_p (dirname, filename)
-     register char *dirname;
+dir_struct_file_exists_p (dir, filename)
+     register struct directory *dir;
      register char *filename;
 {
   register unsigned int hash;
   register char *p;
-  register struct directory *dir;
   register struct dirfile *df;
   register struct direct *d;
-  dir = find_directory (dirname);
 
   if (dir->files == 0)
     /* The directory could not be opened.  */
@@ -217,6 +216,21 @@
     }
 
   return 0;
+}
+
+/* Return 1 if the name FILENAME in the directory named DIRNAME
+   is entered in the dir hash table.
+   FILENAME must contain no slashes.  */
+
+int
+dir_file_exists_p (dirname, filename)
+     register char *dirname;
+     register char *filename;
+{
+  register struct directory *dir;
+
+  dir = find_directory (dirname);
+  return dir_struct_file_exists_p (dir, filename);
 }
 
 /* Return 1 if the file named NAME exists.  */
diff -u make-3.62/vpath.c make-new/vpath.c
--- make-3.62/vpath.c	Mon Jun  3 13:37:37 1991
+++ make-new/vpath.c	Fri Sep 25 14:36:18 1992
@@ -345,11 +345,6 @@
 	     Now NAME is the name of the directory to look in.  */
 	  *n = '\0';
 
-	  /* Make sure the directory exists and we know its contents.  */
-	  if (name_dplen > 0 && !dir_file_exists_p (name, ""))
-	    /* It doesn't exist.  */
-	    continue;
-
 	  /* We know the directory is in the hash table now because either
 	     construct_vpath_list or the code just above put it there.
 	     Does the file we seek exist in it?  */