To: vim_dev@googlegroups.com
Subject: Patch 7.3.1028
Fcc: outbox
From: Bram Moolenaar <Bram@moolenaar.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
------------
Patch 7.3.1028
Problem: New regexp performance: Copying a lot of position state.
Solution: Only copy the sub-expressions that are being used.
Files: src/regexp_nfa.c, src/regexp.h
*** ../vim-7.3.1027/src/regexp_nfa.c 2013-05-26 19:19:48.000000000 +0200
--- src/regexp_nfa.c 2013-05-26 21:35:33.000000000 +0200
***************
*** 161,166 ****
--- 161,170 ----
/* NFA regexp \ze operator encountered. */
static int nfa_has_zend = FALSE;
+ /* Number of sub expressions actually being used during execution. 1 if only
+ * the whole match (subexpr 0) is used. */
+ static int nfa_nsubexpr;
+
static int *post_start; /* holds the postfix form of r.e. */
static int *post_end;
static int *post_ptr;
***************
*** 1645,1656 ****
return OK;
}
! typedef struct
{
! char_u *start[NSUBEXP];
! char_u *end[NSUBEXP];
! lpos_T startpos[NSUBEXP];
! lpos_T endpos[NSUBEXP];
} regsub_T;
static int nfa_regmatch __ARGS((nfa_state_T *start, regsub_T *submatch, regsub_T *m));
--- 1649,1666 ----
return OK;
}
! typedef union
{
! struct multipos
! {
! lpos_T start;
! lpos_T end;
! } multilist[NSUBEXP];
! struct linepos
! {
! char_u *start;
! char_u *end;
! } linelist[NSUBEXP];
} regsub_T;
static int nfa_regmatch __ARGS((nfa_state_T *start, regsub_T *submatch, regsub_T *m));
***************
*** 2479,2514 ****
* NFA execution code.
****************************************************************/
! /* nfa_thread_T contains runtime information of a NFA state */
typedef struct
{
nfa_state_T *state;
! regsub_T sub; /* Submatch info. TODO: expensive! */
} nfa_thread_T;
!
typedef struct
{
nfa_thread_T *t;
int n;
} nfa_list_T;
! static void addstate __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int off, int lid, int *match));
! static void addstate_here __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int lid, int *match, int *ip));
static void
! addstate(l, state, m, off, lid, match)
nfa_list_T *l; /* runtime state list */
nfa_state_T *state; /* state to update */
regsub_T *m; /* pointers to subexpressions */
int off; /* byte offset, when -1 go to next line */
int lid;
- int *match; /* found match? */
{
! regsub_T save;
! int subidx = 0;
nfa_thread_T *lastthread;
if (l == NULL || state == NULL)
return;
--- 2489,2527 ----
* NFA execution code.
****************************************************************/
! /* nfa_thread_T contains execution information of a NFA state */
typedef struct
{
nfa_state_T *state;
! regsub_T sub; /* submatch info, only party used */
} nfa_thread_T;
! /* nfa_list_T contains the alternative NFA execution states. */
typedef struct
{
nfa_thread_T *t;
int n;
} nfa_list_T;
! /* Used during execution: whether a match has been found. */
! static int nfa_match;
!
! static void addstate __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int off, int lid));
! static void addstate_here __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int lid, int *ip));
static void
! addstate(l, state, m, off, lid)
nfa_list_T *l; /* runtime state list */
nfa_state_T *state; /* state to update */
regsub_T *m; /* pointers to subexpressions */
int off; /* byte offset, when -1 go to next line */
int lid;
{
! int subidx;
nfa_thread_T *lastthread;
+ lpos_T save_lpos;
+ char_u *save_ptr;
if (l == NULL || state == NULL)
return;
***************
*** 2544,2550 ****
state->lastlist = lid;
lastthread = &l->t[l->n++];
lastthread->state = state;
! lastthread->sub = *m; /* TODO: expensive! */
}
}
--- 2557,2572 ----
state->lastlist = lid;
lastthread = &l->t[l->n++];
lastthread->state = state;
!
! /* Copy the match start and end positions. */
! if (REG_MULTI)
! mch_memmove(&lastthread->sub.multilist[0],
! &m->multilist[0],
! sizeof(struct multipos) * nfa_nsubexpr);
! else
! mch_memmove(&lastthread->sub.linelist[0],
! &m->linelist[0],
! sizeof(struct linepos) * nfa_nsubexpr);
}
}
***************
*** 2556,2571 ****
switch (state->c)
{
case NFA_MATCH:
! *match = TRUE;
break;
case NFA_SPLIT:
! addstate(l, state->out, m, off, lid, match);
! addstate(l, state->out1, m, off, lid, match);
break;
case NFA_SKIP_CHAR:
! addstate(l, state->out, m, off, lid, match);
break;
#if 0
--- 2578,2593 ----
switch (state->c)
{
case NFA_MATCH:
! nfa_match = TRUE;
break;
case NFA_SPLIT:
! addstate(l, state->out, m, off, lid);
! addstate(l, state->out1, m, off, lid);
break;
case NFA_SKIP_CHAR:
! addstate(l, state->out, m, off, lid);
break;
#if 0
***************
*** 2587,2593 ****
case NFA_NOPEN:
case NFA_NCLOSE:
! addstate(l, state->out, m, off, lid, match);
break;
/* If this state is reached, then a recursive call of nfa_regmatch()
--- 2609,2615 ----
case NFA_NOPEN:
case NFA_NCLOSE:
! addstate(l, state->out, m, off, lid);
break;
/* If this state is reached, then a recursive call of nfa_regmatch()
***************
*** 2609,2659 ****
case NFA_MOPEN + 8:
case NFA_MOPEN + 9:
case NFA_ZSTART:
- subidx = state->c - NFA_MOPEN;
if (state->c == NFA_ZSTART)
subidx = 0;
if (REG_MULTI)
{
! save.startpos[subidx] = m->startpos[subidx];
! save.endpos[subidx] = m->endpos[subidx];
if (off == -1)
{
! m->startpos[subidx].lnum = reglnum + 1;
! m->startpos[subidx].col = 0;
}
else
{
! m->startpos[subidx].lnum = reglnum;
! m->startpos[subidx].col =
(colnr_T)(reginput - regline + off);
}
}
else
{
! save.start[subidx] = m->start[subidx];
! save.end[subidx] = m->end[subidx];
! m->start[subidx] = reginput + off;
}
! addstate(l, state->out, m, off, lid, match);
if (REG_MULTI)
! {
! m->startpos[subidx] = save.startpos[subidx];
! m->endpos[subidx] = save.endpos[subidx];
! }
else
! {
! m->start[subidx] = save.start[subidx];
! m->end[subidx] = save.end[subidx];
! }
break;
case NFA_MCLOSE + 0:
if (nfa_has_zend)
{
! addstate(l, state->out, m, off, lid, match);
break;
}
case NFA_MCLOSE + 1:
--- 2631,2674 ----
case NFA_MOPEN + 8:
case NFA_MOPEN + 9:
case NFA_ZSTART:
if (state->c == NFA_ZSTART)
subidx = 0;
+ else
+ subidx = state->c - NFA_MOPEN;
if (REG_MULTI)
{
! save_lpos = m->multilist[subidx].start;
if (off == -1)
{
! m->multilist[subidx].start.lnum = reglnum + 1;
! m->multilist[subidx].start.col = 0;
}
else
{
! m->multilist[subidx].start.lnum = reglnum;
! m->multilist[subidx].start.col =
(colnr_T)(reginput - regline + off);
}
}
else
{
! save_ptr = m->linelist[subidx].start;
! m->linelist[subidx].start = reginput + off;
}
! addstate(l, state->out, m, off, lid);
if (REG_MULTI)
! m->multilist[subidx].start = save_lpos;
else
! m->linelist[subidx].start = save_ptr;
break;
case NFA_MCLOSE + 0:
if (nfa_has_zend)
{
! addstate(l, state->out, m, off, lid);
break;
}
case NFA_MCLOSE + 1:
***************
*** 2666,2709 ****
case NFA_MCLOSE + 8:
case NFA_MCLOSE + 9:
case NFA_ZEND:
- subidx = state->c - NFA_MCLOSE;
if (state->c == NFA_ZEND)
subidx = 0;
if (REG_MULTI)
{
! save.startpos[subidx] = m->startpos[subidx];
! save.endpos[subidx] = m->endpos[subidx];
if (off == -1)
{
! m->endpos[subidx].lnum = reglnum + 1;
! m->endpos[subidx].col = 0;
}
else
{
! m->endpos[subidx].lnum = reglnum;
! m->endpos[subidx].col = (colnr_T)(reginput - regline + off);
}
}
else
{
! save.start[subidx] = m->start[subidx];
! save.end[subidx] = m->end[subidx];
! m->end[subidx] = reginput + off;
}
! addstate(l, state->out, m, off, lid, match);
if (REG_MULTI)
! {
! m->startpos[subidx] = save.startpos[subidx];
! m->endpos[subidx] = save.endpos[subidx];
! }
else
! {
! m->start[subidx] = save.start[subidx];
! m->end[subidx] = save.end[subidx];
! }
break;
}
}
--- 2681,2718 ----
case NFA_MCLOSE + 8:
case NFA_MCLOSE + 9:
case NFA_ZEND:
if (state->c == NFA_ZEND)
subidx = 0;
+ else
+ subidx = state->c - NFA_MCLOSE;
if (REG_MULTI)
{
! save_lpos = m->multilist[subidx].end;
if (off == -1)
{
! m->multilist[subidx].end.lnum = reglnum + 1;
! m->multilist[subidx].end.col = 0;
}
else
{
! m->multilist[subidx].end.lnum = reglnum;
! m->multilist[subidx].end.col =
! (colnr_T)(reginput - regline + off);
}
}
else
{
! save_ptr = m->linelist[subidx].end;
! m->linelist[subidx].end = reginput + off;
}
! addstate(l, state->out, m, off, lid);
if (REG_MULTI)
! m->multilist[subidx].end = save_lpos;
else
! m->linelist[subidx].end = save_ptr;
break;
}
}
***************
*** 2715,2726 ****
* matters for alternatives.
*/
static void
! addstate_here(l, state, m, lid, matchp, ip)
nfa_list_T *l; /* runtime state list */
nfa_state_T *state; /* state to update */
regsub_T *m; /* pointers to subexpressions */
int lid;
- int *matchp; /* found match? */
int *ip;
{
int tlen = l->n;
--- 2724,2734 ----
* matters for alternatives.
*/
static void
! addstate_here(l, state, m, lid, ip)
nfa_list_T *l; /* runtime state list */
nfa_state_T *state; /* state to update */
regsub_T *m; /* pointers to subexpressions */
int lid;
int *ip;
{
int tlen = l->n;
***************
*** 2728,2734 ****
int i = *ip;
/* first add the state(s) at the end, so that we know how many there are */
! addstate(l, state, m, 0, lid, matchp);
/* when "*ip" was at the end of the list, nothing to do */
if (i + 1 == tlen)
--- 2736,2742 ----
int i = *ip;
/* first add the state(s) at the end, so that we know how many there are */
! addstate(l, state, m, 0, lid);
/* when "*ip" was at the end of the list, nothing to do */
if (i + 1 == tlen)
***************
*** 2925,2931 ****
{
int result;
int size = 0;
- int match = FALSE;
int flag = 0;
int old_reglnum = -1;
int go_to_nextline = FALSE;
--- 2933,2938 ----
***************
*** 2951,2956 ****
--- 2958,2964 ----
return FALSE;
}
#endif
+ nfa_match = FALSE;
/* Allocate memory for the lists of nodes */
size = (nstate + 1) * sizeof(nfa_thread_T);
***************
*** 2989,2995 ****
#ifdef ENABLE_LOG
fprintf(log_fd, "(---) STARTSTATE\n");
#endif
! addstate(thislist, start, m, 0, listid, &match);
/* There are two cases when the NFA advances: 1. input char matches the
* NFA node and 2. input char does not match the NFA node, but the next
--- 2997,3003 ----
#ifdef ENABLE_LOG
fprintf(log_fd, "(---) STARTSTATE\n");
#endif
! addstate(thislist, start, m, 0, listid);
/* There are two cases when the NFA advances: 1. input char matches the
* NFA node and 2. input char does not match the NFA node, but the next
***************
*** 3002,3008 ****
#define ADD_POS_NEG_STATE(node) \
ll = listtbl[result ? 1 : 0][node->negated]; \
if (ll != NULL) \
! addstate(ll, node->out , &t->sub, clen, listid + 1, &match);
/*
--- 3010,3016 ----
#define ADD_POS_NEG_STATE(node) \
ll = listtbl[result ? 1 : 0][node->negated]; \
if (ll != NULL) \
! addstate(ll, node->out , &t->sub, clen, listid + 1);
/*
***************
*** 3090,3096 ****
switch (t->state->c)
{
case NFA_MATCH:
! match = TRUE;
*submatch = t->sub;
#ifdef ENABLE_LOG
for (j = 0; j < 4; j++)
--- 3098,3104 ----
switch (t->state->c)
{
case NFA_MATCH:
! nfa_match = TRUE;
*submatch = t->sub;
#ifdef ENABLE_LOG
for (j = 0; j < 4; j++)
***************
*** 3125,3135 ****
* the parent call. */
if (start->c == NFA_MOPEN + 0)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &match, &listidx);
else
{
*m = t->sub;
! match = TRUE;
}
break;
--- 3133,3143 ----
* the parent call. */
if (start->c == NFA_MOPEN + 0)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &listidx);
else
{
*m = t->sub;
! nfa_match = TRUE;
}
break;
***************
*** 3186,3205 ****
reglnum = old_reglnum;
/* Copy submatch info from the recursive call */
if (REG_MULTI)
! for (j = 1; j < NSUBEXP; j++)
{
! t->sub.startpos[j] = m->startpos[j];
! t->sub.endpos[j] = m->endpos[j];
}
else
! for (j = 1; j < NSUBEXP; j++)
{
! t->sub.start[j] = m->start[j];
! t->sub.end[j] = m->end[j];
}
/* t->state->out1 is the corresponding END_INVISIBLE node */
addstate_here(thislist, t->state->out1->out, &t->sub,
! listid, &match, &listidx);
}
else
{
--- 3194,3213 ----
reglnum = old_reglnum;
/* Copy submatch info from the recursive call */
if (REG_MULTI)
! for (j = 1; j < nfa_nsubexpr; j++)
{
! t->sub.multilist[j].start = m->multilist[j].start;
! t->sub.multilist[j].end = m->multilist[j].end;
}
else
! for (j = 1; j < nfa_nsubexpr; j++)
{
! t->sub.linelist[j].start = m->linelist[j].start;
! t->sub.linelist[j].end = m->linelist[j].end;
}
/* t->state->out1 is the corresponding END_INVISIBLE node */
addstate_here(thislist, t->state->out1->out, &t->sub,
! listid, &listidx);
}
else
{
***************
*** 3211,3223 ****
case NFA_BOL:
if (reginput == regline)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &match, &listidx);
break;
case NFA_EOL:
if (curc == NUL)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &match, &listidx);
break;
case NFA_BOW:
--- 3219,3231 ----
case NFA_BOL:
if (reginput == regline)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &listidx);
break;
case NFA_EOL:
if (curc == NUL)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &listidx);
break;
case NFA_BOW:
***************
*** 3245,3251 ****
bow = FALSE;
if (bow)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &match, &listidx);
break;
}
--- 3253,3259 ----
bow = FALSE;
if (bow)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &listidx);
break;
}
***************
*** 3274,3280 ****
eow = FALSE;
if (eow)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &match, &listidx);
break;
}
--- 3282,3288 ----
eow = FALSE;
if (eow)
addstate_here(thislist, t->state->out, &t->sub, listid,
! &listidx);
break;
}
***************
*** 3364,3377 ****
go_to_nextline = TRUE;
/* Pass -1 for the offset, which means taking the position
* at the start of the next line. */
! addstate(nextlist, t->state->out, &t->sub, -1,
! listid + 1, &match);
}
else if (curc == '\n' && reg_line_lbr)
{
/* match \n as if it is an ordinary character */
! addstate(nextlist, t->state->out, &t->sub, 1,
! listid + 1, &match);
}
break;
--- 3372,3383 ----
go_to_nextline = TRUE;
/* Pass -1 for the offset, which means taking the position
* at the start of the next line. */
! addstate(nextlist, t->state->out, &t->sub, -1, listid + 1);
}
else if (curc == '\n' && reg_line_lbr)
{
/* match \n as if it is an ordinary character */
! addstate(nextlist, t->state->out, &t->sub, 1, listid + 1);
}
break;
***************
*** 3400,3413 ****
* CHAR(x), NFA_NOT, CHAR(y), NFA_NOT etc. */
if (curc > 0)
addstate(nextlist, t->state->out, &t->sub, clen,
! listid + 1, &match);
break;
case NFA_ANY:
/* Any char except '\0', (end of input) does not match. */
if (curc > 0)
addstate(nextlist, t->state->out, &t->sub, clen,
! listid + 1, &match);
break;
/*
--- 3406,3419 ----
* CHAR(x), NFA_NOT, CHAR(y), NFA_NOT etc. */
if (curc > 0)
addstate(nextlist, t->state->out, &t->sub, clen,
! listid + 1);
break;
case NFA_ANY:
/* Any char except '\0', (end of input) does not match. */
if (curc > 0)
addstate(nextlist, t->state->out, &t->sub, clen,
! listid + 1);
break;
/*
***************
*** 3597,3609 ****
* Do not add the start state in recursive calls of nfa_regmatch(),
* because recursive calls should only start in the first position.
* Also don't start a match past the first line. */
! if (match == FALSE && start->c == NFA_MOPEN + 0
&& reglnum == 0 && clen != 0)
{
#ifdef ENABLE_LOG
fprintf(log_fd, "(---) STARTSTATE\n");
#endif
! addstate(nextlist, start, m, clen, listid + 1, &match);
}
#ifdef ENABLE_LOG
--- 3603,3615 ----
* Do not add the start state in recursive calls of nfa_regmatch(),
* because recursive calls should only start in the first position.
* Also don't start a match past the first line. */
! if (nfa_match == FALSE && start->c == NFA_MOPEN + 0
&& reglnum == 0 && clen != 0)
{
#ifdef ENABLE_LOG
fprintf(log_fd, "(---) STARTSTATE\n");
#endif
! addstate(nextlist, start, m, clen, listid + 1);
}
#ifdef ENABLE_LOG
***************
*** 3640,3653 ****
vim_free(list[1].t);
vim_free(list[2].t);
list[0].t = list[1].t = list[2].t = NULL;
! if (listids != NULL)
! vim_free(listids);
#undef ADD_POS_NEG_STATE
#ifdef NFA_REGEXP_DEBUG_LOG
fclose(debug);
#endif
! return match;
}
/*
--- 3646,3658 ----
vim_free(list[1].t);
vim_free(list[2].t);
list[0].t = list[1].t = list[2].t = NULL;
! vim_free(listids);
#undef ADD_POS_NEG_STATE
#ifdef NFA_REGEXP_DEBUG_LOG
fclose(debug);
#endif
! return nfa_match;
}
/*
***************
*** 3690,3706 ****
if (REG_MULTI)
{
/* Use 0xff to set lnum to -1 */
! vim_memset(sub.startpos, 0xff, sizeof(lpos_T) * NSUBEXP);
! vim_memset(sub.endpos, 0xff, sizeof(lpos_T) * NSUBEXP);
! vim_memset(m.startpos, 0xff, sizeof(lpos_T) * NSUBEXP);
! vim_memset(m.endpos, 0xff, sizeof(lpos_T) * NSUBEXP);
}
else
{
! vim_memset(sub.start, 0, sizeof(char_u *) * NSUBEXP);
! vim_memset(sub.end, 0, sizeof(char_u *) * NSUBEXP);
! vim_memset(m.start, 0, sizeof(char_u *) * NSUBEXP);
! vim_memset(m.end, 0, sizeof(char_u *) * NSUBEXP);
}
if (nfa_regmatch(start, &sub, &m) == FALSE)
--- 3695,3707 ----
if (REG_MULTI)
{
/* Use 0xff to set lnum to -1 */
! vim_memset(sub.multilist, 0xff, sizeof(struct multipos) * nfa_nsubexpr);
! vim_memset(m.multilist, 0xff, sizeof(struct multipos) * nfa_nsubexpr);
}
else
{
! vim_memset(sub.linelist, 0, sizeof(struct linepos) * nfa_nsubexpr);
! vim_memset(m.linelist, 0, sizeof(struct linepos) * nfa_nsubexpr);
}
if (nfa_regmatch(start, &sub, &m) == FALSE)
***************
*** 3709,3718 ****
cleanup_subexpr();
if (REG_MULTI)
{
! for (i = 0; i < NSUBEXP; i++)
{
! reg_startpos[i] = sub.startpos[i];
! reg_endpos[i] = sub.endpos[i];
}
if (reg_startpos[0].lnum < 0)
--- 3710,3719 ----
cleanup_subexpr();
if (REG_MULTI)
{
! for (i = 0; i < nfa_nsubexpr; i++)
{
! reg_startpos[i] = sub.multilist[i].start;
! reg_endpos[i] = sub.multilist[i].end;
}
if (reg_startpos[0].lnum < 0)
***************
*** 3731,3740 ****
}
else
{
! for (i = 0; i < NSUBEXP; i++)
{
! reg_startp[i] = sub.start[i];
! reg_endp[i] = sub.end[i];
}
if (reg_startp[0] == NULL)
--- 3732,3741 ----
}
else
{
! for (i = 0; i < nfa_nsubexpr; i++)
{
! reg_startp[i] = sub.linelist[i].start;
! reg_endp[i] = sub.linelist[i].end;
}
if (reg_startp[0] == NULL)
***************
*** 3802,3807 ****
--- 3803,3809 ----
reglnum = 0; /* relative to line */
nfa_has_zend = prog->has_zend;
+ nfa_nsubexpr = prog->nsubexp;
nstate = prog->nstate;
for (i = 0; i < nstate; ++i)
***************
*** 3896,3901 ****
--- 3898,3904 ----
prog->engine = &nfa_regengine;
prog->nstate = nstate;
prog->has_zend = nfa_has_zend;
+ prog->nsubexp = regnpar;
#ifdef ENABLE_LOG
nfa_postfix_dump(expr, OK);
nfa_dump(prog);
*** ../vim-7.3.1027/src/regexp.h 2013-05-26 16:57:23.000000000 +0200
--- src/regexp.h 2013-05-26 20:08:09.000000000 +0200
***************
*** 87,92 ****
--- 87,93 ----
regprog_T regprog;
nfa_state_T *start;
int has_zend; /* pattern contains \ze */
+ int nsubexp; /* number of () */
int nstate;
nfa_state_T state[0]; /* actually longer.. */
} nfa_regprog_T;
*** ../vim-7.3.1027/src/version.c 2013-05-26 19:19:48.000000000 +0200
--- src/version.c 2013-05-26 21:44:20.000000000 +0200
***************
*** 730,731 ****
--- 730,733 ----
{ /* Add new patch number below this line */
+ /**/
+ 1028,
/**/
--
Q: What's a light-year?
A: One-third less calories than a regular year.
/// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\
/// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\ an exciting new programming language -- http://www.Zimbu.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///