svn commit: r368483 - head/usr.bin/grep

[Kyle Evans]

Author: kevans
Date: Wed Dec  9 05:27:45 2020
New Revision: 368483
URL: https://svnweb.freebsd.org/changeset/base/368483

Log:
  grep: replace the internal queue with a ring buffer
  
  We know up front how many items we can have in the queue (-B/Bflag), so
  pay the cost of those particular allocations early on.
  
  The reduced queue maintenance overhead seemed to yield about an ~8%
  improvement for my earlier `grep -C8 -r closefrom .` test.
  
  MFC after:	2 weeks

Modified:
  head/usr.bin/grep/grep.c
  head/usr.bin/grep/grep.h
  head/usr.bin/grep/queue.c

Modified: head/usr.bin/grep/grep.c
==============================================================================
--- head/usr.bin/grep/grep.c	Wed Dec  9 05:12:04 2020	(r368482)
+++ head/usr.bin/grep/grep.c	Wed Dec  9 05:27:45 2020	(r368483)
@@ -707,6 +707,8 @@ main(int argc, char *argv[])
 	if ((aargc == 0 || aargc == 1) && !Hflag)
 		hflag = true;
 
+	initqueue();
+
 	if (aargc == 0 && dirbehave != DIR_RECURSE)
 		exit(!procfile("-"));
 

Modified: head/usr.bin/grep/grep.h
==============================================================================
--- head/usr.bin/grep/grep.h	Wed Dec  9 05:12:04 2020	(r368482)
+++ head/usr.bin/grep/grep.h	Wed Dec  9 05:27:45 2020	(r368483)
@@ -149,6 +149,7 @@ char	*grep_strdup(const char *str);
 void	 grep_printline(struct str *line, int sep);
 
 /* queue.c */
+void	 initqueue(void);
 bool	 enqueue(struct str *x);
 void	 printqueue(void);
 void	 clearqueue(void);

Modified: head/usr.bin/grep/queue.c
==============================================================================
--- head/usr.bin/grep/queue.c	Wed Dec  9 05:12:04 2020	(r368482)
+++ head/usr.bin/grep/queue.c	Wed Dec  9 05:27:45 2020	(r368483)
@@ -6,6 +6,7 @@
  *
  * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
  * All rights reserved.
+ * Copyright (c) 2020 Kyle Evans <kevans at FreeBSD.org>
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -45,77 +46,99 @@ __FBSDID("$FreeBSD$");
 
 #include "grep.h"
 
-struct qentry {
-	STAILQ_ENTRY(qentry)	list;
-	struct str	 	data;
-};
+typedef struct str		qentry_t;
 
-static STAILQ_HEAD(, qentry)	queue = STAILQ_HEAD_INITIALIZER(queue);
-static long long		count;
+static long long		filled;
+static qentry_t			*qend, *qpool;
 
-static struct qentry	*dequeue(void);
-
 /*
- * Enqueue another line; return true if we've dequeued a line as a result
+ * qnext is the next entry to populate.  qlist is where the list actually
+ * starts, for the purposes of printing.
  */
-bool
-enqueue(struct str *x)
+static qentry_t		*qlist, *qnext;
+
+void
+initqueue(void)
 {
-	struct qentry *item;
 
-	item = grep_malloc(sizeof(struct qentry));
-	item->data.dat = grep_malloc(sizeof(char) * x->len);
-	item->data.len = x->len;
-	item->data.line_no = x->line_no;
-	item->data.boff = x->boff;
-	item->data.off = x->off;
-	memcpy(item->data.dat, x->dat, x->len);
-	item->data.file = x->file;
+	qlist = qnext = qpool = grep_calloc(Bflag, sizeof(*qpool));
+	qend = qpool + (Bflag - 1);
+}
 
-	STAILQ_INSERT_TAIL(&queue, item, list);
+static qentry_t *
+advqueue(qentry_t *itemp)
+{
 
-	if (++count > Bflag) {
-		item = dequeue();
-		free(item->data.dat);
-		free(item);
-		return (true);
-	}
-	return (false);
+	if (itemp == qend)
+		return (qpool);
+	return (itemp + 1);
 }
 
-static struct qentry *
-dequeue(void)
+/*
+ * Enqueue another line; return true if we've dequeued a line as a result
+ */
+bool
+enqueue(struct str *x)
 {
-	struct qentry *item;
+	qentry_t *item;
+	bool rotated;
 
-	item = STAILQ_FIRST(&queue);
-	if (item == NULL)
-		return (NULL);
+	item = qnext;
+	qnext = advqueue(qnext);
+	rotated = false;
 
-	STAILQ_REMOVE_HEAD(&queue, list);
-	--count;
-	return (item);
+	if (filled < Bflag) {
+		filled++;
+	} else if (filled == Bflag) {
+		/* We had already filled up coming in; just rotate. */
+		qlist = advqueue(qlist);
+		rotated = true;
+		free(item->dat);
+	}
+	item->dat = grep_malloc(sizeof(char) * x->len);
+	item->len = x->len;
+	item->line_no = x->line_no;
+	item->boff = x->boff;
+	item->off = x->off;
+	memcpy(item->dat, x->dat, x->len);
+	item->file = x->file;
+
+	return (rotated);
 }
 
 void
 printqueue(void)
 {
-	struct qentry *item;
+	qentry_t *item;
 
-	while ((item = dequeue()) != NULL) {
-		grep_printline(&item->data, '-');
-		free(item->data.dat);
-		free(item);
-	}
+	item = qlist;
+	do {
+		/* Buffer must have ended early. */
+		if (item->dat == NULL)
+			break;
+
+		grep_printline(item, '-');
+		free(item->dat);
+		item->dat = NULL;
+		item = advqueue(item);
+	} while (item != qlist);
+
+	qlist = qnext = qpool;
+	filled = 0;
 }
 
 void
 clearqueue(void)
 {
-	struct qentry *item;
+	qentry_t *item;
 
-	while ((item = dequeue()) != NULL) {
-		free(item->data.dat);
-		free(item);
-	}
+	item = qlist;
+	do {
+		free(item->dat);
+		item->dat = NULL;
+		item = advqueue(item);
+	} while (item != qlist);
+
+	qlist = qnext = qpool;
+	filled = 0;
 }