To: eliz AT is DOT elta DOT co DOT il, djgpp AT delorie DOT com, djgpp-workers AT delorie DOT com
References: <Pine DOT SUN DOT 3 DOT 91 DOT 1021014073440 DOT 22060A-100000 AT is>
Message-Id: <2.7.9.1DQU1.H402DW@pauzner.dnttm.ru>
From: "Leonid Pauzner" <uue AT pauzner DOT dnttm DOT ru>
Date: Tue, 15 Oct 2002 05:49:08 +0400 (MSD)
X-Mailer: dMail [Demos Mail for DOS v2.7.9]
Subject: libc' getenv optimization (patch)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reply-To: djgpp AT delorie DOT com

13-Oct-2002 07:58 Eli Zaretskii wrote:
> On Sat, 12 Oct 2002, Leonid Pauzner wrote:

>> > In general, time functions _are_ heavy, since the computations are
...
>> Just indexing by the first letter of the environment variable name
>> may speeds up getenv by the factor of 10.

> If you can come up with a patch to getenv that speeds it up tenfold, I'm
> sure it will be gratefully accepted.

So here is my 10 cents.

Speedup detected speedup on my system is about 4 times;
the distribution of env names by the first letter was:

(gdb) p size
$1 = {0 <repeats 67 times>, 2, 3, 2, 0, 2, 1, 0, 0, 0, 3, 0, 1, 0, 2, 0, 0, 1,
  4, 1, 0, 1, 0 <repeats 31 times>, 1, 0 <repeats 136 times>}


perhaps a realistic estimates is around 3-10 times for others.
Preparing procedure set_hash_env() will effectively slowdown putenv() a bit,
but we putenv less frequently than getenv, right?

Leonid.


diff -u old/getenv.c ./getenv.c
--- old/getenv.c        Fri Nov 24 22:21:18 1995
+++ ./getenv.c  Tue Oct 15 04:31:34 2002
@@ -1,20 +1,39 @@
 /* Copyright (C) 1995 DJ Delorie, see COPYING.DJ for details */
 #include <stdlib.h>
 #include <string.h>
+#include <libc/environ.h>

 extern char **environ;

+/*
+   getenv optimization: we copy environ pointers into 256 lists,
+   associated with the first letter of the text string.
+   This will speedup getenv by the factor of 4, or like.
+   Recalculate hash_env[] if environ have changed.
+*/
+char **hash_env[256] = {}; /* init with NULLs*/
+void set_hash_env(void);
+
 char *
 getenv(const char *name)
 {
-  int i;
+  static unsigned last_env_changed = 0;
+  char **envi;
+
+  if (last_env_changed != __environ_changed)
+  {
+    last_env_changed = __environ_changed;
+    set_hash_env();
+  }

-  if (environ == 0)
+  envi = hash_env[(unsigned char)*name];
+  if (envi == 0)
     return 0;

-  for (i=0; environ[i]; i++)
+  envi++;                 /* envi[0] is reserved */
+  for ( ; *envi; envi++)
   {
-    char *ep = environ[i];
+    char *ep = *envi;
     const char *np = name;
     while (*ep && *np && *ep == *np && *np != '=')
       ep++, np++;
@@ -22,4 +41,60 @@
       return ep+1;
   }
   return 0;
+}
+
+
+void
+set_hash_env(void)
+{
+  char **env = environ;
+  int size[256];
+  int i;
+  int alloc;
+
+  for (i=1; i < 256; i++)
+    size[i] = 0;
+  while (*env)
+  {
+    size[(unsigned char)**env]++;
+    env++;
+  }
+
+  /* (re)allocation:  to avoid too many small realloc's
+   * we reserve  hash_env[i][0]  for allocated size info, using a cast.
+   * Do not forget it in this file to avoid off-by-one error.
+   */
+  for (i=1; i < 256; i++)
+  {
+    if (size[i])
+    {
+      if (!hash_env[i]  ||  (int)hash_env[i][0] < size[i] + 2)
+      {
+        alloc = 2 * size[i] + 2;  /* x2 step */
+        hash_env[i] = (char **)realloc(hash_env[i], (alloc) * sizeof(char *));
+        hash_env[i][0] = (char *)alloc;
+        hash_env[i][size[i]+1] = 0;
+      }
+      else
+        hash_env[i][size[i]+1] = 0;
+    }
+    else
+    {
+      if (hash_env[i])
+      {
+        free(hash_env[i]);
+        hash_env[i] = 0;
+      }
+    }
+  }
+  /* (re)allocation done */
+
+  env = environ;
+  while (*env)
+  {
+    i = (unsigned char)**env ;
+    hash_env[i][size[i]] = *env;
+    size[i]--;
+    env++;
+  }
 }