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 <kev...@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;
}
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
