Zsh Mailing List Archive
Messages sorted by:
Reverse Date,
Date,
Thread,
Author
Re: Extended globbing seems to have become much slower in recent versions of Zsh
On Fri, 04 Mar 2016 14:20:46 +0000
Peter Stephenson <p.stephenson@xxxxxxxxxxx> wrote:
> Another possible clue here: the exclusion modifiers require additional
> allocations when running the platform --- see line 3037 of pattern.c
> (there's another one later). This is currently permanently rather than
> heap allocated. It's easy to change to heap, but I wouldn't suggest
> that --- with any kind of complicated backtracking this would eat memory
> like there's no tomorrow.
>
> It would be possible to use local pools of memory for this, however, so
> it didn't get allocated and freed every single time it was needed. I
> think we only need one allocation for each occurrence of an exclusion,
> and usually there are very few in a pattern, so this isn't hard to
> manage. This might be an optimisation worth having anyway.
This is what I meant. It may not be related to the slow down in
question, but it should speed up repeated use of exclusion patterns in
any case.
If you have DEBUG turned on you get an output for the maximum number of
pool entries that were in use at one time in the globbing tests, which
is currently 4. That's a measure of how complcated repeated patterns
with exclusion that required backtracking became. 4 suggests the pool
method is eminently practical.
I ran the globtests under valgrind and it reported no errors.
Follow-ups on the details of this patch should go to zsh-workers.
diff --git a/Src/glob.c b/Src/glob.c
index 2051016..3aa5a3c 100644
--- a/Src/glob.c
+++ b/Src/glob.c
@@ -1827,11 +1827,14 @@ zglob(LinkList list, LinkNode np, int nountok)
sizeof(struct gmatch));
matchct = 0;
pattrystart();
+ patopt_glob_use();
/* The actual processing takes place here: matches go into *
* matchbuf. This is the only top-level call to scanner(). */
scanner(q, shortcircuit);
+ patopt_glob_release();
+
/* Deal with failures to match depending on options */
if (matchct)
badcshglob |= 2; /* at least one cmd. line expansion O.K. */
diff --git a/Src/pattern.c b/Src/pattern.c
index 72c7d97..348779c 100644
--- a/Src/pattern.c
+++ b/Src/pattern.c
@@ -73,7 +73,7 @@
/*
* The following union is used mostly for alignment purposes.
- * Normal nodes are longs, while certain nodes take a char * as an argument;
+ * Normal nodes are longs, while certain nodes take a pointer as an argument;
* here we make sure that they both work out to the same length.
* The compiled regexp we construct consists of upats stuck together;
* anything else to be added (strings, numbers) is stuck after and
@@ -84,6 +84,7 @@
union upat {
long l;
unsigned char *p;
+ Patopt_ref ref;
};
typedef union upat *Upat;
@@ -1852,10 +1853,129 @@ static void patoptail(long p, long val)
/*
+ * Optimisation of memory allocation for pattern exclusion.
+ * This is to reduce the amount of allocation we do when
+ * running a platform. We'll keep a pool available for
+ * this purpose. We also optimise so that we never free
+ * or reduce string sizes across globbing for a particular
+ * pattern as this will have similar uses multiple times.
+ */
+
+/* The size of the pool */
+#define PATOPT_MEM_POOL_SIZE (16)
+/* The maximum length of entries in the pool we'll retain normally */
+#define PATOPT_MEM_MAX_LEN (128)
+
+/* Flag that we are globbing and should keep memory */
+static int patopt_glob;
+/* The pool */
+struct patopt_mem patopt_pool[PATOPT_MEM_POOL_SIZE];
+#ifdef DEBUG
+/* The most pool entries we've usd at once */
+static int patopt_pool_max_used;
+#endif
+
+static void
+patopt_free_excess(void)
+{
+ int iref;
+ Patopt_mem entry;
+ for (iref = 0, entry = patopt_pool;
+ iref < PATOPT_MEM_POOL_SIZE;
+ iref++, entry++) {
+ if (!entry->in_use /* wow, that's paranoid */
+ && entry->len > PATOPT_MEM_MAX_LEN)
+ {
+ free(entry->mem.ptr);
+ entry->mem.ptr = NULL;
+ entry->len = 0;
+ }
+ }
+}
+
+/**/
+mod_export void
+patopt_glob_use(void)
+{
+ patopt_glob++;
+}
+
+/**/
+mod_export void
+patopt_glob_release(void)
+{
+ if (!--patopt_glob)
+ patopt_free_excess();
+ DPUTS(patopt_glob < 0, "unmatched patopt_glob_release call");
+}
+
+/**/
+static Patopt_ref
+patopt_mem_alloc(size_t allocsize)
+{
+ /*
+ * The strategy here is we find the first unused entry and if
+ * it's too small we resize it immediately, on the basis that
+ * there will be many calls requiring the same (maximum) allocation
+ * size.
+ */
+ int iref;
+ Patopt_mem entry;
+ Patopt_ref ref;
+ for (iref = 0, entry = patopt_pool;
+ iref < PATOPT_MEM_POOL_SIZE;
+ iref++, entry++) {
+ if (!entry->in_use) {
+ /* Grab this one */
+ entry->in_use = 1;
+ entry->mem.ref = iref;
+ if (entry->len < allocsize) {
+ /* Handles null */
+ entry->mem.ptr = (unsigned char *)
+ zrealloc(entry->mem.ptr, allocsize);
+ entry->len = allocsize;
+ }
+#ifdef DEBUG
+ if (iref+1 > patopt_pool_max_used) {
+ patopt_pool_max_used = iref + 1;
+ setiparam("ZSH_PATOPT_POOL_MAX_USED", patopt_pool_max_used);
+ }
+#endif
+ return &entry->mem;
+ }
+ }
+ /*
+ * Overflowed pool, just allocate normally, except we need
+ * the reference structure as well which we'll tack on the
+ * front.
+ */
+ ref = (Patopt_ref)zalloc(sizeof(struct patopt_ref) + allocsize);
+ ref->ptr = (unsigned char *)ref + sizeof(struct patopt_ref);
+ ref->ref = -1;
+ return ref;
+}
+
+
+static void
+patopt_mem_free(Patopt_ref ref)
+{
+ Patopt_mem entry;
+ if (ref->ref < 0) {
+ free((void *)ref);
+ return;
+ }
+ entry = patopt_pool + ref->ref;
+ entry->in_use = 0;
+}
+
+/*
* Run a pattern.
+ *
+ * P.S. this code is not re-entrant...
*/
static char *patinstart; /* Start of input string */
static char *patinend; /* End of input string */
+static int patintotlen; /* Full length of input string */
static char *patinput; /* String input pointer */
static char *patinpath; /* Full path for use with ~ exclusions */
static int patinlen; /* Length of last successful match.
@@ -2291,6 +2411,7 @@ pattryrefs(Patprog prog, char *string, int stringlen, int unmetalenin,
patflags = prog->flags;
patinend = patinstart + stringlen;
+ patintotlen = stringlen;
/*
* From now on we do not require NULL termination of
* the test string. There should also be no more references
@@ -2302,7 +2423,7 @@ pattryrefs(Patprog prog, char *string, int stringlen, int unmetalenin,
* Either we are testing against a pure string,
* or we can match anything at all.
*/
- int ret, pstrlen;
+ int pstrlen;
char *pstr;
if (patstralloc->alloced)
{
@@ -2404,8 +2525,6 @@ pattryrefs(Patprog prog, char *string, int stringlen, int unmetalenin,
}
}
}
-
- return ret;
} else {
int q = queue_signal_level();
@@ -2456,6 +2575,7 @@ pattryrefs(Patprog prog, char *string, int stringlen, int unmetalenin,
dont_queue_signals();
+ patopt_glob_use();
if (patmatch((Upat)progstr)) {
/*
* we were lazy and didn't save the globflags if an exclusion
@@ -2594,11 +2714,11 @@ pattryrefs(Patprog prog, char *string, int stringlen, int unmetalenin,
ret = 1;
} else
ret = 0;
+ patopt_glob_release();
restore_queue_signals(q);
-
- return ret;
}
+ return ret;
}
/*
@@ -2947,9 +3067,9 @@ patmatch(Upat prog)
after = P_OPERAND(scan);
DPUTS(!P_ISEXCLUDE(after),
"BUG: EXCSYNC not followed by EXCLUDE.");
- DPUTS(!P_OPERAND(after)->p,
+ DPUTS(!P_OPERAND(after)->ref,
"BUG: EXCSYNC not handled by EXCLUDE");
- syncptr = P_OPERAND(after)->p + (patinput - patinstart);
+ syncptr = P_OPERAND(after)->ref->ptr + (patinput - patinstart);
/*
* If we already matched from here, this time we fail.
* See WBRANCH code for story about error count.
@@ -3018,7 +3138,7 @@ patmatch(Upat prog)
*/
Upat syncstrp;
char *origpatinend;
- unsigned char *oldsyncstr;
+ Patopt_ref oldsyncstr;
char *matchpt = NULL;
int ret, savglobdots, matchederrs = 0;
int savparsfound = parsfound;
@@ -3032,9 +3152,15 @@ patmatch(Upat prog)
* (foo~bar)(foo~bar)... from the exclusion point
* of view, so we use a different sync string.
*/
- oldsyncstr = syncstrp->p;
- syncstrp->p = (unsigned char *)
- zshcalloc((patinend - patinstart) + 1);
+ oldsyncstr = syncstrp->ref;
+ /*
+ * Allocate maximum length we could need, in
+ * case we do this repeatedly, so we don't
+ * to reallocate.
+ */
+ syncstrp->ref = patopt_mem_alloc(patintotlen+1);
+ memset(syncstrp->ref->ptr, 0,
+ (patinend - patinstart) + 1);
origpatinend = patinend;
while ((ret = patmatch(P_OPERAND(scan)))) {
unsigned char *syncpt;
@@ -3054,9 +3180,11 @@ patmatch(Upat prog)
* possibilities for approximation have been
* checked.)
*/
- for (syncpt = syncstrp->p; !*syncpt; syncpt++)
+ for (syncpt = syncstrp->ref->ptr;
+ !*syncpt;
+ syncpt++)
;
- synclen = syncpt - syncstrp->p;
+ synclen = syncpt - syncstrp->ref->ptr;
if (patinstart + synclen != patinend) {
/*
* Temporarily mark the string as
@@ -3129,9 +3257,8 @@ patmatch(Upat prog)
patglobflags = savglobflags;
errsfound = saverrsfound;
}
- zfree((char *)syncstrp->p,
- (patinend - patinstart) + 1);
- syncstrp->p = oldsyncstr;
+ patopt_mem_free(syncstrp->ref);
+ syncstrp->ref = oldsyncstr;
if (ret) {
patinput = matchpt;
errsfound = matchederrs;
@@ -3141,7 +3268,8 @@ patmatch(Upat prog)
P_ISEXCLUDE(scan))
;
} else {
- int ret = 1, pfree = 0;
+ int ret = 1;
+ Patopt_ref pfree = NULL;
Upat ptrp = NULL;
unsigned char *ptr;
if (P_OP(scan) == P_WBRANCH) {
@@ -3162,12 +3290,13 @@ patmatch(Upat prog)
*/
opnd = P_OPERAND(scan);
ptrp = opnd++;
- if (!ptrp->p) {
- ptrp->p = (unsigned char *)
- zshcalloc((patinend - patinstart) + 1);
- pfree = 1;
+ if (!ptrp->ref) {
+ pfree = ptrp->ref =
+ patopt_mem_alloc(patintotlen+1);
+ memset(pfree->ptr, 0,
+ (patinend - patinstart) + 1);
}
- ptr = ptrp->p + (patinput - patinstart);
+ ptr = ptrp->ref->ptr + (patinput - patinstart);
/*
* Without approximation, this is just a
@@ -3188,9 +3317,8 @@ patmatch(Upat prog)
if (ret)
ret = patmatch(opnd);
if (pfree) {
- zfree((char *)ptrp->p,
- (patinend - patinstart) + 1);
- ptrp->p = NULL;
+ patopt_mem_free(pfree);
+ ptrp->ref = NULL;
}
if (ret)
return 1;
diff --git a/Src/zsh.h b/Src/zsh.h
index eee31da..34bdc50 100644
--- a/Src/zsh.h
+++ b/Src/zsh.h
@@ -1613,6 +1613,38 @@ typedef struct zpc_disables_save *Zpc_disables_save;
#define PP_UNKWN 20
/* Range: token followed by the (possibly multibyte) start and end */
#define PP_RANGE 21
+/*
+ * A reference to memory that may be from the pool or not.
+ * For convenience in use it contains the reference to say where it
+ * has come from as well as the memory.
+ *
+ * If this was from the pool, ptr is allocated from zalloc().
+ *
+ * If this was not from the pool, ref is -1, the structure is
+ * allocated form zalloc() with ptr pointing sizeof(the structure)
+ * bytes into that chunk.
+ */
+
+/**/
+struct patopt_ref
+{
+ /* Reference to a pool entry, or -1 if from zalloc() */
+ int ref;
+ /*
+ * Pointer to the memory.
+ */
+ unsigned char *ptr;
+};
+typedef struct patopt_ref *Patopt_ref;
+
+/* A chunk of emory from the pool */
+struct patopt_mem
+{
+ size_t len;
+ struct patopt_ref mem;
+ int in_use;
+};
+typedef struct patopt_mem *Patopt_mem;
/*
* Argument to get_match_ret() in glob.c
diff --git a/Test/D02glob.ztst b/Test/D02glob.ztst
index a6b704a..76209a0 100644
--- a/Test/D02glob.ztst
+++ b/Test/D02glob.ztst
@@ -7,7 +7,11 @@
: >glob.tmp/{,{dir1,dir2}/}{a,b,c}
globtest () {
- $ZTST_testdir/../Src/zsh -f $ZTST_srcdir/../Misc/$1
+ $ZTST_testdir/../Src/zsh -fc "
+ . $ZTST_srcdir/../Misc/$1
+ if [[ -n \$ZSH_PATOPT_POOL_MAX_USED ]]; then
+ print -u $ZTST_fd \"Max patopt_pool use: \$ZSH_PATOPT_POOL_MAX_USED\"
+ fi"
}
regress_absolute_path_and_core_dump() {
Messages sorted by:
Reverse Date,
Date,
Thread,
Author