home *** CD-ROM | disk | FTP | other *** search
/ vim.ftp.fu-berlin.de / 2015-02-03.vim.ftp.fu-berlin.de.tar / vim.ftp.fu-berlin.de / patches / 7.3 / 7.3.1103 < prev    next >
Encoding:
Internet Message Format  |  2013-06-01  |  11.0 KB
  1. To: vim_dev@googlegroups.com
  2. Subject: Patch 7.3.1103
  3. Fcc: outbox
  4. From: Bram Moolenaar <Bram@moolenaar.net>
  5. Mime-Version: 1.0
  6. Content-Type: text/plain; charset=UTF-8
  7. Content-Transfer-Encoding: 8bit
  8. ------------
  9.  
  10. Patch 7.3.1103
  11. Problem:    New regexp engine: overhead in saving and restoring.
  12. Solution:   Make saving and restoring list IDs faster.  Don't copy or check \z
  13.         subexpressions when they are not used.
  14. Files:        src/regexp_nfa.c
  15.  
  16.  
  17. *** ../vim-7.3.1102/src/regexp_nfa.c    2013-06-02 16:40:44.000000000 +0200
  18. --- src/regexp_nfa.c    2013-06-02 21:00:41.000000000 +0200
  19. ***************
  20. *** 237,242 ****
  21. --- 237,245 ----
  22.   /* NFA regexp \1 .. \9 encountered. */
  23.   static int nfa_has_backref;
  24.   
  25. + /* NFA regexp has \z( ), set zsubexpr. */
  26. + static int nfa_has_zsubexpr;
  27. + 
  28.   /* Number of sub expressions actually being used during execution. 1 if only
  29.    * the whole match (subexpr 0) is used. */
  30.   static int nfa_nsubexpr;
  31. ***************
  32. *** 272,281 ****
  33.   static nfa_state_T *post2nfa __ARGS((int *postfix, int *end, int nfa_calc_size));
  34.   static int check_char_class __ARGS((int class, int c));
  35.   static void st_error __ARGS((int *postfix, int *end, int *p));
  36. ! static void nfa_set_neg_listids __ARGS((nfa_state_T *start));
  37. ! static void nfa_set_null_listids __ARGS((nfa_state_T *start));
  38. ! static void nfa_save_listids __ARGS((nfa_state_T *start, int *list));
  39. ! static void nfa_restore_listids __ARGS((nfa_state_T *start, int *list));
  40.   static int nfa_re_num_cmp __ARGS((long_u val, int op, long_u pos));
  41.   static long nfa_regtry __ARGS((nfa_regprog_T *prog, colnr_T col));
  42.   static long nfa_regexec_both __ARGS((char_u *line, colnr_T col));
  43. --- 275,282 ----
  44.   static nfa_state_T *post2nfa __ARGS((int *postfix, int *end, int nfa_calc_size));
  45.   static int check_char_class __ARGS((int class, int c));
  46.   static void st_error __ARGS((int *postfix, int *end, int *p));
  47. ! static void nfa_save_listids __ARGS((nfa_regprog_T *prog, int *list));
  48. ! static void nfa_restore_listids __ARGS((nfa_regprog_T *prog, int *list));
  49.   static int nfa_re_num_cmp __ARGS((long_u val, int op, long_u pos));
  50.   static long nfa_regtry __ARGS((nfa_regprog_T *prog, colnr_T col));
  51.   static long nfa_regexec_both __ARGS((char_u *line, colnr_T col));
  52. ***************
  53. *** 3000,3005 ****
  54. --- 3001,3024 ----
  55.       return TRUE;
  56.   }
  57.   
  58. + #ifdef ENABLE_LOG
  59. +     static void
  60. + report_state(char *action, regsub_T *sub, nfa_state_T *state, int lid);
  61. + {
  62. +     int col;
  63. + 
  64. +     if (sub->in_use <= 0)
  65. +     col = -1;
  66. +     else if (REG_MULTI)
  67. +     col = sub->list.multi[0].start.col;
  68. +     else
  69. +     col = (int)(sub->list.line[0].start - regline);
  70. +     nfa_set_code(state->c);
  71. +     fprintf(log_fd, "> %s state %d to list %d. char %d: %s (start col %d)\n",
  72. +         action, abs(state->id), lid, state->c, code, col);
  73. + }
  74. + #endif
  75. + 
  76.       static void
  77.   addstate(l, state, subs, off)
  78.       nfa_list_T        *l;    /* runtime state list */
  79. ***************
  80. *** 3118,3124 ****
  81.               if (thread->state->id == state->id
  82.                   && sub_equal(&thread->subs.norm, &subs->norm)
  83.   #ifdef FEAT_SYN_HL
  84. !                 && sub_equal(&thread->subs.synt, &subs->synt)
  85.   #endif
  86.                         )
  87.               goto skip_add;
  88. --- 3137,3144 ----
  89.               if (thread->state->id == state->id
  90.                   && sub_equal(&thread->subs.norm, &subs->norm)
  91.   #ifdef FEAT_SYN_HL
  92. !                 && (!nfa_has_zsubexpr ||
  93. !                    sub_equal(&thread->subs.synt, &subs->synt))
  94.   #endif
  95.                         )
  96.               goto skip_add;
  97. ***************
  98. *** 3141,3181 ****
  99.           thread->state = state;
  100.           copy_sub(&thread->subs.norm, &subs->norm);
  101.   #ifdef FEAT_SYN_HL
  102. !         copy_sub(&thread->subs.synt, &subs->synt);
  103.   #endif
  104.   #ifdef ENABLE_LOG
  105. !         {
  106. !         int col;
  107. ! 
  108. !         if (thread->subs.norm.in_use <= 0)
  109. !             col = -1;
  110. !         else if (REG_MULTI)
  111. !             col = thread->subs.norm.list.multi[0].start.col;
  112. !         else
  113. !             col = (int)(thread->subs.norm.list.line[0].start - regline);
  114. !         nfa_set_code(state->c);
  115. !         fprintf(log_fd, "> Adding state %d to list %d. char %d: %s (start col %d)\n",
  116. !                 abs(state->id), l->id, state->c, code, col);
  117. !         did_print = TRUE;
  118. !         }
  119.   #endif
  120.       }
  121.   
  122.   #ifdef ENABLE_LOG
  123.       if (!did_print)
  124. !     {
  125. !     int col;
  126. ! 
  127. !     if (subs->norm.in_use <= 0)
  128. !         col = -1;
  129. !     else if (REG_MULTI)
  130. !         col = subs->norm.list.multi[0].start.col;
  131. !     else
  132. !         col = (int)(subs->norm.list.line[0].start - regline);
  133. !     nfa_set_code(state->c);
  134. !     fprintf(log_fd, "> Processing state %d for list %d. char %d: %s (start col %d)\n",
  135. !         abs(state->id), l->id, state->c, code, col);
  136. !     }
  137.   #endif
  138.       switch (state->c)
  139.       {
  140. --- 3161,3178 ----
  141.           thread->state = state;
  142.           copy_sub(&thread->subs.norm, &subs->norm);
  143.   #ifdef FEAT_SYN_HL
  144. !         if (nfa_has_zsubexpr)
  145. !         copy_sub(&thread->subs.synt, &subs->synt);
  146.   #endif
  147.   #ifdef ENABLE_LOG
  148. !         report_state("Adding", &thread->subs.norm, state, l->id);
  149. !         did_print = TRUE;
  150.   #endif
  151.       }
  152.   
  153.   #ifdef ENABLE_LOG
  154.       if (!did_print)
  155. !     report_state("Processing", &subs->norm, state, l->id);
  156.   #endif
  157.       switch (state->c)
  158.       {
  159. ***************
  160. *** 3600,3648 ****
  161.   #endif
  162.   
  163.   /*
  164. !  * Set all NFA nodes' list ID equal to -1.
  165.    */
  166.       static void
  167. ! nfa_set_neg_listids(start)
  168. !     nfa_state_T        *start;
  169. ! {
  170. !     if (start != NULL && start->lastlist >= 0)
  171. !     {
  172. !     start->lastlist = -1;
  173. !     nfa_set_neg_listids(start->out);
  174. !     nfa_set_neg_listids(start->out1);
  175. !     }
  176. ! }
  177. ! 
  178. ! /*
  179. !  * Set all NFA nodes' list ID equal to 0.
  180. !  */
  181. !     static void
  182. ! nfa_set_null_listids(start)
  183. !     nfa_state_T        *start;
  184. ! {
  185. !     if (start != NULL && start->lastlist == -1)
  186. !     {
  187. !     start->lastlist = 0;
  188. !     nfa_set_null_listids(start->out);
  189. !     nfa_set_null_listids(start->out1);
  190. !     }
  191. ! }
  192. ! 
  193. ! /*
  194. !  * Save list IDs for all NFA states in "list".
  195. !  */
  196. !     static void
  197. ! nfa_save_listids(start, list)
  198. !     nfa_state_T        *start;
  199.       int            *list;
  200.   {
  201. !     if (start != NULL && start->lastlist != -1)
  202. !     {
  203. !     list[abs(start->id)] = start->lastlist;
  204. !     start->lastlist = -1;
  205. !     nfa_save_listids(start->out, list);
  206. !     nfa_save_listids(start->out1, list);
  207.       }
  208.   }
  209.   
  210. --- 3597,3620 ----
  211.   #endif
  212.   
  213.   /*
  214. !  * Save list IDs for all NFA states of "prog" into "list".
  215. !  * Also reset the IDs to zero.
  216.    */
  217.       static void
  218. ! nfa_save_listids(prog, list)
  219. !     nfa_regprog_T   *prog;
  220.       int            *list;
  221.   {
  222. !     int            i;
  223. !     nfa_state_T        *p;
  224. ! 
  225. !     /* Order in the list is reverse, it's a bit faster that way. */
  226. !     p = &prog->state[0];
  227. !     for (i = prog->nstate; --i >= 0; )
  228. !     {
  229. !     list[i] = p->lastlist;
  230. !     p->lastlist = 0;
  231. !     ++p;
  232.       }
  233.   }
  234.   
  235. ***************
  236. *** 3650,3664 ****
  237.    * Restore list IDs from "list" to all NFA states.
  238.    */
  239.       static void
  240. ! nfa_restore_listids(start, list)
  241. !     nfa_state_T        *start;
  242.       int            *list;
  243.   {
  244. !     if (start != NULL && start->lastlist == -1)
  245.       {
  246. !     start->lastlist = list[abs(start->id)];
  247. !     nfa_restore_listids(start->out, list);
  248. !     nfa_restore_listids(start->out1, list);
  249.       }
  250.   }
  251.   
  252. --- 3622,3639 ----
  253.    * Restore list IDs from "list" to all NFA states.
  254.    */
  255.       static void
  256. ! nfa_restore_listids(prog, list)
  257. !     nfa_regprog_T   *prog;
  258.       int            *list;
  259.   {
  260. !     int            i;
  261. !     nfa_state_T        *p;
  262. ! 
  263. !     p = &prog->state[0];
  264. !     for (i = prog->nstate; --i >= 0; )
  265.       {
  266. !     p->lastlist = list[i];
  267. !     ++p;
  268.       }
  269.   }
  270.   
  271. ***************
  272. *** 3673,3679 ****
  273.       return val == pos;
  274.   }
  275.   
  276. ! static int nfa_regmatch __ARGS((nfa_state_T *start, regsubs_T *submatch, regsubs_T *m));
  277.   
  278.   /*
  279.    * Main matching routine.
  280. --- 3648,3654 ----
  281.       return val == pos;
  282.   }
  283.   
  284. ! static int nfa_regmatch __ARGS((nfa_regprog_T *prog, nfa_state_T *start, regsubs_T *submatch, regsubs_T *m));
  285.   
  286.   /*
  287.    * Main matching routine.
  288. ***************
  289. *** 3686,3692 ****
  290.    * Note: Caller must ensure that: start != NULL.
  291.    */
  292.       static int
  293. ! nfa_regmatch(start, submatch, m)
  294.       nfa_state_T        *start;
  295.       regsubs_T        *submatch;
  296.       regsubs_T        *m;
  297. --- 3661,3668 ----
  298.    * Note: Caller must ensure that: start != NULL.
  299.    */
  300.       static int
  301. ! nfa_regmatch(prog, start, submatch, m)
  302. !     nfa_regprog_T    *prog;
  303.       nfa_state_T        *start;
  304.       regsubs_T        *submatch;
  305.       regsubs_T        *m;
  306. ***************
  307. *** 3872,3878 ****
  308.           nfa_match = TRUE;
  309.           copy_sub(&submatch->norm, &t->subs.norm);
  310.   #ifdef FEAT_SYN_HL
  311. !         copy_sub(&submatch->synt, &t->subs.synt);
  312.   #endif
  313.   #ifdef ENABLE_LOG
  314.           log_subsexpr(&t->subs);
  315. --- 3848,3855 ----
  316.           nfa_match = TRUE;
  317.           copy_sub(&submatch->norm, &t->subs.norm);
  318.   #ifdef FEAT_SYN_HL
  319. !         if (nfa_has_zsubexpr)
  320. !             copy_sub(&submatch->synt, &t->subs.synt);
  321.   #endif
  322.   #ifdef ENABLE_LOG
  323.           log_subsexpr(&t->subs);
  324. ***************
  325. *** 3928,3934 ****
  326.               {
  327.               copy_sub(&m->norm, &t->subs.norm);
  328.   #ifdef FEAT_SYN_HL
  329. !             copy_sub(&m->synt, &t->subs.synt);
  330.   #endif
  331.               }
  332.               nfa_match = TRUE;
  333. --- 3905,3912 ----
  334.               {
  335.               copy_sub(&m->norm, &t->subs.norm);
  336.   #ifdef FEAT_SYN_HL
  337. !             if (nfa_has_zsubexpr)
  338. !                 copy_sub(&m->synt, &t->subs.synt);
  339.   #endif
  340.               }
  341.               nfa_match = TRUE;
  342. ***************
  343. *** 4024,4035 ****
  344.           /* Have to clear the listid field of the NFA nodes, so that
  345.            * nfa_regmatch() and addstate() can run properly after
  346.            * recursion. */
  347. !         nfa_save_listids(start, listids);
  348. !         nfa_set_null_listids(start);
  349.           nfa_endp = endposp;
  350. !         result = nfa_regmatch(t->state->out, submatch, m);
  351. !         nfa_set_neg_listids(start);
  352. !         nfa_restore_listids(start, listids);
  353.   
  354.           /* restore position in input text */
  355.           reginput = save_reginput;
  356. --- 4002,4011 ----
  357.           /* Have to clear the listid field of the NFA nodes, so that
  358.            * nfa_regmatch() and addstate() can run properly after
  359.            * recursion. */
  360. !         nfa_save_listids(prog, listids);
  361.           nfa_endp = endposp;
  362. !         result = nfa_regmatch(prog, t->state->out, submatch, m);
  363. !         nfa_restore_listids(prog, listids);
  364.   
  365.           /* restore position in input text */
  366.           reginput = save_reginput;
  367. ***************
  368. *** 4665,4671 ****
  369. --- 4641,4652 ----
  370.   #ifdef FEAT_SYN_HL
  371.       /* Clear the external match subpointers if necessary. */
  372.       if (prog->reghasz == REX_SET)
  373. +     {
  374. +     nfa_has_zsubexpr = TRUE;
  375.       need_clear_zsubexpr = TRUE;
  376. +     }
  377. +     else
  378. +     nfa_has_zsubexpr = FALSE;
  379.   #endif
  380.   
  381.   #ifdef ENABLE_LOG
  382. ***************
  383. *** 4694,4700 ****
  384.       clear_sub(&m.synt);
  385.   #endif
  386.   
  387. !     if (nfa_regmatch(start, &subs, &m) == FALSE)
  388.       return 0;
  389.   
  390.       cleanup_subexpr();
  391. --- 4675,4681 ----
  392.       clear_sub(&m.synt);
  393.   #endif
  394.   
  395. !     if (nfa_regmatch(prog, start, &subs, &m) == FALSE)
  396.       return 0;
  397.   
  398.       cleanup_subexpr();
  399. *** ../vim-7.3.1102/src/version.c    2013-06-02 19:22:05.000000000 +0200
  400. --- src/version.c    2013-06-02 21:24:50.000000000 +0200
  401. ***************
  402. *** 730,731 ****
  403. --- 730,733 ----
  404.   {   /* Add new patch number below this line */
  405. + /**/
  406. +     1103,
  407.   /**/
  408.  
  409. -- 
  410. hundred-and-one symptoms of being an internet addict:
  411. 53. To find out what time it is, you send yourself an e-mail and check the
  412.     "Date:" field.
  413.  
  414.  /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net   \\\
  415. ///        sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
  416. \\\  an exciting new programming language -- http://www.Zimbu.org        ///
  417.  \\\            help me help AIDS victims -- http://ICCF-Holland.org    ///
  418.