diff options
| author | rillig <rillig@NetBSD.org> | 2021-04-11 22:53:45 +0000 |
|---|---|---|
| committer | rillig <rillig@NetBSD.org> | 2021-04-11 22:53:45 +0000 |
| commit | 45ceab83fa6baee2df9ed4f8d56782160fe88f9e (patch) | |
| tree | 7219ac7bd5ad8a4bcdcb41e84b31c4f5176de5c6 /usr.bin/make | |
| parent | 3501fc516c666abba5644f3e1c8bdd6444dab4c4 (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.h | 14 | ||||
| -rw-r--r-- | usr.bin/make/var.c | 8 |
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) |
