Module Name: src
Committed By: rillig
Date: Sun Apr 11 22:53:46 UTC 2021
Modified Files:
src/usr.bin/make: str.h var.c
Log Message:
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.
To generate a diff of this commit:
cvs rdiff -u -r1.4 -r1.5 src/usr.bin/make/str.h
cvs rdiff -u -r1.922 -r1.923 src/usr.bin/make/var.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/make/str.h
diff -u src/usr.bin/make/str.h:1.4 src/usr.bin/make/str.h:1.5
--- src/usr.bin/make/str.h:1.4 Sun Apr 11 20:38:43 2021
+++ src/usr.bin/make/str.h Sun Apr 11 22:53:45 2021
@@ -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 <[email protected]>
@@ -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, Subst
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);
}
Index: src/usr.bin/make/var.c
diff -u src/usr.bin/make/var.c:1.922 src/usr.bin/make/var.c:1.923
--- src/usr.bin/make/var.c:1.922 Sun Apr 11 21:29:57 2021
+++ src/usr.bin/make/var.c Sun Apr 11 22:53:45 2021
@@ -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 start
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)
