summaryrefslogtreecommitdiff
path: root/usr.bin/make
diff options
context:
space:
mode:
authorrillig <rillig@NetBSD.org>2021-04-11 22:53:45 +0000
committerrillig <rillig@NetBSD.org>2021-04-11 22:53:45 +0000
commit45ceab83fa6baee2df9ed4f8d56782160fe88f9e (patch)
tree7219ac7bd5ad8a4bcdcb41e84b31c4f5176de5c6 /usr.bin/make
parent3501fc516c666abba5644f3e1c8bdd6444dab4c4 (diff)
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 (limited to 'usr.bin/make')
-rw-r--r--usr.bin/make/str.h14
-rw-r--r--usr.bin/make/var.c8
2 files changed, 10 insertions, 12 deletions
diff --git a/usr.bin/make/str.h b/usr.bin/make/str.h
index 896ca009777..f6422550197 100644
--- a/usr.bin/make/str.h
+++ b/usr.bin/make/str.h
@@ -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>
@@ -59,7 +59,7 @@ typedef struct LazyBuf {
char *data;
size_t len;
size_t cap;
- Substring expected;
+ const char *expected;
void *freeIt;
} LazyBuf;
@@ -231,7 +231,7 @@ Substring_Basename(Substring pathname)
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 @@ LazyBuf_Add(LazyBuf *buf, char ch)
}
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 @@ LazyBuf_AddSubstring(LazyBuf *buf, Substring sub)
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 --git a/usr.bin/make/var.c b/usr.bin/make/var.c
index e785b396649..ff7b72897a2 100644
--- a/usr.bin/make/var.c
+++ b/usr.bin/make/var.c
@@ -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 @@ ParseModifierPartSubst(
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 @@ ParseVarname(const char **pp, char startc, char endc,
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)