From owner-svn-src-all@freebsd.org Wed Dec 9 05:27:46 2020 Return-Path: Delivered-To: svn-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 82D234B6DF2; Wed, 9 Dec 2020 05:27:46 +0000 (UTC) (envelope-from kevans@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4CrQYG3HvBz4RF8; Wed, 9 Dec 2020 05:27:46 +0000 (UTC) (envelope-from kevans@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 63C6D212E1; Wed, 9 Dec 2020 05:27:46 +0000 (UTC) (envelope-from kevans@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id 0B95RkWV026542; Wed, 9 Dec 2020 05:27:46 GMT (envelope-from kevans@FreeBSD.org) Received: (from kevans@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id 0B95Rj5M026539; Wed, 9 Dec 2020 05:27:45 GMT (envelope-from kevans@FreeBSD.org) Message-Id: <202012090527.0B95Rj5M026539@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: kevans set sender to kevans@FreeBSD.org using -f From: Kyle Evans Date: Wed, 9 Dec 2020 05:27:45 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r368483 - head/usr.bin/grep X-SVN-Group: head X-SVN-Commit-Author: kevans X-SVN-Commit-Paths: head/usr.bin/grep X-SVN-Commit-Revision: 368483 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 09 Dec 2020 05:27:46 -0000 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 * * 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; }