To: vim_dev@googlegroups.com

Subject: Patch 7.3.1103

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.1103

Problem:    New regexp engine: overhead in saving and restoring.

Solution:   Make saving and restoring list IDs faster.  Don't copy or check \z

	    subexpressions when they are not used.

Files:	    src/regexp_nfa.c

*** ../vim-7.3.1102/src/regexp_nfa.c	2013-06-02 16:40:44.000000000 +0200

--- src/regexp_nfa.c	2013-06-02 21:00:41.000000000 +0200

***************

*** 237,242 ****

--- 237,245 ----

  /* NFA regexp \1 .. \9 encountered. */

  static int nfa_has_backref;

+ /* NFA regexp has \z( ), set zsubexpr. */

+ static int nfa_has_zsubexpr;

+ 

  /* Number of sub expressions actually being used during execution. 1 if only

   * the whole match (subexpr 0) is used. */

  static int nfa_nsubexpr;

***************

*** 272,281 ****

  static nfa_state_T *post2nfa __ARGS((int *postfix, int *end, int nfa_calc_size));

  static int check_char_class __ARGS((int class, int c));

  static void st_error __ARGS((int *postfix, int *end, int *p));

! static void nfa_set_neg_listids __ARGS((nfa_state_T *start));

! static void nfa_set_null_listids __ARGS((nfa_state_T *start));

! static void nfa_save_listids __ARGS((nfa_state_T *start, int *list));

! static void nfa_restore_listids __ARGS((nfa_state_T *start, int *list));

  static int nfa_re_num_cmp __ARGS((long_u val, int op, long_u pos));

  static long nfa_regtry __ARGS((nfa_regprog_T *prog, colnr_T col));

  static long nfa_regexec_both __ARGS((char_u *line, colnr_T col));

--- 275,282 ----

  static nfa_state_T *post2nfa __ARGS((int *postfix, int *end, int nfa_calc_size));

  static int check_char_class __ARGS((int class, int c));

  static void st_error __ARGS((int *postfix, int *end, int *p));

! static void nfa_save_listids __ARGS((nfa_regprog_T *prog, int *list));

! static void nfa_restore_listids __ARGS((nfa_regprog_T *prog, int *list));

  static int nfa_re_num_cmp __ARGS((long_u val, int op, long_u pos));

  static long nfa_regtry __ARGS((nfa_regprog_T *prog, colnr_T col));

  static long nfa_regexec_both __ARGS((char_u *line, colnr_T col));

***************

*** 3000,3005 ****

--- 3001,3024 ----

      return TRUE;

  }

+ #ifdef ENABLE_LOG

+     static void

+ report_state(char *action, regsub_T *sub, nfa_state_T *state, int lid);

+ {

+     int col;

+ 

+     if (sub->in_use <= 0)

+ 	col = -1;

+     else if (REG_MULTI)

+ 	col = sub->list.multi[0].start.col;

+     else

+ 	col = (int)(sub->list.line[0].start - regline);

+     nfa_set_code(state->c);

+     fprintf(log_fd, "> %s state %d to list %d. char %d: %s (start col %d)\n",

+ 	    action, abs(state->id), lid, state->c, code, col);

+ }

+ #endif

+ 

      static void

  addstate(l, state, subs, off)

      nfa_list_T		*l;	/* runtime state list */

***************

*** 3118,3124 ****

  		    if (thread->state->id == state->id

  			    && sub_equal(&thread->subs.norm, &subs->norm)

  #ifdef FEAT_SYN_HL

! 			    && sub_equal(&thread->subs.synt, &subs->synt)

  #endif

  					  )

  			goto skip_add;

--- 3137,3144 ----

  		    if (thread->state->id == state->id

  			    && sub_equal(&thread->subs.norm, &subs->norm)

  #ifdef FEAT_SYN_HL

! 			    && (!nfa_has_zsubexpr ||

! 				   sub_equal(&thread->subs.synt, &subs->synt))

  #endif

  					  )

  			goto skip_add;

***************

*** 3141,3181 ****

  	    thread->state = state;

  	    copy_sub(&thread->subs.norm, &subs->norm);

  #ifdef FEAT_SYN_HL

! 	    copy_sub(&thread->subs.synt, &subs->synt);

  #endif

  #ifdef ENABLE_LOG

! 	    {

! 		int col;

! 

! 		if (thread->subs.norm.in_use <= 0)

! 		    col = -1;

! 		else if (REG_MULTI)

! 		    col = thread->subs.norm.list.multi[0].start.col;

! 		else

! 		    col = (int)(thread->subs.norm.list.line[0].start - regline);

! 		nfa_set_code(state->c);

! 		fprintf(log_fd, "> Adding state %d to list %d. char %d: %s (start col %d)\n",

! 		        abs(state->id), l->id, state->c, code, col);

! 		did_print = TRUE;

! 	    }

  #endif

      }

  #ifdef ENABLE_LOG

      if (!did_print)

!     {

! 	int col;

! 

! 	if (subs->norm.in_use <= 0)

! 	    col = -1;

! 	else if (REG_MULTI)

! 	    col = subs->norm.list.multi[0].start.col;

! 	else

! 	    col = (int)(subs->norm.list.line[0].start - regline);

! 	nfa_set_code(state->c);

! 	fprintf(log_fd, "> Processing state %d for list %d. char %d: %s (start col %d)\n",

! 		abs(state->id), l->id, state->c, code, col);

!     }

  #endif

      switch (state->c)

      {

--- 3161,3178 ----

  	    thread->state = state;

  	    copy_sub(&thread->subs.norm, &subs->norm);

  #ifdef FEAT_SYN_HL

! 	    if (nfa_has_zsubexpr)

! 		copy_sub(&thread->subs.synt, &subs->synt);

  #endif

  #ifdef ENABLE_LOG

! 	    report_state("Adding", &thread->subs.norm, state, l->id);

! 	    did_print = TRUE;

  #endif

      }

  #ifdef ENABLE_LOG

      if (!did_print)

! 	report_state("Processing", &subs->norm, state, l->id);

  #endif

      switch (state->c)

      {

***************

*** 3600,3648 ****

  #endif

  /*

!  * Set all NFA nodes' list ID equal to -1.

   */

      static void

! nfa_set_neg_listids(start)

!     nfa_state_T	    *start;

! {

!     if (start != NULL && start->lastlist >= 0)

!     {

! 	start->lastlist = -1;

! 	nfa_set_neg_listids(start->out);

! 	nfa_set_neg_listids(start->out1);

!     }

! }

! 

! /*

!  * Set all NFA nodes' list ID equal to 0.

!  */

!     static void

! nfa_set_null_listids(start)

!     nfa_state_T	    *start;

! {

!     if (start != NULL && start->lastlist == -1)

!     {

! 	start->lastlist = 0;

! 	nfa_set_null_listids(start->out);

! 	nfa_set_null_listids(start->out1);

!     }

! }

! 

! /*

!  * Save list IDs for all NFA states in "list".

!  */

!     static void

! nfa_save_listids(start, list)

!     nfa_state_T	    *start;

      int		    *list;

  {

!     if (start != NULL && start->lastlist != -1)

!     {

! 	list[abs(start->id)] = start->lastlist;

! 	start->lastlist = -1;

! 	nfa_save_listids(start->out, list);

! 	nfa_save_listids(start->out1, list);

      }

  }

--- 3597,3620 ----

  #endif

  /*

!  * Save list IDs for all NFA states of "prog" into "list".

!  * Also reset the IDs to zero.

   */

      static void

! nfa_save_listids(prog, list)

!     nfa_regprog_T   *prog;

      int		    *list;

  {

!     int		    i;

!     nfa_state_T	    *p;

! 

!     /* Order in the list is reverse, it's a bit faster that way. */

!     p = &prog->state[0];

!     for (i = prog->nstate; --i >= 0; )

!     {

! 	list[i] = p->lastlist;

! 	p->lastlist = 0;

! 	++p;

      }

  }

***************

*** 3650,3664 ****

   * Restore list IDs from "list" to all NFA states.

   */

      static void

! nfa_restore_listids(start, list)

!     nfa_state_T	    *start;

      int		    *list;

  {

!     if (start != NULL && start->lastlist == -1)

      {

! 	start->lastlist = list[abs(start->id)];

! 	nfa_restore_listids(start->out, list);

! 	nfa_restore_listids(start->out1, list);

      }

  }

--- 3622,3639 ----

   * Restore list IDs from "list" to all NFA states.

   */

      static void

! nfa_restore_listids(prog, list)

!     nfa_regprog_T   *prog;

      int		    *list;

  {

!     int		    i;

!     nfa_state_T	    *p;

! 

!     p = &prog->state[0];

!     for (i = prog->nstate; --i >= 0; )

      {

! 	p->lastlist = list[i];

! 	++p;

      }

  }

***************

*** 3673,3679 ****

      return val == pos;

  }

! static int nfa_regmatch __ARGS((nfa_state_T *start, regsubs_T *submatch, regsubs_T *m));

  /*

   * Main matching routine.

--- 3648,3654 ----

      return val == pos;

  }

! static int nfa_regmatch __ARGS((nfa_regprog_T *prog, nfa_state_T *start, regsubs_T *submatch, regsubs_T *m));

  /*

   * Main matching routine.

***************

*** 3686,3692 ****

   * Note: Caller must ensure that: start != NULL.

   */

      static int

! nfa_regmatch(start, submatch, m)

      nfa_state_T		*start;

      regsubs_T		*submatch;

      regsubs_T		*m;

--- 3661,3668 ----

   * Note: Caller must ensure that: start != NULL.

   */

      static int

! nfa_regmatch(prog, start, submatch, m)

!     nfa_regprog_T	*prog;

      nfa_state_T		*start;

      regsubs_T		*submatch;

      regsubs_T		*m;

***************

*** 3872,3878 ****

  		nfa_match = TRUE;

  		copy_sub(&submatch->norm, &t->subs.norm);

  #ifdef FEAT_SYN_HL

! 		copy_sub(&submatch->synt, &t->subs.synt);

  #endif

  #ifdef ENABLE_LOG

  		log_subsexpr(&t->subs);

--- 3848,3855 ----

  		nfa_match = TRUE;

  		copy_sub(&submatch->norm, &t->subs.norm);

  #ifdef FEAT_SYN_HL

! 		if (nfa_has_zsubexpr)

! 		    copy_sub(&submatch->synt, &t->subs.synt);

  #endif

  #ifdef ENABLE_LOG

  		log_subsexpr(&t->subs);

***************

*** 3928,3934 ****

  		    {

  			copy_sub(&m->norm, &t->subs.norm);

  #ifdef FEAT_SYN_HL

! 			copy_sub(&m->synt, &t->subs.synt);

  #endif

  		    }

  		    nfa_match = TRUE;

--- 3905,3912 ----

  		    {

  			copy_sub(&m->norm, &t->subs.norm);

  #ifdef FEAT_SYN_HL

! 			if (nfa_has_zsubexpr)

! 			    copy_sub(&m->synt, &t->subs.synt);

  #endif

  		    }

  		    nfa_match = TRUE;

***************

*** 4024,4035 ****

  		/* Have to clear the listid field of the NFA nodes, so that

  		 * nfa_regmatch() and addstate() can run properly after

  		 * recursion. */

! 		nfa_save_listids(start, listids);

! 		nfa_set_null_listids(start);

  		nfa_endp = endposp;

! 		result = nfa_regmatch(t->state->out, submatch, m);

! 		nfa_set_neg_listids(start);

! 		nfa_restore_listids(start, listids);

  		/* restore position in input text */

  		reginput = save_reginput;

--- 4002,4011 ----

  		/* Have to clear the listid field of the NFA nodes, so that

  		 * nfa_regmatch() and addstate() can run properly after

  		 * recursion. */

! 		nfa_save_listids(prog, listids);

  		nfa_endp = endposp;

! 		result = nfa_regmatch(prog, t->state->out, submatch, m);

! 		nfa_restore_listids(prog, listids);

  		/* restore position in input text */

  		reginput = save_reginput;

***************

*** 4665,4671 ****

--- 4641,4652 ----

  #ifdef FEAT_SYN_HL

      /* Clear the external match subpointers if necessary. */

      if (prog->reghasz == REX_SET)

+     {

+ 	nfa_has_zsubexpr = TRUE;

  	need_clear_zsubexpr = TRUE;

+     }

+     else

+ 	nfa_has_zsubexpr = FALSE;

  #endif

  #ifdef ENABLE_LOG

***************

*** 4694,4700 ****

      clear_sub(&m.synt);

  #endif

!     if (nfa_regmatch(start, &subs, &m) == FALSE)

  	return 0;

      cleanup_subexpr();

--- 4675,4681 ----

      clear_sub(&m.synt);

  #endif

!     if (nfa_regmatch(prog, start, &subs, &m) == FALSE)

  	return 0;

      cleanup_subexpr();

*** ../vim-7.3.1102/src/version.c	2013-06-02 19:22:05.000000000 +0200

--- src/version.c	2013-06-02 21:24:50.000000000 +0200

***************

*** 730,731 ****

--- 730,733 ----

  {   /* Add new patch number below this line */

+ /**/

+     1103,

  /**/

-- 

hundred-and-one symptoms of being an internet addict:

53. To find out what time it is, you send yourself an e-mail and check the

    "Date:" field.

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