To: vim_dev@googlegroups.com Subject: Patch 7.3.1028 Fcc: outbox From: Bram Moolenaar Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ------------ Patch 7.3.1028 Problem: New regexp performance: Copying a lot of position state. Solution: Only copy the sub-expressions that are being used. Files: src/regexp_nfa.c, src/regexp.h *** ../vim-7.3.1027/src/regexp_nfa.c 2013-05-26 19:19:48.000000000 +0200 --- src/regexp_nfa.c 2013-05-26 21:35:33.000000000 +0200 *************** *** 161,166 **** --- 161,170 ---- /* NFA regexp \ze operator encountered. */ static int nfa_has_zend = FALSE; + /* Number of sub expressions actually being used during execution. 1 if only + * the whole match (subexpr 0) is used. */ + static int nfa_nsubexpr; + static int *post_start; /* holds the postfix form of r.e. */ static int *post_end; static int *post_ptr; *************** *** 1645,1656 **** return OK; } ! typedef struct { ! char_u *start[NSUBEXP]; ! char_u *end[NSUBEXP]; ! lpos_T startpos[NSUBEXP]; ! lpos_T endpos[NSUBEXP]; } regsub_T; static int nfa_regmatch __ARGS((nfa_state_T *start, regsub_T *submatch, regsub_T *m)); --- 1649,1666 ---- 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)); *************** *** 2479,2514 **** * NFA execution code. ****************************************************************/ ! /* nfa_thread_T contains runtime information of a NFA state */ typedef struct { nfa_state_T *state; ! regsub_T sub; /* Submatch info. TODO: expensive! */ } nfa_thread_T; ! typedef struct { nfa_thread_T *t; int n; } nfa_list_T; ! static void addstate __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int off, int lid, int *match)); ! static void addstate_here __ARGS((nfa_list_T *l, nfa_state_T *state, regsub_T *m, int lid, int *match, int *ip)); static void ! addstate(l, state, m, off, lid, match) nfa_list_T *l; /* runtime state list */ nfa_state_T *state; /* state to update */ regsub_T *m; /* pointers to subexpressions */ int off; /* byte offset, when -1 go to next line */ int lid; - int *match; /* found match? */ { ! regsub_T save; ! int subidx = 0; nfa_thread_T *lastthread; if (l == NULL || state == NULL) return; --- 2489,2527 ---- * NFA execution code. ****************************************************************/ ! /* nfa_thread_T contains execution information of a NFA state */ typedef struct { nfa_state_T *state; ! regsub_T sub; /* submatch info, only party used */ } nfa_thread_T; ! /* nfa_list_T contains the alternative NFA execution states. */ typedef struct { nfa_thread_T *t; int n; } nfa_list_T; ! /* Used during execution: whether a match has been found. */ ! 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 ! addstate(l, state, m, off, lid) nfa_list_T *l; /* runtime state list */ nfa_state_T *state; /* state to update */ regsub_T *m; /* pointers to subexpressions */ int off; /* byte offset, when -1 go to next line */ int lid; { ! int subidx; nfa_thread_T *lastthread; + lpos_T save_lpos; + char_u *save_ptr; if (l == NULL || state == NULL) return; *************** *** 2544,2550 **** state->lastlist = lid; lastthread = &l->t[l->n++]; lastthread->state = state; ! lastthread->sub = *m; /* TODO: expensive! */ } } --- 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); } } *************** *** 2556,2571 **** switch (state->c) { case NFA_MATCH: ! *match = TRUE; break; case NFA_SPLIT: ! addstate(l, state->out, m, off, lid, match); ! addstate(l, state->out1, m, off, lid, match); break; case NFA_SKIP_CHAR: ! addstate(l, state->out, m, off, lid, match); break; #if 0 --- 2578,2593 ---- switch (state->c) { case NFA_MATCH: ! nfa_match = TRUE; break; case NFA_SPLIT: ! addstate(l, state->out, m, off, lid); ! addstate(l, state->out1, m, off, lid); break; case NFA_SKIP_CHAR: ! addstate(l, state->out, m, off, lid); break; #if 0 *************** *** 2587,2593 **** case NFA_NOPEN: case NFA_NCLOSE: ! addstate(l, state->out, m, off, lid, match); break; /* If this state is reached, then a recursive call of nfa_regmatch() --- 2609,2615 ---- case NFA_NOPEN: case NFA_NCLOSE: ! addstate(l, state->out, m, off, lid); break; /* If this state is reached, then a recursive call of nfa_regmatch() *************** *** 2609,2659 **** case NFA_MOPEN + 8: case NFA_MOPEN + 9: case NFA_ZSTART: - subidx = state->c - NFA_MOPEN; if (state->c == NFA_ZSTART) subidx = 0; if (REG_MULTI) { ! save.startpos[subidx] = m->startpos[subidx]; ! save.endpos[subidx] = m->endpos[subidx]; if (off == -1) { ! m->startpos[subidx].lnum = reglnum + 1; ! m->startpos[subidx].col = 0; } else { ! m->startpos[subidx].lnum = reglnum; ! m->startpos[subidx].col = (colnr_T)(reginput - regline + off); } } else { ! save.start[subidx] = m->start[subidx]; ! save.end[subidx] = m->end[subidx]; ! m->start[subidx] = reginput + off; } ! addstate(l, state->out, m, off, lid, match); if (REG_MULTI) ! { ! m->startpos[subidx] = save.startpos[subidx]; ! m->endpos[subidx] = save.endpos[subidx]; ! } else ! { ! m->start[subidx] = save.start[subidx]; ! m->end[subidx] = save.end[subidx]; ! } break; case NFA_MCLOSE + 0: if (nfa_has_zend) { ! addstate(l, state->out, m, off, lid, match); break; } case NFA_MCLOSE + 1: --- 2631,2674 ---- case NFA_MOPEN + 8: case NFA_MOPEN + 9: case NFA_ZSTART: if (state->c == NFA_ZSTART) subidx = 0; + 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; ! m->multilist[subidx].start.col = 0; } else { ! m->multilist[subidx].start.lnum = reglnum; ! m->multilist[subidx].start.col = (colnr_T)(reginput - regline + off); } } 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: if (nfa_has_zend) { ! addstate(l, state->out, m, off, lid); break; } case NFA_MCLOSE + 1: *************** *** 2666,2709 **** case NFA_MCLOSE + 8: case NFA_MCLOSE + 9: case NFA_ZEND: - subidx = state->c - NFA_MCLOSE; if (state->c == NFA_ZEND) subidx = 0; if (REG_MULTI) { ! save.startpos[subidx] = m->startpos[subidx]; ! save.endpos[subidx] = m->endpos[subidx]; if (off == -1) { ! m->endpos[subidx].lnum = reglnum + 1; ! m->endpos[subidx].col = 0; } else { ! m->endpos[subidx].lnum = reglnum; ! m->endpos[subidx].col = (colnr_T)(reginput - regline + off); } } else { ! save.start[subidx] = m->start[subidx]; ! save.end[subidx] = m->end[subidx]; ! m->end[subidx] = reginput + off; } ! addstate(l, state->out, m, off, lid, match); if (REG_MULTI) ! { ! m->startpos[subidx] = save.startpos[subidx]; ! m->endpos[subidx] = save.endpos[subidx]; ! } else ! { ! m->start[subidx] = save.start[subidx]; ! m->end[subidx] = save.end[subidx]; ! } break; } } --- 2681,2718 ---- case NFA_MCLOSE + 8: case NFA_MCLOSE + 9: case NFA_ZEND: if (state->c == NFA_ZEND) subidx = 0; + else + subidx = state->c - NFA_MCLOSE; if (REG_MULTI) { ! save_lpos = m->multilist[subidx].end; if (off == -1) { ! m->multilist[subidx].end.lnum = reglnum + 1; ! m->multilist[subidx].end.col = 0; } else { ! m->multilist[subidx].end.lnum = reglnum; ! m->multilist[subidx].end.col = ! (colnr_T)(reginput - regline + off); } } else { ! save_ptr = m->linelist[subidx].end; ! m->linelist[subidx].end = reginput + off; } ! addstate(l, state->out, m, off, lid); if (REG_MULTI) ! m->multilist[subidx].end = save_lpos; else ! m->linelist[subidx].end = save_ptr; break; } } *************** *** 2715,2726 **** * matters for alternatives. */ static void ! addstate_here(l, state, m, lid, matchp, ip) nfa_list_T *l; /* runtime state list */ nfa_state_T *state; /* state to update */ regsub_T *m; /* pointers to subexpressions */ int lid; - int *matchp; /* found match? */ int *ip; { int tlen = l->n; --- 2724,2734 ---- * matters for alternatives. */ static void ! addstate_here(l, state, m, lid, ip) nfa_list_T *l; /* runtime state list */ nfa_state_T *state; /* state to update */ regsub_T *m; /* pointers to subexpressions */ int lid; int *ip; { int tlen = l->n; *************** *** 2728,2734 **** int i = *ip; /* first add the state(s) at the end, so that we know how many there are */ ! addstate(l, state, m, 0, lid, matchp); /* when "*ip" was at the end of the list, nothing to do */ if (i + 1 == tlen) --- 2736,2742 ---- int i = *ip; /* first add the state(s) at the end, so that we know how many there are */ ! addstate(l, state, m, 0, lid); /* when "*ip" was at the end of the list, nothing to do */ if (i + 1 == tlen) *************** *** 2925,2931 **** { int result; int size = 0; - int match = FALSE; int flag = 0; int old_reglnum = -1; int go_to_nextline = FALSE; --- 2933,2938 ---- *************** *** 2951,2956 **** --- 2958,2964 ---- return FALSE; } #endif + nfa_match = FALSE; /* Allocate memory for the lists of nodes */ size = (nstate + 1) * sizeof(nfa_thread_T); *************** *** 2989,2995 **** #ifdef ENABLE_LOG fprintf(log_fd, "(---) STARTSTATE\n"); #endif ! addstate(thislist, start, m, 0, listid, &match); /* There are two cases when the NFA advances: 1. input char matches the * NFA node and 2. input char does not match the NFA node, but the next --- 2997,3003 ---- #ifdef ENABLE_LOG fprintf(log_fd, "(---) STARTSTATE\n"); #endif ! addstate(thislist, start, m, 0, listid); /* There are two cases when the NFA advances: 1. input char matches the * NFA node and 2. input char does not match the NFA node, but the next *************** *** 3002,3008 **** #define ADD_POS_NEG_STATE(node) \ ll = listtbl[result ? 1 : 0][node->negated]; \ if (ll != NULL) \ ! addstate(ll, node->out , &t->sub, clen, listid + 1, &match); /* --- 3010,3016 ---- #define ADD_POS_NEG_STATE(node) \ ll = listtbl[result ? 1 : 0][node->negated]; \ if (ll != NULL) \ ! addstate(ll, node->out , &t->sub, clen, listid + 1); /* *************** *** 3090,3096 **** switch (t->state->c) { case NFA_MATCH: ! match = TRUE; *submatch = t->sub; #ifdef ENABLE_LOG for (j = 0; j < 4; j++) --- 3098,3104 ---- switch (t->state->c) { case NFA_MATCH: ! nfa_match = TRUE; *submatch = t->sub; #ifdef ENABLE_LOG for (j = 0; j < 4; j++) *************** *** 3125,3135 **** * the parent call. */ if (start->c == NFA_MOPEN + 0) addstate_here(thislist, t->state->out, &t->sub, listid, ! &match, &listidx); else { *m = t->sub; ! match = TRUE; } break; --- 3133,3143 ---- * the parent call. */ if (start->c == NFA_MOPEN + 0) addstate_here(thislist, t->state->out, &t->sub, listid, ! &listidx); else { *m = t->sub; ! nfa_match = TRUE; } break; *************** *** 3186,3205 **** reglnum = old_reglnum; /* Copy submatch info from the recursive call */ if (REG_MULTI) ! for (j = 1; j < NSUBEXP; j++) { ! t->sub.startpos[j] = m->startpos[j]; ! t->sub.endpos[j] = m->endpos[j]; } else ! for (j = 1; j < NSUBEXP; j++) { ! t->sub.start[j] = m->start[j]; ! t->sub.end[j] = m->end[j]; } /* t->state->out1 is the corresponding END_INVISIBLE node */ addstate_here(thislist, t->state->out1->out, &t->sub, ! listid, &match, &listidx); } else { --- 3194,3213 ---- 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); } else { *************** *** 3211,3223 **** case NFA_BOL: if (reginput == regline) addstate_here(thislist, t->state->out, &t->sub, listid, ! &match, &listidx); break; case NFA_EOL: if (curc == NUL) addstate_here(thislist, t->state->out, &t->sub, listid, ! &match, &listidx); break; case NFA_BOW: --- 3219,3231 ---- case NFA_BOL: if (reginput == regline) addstate_here(thislist, t->state->out, &t->sub, listid, ! &listidx); break; case NFA_EOL: if (curc == NUL) addstate_here(thislist, t->state->out, &t->sub, listid, ! &listidx); break; case NFA_BOW: *************** *** 3245,3251 **** bow = FALSE; if (bow) addstate_here(thislist, t->state->out, &t->sub, listid, ! &match, &listidx); break; } --- 3253,3259 ---- bow = FALSE; if (bow) addstate_here(thislist, t->state->out, &t->sub, listid, ! &listidx); break; } *************** *** 3274,3280 **** eow = FALSE; if (eow) addstate_here(thislist, t->state->out, &t->sub, listid, ! &match, &listidx); break; } --- 3282,3288 ---- eow = FALSE; if (eow) addstate_here(thislist, t->state->out, &t->sub, listid, ! &listidx); break; } *************** *** 3364,3377 **** go_to_nextline = TRUE; /* Pass -1 for the offset, which means taking the position * at the start of the next line. */ ! addstate(nextlist, t->state->out, &t->sub, -1, ! listid + 1, &match); } else if (curc == '\n' && reg_line_lbr) { /* match \n as if it is an ordinary character */ ! addstate(nextlist, t->state->out, &t->sub, 1, ! listid + 1, &match); } break; --- 3372,3383 ---- go_to_nextline = TRUE; /* Pass -1 for the offset, which means taking the position * at the start of the next line. */ ! addstate(nextlist, t->state->out, &t->sub, -1, listid + 1); } else if (curc == '\n' && reg_line_lbr) { /* match \n as if it is an ordinary character */ ! addstate(nextlist, t->state->out, &t->sub, 1, listid + 1); } break; *************** *** 3400,3413 **** * CHAR(x), NFA_NOT, CHAR(y), NFA_NOT etc. */ if (curc > 0) addstate(nextlist, t->state->out, &t->sub, clen, ! listid + 1, &match); break; case NFA_ANY: /* Any char except '\0', (end of input) does not match. */ if (curc > 0) addstate(nextlist, t->state->out, &t->sub, clen, ! listid + 1, &match); break; /* --- 3406,3419 ---- * CHAR(x), NFA_NOT, CHAR(y), NFA_NOT etc. */ if (curc > 0) addstate(nextlist, t->state->out, &t->sub, clen, ! listid + 1); break; case NFA_ANY: /* Any char except '\0', (end of input) does not match. */ if (curc > 0) addstate(nextlist, t->state->out, &t->sub, clen, ! listid + 1); break; /* *************** *** 3597,3609 **** * Do not add the start state in recursive calls of nfa_regmatch(), * because recursive calls should only start in the first position. * Also don't start a match past the first line. */ ! if (match == FALSE && start->c == NFA_MOPEN + 0 && reglnum == 0 && clen != 0) { #ifdef ENABLE_LOG fprintf(log_fd, "(---) STARTSTATE\n"); #endif ! addstate(nextlist, start, m, clen, listid + 1, &match); } #ifdef ENABLE_LOG --- 3603,3615 ---- * Do not add the start state in recursive calls of nfa_regmatch(), * because recursive calls should only start in the first position. * Also don't start a match past the first line. */ ! if (nfa_match == FALSE && start->c == NFA_MOPEN + 0 && reglnum == 0 && clen != 0) { #ifdef ENABLE_LOG fprintf(log_fd, "(---) STARTSTATE\n"); #endif ! addstate(nextlist, start, m, clen, listid + 1); } #ifdef ENABLE_LOG *************** *** 3640,3653 **** vim_free(list[1].t); vim_free(list[2].t); list[0].t = list[1].t = list[2].t = NULL; ! if (listids != NULL) ! vim_free(listids); #undef ADD_POS_NEG_STATE #ifdef NFA_REGEXP_DEBUG_LOG fclose(debug); #endif ! return match; } /* --- 3646,3658 ---- vim_free(list[1].t); vim_free(list[2].t); list[0].t = list[1].t = list[2].t = NULL; ! vim_free(listids); #undef ADD_POS_NEG_STATE #ifdef NFA_REGEXP_DEBUG_LOG fclose(debug); #endif ! return nfa_match; } /* *************** *** 3690,3706 **** if (REG_MULTI) { /* Use 0xff to set lnum to -1 */ ! vim_memset(sub.startpos, 0xff, sizeof(lpos_T) * NSUBEXP); ! vim_memset(sub.endpos, 0xff, sizeof(lpos_T) * NSUBEXP); ! vim_memset(m.startpos, 0xff, sizeof(lpos_T) * NSUBEXP); ! vim_memset(m.endpos, 0xff, sizeof(lpos_T) * NSUBEXP); } else { ! vim_memset(sub.start, 0, sizeof(char_u *) * NSUBEXP); ! vim_memset(sub.end, 0, sizeof(char_u *) * NSUBEXP); ! vim_memset(m.start, 0, sizeof(char_u *) * NSUBEXP); ! vim_memset(m.end, 0, sizeof(char_u *) * NSUBEXP); } if (nfa_regmatch(start, &sub, &m) == FALSE) --- 3695,3707 ---- if (REG_MULTI) { /* Use 0xff to set lnum to -1 */ ! vim_memset(sub.multilist, 0xff, sizeof(struct multipos) * nfa_nsubexpr); ! vim_memset(m.multilist, 0xff, sizeof(struct multipos) * nfa_nsubexpr); } else { ! vim_memset(sub.linelist, 0, sizeof(struct linepos) * nfa_nsubexpr); ! vim_memset(m.linelist, 0, sizeof(struct linepos) * nfa_nsubexpr); } if (nfa_regmatch(start, &sub, &m) == FALSE) *************** *** 3709,3718 **** cleanup_subexpr(); if (REG_MULTI) { ! for (i = 0; i < NSUBEXP; i++) { ! reg_startpos[i] = sub.startpos[i]; ! reg_endpos[i] = sub.endpos[i]; } if (reg_startpos[0].lnum < 0) --- 3710,3719 ---- 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; } if (reg_startpos[0].lnum < 0) *************** *** 3731,3740 **** } else { ! for (i = 0; i < NSUBEXP; i++) { ! reg_startp[i] = sub.start[i]; ! reg_endp[i] = sub.end[i]; } if (reg_startp[0] == NULL) --- 3732,3741 ---- } else { ! for (i = 0; i < nfa_nsubexpr; i++) { ! reg_startp[i] = sub.linelist[i].start; ! reg_endp[i] = sub.linelist[i].end; } if (reg_startp[0] == NULL) *************** *** 3802,3807 **** --- 3803,3809 ---- reglnum = 0; /* relative to line */ nfa_has_zend = prog->has_zend; + nfa_nsubexpr = prog->nsubexp; nstate = prog->nstate; for (i = 0; i < nstate; ++i) *************** *** 3896,3901 **** --- 3898,3904 ---- prog->engine = &nfa_regengine; prog->nstate = nstate; prog->has_zend = nfa_has_zend; + prog->nsubexp = regnpar; #ifdef ENABLE_LOG nfa_postfix_dump(expr, OK); nfa_dump(prog); *** ../vim-7.3.1027/src/regexp.h 2013-05-26 16:57:23.000000000 +0200 --- src/regexp.h 2013-05-26 20:08:09.000000000 +0200 *************** *** 87,92 **** --- 87,93 ---- regprog_T regprog; nfa_state_T *start; int has_zend; /* pattern contains \ze */ + int nsubexp; /* number of () */ int nstate; nfa_state_T state[0]; /* actually longer.. */ } nfa_regprog_T; *** ../vim-7.3.1027/src/version.c 2013-05-26 19:19:48.000000000 +0200 --- src/version.c 2013-05-26 21:44:20.000000000 +0200 *************** *** 730,731 **** --- 730,733 ---- { /* Add new patch number below this line */ + /**/ + 1028, /**/ -- Q: What's a light-year? A: One-third less calories than a regular year. /// 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 ///