To: djgpp-workers AT delorie DOT com
References: <10210150631 DOT AA20605 AT clio DOT rice DOT edu>
    <2 DOT 7 DOT 9 DOT 1C51G DOT H41539 AT pauzner DOT dnttm DOT ru>
Message-Id: <2.7.9.15OOH.H4M4AK@pauzner.dnttm.ru>
From: "Leonid Pauzner" <uue AT pauzner DOT dnttm DOT ru>
Date: Sun, 27 Oct 2002 02:37:32 +0400 (MSD)
X-Mailer: dMail [Demos Mail for DOS v2.7.9]
Subject: Re: libc' getenv optimization (patch3)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reply-To: djgpp-workers AT delorie DOT com

This is a revised patch:

set_hash_env() now uses a single realloc, if any (literally: only the first
allocation in most cases), its weight is nearly as much as 2 old getenv calls
and definitely less then putenv().



diff -u -p old/getenv.c ./getenv.c
--- old/getenv.c        Fri Nov 24 22:21:18 1995
+++ ./getenv.c  Sun Oct 27 01:40:38 2002
@@ -1,20 +1,40 @@
 /* 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 16 (or 32) lists,
+   associated with the mask of the first letter of the text string.
+   This will speedup getenv by the factor of 4, or like.
+   Reset hash_env[] if environ was changed since the previous getenv call.
+*/
+#define BUCKETS  16
+
+char **hash_env[BUCKETS];
+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 % BUCKETS];
+  if (envi == 0)
     return 0;

-  for (i=0; environ[i]; i++)
+  for ( ; *envi; envi++)
   {
-    char *ep = environ[i];
+    char *ep = *envi;
     const char *np = name;
     while (*ep && *np && *ep == *np && *np != '=')
       ep++, np++;
@@ -22,4 +42,60 @@ getenv(const char *name)
       return ep+1;
   }
   return 0;
+}
+
+
+/**********************************************************************
+ *   set_hash_env()  read environ and set hash_env[]
+ */
+int data_size = 0;
+char **data = 0;   /*linear storage for hash_env[i][]*/
+
+void
+set_hash_env(void)
+{
+  char **env = environ;
+  int size[BUCKETS] = {0};
+  int total = 0;
+  int i;
+  char **p;
+
+  while (*env)
+  {
+    i = (unsigned char)**env % BUCKETS;
+    size[i]++;
+    total++;
+    env++;
+  }
+
+  /* (re)allocation: we need  total+(num of not empty buckets),
+   * allow 1/3 extra and assume nearly all buckets are filled.
+   */
+  if (data_size < total + BUCKETS) {
+    data_size = (total*4)/3 + BUCKETS;
+    data = (char **)realloc(data, data_size * sizeof(char *));
+  }
+
+  p = data;
+  for (i=0; i < BUCKETS; i++)
+  {
+    if (size[i])
+    {
+      hash_env[i] = p;
+      p += size[i];
+      *p++ = 0;
+    }
+    else
+      hash_env[i] = 0;
+  }
+  /* (re)allocation done */
+
+  env = environ;
+  while (*env)
+  {
+    i = (unsigned char)**env % BUCKETS;
+    size[i]--;
+    hash_env[i][size[i]] = *env;
+    env++;
+  }
 }