To: vim_dev@googlegroups.com
Subject: Patch 7.3.1029
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.1029
Problem: New regexp performance: Unused position state being copied.
Solution: Keep track of which positions are actually valid.
Files: src/regexp_nfa.c
*** ../vim-7.3.1028/src/regexp_nfa.c 2013-05-26 21:47:22.000000000 +0200
--- src/regexp_nfa.c 2013-05-26 22:45:26.000000000 +0200
***************
*** 1649,1670 ****
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));
-
#ifdef DEBUG
static char_u code[50];
--- 1649,1654 ----
***************
*** 2489,2494 ****
--- 2473,2498 ----
* NFA execution code.
****************************************************************/
+ typedef struct
+ {
+ int in_use; /* number of subexpr with useful info */
+
+ /* When REG_MULTI is TRUE multilist is used, otherwise linelist. */
+ union
+ {
+ struct multipos
+ {
+ lpos_T start;
+ lpos_T end;
+ } multilist[NSUBEXP];
+ struct linepos
+ {
+ char_u *start;
+ char_u *end;
+ } linelist[NSUBEXP];
+ };
+ } regsub_T;
+
/* nfa_thread_T contains execution information of a NFA state */
typedef struct
{
***************
*** 2507,2513 ****
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
--- 2511,2516 ----
***************
*** 2521,2527 ****
--- 2524,2532 ----
int subidx;
nfa_thread_T *lastthread;
lpos_T save_lpos;
+ int save_in_use;
char_u *save_ptr;
+ int i;
if (l == NULL || state == NULL)
return;
***************
*** 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);
}
}
--- 2562,2580 ----
state->lastlist = lid;
lastthread = &l->t[l->n++];
lastthread->state = state;
! lastthread->sub.in_use = m->in_use;
! if (m->in_use > 0)
! {
! /* Copy the match start and end positions. */
! if (REG_MULTI)
! mch_memmove(&lastthread->sub.multilist[0],
! &m->multilist[0],
! sizeof(struct multipos) * m->in_use);
! else
! mch_memmove(&lastthread->sub.linelist[0],
! &m->linelist[0],
! sizeof(struct linepos) * m->in_use);
! }
}
}
***************
*** 2636,2644 ****
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;
--- 2644,2668 ----
else
subidx = state->c - NFA_MOPEN;
+ /* Set the position (with "off") in the subexpression. Save and
+ * restore it when it was in use. Otherwise fill any gap. */
if (REG_MULTI)
{
! if (subidx < m->in_use)
! {
! save_lpos = m->multilist[subidx].start;
! save_in_use = -1;
! }
! else
! {
! save_in_use = m->in_use;
! for (i = m->in_use; i < subidx; ++i)
! {
! m->multilist[i].start.lnum = -1;
! m->multilist[i].end.lnum = -1;
! }
! m->in_use = subidx + 1;
! }
if (off == -1)
{
m->multilist[subidx].start.lnum = reglnum + 1;
***************
*** 2653,2668 ****
}
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:
--- 2677,2711 ----
}
else
{
! if (subidx < m->in_use)
! {
! save_ptr = m->linelist[subidx].start;
! save_in_use = -1;
! }
! else
! {
! save_in_use = m->in_use;
! for (i = m->in_use; i < subidx; ++i)
! {
! m->linelist[i].start = NULL;
! m->linelist[i].end = NULL;
! }
! m->in_use = subidx + 1;
! }
m->linelist[subidx].start = reginput + off;
}
addstate(l, state->out, m, off, lid);
! if (save_in_use == -1)
! {
! if (REG_MULTI)
! m->multilist[subidx].start = save_lpos;
! else
! m->linelist[subidx].start = save_ptr;
! }
else
! m->in_use = save_in_use;
break;
case NFA_MCLOSE + 0:
***************
*** 2686,2691 ****
--- 2729,2739 ----
else
subidx = state->c - NFA_MCLOSE;
+ /* We don't fill in gaps here, there must have been an MOPEN that
+ * has done that. */
+ save_in_use = m->in_use;
+ if (m->in_use <= subidx)
+ m->in_use = subidx + 1;
if (REG_MULTI)
{
save_lpos = m->multilist[subidx].end;
***************
*** 2713,2718 ****
--- 2761,2767 ----
m->multilist[subidx].end = save_lpos;
else
m->linelist[subidx].end = save_ptr;
+ m->in_use = save_in_use;
break;
}
}
***************
*** 2917,2922 ****
--- 2966,2973 ----
}
}
+ static int nfa_regmatch __ARGS((nfa_state_T *start, regsub_T *submatch, regsub_T *m));
+
/*
* Main matching routine.
*
***************
*** 2960,2966 ****
#endif
nfa_match = FALSE;
! /* Allocate memory for the lists of nodes */
size = (nstate + 1) * sizeof(nfa_thread_T);
list[0].t = (nfa_thread_T *)lalloc(size, TRUE);
list[1].t = (nfa_thread_T *)lalloc(size, TRUE);
--- 3011,3017 ----
#endif
nfa_match = FALSE;
! /* Allocate memory for the lists of nodes. */
size = (nstate + 1) * sizeof(nfa_thread_T);
list[0].t = (nfa_thread_T *)lalloc(size, TRUE);
list[1].t = (nfa_thread_T *)lalloc(size, TRUE);
***************
*** 3099,3105 ****
{
case NFA_MATCH:
nfa_match = TRUE;
! *submatch = t->sub;
#ifdef ENABLE_LOG
for (j = 0; j < 4; j++)
if (REG_MULTI)
--- 3150,3168 ----
{
case NFA_MATCH:
nfa_match = TRUE;
! submatch->in_use = t->sub.in_use;
! if (REG_MULTI)
! for (j = 0; j < submatch->in_use; j++)
! {
! submatch->multilist[j].start = t->sub.multilist[j].start;
! submatch->multilist[j].end = t->sub.multilist[j].end;
! }
! else
! for (j = 0; j < submatch->in_use; j++)
! {
! submatch->linelist[j].start = t->sub.linelist[j].start;
! submatch->linelist[j].end = t->sub.linelist[j].end;
! }
#ifdef ENABLE_LOG
for (j = 0; j < 4; j++)
if (REG_MULTI)
***************
*** 3194,3210 ****
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);
--- 3257,3275 ----
reglnum = old_reglnum;
/* Copy submatch info from the recursive call */
if (REG_MULTI)
! for (j = 1; j < m->in_use; j++)
{
t->sub.multilist[j].start = m->multilist[j].start;
t->sub.multilist[j].end = m->multilist[j].end;
}
else
! for (j = 1; j < m->in_use; j++)
{
t->sub.linelist[j].start = m->linelist[j].start;
t->sub.linelist[j].end = m->linelist[j].end;
}
+ t->sub.in_use = m->in_use;
+
/* t->state->out1 is the corresponding END_INVISIBLE node */
addstate_here(thislist, t->state->out1->out, &t->sub,
listid, &listidx);
***************
*** 3703,3708 ****
--- 3768,3775 ----
vim_memset(sub.linelist, 0, sizeof(struct linepos) * nfa_nsubexpr);
vim_memset(m.linelist, 0, sizeof(struct linepos) * nfa_nsubexpr);
}
+ sub.in_use = 0;
+ m.in_use = 0;
if (nfa_regmatch(start, &sub, &m) == FALSE)
return 0;
***************
*** 3710,3716 ****
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;
--- 3777,3783 ----
cleanup_subexpr();
if (REG_MULTI)
{
! for (i = 0; i < sub.in_use; i++)
{
reg_startpos[i] = sub.multilist[i].start;
reg_endpos[i] = sub.multilist[i].end;
***************
*** 3732,3738 ****
}
else
{
! for (i = 0; i < nfa_nsubexpr; i++)
{
reg_startp[i] = sub.linelist[i].start;
reg_endp[i] = sub.linelist[i].end;
--- 3799,3805 ----
}
else
{
! for (i = 0; i < sub.in_use; i++)
{
reg_startp[i] = sub.linelist[i].start;
reg_endp[i] = sub.linelist[i].end;
*** ../vim-7.3.1028/src/version.c 2013-05-26 21:47:22.000000000 +0200
--- src/version.c 2013-05-26 22:53:55.000000000 +0200
***************
*** 730,731 ****
--- 730,733 ----
{ /* Add new patch number below this line */
+ /**/
+ 1029,
/**/
--
I used to be indecisive, now I'm not sure.
/// 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 ///