Date: Mon, 28 Dec 2020 03:19:42 GMT From: Kyle Evans <kevans@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org Subject: git: a3abf6658334 - stable/12 - grep: replace the internal queue with a ring buffer Message-ID: <202012280319.0BS3JgB4081688@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch stable/12 has been updated by kevans: URL: https://cgit.FreeBSD.org/src/commit/?id=a3abf665833465461030c413f07d324e7d64ae30 commit a3abf665833465461030c413f07d324e7d64ae30 Author: Kyle Evans <kevans@FreeBSD.org> AuthorDate: 2020-12-09 05:27:45 +0000 Commit: Kyle Evans <kevans@FreeBSD.org> CommitDate: 2020-12-28 03:19:26 +0000 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. (cherry picked from commit df546c3b730d4abcace1da24226bd5f01280588e) --- usr.bin/grep/grep.c | 2 + usr.bin/grep/grep.h | 1 + usr.bin/grep/queue.c | 127 ++++++++++++++++++++++++++++++--------------------- 3 files changed, 78 insertions(+), 52 deletions(-) diff --git a/usr.bin/grep/grep.c b/usr.bin/grep/grep.c index 731e46bb112e..a7ecc2015571 100644 --- a/usr.bin/grep/grep.c +++ b/usr.bin/grep/grep.c @@ -712,6 +712,8 @@ main(int argc, char *argv[]) if ((aargc == 0 || aargc == 1) && !Hflag) hflag = true; + initqueue(); + if (aargc == 0 && dirbehave != DIR_RECURSE) exit(!procfile("-")); diff --git a/usr.bin/grep/grep.h b/usr.bin/grep/grep.h index 6d1e87ae4d7c..62e82c7f56b6 100644 --- a/usr.bin/grep/grep.h +++ b/usr.bin/grep/grep.h @@ -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); diff --git a/usr.bin/grep/queue.c b/usr.bin/grep/queue.c index b5f3aa14f0e2..ac15185f0694 100644 --- a/usr.bin/grep/queue.c +++ b/usr.bin/grep/queue.c @@ -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@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 struct qentry *dequeue(void); +static long long filled; +static qentry_t *qend, *qpool; /* - * 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; - - STAILQ_INSERT_TAIL(&queue, item, list); - - if (++count > Bflag) { - item = dequeue(); - free(item->data.dat); - free(item); - return (true); - } - return (false); + + qlist = qnext = qpool = grep_calloc(Bflag, sizeof(*qpool)); + qend = qpool + (Bflag - 1); } -static struct qentry * -dequeue(void) +static qentry_t * +advqueue(qentry_t *itemp) { - struct qentry *item; - item = STAILQ_FIRST(&queue); - if (item == NULL) - return (NULL); + if (itemp == qend) + return (qpool); + return (itemp + 1); +} - STAILQ_REMOVE_HEAD(&queue, list); - --count; - return (item); +/* + * Enqueue another line; return true if we've dequeued a line as a result + */ +bool +enqueue(struct str *x) +{ + qentry_t *item; + bool rotated; + + item = qnext; + qnext = advqueue(qnext); + rotated = false; + + 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; - - while ((item = dequeue()) != NULL) { - grep_printline(&item->data, '-'); - free(item->data.dat); - free(item); - } + qentry_t *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; }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202012280319.0BS3JgB4081688>