As far as I examined a cause of slowness, it seems that it's caused by not state merge but dfamust.
Although I'm suspicious of memory allocations in dfamust, I don't still have any ideas to fix them. I tried an attachment, but it became more and more slowdown.
From 7f9f56849e1bab8d0f3710638adc111e3ccef3ff Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka <[email protected]> Date: Wed, 7 May 2014 14:15:01 +0900 Subject: [PATCH] dfa: efficient memory allocation * src/dfa.c (struct must): Define new member `next'. (allocmust): Consider the reuse of must. (dfamust): Don't deallocate must with CAT or OR. --- src/dfa.c | 53 +++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 37 insertions(+), 16 deletions(-) diff --git a/src/dfa.c b/src/dfa.c index fc2acdc..dee3fed 100644 --- a/src/dfa.c +++ b/src/dfa.c @@ -3852,12 +3852,29 @@ struct must bool begline; bool endline; must *prev; + must *next; }; +static void +resetmust (must *mp) +{ + freelist (mp->in); + mp->in[0] = NULL; + mp->left[0] = mp->right[0] = mp->is[0] = '\0'; + mp->begline = false; + mp->endline = false; +} + static must * allocmust (must *mp) { - must *new_mp = xmalloc (sizeof *new_mp); + must *new_mp; + if (mp && mp->next) + { + resetmust (mp->next); + return mp->next; + } + new_mp = xmalloc (sizeof *new_mp); new_mp->in = xzalloc (sizeof *new_mp->in); new_mp->left = xzalloc (2); new_mp->right = xzalloc (2); @@ -3865,20 +3882,13 @@ allocmust (must *mp) new_mp->begline = false; new_mp->endline = false; new_mp->prev = mp; + new_mp->next = NULL; + if (mp) + mp->next = new_mp; return new_mp; } static void -resetmust (must *mp) -{ - freelist (mp->in); - mp->in[0] = NULL; - mp->left[0] = mp->right[0] = mp->is[0] = '\0'; - mp->begline = false; - mp->endline = false; -} - -static void freemust (must *mp) { freelist (mp->in); @@ -3967,7 +3977,6 @@ dfamust (struct dfa *d) freelist (lmp->in); free (lmp->in); lmp->in = new; - freemust (rmp); } break; @@ -4027,7 +4036,6 @@ dfamust (struct dfa *d) lmp->begline = false; lmp->endline = false; } - freemust (rmp); } break; @@ -4078,11 +4086,24 @@ done: d->musts = dm; } - while (mp) + if (mp) { - must *prev = mp->prev; + must *mp_tmp; + mp_tmp = mp->prev; + while (mp_tmp) + { + must *prev = mp_tmp->prev; + freemust (mp_tmp); + mp_tmp = prev; + } + mp_tmp = mp->next; + while (mp_tmp) + { + must *next = mp_tmp->next; + freemust (mp_tmp); + mp_tmp = next; + } freemust (mp); - mp = prev; } } -- 1.9.2
