performance improvements

--=-=-=

My .idata database has grown to 251 categories and has in the range of
16,500 words and 1.7 megabytes in it, and I've become annoyed with how
slow ifile is on my Sun SPARC Solaris system.

I've come up with some performance improvements that I submit here for
your perusal.  I did some profiling to come up with places to attack.
First, I noticed that ifile_read_db() and ifile_write_db() and their
descendants are the big hitters, not surprisingly.  ifile_write_db()
looks about as efficient as you can make it without a lot of
investment in major rewriting.

I noticed many calls to realloc() in ifile_read_db() (heavily
optimized and inlined by Sun's compiler).  I took a look, and it seems
to me that we could optimize setting up the extendable array for word
frequencies, so I created a macro that would allocate the whole array,
set all the values to 0, and then update the array's metadata.  That
got rid of most of the realloc() calls within ifile.

Secondly, I was concerned with the number of copies of data when
reading and parsing the database.  The current implementation has this
sort of path:

 disk -> stdio buffers -> automatic variable -> small malloc'd space

I replaced stdio with a large malloc'd buffer and a single read, and
stopped using the automatic variable.  Now the path is

        disk -> large malloc'd buffer -> small malloc'd space

The result of this work can be seen when comparing the logfiles of the
"stock" version in CVS and my modified version.  I show you them here:

Stock version:

ifile 1.2.1 called
Reading /export/home/davemq/.idata from disk...
Read 251 categories, 16578 words.  Time used: 1.080 sec
Reading message from standard input...
Read 1 message(s).  Time used: 0.010 sec
Trimmed 18 words due to lack of frequency
Writing /export/home/davemq/.idata to disk...
Wrote 251 folders, 16580 words.  Time used: 0.600 sec

My version:

ifile 1.2.1 called
Reading /export/home/davemq/.idata from disk...
Read 251 categories, 16548 words.  Time used: 0.770 sec
Reading message from standard input...
Read 1 message(s).  Time used: 0.000 sec
Trimmed 3 words due to lack of frequency
Writing /export/home/davemq/.idata to disk...
Wrote 251 folders, 16550 words.  Time used: 0.590 sec

When comparing words per second, I show a 40% improvement:
        Stock: 15,350 words / sec
        Mine:  21,491 words / sec
        Ratio of Mine/Stock: 1.40005

I'm attaching unified diffs from CVS.

The next thing I'd like to try is mmap() and see if that makes any
improvement.  If I get a reasonable mmap() implementation, I may look
at creating an option to write a machine-specific binary database.
Then I can just mmap() in the database, manipulate it, then close it.
That would dispense with all of the parsing.  Of course, such a
database on a little endian machine wouldn't be usable on a big endian
machine and vice versa, but it should be fast!

I guess another option would be to invent some sort of portable binary
database format, but that's pretty far down on my list right now.

Thanks!

--=-=-=
Content-Disposition: attachment; filename=DIFFS
Content-Description: DIFFS

? config.log
? config.cache
? config.status
? OUT
? Makefile
? ifile
? DIFFS
? argp/config.log
? argp/config.status
? argp/Makefile
? argp/mon.out
? argp/gmon.out
Index: database.c
===================================================================
RCS file: /cvsroot/ifile/ifile/database.c,v
retrieving revision 1.1
diff -u -r1.1 database.c
--- database.c	24 Oct 2002 11:55:42 -0000	1.1
+++ database.c	28 Jan 2003 20:47:04 -0000
@@ -23,6 +23,8 @@
 #include <pwd.h>
 #include <unistd.h>
 #include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
 #include <ifile.h>
 
 #define LOG_2 0.69314718
@@ -132,14 +134,14 @@
  * Returns number of folders upon success, -1 upon failure. */
 /* Written by Jason Rennie <[email protected]> */
 long int
-ifile_read_header (FILE * DATA, ifile_db * idata)
+ifile_read_header (ifile_db * idata, char **bufp)
 {
-  char line[MAX_STR_LEN*64];
+  char *line;
   char *token = NULL;
   long int i;
   long int num;
 
-  if (readline(line, sizeof(line), DATA) == NULL) return -1;
+  if ((line = readline(bufp)) == NULL) return -1;
 
   /* read folder names */
   token = strtok(line, " \t");
@@ -150,7 +152,7 @@
     }
   idata->num_folders = i;
 
-  if (readline(line, sizeof(line), DATA) == NULL) return -1;
+  if ((line = readline(bufp)) == NULL) return -1;
 
   /* read word frequencies */
   token = strtok(line, " \t");
@@ -165,7 +167,7 @@
   if (i != idata->num_folders)
     ifile_verbosify(ifile_quiet, "Bad data file format - line #2\n");
 
-  if (readline(line, sizeof(line), DATA) == NULL) return -1;
+  if ((line = readline(bufp)) == NULL) return -1;
 
   /* read document frequencies */
   token = strtok(line, " \t");
@@ -192,12 +194,12 @@
  * Returns number of word entries upon success, -1 upon failure.*/
 /* Written by Jason Rennie <[email protected]> */
 long int
-ifile_read_word_frequencies (FILE * DATA, ifile_db * idata)
+ifile_read_word_frequencies (ifile_db * idata, char **bufp)
 {
-  char line[MAX_STR_LEN*4];
+  char *line;
   long int i = 1;
 
-  while (readline(line, sizeof(line), DATA) != NULL)
+  while ((line = readline(bufp)) != NULL)
     {
       if (line == NULL || line[0] == '\0')
 	ifile_verbosify(ifile_quiet, "Line # %d not in proper word entry format\n", (i+3));
@@ -230,10 +232,7 @@
    * when creating the DB */
   wentry->freq = (extendable_array *) malloc(sizeof(extendable_array));
   freq_array = wentry->freq;
-  EXT_ARRAY_INIT((*freq_array), long int, IFILE_INIT_FOLDERS);
-
-  for (i=0; i < num_folders; i++)
-    EXT_ARRAY_SET((*freq_array), long int, i, 0);
+  EXT_ARRAY_INIT_N_SET((*freq_array), long int, num_folders, 0);
 
   token = strtok(line, " \t");
 
@@ -281,15 +280,20 @@
 long int
 ifile_read_db (char * data_file, ifile_db * idata)
 {
-  FILE * DATA;
+  int DATA;
   long int folders;
   long int words;
+  char *buf, *saved_buf;
+  struct stat st;
+  size_t bufsize;
+  ssize_t nread;
+  ssize_t rc;
 
   ifile_verbosify(ifile_progress, "Reading %s from disk...\n", data_file);
 
-  DATA = fopen(data_file, "r");
+  DATA = open(data_file, O_RDONLY, 0);
 
-  if (DATA == NULL)
+  if (DATA == -1)
     {
       ifile_verbosify(ifile_quiet, "Not able to open %s for reading!\n",
 		      data_file);
@@ -298,14 +302,41 @@
 
   DMZ_start = clock();
 
-  folders = ifile_read_header (DATA, idata);
-  
-  words = ifile_read_word_frequencies (DATA, idata);
+  /* Allocate buffer. */
+  if (stat(data_file, &st) == -1)
+    {
+      ifile_verbosify(ifile_quiet, "Not able to stat %s!\n", data_file);
+      return -1;
+    }
+  bufsize = (size_t) st.st_size;
+
+  if ((saved_buf = buf = malloc(bufsize)) == NULL)
+    {
+      ifile_verbosify(ifile_quiet, "Not able to allocate %d bytes!\n",
+		      bufsize);
+      return -1;
+    }
 
-  if (ferror(DATA))
-    ifile_error("Error reading %s.\n", data_file);
+  /* Read file. */
+  nread = 0;
+  while (nread < bufsize)
+    {
+      if ((rc = read(DATA, buf + nread, bufsize - nread)) == -1)
+	{
+	  ifile_verbosify(ifile_quiet, "Not able to read %s!\n", data_file);
+	  return -1;
+	}
+      nread += rc;
+    }
+
+  /* Close file. */
+  (void) close(DATA);
+  
+  folders = ifile_read_header (idata, &buf);
+  
+  words = ifile_read_word_frequencies (idata, &buf);
 
-  fclose(DATA);
+  free(saved_buf);
 
   DMZ_end = clock();
   ifile_verbosify(ifile_progress,
@@ -478,7 +509,7 @@
 
   for (i=0; i < idata->num_folders; i++)
     fprintf(DATA, "%s ", EXT_ARRAY_GET(idata->folder_name, char *, i));
-  fputc('\n', DATA);
+  putc('\n', DATA);
 
   for (i=0; i < idata->num_folders; i++)
     {
Index: hash_table.c
===================================================================
RCS file: /cvsroot/ifile/ifile/hash_table.c,v
retrieving revision 1.1
diff -u -r1.1 hash_table.c
--- hash_table.c	24 Oct 2002 11:55:42 -0000	1.1
+++ hash_table.c	28 Jan 2003 20:47:04 -0000
@@ -21,6 +21,7 @@
 #include <stddef.h>    /* stdlib doesn't have NULL defined on SunOS 4.1.3_U1 */
 #include <stdlib.h>
 #include <assert.h>
+#include <string.h>
 #include <hash_table.h>
 
 /* Crock:  hashtables should create their own copies of string indices,
Index: int4str.c
===================================================================
RCS file: /cvsroot/ifile/ifile/int4str.c,v
retrieving revision 1.1
diff -u -r1.1 int4str.c
--- int4str.c	24 Oct 2002 11:55:42 -0000	1.1
+++ int4str.c	28 Jan 2003 20:47:04 -0000
@@ -379,7 +379,7 @@
 {
   int i;
   for (i = 0; i < map->str_array_length; i++)
-    free(map->str_array[i]);
+    free((void *) map->str_array[i]);
   ifile_free (map->str_array);
   ifile_free (map->str_hash);
 }
Index: primes.c
===================================================================
RCS file: /cvsroot/ifile/ifile/primes.c,v
retrieving revision 1.1
diff -u -r1.1 primes.c
--- primes.c	24 Oct 2002 11:55:42 -0000	1.1
+++ primes.c	28 Jan 2003 20:47:04 -0000
@@ -109,10 +109,10 @@
 	    if (primes_len >= primes_size)
 	      {
 		primes_size *= 2;
-		primes = (int *) ifile_realloc (primes,
+		primes = (unsigned int *) ifile_realloc (primes,
 					      primes_size * sizeof (*primes));
 		next_multiple
-		  = (int *) ifile_realloc (next_multiple,
+		  = (unsigned int *) ifile_realloc (next_multiple,
 				     primes_size * sizeof (*next_multiple));
 	      }
 	    primes[primes_len] = i;
Index: util.c
===================================================================
RCS file: /cvsroot/ifile/ifile/util.c,v
retrieving revision 1.1
diff -u -r1.1 util.c
--- util.c	24 Oct 2002 11:55:42 -0000	1.1
+++ util.c	28 Jan 2003 20:47:04 -0000
@@ -159,27 +159,25 @@
 }
 
 
-/* Reads up to and including the next feedline (\n) and stores the
- * string in the STRING buffer.  This function relies on STRING
- * being allocated with space for at least MAX_LEN-1 characters.
- * Wrapper for fgets().  Returns a pointer to STRING on success,
- * and NULL on EOF or error.  */
+/*
+ * Reads up to and including the next feedline (\n).  Returns a pointer to
+ * STRING on success, and NULL on EOF or error.  Updates bufp also.
+ */
 /* Written by Jason Rennie <[email protected]> for ifile */
 char *
-readline (char * string, long int max_len, FILE * stream)
+readline (char **bufp)
 {
-  long int last;
-  
-  if (fgets(string, max_len, stream) != NULL)
-    {
-      last = strlen(string)-1;
-      if (string[last] == '\n')
-       string[last] = '\0';
+  char *first = *bufp, *last;
 
-      return string;
+  last = strchr(first, '\n');
+  if (last == NULL)
+    {
+      return NULL;
     }
-  else
-    return NULL;
+  *last = '\0';
+  *bufp = last + 1;
+
+  return first;
 }
 
 
Index: include/extendable_array.h
===================================================================
RCS file: /cvsroot/ifile/ifile/include/extendable_array.h,v
retrieving revision 1.1
diff -u -r1.1 extendable_array.h
--- include/extendable_array.h	24 Oct 2002 11:55:21 -0000	1.1
+++ include/extendable_array.h	28 Jan 2003 20:47:04 -0000
@@ -63,6 +63,19 @@
      ((type *) var.data)[n]=val;\
 }\
 
+/* Initialize for n elements and set elements to val.  We can save a lot of
+ * manipulations of parts of var until we're finished. */
+#define EXT_ARRAY_INIT_N_SET(var,type,inisize,val) \
+{\
+  int i;\
+  (var).size=(inisize);\
+  (var).data=(type *)malloc(sizeof(type) * (inisize));\
+  for (i=0; i < (inisize); i++)\
+    ((type *)var.data)[i] = (val);\
+  (var).elems = (inisize)+1;\
+  (var).last_elem = (inisize);\
+}
+
 /* Get the value of an element.  If index is out of range, returns 0 */
 #define EXT_ARRAY_GET(var,type,n) \
 ((n < var.elems && n >= 0) ? (((type *)(var.data))[n]) : (type) 0)
Index: include/ifile.h
===================================================================
RCS file: /cvsroot/ifile/ifile/include/ifile.h,v
retrieving revision 1.4
diff -u -r1.4 ifile.h
--- include/ifile.h	25 Nov 2002 17:17:47 -0000	1.4
+++ include/ifile.h	28 Jan 2003 20:47:04 -0000
@@ -166,7 +166,7 @@
 char * ifile_sprintf (char * format, ...);
 char * ifile_cats (long int num_strings, ...);
 char * itoa (long int number);
-char * readline (char * string, long int max_len, FILE * stream);
+char * readline (char ** bufp);
 void ifile_free (void * var);
 char * ifile_strdup (const char *s1);
 void ifile_bitify_document(htable * message);
@@ -184,8 +184,8 @@
 void ifile_db_init(ifile_db * idata);
 htable * ifile_read_message (FILE * FP);
 void ifile_print_message (htable * message);
-long int ifile_read_header (FILE * DATA, ifile_db * idata);
-long int ifile_read_word_frequencies (FILE * DATA, ifile_db * idata);
+long int ifile_read_header (ifile_db * idata, char ** bufp);
+long int ifile_read_word_frequencies (ifile_db * idata, char ** bufp);
 long int ifile_read_word_entry (char * line, ifile_db * idata);
 long int ifile_read_db (char * data_file, ifile_db * idata);
 long int ifile_write_db (char * data_file, ifile_db * idata);

--=-=-=


-- 
Dave Marquardt
Round Rock, TX

--=-=-=
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit

_______________________________________________
Ifile-dev mailing list
[email protected]
http://mail.nongnu.org/mailman/listinfo/ifile-dev

--=-=-=--