Newsgroups: tw.bbs.netnews
Subject: [patch] make tin threading faster
Date: 29 Nov 1994 23:26:26 GMT
Message-ID: <3bgdb2$i9a@news.csie.nctu.edu.tw>

最近 tw.bbs.soc.politics 極度熱門, 每天高達 500 封,
就算只放 7 天, 也高達 3500 封, 在 grouping 和 threading
上都耗時甚久. 以下的 patch 使 "threading" 從 O(n^2) 降為
O(n), 但每個 hash node 多 1 int.
測試的結果對 tw.bbs.soc.politics 14天 7445 封信,
未 patch: grouping 10 秒, threading 19 秒 
   patch: grouping 10 秒, threading 小於 1 秒 

以下 patch 已送給 tin 作者.
---------------------------------------------------------
The following patch is a little modification for tin's make_thread to 
speed up "making thread" from O(n^2) to O(n) at the expanse of one
extra int for each "hash node".
Two files art.c and hashstr.c are modified and the modifications
are wrapped with "FAST_THREADING".
The speedup won't be sensed if articles are few, but if 
there are more than thousands of articles, the speedup are tremendous.


---------------------------------------------------------------------
diff -rus tin/art.c ntin/art.c
--- tin/art.c	Tue Nov 29 09:51:23 1994
+++ ntin/art.c	Tue Nov 29 09:51:16 1994
@@ -462,9 +462,27 @@
 }
 */
 	for (i = 0; i < top; i++) {
+#ifdef FAST_THREADING
+		int j, *aptr; 
+#endif
 		if (arts[i].thread != ART_NORMAL || IGNORE_ART(i)) {
 			continue;
 		}	
+#ifdef FAST_THREADING
+		aptr = (int*)arts[i].subject;
+		aptr -=2;
+	        j = *aptr;	
+		if (j != -1 && j < i) {
+		  if (! IGNORE_ART(i) && arts[i].inthread == FALSE &&
+			   ((arts[i].subject == arts[j].subject) ||
+			   ((arts[i].part || arts[i].patch) &&
+			   arts[i].archive == arts[j].archive))) {
+		       arts[j].thread = i;
+		       arts[i].inthread = TRUE;
+                   }
+		} 
+		*aptr = i; 
+#else
 		for (j = i+1; j < top; j++) {
 			if (! IGNORE_ART(j) && arts[j].inthread == FALSE &&
 			   ((arts[i].subject == arts[j].subject) ||
@@ -475,6 +493,7 @@
 				break;
 			}
 		}
+#endif
 	}
 }
 
diff -rus tin/hashstr.c ntin/hashstr.c
--- tin/hashstr.c	Tue Nov 29 09:51:23 1994
+++ ntin/hashstr.c	Tue Nov 29 09:51:16 1994
@@ -32,7 +32,6 @@
 
 struct t_hashnode *table[HASHNODE_TABLE_SIZE];
 
-
 char *
 hash_str (s)
 	char *s;
@@ -85,8 +84,14 @@
 	p = (struct t_hashnode *) my_malloc ((unsigned) sizeof (struct t_hashnode));
 
 	p->next = (struct t_hashnode *) 0;
+#ifdef FAST_THREADING
+	iptr = (int *) my_malloc ((unsigned) strlen (s) + sizeof (int)*2 + 1);
+	*iptr++ = -1;
+	*iptr++ = -1;
+#else
 	iptr = (int *) my_malloc ((unsigned) strlen (s) + sizeof (int) + 1);
 	*iptr++ = -1;
+#endif
 	p->s = (char *) iptr;
 	strcpy (p->s, s);
 	return (p);
@@ -118,7 +123,11 @@
 				next = p->next;
 				if (p->s != (char *) 0) {
 					iptr = (int *) p->s;
+#ifdef FAST_THREADING
+					iptr-=2;
+#else
 					iptr--;
+#endif
 					free ((char *) iptr);
 				}
 				free ((char *) p);