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    ///