speedups and bug fixes

From: Andrew Tridgell <tridge_at_samba.anu.edu.au_at_hypermail-project.org>
Date: Tue, 27 Oct 1998 23:23:32 +1100
Message-Id: <19981027122336Z12583050-479+4696_at_samba.anu.edu.au>

hypermail was chewing enormous amounts of CPU on my system (samba.anu.edu.au). The cause was some bugs plus some very inefficient algorithms. The patch below (against 2.0b3) fixes both.

with these patches my Origin200 can add a message to a directory with 4500 messages in it in about 10 seconds. It took about 10 minutes before (after the infinite loops were fixed, of course!).

changes:

• make addheader() simpler and non-recursive. With 4k messages in a directory the recursive calls were a killer.
• fixed convtoshortdate() to handle 2 more date formats and made the code much simpler.
• put a limit of year 3000 on getyearsecs() as bad dates caused it to chew huge amounts of CPU.
• don't sprintf for %c%c as that's too slow in convtoyearsecs()
• fixed missing type in tmpname()
• fixed a potential infinite loop in loadoldheaders()

I'm not on this list at the moment, so please CC replies to me.

diff -u ../hypermail-20b3/src/date.c src/date.c

--- ../hypermail-20b3/src/date.c	Fri Aug 21 09:12:36 1998


+++ src/date.c	Tue Oct 27 22:50:00 1998

_at_@ -53,88 +53,56 @@
 {

     char c, d, e;
     int i, month;

-
+ char *month_p, *day_p, *year_p;
+
+ memset(shortdate, 0, 9);
+
+

     if (date[3] == ' ') {  /* (Wed Mar 19 19:15:53 1997 CST) format */
-        c = date[4];
-        d = date[5];
-        e = date[6];
- 
-        for (i = 0; !(c == (months[i])[0] && d == (months[i])[1] &&
-           e == (months[i])[2]); i++)
-             ;
-        month = i + 1;
- 
-        shortdate[0] = (month > 9) ? '1' : '0';
-        shortdate[1] = monthnums[month];
-        shortdate[2] = '/';
-        shortdate[3] = (date[8] == ' ') ? '0' : date[8];
-        shortdate[4] = date[9];
-        shortdate[5] = '/';
-        shortdate[6] = date[22];
-        shortdate[7] = date[23];
-        shortdate[8] = '\0';


+	    /* (Wed Mar 19 19:15:53 1997 CST) */

+	    month_p = &date[4];

+	    day_p = &date[8];

+	    year_p = &date[22];

+    } else if (date[2] == ' ') {

+	    /* [30 Sep 1998 15:44:17 +0200] */

+	    month_p = &date[3];

+	    day_p = &date[0];

+	    year_p = &date[7];

+    } else if (date[1] == ' ') {

+	    /* [3 Sep 1998 15:44:17 +0200] */

+	    month_p = &date[2];

+	    day_p = &date[0];

+	    year_p = &date[6];

+    } else if (date[3] == ',') {

+	    /* (Wed, 19 Mar 19:15:53 1997 CST) format */

+	    month_p = &date[8];

+	    day_p = &date[5];

+	    year_p = &date[23];

+    } else {

+	    fprintf(stderr,"Date: [%s]\n", date);

+	    return;

     }

- else if (date[3] == ',') { /* (Wed, 19 Mar 19:15:53 1997 CST) format */  

• /* Determine the day. */
  + for (i = 0; i<11 && !(
  + month_p[0] == (months[i])[0] &&
  + month_p[1] == (months[i])[1] &&
  + month_p[2] == (months[i])[2]);
  + i++) ;
  + month = i + 1;
  +
  + shortdate[0] = (month > 9) ? '1' : '0';
  + shortdate[1] = monthnums[month];
  
• if (date[7] == ' ') { /* Day > 9 */
• c = date[8];
• d = date[9];
• e = date[10];
• }
• else { /* Day <= 9 */
• c = date[7];
• d = date[8];
• e = date[9];
• } -
• /* Determine the month. */
  + shortdate[2] = '/';
  
• for (i = 0; !(c == (months[i])[0] && d == (months[i])[1] &&
• e == (months[i])[2]); i++)
• ;
• month = i + 1; -
• shortdate[0] = (month > 9) ? '1' : '0';
• shortdate[1] = monthnums[month];
• shortdate[2] = '/'; -
• if (date[4] == ' ' && date[6] == ' ') { /* day < 9 */
• shortdate[3] = '0';
• shortdate[4] = date[5];
• }
• else {
• shortdate[3] = date[5];
• shortdate[4] = date[6];
• }
• shortdate[5] = '/'; -
• /* Determine the year. */ -
• if (date[4] == ' ' && date[6] == ' ' && date[10] == ' ') { /* day<9 */
• if (date[13] == ' ') { /* two digit year */
• shortdate[6] = date[11];
• shortdate[7] = date[12];
• }
• else {
• shortdate[6] = date[13];
• shortdate[7] = date[14];
• }
• }
• else {
• if (date[14] == ' ') { /* two digit year */
• shortdate[6] = date[12];
• shortdate[7] = date[13];
• }
• else {
• shortdate[6] = date[14];
• shortdate[7] = date[15];
• }
• }
• shortdate[8] = '\0';
• }
• else fprintf(stderr,"Date: [%s]\n", date);
  + shortdate[3] = (day_p[0] == ' ') ? '0' : day_p[0];
  + shortdate[4] = day_p[1];
  +
  + shortdate[5] = '/';
  +
  + shortdate[6] = year_p[0];
  + shortdate[7] = year_p[1];
  + shortdate[8] = '\0';
  }

_at_@ -187,6 +155,8 @@

     splitshortdate(shortdate, &month, &day, &year);
     year += CENTURY;
 

+ if (year > 3000) return 0;
+

     for (i = BASEYEAR; i < year; i++) {
          if (IS_LEAP(i)) 
              dayspast++;
_at_@ -219,9 +189,15 @@
     convtoshortdate(date, shortdate);
     yearsecs = getyearsecs(shortdate);
 
-    sprintf(hourstr, "%c%c", date[11], date[12]);

- sprintf(minstr, "%c%c", date[14], date[15]); - sprintf(secstr, "%c%c", date[17], date[18]);
+ hourstr[0] = date[11];
+ hourstr[1] = date[12];
+ hourstr[2] = 0;
+ minstr[0] = date[14];
+ minstr[1] = date[15];
+ minstr[2] = 0;
+ secstr[0] = date[17];
+ secstr[1] = date[18];
+ secstr[2] = 0;
 

     hours = atoi(hourstr);
     minutes = atoi(minstr);
diff -u ../hypermail-20b3/src/hypermail.h src/hypermail.h
--- ../hypermail-20b3/src/hypermail.h	Fri Aug 21 09:12:36 1998


+++ src/hypermail.h	Tue Oct 27 22:31:06 1998

_at_@ -89,7 +89,7 @@
 #define SECSPERMIN     60
 #define SECSPERHOUR    3600
 #define SECSPERDAY     86400

-#define IS_LEAP(y) (y > 1752 && (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0)))
+#define IS_LEAP(y) (y > 1752 && ((y % 4) == 0 && ((y % 100) != 0 || (y % 400) == 0)))
 

 #define FROM_AUTHOR 0
 #define FROM_DATE 1
diff -u ../hypermail-20b3/src/parse.c src/parse.c

--- ../hypermail-20b3/src/parse.c	Fri Aug 21 09:12:36 1998


+++ src/parse.c	Tue Oct 27 21:53:45 1998

_at_@ -95,7 +95,7 @@
 char *tmpname(char *dir, char *pfx)
 {

     char *f, *name;
- static cntr = 0;
+ static int cntr = 0;
 

     char *mktemp(char *template);  

_at_@ -1753,7 +1753,7 @@

     while ((fp = fopen(filename, "r")) != NULL) {  

         /* skip all lines before the first <!-- */
-        while (fgets(line,sizeof(line),fp), strncmp(line, "<!-- received", 13));


+        while (fgets(line,sizeof(line),fp) && strncmp(line, "<!-- received", 13));

 
         strcpymax(fromdate, (char *) getvalue(line), DATESTRLEN);
 
diff -u ../hypermail-20b3/src/struct.c src/struct.c
--- ../hypermail-20b3/src/struct.c	Fri Aug 21 09:12:36 1998


+++ src/struct.c	Tue Oct 27 21:43:54 1998

_at_@ -425,68 +425,85 @@
 	return 0;

 }  

-/*
-** Add article header information to a binary tree and sort by date,
-** subject, or author. This is necessary for printing the index files.
-*/
-
-struct header *addheader(struct header *hp, int num, char *name,
-                         char *subject, char *date, int sorttype)

+static struct header *newheader(int num, char *name, char *subject, char *date, int sorttype)
 {

-        int isbigger;
-        long yearsecs;
-
-        isbigger = 0;
-        if (hp == NULL) {
-                hp = (struct header *) emalloc(sizeof(struct header));
-                hp->msgnum = num;
-		hp->name = (char *) strsav(name);
-		hp->subject = (char *) strsav(subject);
-		hp->datestr = (char *) strsav(date);
-		if (sorttype == 2) {
-			yearsecs = convtoyearsecs(date);
-			if (!yearsecs)
-				yearsecs = (long)time((time_t *) 0);
-			hp->datenum = yearsecs;
-			if (!firstdatenum || yearsecs < firstdatenum)
-				firstdatenum = yearsecs;
-			if (yearsecs > lastdatenum)
-				lastdatenum = yearsecs;
-		}
-		else
-			hp->datenum = 0;
-                hp->left = hp->right = NULL;
-                return hp;
-        }


+	struct header *hp;

 
-	if (sorttype == 1)
-	        isbigger = (strcasecmp(name, hp->name) > 0) ? 0 : 1;
-	else if (sorttype == 0)
-	        isbigger = (strcasecmp(subject, hp->subject) > 0) ? 0 : 1;
-	else if (sorttype == 2) {
-		yearsecs = convtoyearsecs(date);


+	hp = (struct header *) emalloc(sizeof(struct header));

+	hp->msgnum = num;

+	hp->name = (char *) strsav(name);

+	hp->subject = (char *) strsav(subject);

+	hp->datestr = (char *) strsav(date);

+	if (sorttype == 2) {

+		long yearsecs = convtoyearsecs(date);

 		if (!yearsecs)
 			yearsecs = (long)time((time_t *) 0);
-		if (reverse)
-		        isbigger = (yearsecs < hp->datenum) ? 0 : 1;
-		else
-		        isbigger = (yearsecs >= hp->datenum) ? 0 : 1;


+		hp->datenum = yearsecs;

 		if (!firstdatenum || yearsecs < firstdatenum)
 			firstdatenum = yearsecs;
 		if (yearsecs > lastdatenum)
 			lastdatenum = yearsecs;
 	}


+	else

+		hp->datenum = 0;

+	hp->left = hp->right = NULL;

+	return hp;

+}
+
+static int head_compare(int sorttype, char *name, char *subject, int yearsecs, struct header *hp)
+{
+ if (sorttype == 1)
+ return (strcasecmp(name, hp->name) > 0) ? 0 : 1;
 

• if (isbigger)
• hp->left = addheader(hp->left, num, name, subject, date,
• sorttype);
• else
• hp->right = addheader(hp->right, num, name, subject, date,
• sorttype);
  + if (sorttype == 0)
  + return (strcasecmp(subject, hp->subject) > 0) ? 0 : 1;
  
• return hp;
  + if (sorttype == 2) {
  + if (reverse)
  + return (yearsecs < hp->datenum) ? 0 : 1;
  + else
  + return (yearsecs >= hp->datenum) ? 0 : 1;
  + }
  + return 0;
  }

+/* Add article header information to a binary tree and sort by date,
+** subject, or author. This is necessary for printing the index files.
+*/
+
+struct header *addheader(hp1, num, name, subject, date, sorttype)
+ struct header *hp1;
+ int num;
+ char *name;
+ char *subject;
+ char *date;
+ int sorttype;
+{
+ int isbigger;
+ int yearsecs;
+ struct header **hpp, *hp=hp1;
+
+ if (!hp) return newheader(num, name, subject, date, sorttype);
+
+ yearsecs = convtoyearsecs(date);
+ if (!yearsecs)
+ yearsecs = (long)time((time_t *) 0);
+
+ while (hp) {
+ isbigger = head_compare(sorttype, name, subject, yearsecs, hp);
+
+ if (isbigger) {
+ hpp = &hp->left;
+ } else {
+ hpp = &hp->right;
+ }
+ hp = *hpp;
+ }
+
+ *hpp = newheader(num, name, subject, date, sorttype);
+
+ return hp1;
+}
 

 /*

• And Now The List Addition Routines!

Received on Tue 27 Oct 1998 05:58:14 PM GMT