[src/trunk]: src/usr.bin/make make: improve performance for LazyBuf

[rillig <rillig%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/17aa0d5c26cb
branches:  trunk
changeset: 982371:17aa0d5c26cb
user:      rillig <rillig%NetBSD.org@localhost>
date:      Sun Apr 11 22:53:45 2021 +0000

description:
make: improve performance for LazyBuf

The previous O(n^2) time complexity for parsing a long string with many
variable expressions was not meant to last for long.  I had hoped to fix
it within a few minutes, but that will take more time.

For now, make LazyBuf simpler by using a traditional C string for the
expected part instead of a Substring.  This avoids a strlen call per
Var_Parse.

No functional change, only performance.

diffstat:

 usr.bin/make/str.h |  14 ++++++--------
 usr.bin/make/var.c |   8 ++++----
 2 files changed, 10 insertions(+), 12 deletions(-)

diffs (91 lines):

diff -r bb2b381ce221 -r 17aa0d5c26cb usr.bin/make/str.h
--- a/usr.bin/make/str.h        Sun Apr 11 21:29:57 2021 +0000
+++ b/usr.bin/make/str.h        Sun Apr 11 22:53:45 2021 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: str.h,v 1.4 2021/04/11 20:38:43 rillig Exp $   */
+/*     $NetBSD: str.h,v 1.5 2021/04/11 22:53:45 rillig Exp $   */
 
 /*
  Copyright (c) 2021 Roland Illig <rillig%NetBSD.org@localhost>
@@ -59,7 +59,7 @@
        char *data;
        size_t len;
        size_t cap;
-       Substring expected;
+       const char *expected;
        void *freeIt;
 } LazyBuf;
 
@@ -231,7 +231,7 @@
 
 
 MAKE_INLINE void
-LazyBuf_Init(LazyBuf *buf, Substring expected)
+LazyBuf_Init(LazyBuf *buf, const char *expected)
 {
        buf->data = NULL;
        buf->len = 0;
@@ -257,15 +257,14 @@
                }
                buf->data[buf->len++] = ch;
 
-       } else if (buf->len < Substring_Length(buf->expected) &&
-           ch == buf->expected.start[buf->len]) {
+       } else if (ch == buf->expected[buf->len]) {
                buf->len++;
                return;
 
        } else {
                buf->cap = buf->len + 16;
                buf->data = bmake_malloc(buf->cap);
-               memcpy(buf->data, buf->expected.start, buf->len);
+               memcpy(buf->data, buf->expected, buf->len);
                buf->data[buf->len++] = ch;
        }
 }
@@ -297,8 +296,7 @@
 MAKE_INLINE Substring
 LazyBuf_Get(const LazyBuf *buf)
 {
-       const char *start = buf->data != NULL
-           ? buf->data : buf->expected.start;
+       const char *start = buf->data != NULL ? buf->data : buf->expected;
        return Substring_Init(start, start + buf->len);
 }
 
diff -r bb2b381ce221 -r 17aa0d5c26cb usr.bin/make/var.c
--- a/usr.bin/make/var.c        Sun Apr 11 21:29:57 2021 +0000
+++ b/usr.bin/make/var.c        Sun Apr 11 22:53:45 2021 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: var.c,v 1.922 2021/04/11 21:29:57 rillig Exp $ */
+/*     $NetBSD: var.c,v 1.923 2021/04/11 22:53:45 rillig Exp $ */
 
 /*
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -140,7 +140,7 @@
 #include "metachar.h"
 
 /*     "@(#)var.c      8.3 (Berkeley) 3/19/94" */
-MAKE_RCSID("$NetBSD: var.c,v 1.922 2021/04/11 21:29:57 rillig Exp $");
+MAKE_RCSID("$NetBSD: var.c,v 1.923 2021/04/11 22:53:45 rillig Exp $");
 
 /*
  * Variables are defined using one of the VAR=value assignments.  Their
@@ -2233,7 +2233,7 @@
        const char *p;
 
        p = *pp;
-       LazyBuf_Init(part, Substring_InitStr(p)); /* TODO: O(n^2) */
+       LazyBuf_Init(part, p);
 
        /*
         * Skim through until the matching delimiter is found; pick up
@@ -4136,7 +4136,7 @@
        const char *p = *pp;
        int depth = 0;          /* Track depth so we can spot parse errors. */
 
-       LazyBuf_Init(buf, Substring_InitStr(p));
+       LazyBuf_Init(buf, p);
 
        while (*p != '\0') {
                if ((*p == endc || *p == ':') && depth == 0)