From: jerry@strobe.ATC.Olivetti.Com (Jerry Aguirre)
Newsgroups: news.software.nntp
Subject: performance patch for msgidd
Keywords: hash msgidd nntp cnews
Date: 10 Oct 92 01:21:47 GMT

I don't know if this patch ever made it out.  Perhaps Paul switched
to INN and dropped msgidd about that time.

I, and perhaps others, have noticed that msgidd tends to consume
several percent of the CPU.  It seemed a little large so I went in
and poked around in the code.

The msgidd code uses a hash table to speed looking up the message ID of
already received messages.  Unfortunately the simple hashing method used
does not interact well with current news software.  Basically it used
the first character after the "<" as a hash value.  That limits it to
ascii printables which is not too good.  But B news sites only put
numerics so that limits it to 10 values that should be fairly randomly
distributed.  But most sites are C news and they put the date as the
first field so every C news posting starts with the same value.

I ran some statistics and found that well over half the articles wind up
in the same hash entry.  So msgidd spends its time doing a sequental
search thru half its entries.

I enhanced the hash used and cut the overhead by at least an order of
magnitude.  Now msgidd CPU used is unnoticable.  If you are still
running msgidd with the old hashing code I offer the following
enhancement.

				Jerry Aguire

*** msgidd.c.orig	Thu Jan 23 14:32:10 1992
--- msgidd.c	Fri Apr 24 21:18:22 1992
***************
*** 63,74 ****
      int freed;
  } stats;
  
  struct el {
      struct el *next;
      time_t age;
      int refcnt;
      char id[1];
! } *ids[256];
  
  char *months[12] = {
      "Jan", "Feb", "Mar", "Apr", "May", "Jun",
--- 63,76 ----
      int freed;
  } stats;
  
+ #define IDSSZ 2053
+ 
  struct el {
      struct el *next;
      time_t age;
      int refcnt;
      char id[1];
! } *ids[IDSSZ];
  
  char *months[12] = {
      "Jan", "Feb", "Mar", "Apr", "May", "Jun",
***************
*** 322,332 ****
  {
      register struct el *i, *p;
      register found = 0;
  
!     for (i = ids[*bufp], p = NULL; i; p = i, i = i->next)
  	if (strcmp(i->id, bufp) == 0) {
  	    if (p == NULL)
! 		ids[*bufp] = i->next;
  	    else
  		p->next = i->next;
  	    if (log)
--- 324,337 ----
  {
      register struct el *i, *p;
      register found = 0;
+     register int hash;
+ 
+     hash = idshash(bufp);
  
!     for (i = ids[hash], p = NULL; i; p = i, i = i->next)
  	if (strcmp(i->id, bufp) == 0) {
  	    if (p == NULL)
! 		ids[hash] = i->next;
  	    else
  		p->next = i->next;
  	    if (log)
***************
*** 356,361 ****
--- 361,367 ----
      time_t now;
  {
      register struct el *i;
+     register int hash;
  
      /* this malloc includes the id[1] array, which means
       * that there's already room for strcpy's null
***************
*** 368,375 ****
  	(void) fprintf(logfp, "%s Add %s %s\n", ptime(now),
  				hosts[fd] ? hosts[fd] : "", bufp);
      }
!     i->next = ids[*bufp];
!     ids[*bufp] = i;
      stats.new++;
      dprintf(stderr, "Add(%d/%s): `%s'\n", fd, hosts[fd], bufp);
  }
--- 374,382 ----
  	(void) fprintf(logfp, "%s Add %s %s\n", ptime(now),
  				hosts[fd] ? hosts[fd] : "", bufp);
      }
!     hash = idshash(bufp);
!     i->next = ids[hash];
!     ids[hash] = i;
      stats.new++;
      dprintf(stderr, "Add(%d/%s): `%s'\n", fd, hosts[fd], bufp);
  }
***************
*** 384,394 ****
      register struct el *i, *p;
      int found = 0, searched = 0;
      register char bufc = *bufp;
  
      /* 
       * search the appropriate list.
       */
!     for (i = ids[bufc], p = NULL; i; p = i, i = i->next) {
  	/* 
  	 * if too old, everything from here to the end
  	 * can be nuked (we always add at the top).
--- 391,403 ----
      register struct el *i, *p;
      int found = 0, searched = 0;
      register char bufc = *bufp;
+     register int hash;
  
      /* 
       * search the appropriate list.
       */
!     hash = idshash(bufp);
!     for (i = ids[hash], p = NULL; i; p = i, i = i->next) {
  	/* 
  	 * if too old, everything from here to the end
  	 * can be nuked (we always add at the top).
***************
*** 400,406 ****
  		if (p)
  		    p->next = n;
  		else
! 		    ids[bufc] = n;
  		free(i);
  		i = n;
  		stats.freed++;
--- 409,415 ----
  		if (p)
  		    p->next = n;
  		else
! 		    ids[hash] = n;
  		free(i);
  		i = n;
  		stats.freed++;
***************
*** 532,535 ****
--- 541,560 ----
  	if (log)
  		fprintf(logfp, "%s Got SIGPIPE\n", ptime(now));
  	sigpiped++;
+ }
+ 
+ /* calculate a hash value for an ID */
+ int
+ idshash(buf)
+ 	char *buf;
+ {
+ 	register char *p;
+ 	register int h;
+ 
+ 	h = 0;
+ 	p = buf;
+ 	while (*p) h += *p++;
+ 	h %= IDSSZ;
+ 	if (h < 0) h = 0;	/* just in case */
+ 	return(h);
  }
Newsgroups: news.software.nntp