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.1029 < prev    next >
Encoding:
Internet Message Format  |  2013-05-25  |  10.1 KB

  1. To: vim_dev@googlegroups.com
  2. Subject: Patch 7.3.1029
  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.1029
  11. Problem:    New regexp performance: Unused position state being copied.
  12. Solution:   Keep track of which positions are actually valid.
  13. Files:        src/regexp_nfa.c
  14.  
  15.  
  16. *** ../vim-7.3.1028/src/regexp_nfa.c    2013-05-26 21:47:22.000000000 +0200
  17. --- src/regexp_nfa.c    2013-05-26 22:45:26.000000000 +0200
  18. ***************
  19. *** 1649,1670 ****
  20.       return OK;
  21.   }
  22.   
  23. - typedef union
  24. - {
  25. -     struct multipos
  26. -     {
  27. -     lpos_T    start;
  28. -     lpos_T    end;
  29. -     } multilist[NSUBEXP];
  30. -     struct linepos
  31. -     {
  32. -     char_u    *start;
  33. -     char_u    *end;
  34. -     } linelist[NSUBEXP];
  35. - } regsub_T;
  36. - static int nfa_regmatch __ARGS((nfa_state_T *start, regsub_T *submatch, regsub_T *m));
  37.   #ifdef DEBUG
  38.   static char_u code[50];
  39.   
  40. --- 1649,1654 ----
  41. ***************
  42. *** 2489,2494 ****
  43. --- 2473,2498 ----
  44.    * NFA execution code.
  45.    ****************************************************************/
  46.   
  47. + typedef struct
  48. + {
  49. +     int        in_use; /* number of subexpr with useful info */
  50. +     /* When REG_MULTI is TRUE multilist is used, otherwise linelist. */
  51. +     union
  52. +     {
  53. +     struct multipos
  54. +     {
  55. +         lpos_T    start;
  56. +         lpos_T    end;
  57. +     } multilist[NSUBEXP];
  58. +     struct linepos
  59. +     {
  60. +         char_u    *start;
  61. +         char_u    *end;
  62. +     } linelist[NSUBEXP];
  63. +     };
  64. + } regsub_T;
  65.   /* nfa_thread_T contains execution information of a NFA state */
  66.   typedef struct
  67.   {
  68. ***************
  69. *** 2507,2513 ****
  70.   static int nfa_match;
  71.   
  72.   static void addstate __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int off, int lid));
  73.   static void addstate_here __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int lid, int *ip));
  74.   
  75.       static void
  76. --- 2511,2516 ----
  77. ***************
  78. *** 2521,2527 ****
  79. --- 2524,2532 ----
  80.       int            subidx;
  81.       nfa_thread_T    *lastthread;
  82.       lpos_T        save_lpos;
  83. +     int            save_in_use;
  84.       char_u        *save_ptr;
  85. +     int            i;
  86.   
  87.       if (l == NULL || state == NULL)
  88.       return;
  89. ***************
  90. *** 2557,2572 ****
  91.           state->lastlist = lid;
  92.           lastthread = &l->t[l->n++];
  93.           lastthread->state = state;
  94. !         /* Copy the match start and end positions. */
  95. !         if (REG_MULTI)
  96. !             mch_memmove(&lastthread->sub.multilist[0],
  97. !                     &m->multilist[0],
  98. !                 sizeof(struct multipos) * nfa_nsubexpr);
  99. !         else
  100. !             mch_memmove(&lastthread->sub.linelist[0],
  101. !                     &m->linelist[0],
  102. !                     sizeof(struct linepos) * nfa_nsubexpr);
  103.           }
  104.       }
  105.   
  106. --- 2562,2580 ----
  107.           state->lastlist = lid;
  108.           lastthread = &l->t[l->n++];
  109.           lastthread->state = state;
  110. !         lastthread->sub.in_use = m->in_use;
  111. !         if (m->in_use > 0)
  112. !         {
  113. !             /* Copy the match start and end positions. */
  114. !             if (REG_MULTI)
  115. !             mch_memmove(&lastthread->sub.multilist[0],
  116. !                     &m->multilist[0],
  117. !                     sizeof(struct multipos) * m->in_use);
  118. !             else
  119. !             mch_memmove(&lastthread->sub.linelist[0],
  120. !                     &m->linelist[0],
  121. !                     sizeof(struct linepos) * m->in_use);
  122. !         }
  123.           }
  124.       }
  125.   
  126. ***************
  127. *** 2636,2644 ****
  128.           else
  129.           subidx = state->c - NFA_MOPEN;
  130.   
  131.           if (REG_MULTI)
  132.           {
  133. !         save_lpos = m->multilist[subidx].start;
  134.           if (off == -1)
  135.           {
  136.               m->multilist[subidx].start.lnum = reglnum + 1;
  137. --- 2644,2668 ----
  138.           else
  139.           subidx = state->c - NFA_MOPEN;
  140.   
  141. +         /* Set the position (with "off") in the subexpression.  Save and
  142. +          * restore it when it was in use.  Otherwise fill any gap. */
  143.           if (REG_MULTI)
  144.           {
  145. !         if (subidx < m->in_use)
  146. !         {
  147. !             save_lpos = m->multilist[subidx].start;
  148. !             save_in_use = -1;
  149. !         }
  150. !         else
  151. !         {
  152. !             save_in_use = m->in_use;
  153. !             for (i = m->in_use; i < subidx; ++i)
  154. !             {
  155. !             m->multilist[i].start.lnum = -1;
  156. !             m->multilist[i].end.lnum = -1;
  157. !             }
  158. !             m->in_use = subidx + 1;
  159. !         }
  160.           if (off == -1)
  161.           {
  162.               m->multilist[subidx].start.lnum = reglnum + 1;
  163. ***************
  164. *** 2653,2668 ****
  165.           }
  166.           else
  167.           {
  168. !         save_ptr = m->linelist[subidx].start;
  169.           m->linelist[subidx].start = reginput + off;
  170.           }
  171.   
  172.           addstate(l, state->out, m, off, lid);
  173.   
  174. !         if (REG_MULTI)
  175. !         m->multilist[subidx].start = save_lpos;
  176.           else
  177. !         m->linelist[subidx].start = save_ptr;
  178.           break;
  179.   
  180.       case NFA_MCLOSE + 0:
  181. --- 2677,2711 ----
  182.           }
  183.           else
  184.           {
  185. !         if (subidx < m->in_use)
  186. !         {
  187. !             save_ptr = m->linelist[subidx].start;
  188. !             save_in_use = -1;
  189. !         }
  190. !         else
  191. !         {
  192. !             save_in_use = m->in_use;
  193. !             for (i = m->in_use; i < subidx; ++i)
  194. !             {
  195. !             m->linelist[i].start = NULL;
  196. !             m->linelist[i].end = NULL;
  197. !             }
  198. !             m->in_use = subidx + 1;
  199. !         }
  200.           m->linelist[subidx].start = reginput + off;
  201.           }
  202.   
  203.           addstate(l, state->out, m, off, lid);
  204.   
  205. !         if (save_in_use == -1)
  206. !         {
  207. !         if (REG_MULTI)
  208. !             m->multilist[subidx].start = save_lpos;
  209. !         else
  210. !             m->linelist[subidx].start = save_ptr;
  211. !         }
  212.           else
  213. !         m->in_use = save_in_use;
  214.           break;
  215.   
  216.       case NFA_MCLOSE + 0:
  217. ***************
  218. *** 2686,2691 ****
  219. --- 2729,2739 ----
  220.           else
  221.           subidx = state->c - NFA_MCLOSE;
  222.   
  223. +         /* We don't fill in gaps here, there must have been an MOPEN that
  224. +          * has done that. */
  225. +         save_in_use = m->in_use;
  226. +         if (m->in_use <= subidx)
  227. +         m->in_use = subidx + 1;
  228.           if (REG_MULTI)
  229.           {
  230.           save_lpos = m->multilist[subidx].end;
  231. ***************
  232. *** 2713,2718 ****
  233. --- 2761,2767 ----
  234.           m->multilist[subidx].end = save_lpos;
  235.           else
  236.           m->linelist[subidx].end = save_ptr;
  237. +         m->in_use = save_in_use;
  238.           break;
  239.       }
  240.   }
  241. ***************
  242. *** 2917,2922 ****
  243. --- 2966,2973 ----
  244.       }
  245.   }
  246.   
  247. + static int nfa_regmatch __ARGS((nfa_state_T *start, regsub_T *submatch, regsub_T *m));
  248.   /*
  249.    * Main matching routine.
  250.    *
  251. ***************
  252. *** 2960,2966 ****
  253.   #endif
  254.       nfa_match = FALSE;
  255.   
  256. !     /* Allocate memory for the lists of nodes */
  257.       size = (nstate + 1) * sizeof(nfa_thread_T);
  258.       list[0].t = (nfa_thread_T *)lalloc(size, TRUE);
  259.       list[1].t = (nfa_thread_T *)lalloc(size, TRUE);
  260. --- 3011,3017 ----
  261.   #endif
  262.       nfa_match = FALSE;
  263.   
  264. !     /* Allocate memory for the lists of nodes. */
  265.       size = (nstate + 1) * sizeof(nfa_thread_T);
  266.       list[0].t = (nfa_thread_T *)lalloc(size, TRUE);
  267.       list[1].t = (nfa_thread_T *)lalloc(size, TRUE);
  268. ***************
  269. *** 3099,3105 ****
  270.           {
  271.           case NFA_MATCH:
  272.           nfa_match = TRUE;
  273. !         *submatch = t->sub;
  274.   #ifdef ENABLE_LOG
  275.           for (j = 0; j < 4; j++)
  276.               if (REG_MULTI)
  277. --- 3150,3168 ----
  278.           {
  279.           case NFA_MATCH:
  280.           nfa_match = TRUE;
  281. !         submatch->in_use = t->sub.in_use;
  282. !         if (REG_MULTI)
  283. !             for (j = 0; j < submatch->in_use; j++)
  284. !             {
  285. !             submatch->multilist[j].start = t->sub.multilist[j].start;
  286. !             submatch->multilist[j].end = t->sub.multilist[j].end;
  287. !             }
  288. !         else
  289. !             for (j = 0; j < submatch->in_use; j++)
  290. !             {
  291. !             submatch->linelist[j].start = t->sub.linelist[j].start;
  292. !             submatch->linelist[j].end = t->sub.linelist[j].end;
  293. !             }
  294.   #ifdef ENABLE_LOG
  295.           for (j = 0; j < 4; j++)
  296.               if (REG_MULTI)
  297. ***************
  298. *** 3194,3210 ****
  299.               reglnum = old_reglnum;
  300.               /* Copy submatch info from the recursive call */
  301.               if (REG_MULTI)
  302. !             for (j = 1; j < nfa_nsubexpr; j++)
  303.               {
  304.                   t->sub.multilist[j].start = m->multilist[j].start;
  305.                   t->sub.multilist[j].end = m->multilist[j].end;
  306.               }
  307.               else
  308. !             for (j = 1; j < nfa_nsubexpr; j++)
  309.               {
  310.                   t->sub.linelist[j].start = m->linelist[j].start;
  311.                   t->sub.linelist[j].end = m->linelist[j].end;
  312.               }
  313.               /* t->state->out1 is the corresponding END_INVISIBLE node */
  314.               addstate_here(thislist, t->state->out1->out, &t->sub,
  315.                                   listid, &listidx);
  316. --- 3257,3275 ----
  317.               reglnum = old_reglnum;
  318.               /* Copy submatch info from the recursive call */
  319.               if (REG_MULTI)
  320. !             for (j = 1; j < m->in_use; j++)
  321.               {
  322.                   t->sub.multilist[j].start = m->multilist[j].start;
  323.                   t->sub.multilist[j].end = m->multilist[j].end;
  324.               }
  325.               else
  326. !             for (j = 1; j < m->in_use; j++)
  327.               {
  328.                   t->sub.linelist[j].start = m->linelist[j].start;
  329.                   t->sub.linelist[j].end = m->linelist[j].end;
  330.               }
  331. +             t->sub.in_use = m->in_use;
  332.               /* t->state->out1 is the corresponding END_INVISIBLE node */
  333.               addstate_here(thislist, t->state->out1->out, &t->sub,
  334.                                   listid, &listidx);
  335. ***************
  336. *** 3703,3708 ****
  337. --- 3768,3775 ----
  338.       vim_memset(sub.linelist, 0, sizeof(struct linepos) * nfa_nsubexpr);
  339.       vim_memset(m.linelist, 0, sizeof(struct linepos) * nfa_nsubexpr);
  340.       }
  341. +     sub.in_use = 0;
  342. +     m.in_use = 0;
  343.   
  344.       if (nfa_regmatch(start, &sub, &m) == FALSE)
  345.       return 0;
  346. ***************
  347. *** 3710,3716 ****
  348.       cleanup_subexpr();
  349.       if (REG_MULTI)
  350.       {
  351. !     for (i = 0; i < nfa_nsubexpr; i++)
  352.       {
  353.           reg_startpos[i] = sub.multilist[i].start;
  354.           reg_endpos[i] = sub.multilist[i].end;
  355. --- 3777,3783 ----
  356.       cleanup_subexpr();
  357.       if (REG_MULTI)
  358.       {
  359. !     for (i = 0; i < sub.in_use; i++)
  360.       {
  361.           reg_startpos[i] = sub.multilist[i].start;
  362.           reg_endpos[i] = sub.multilist[i].end;
  363. ***************
  364. *** 3732,3738 ****
  365.       }
  366.       else
  367.       {
  368. !     for (i = 0; i < nfa_nsubexpr; i++)
  369.       {
  370.           reg_startp[i] = sub.linelist[i].start;
  371.           reg_endp[i] = sub.linelist[i].end;
  372. --- 3799,3805 ----
  373.       }
  374.       else
  375.       {
  376. !     for (i = 0; i < sub.in_use; i++)
  377.       {
  378.           reg_startp[i] = sub.linelist[i].start;
  379.           reg_endp[i] = sub.linelist[i].end;
  380. *** ../vim-7.3.1028/src/version.c    2013-05-26 21:47:22.000000000 +0200
  381. --- src/version.c    2013-05-26 22:53:55.000000000 +0200
  382. ***************
  383. *** 730,731 ****
  384. --- 730,733 ----
  385.   {   /* Add new patch number below this line */
  386. + /**/
  387. +     1029,
  388.   /**/
  389.  
  390. -- 
  391. I used to be indecisive, now I'm not sure.
  392.  
  393.  /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net   \\\
  394. ///        sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
  395. \\\  an exciting new programming language -- http://www.Zimbu.org        ///
  396.  \\\            help me help AIDS victims -- http://ICCF-Holland.org    ///
  397.