* [PATCH] Small regex optimizations
@ 2003-11-29 4:38 Jakub Jelinek
0 siblings, 0 replies; only message in thread
From: Jakub Jelinek @ 2003-11-29 4:38 UTC (permalink / raw)
To: Ulrich Drepper, Roland McGrath; +Cc: Glibc hackers
Hi!
Just small optimizations, the speedup is not big but they also
decrease regex.os code size. E.g. no DFA state can be has_backref
it dfa->nbackref == 0, so there is no need to do too many checks in
the fast path unless there are back references.
Also, this patch adds a few new palindrome tests to bug-regex11.
2003-11-28 Jakub Jelinek <jakub@redhat.com>
* posix/regexec.c (acquire_init_state_context): Make inline.
Add always_inline attribute.
(check_matching): Add BE macro. Move if (cur_state->has_backref)
into if (dfa->nbackref).
(sift_states_backward): Fix comment.
(transit_state): Add BE macro. Move if (next_state->has_backref)
into if (dfa->nbackref && next_state). Don't check for next_state
!= NULL twice.
* posix/regcomp.c (peek_token): Use opr.ctx_type instead of opr.idx
for ANCHOR.
(parse_expression): Only call init_word_char if word context will be
needed.
* posix/bug-regex11.c (tests): Add new tests.
* posix/tst-regex.c: Include getopt.h.
(timing): New variable.
(main): Set timing to 1 if --timing argument is present.
Add 2 new tests.
(run_test, run_test_backwards): Handle timing.
--- libc/posix/regexec.c.jj 2003-11-27 17:36:46.000000000 +0100
+++ libc/posix/regexec.c 2003-11-28 23:24:41.000000000 +0100
@@ -50,10 +50,9 @@ static int re_search_stub (struct re_pat
int ret_len);
static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
int nregs, int regs_allocated);
-static re_dfastate_t *acquire_init_state_context (reg_errcode_t *err,
- const regex_t *preg,
- const re_match_context_t *mctx,
- int idx);
+static inline re_dfastate_t *acquire_init_state_context
+ (reg_errcode_t *err, const regex_t *preg, const re_match_context_t *mctx,
+ int idx) __attribute ((always_inline));
static reg_errcode_t prune_impossible_nodes (const regex_t *preg,
re_match_context_t *mctx);
static int check_matching (const regex_t *preg, re_match_context_t *mctx,
@@ -921,7 +920,7 @@ prune_impossible_nodes (preg, mctx)
We must select appropriate initial state depending on the context,
since initial states may have constraints like "\<", "^", etc.. */
-static re_dfastate_t *
+static inline re_dfastate_t *
acquire_init_state_context (err, preg, mctx, idx)
reg_errcode_t *err;
const regex_t *preg;
@@ -988,22 +987,22 @@ check_matching (preg, mctx, fl_longest_m
/* Check OP_OPEN_SUBEXP in the initial state in case that we use them
later. E.g. Processing back references. */
- if (dfa->nbackref)
+ if (BE (dfa->nbackref, 0))
{
err = check_subexp_matching_top (dfa, mctx, &cur_state->nodes, 0);
if (BE (err != REG_NOERROR, 0))
return err;
- }
- if (cur_state->has_backref)
- {
- err = transit_state_bkref (preg, &cur_state->nodes, mctx);
- if (BE (err != REG_NOERROR, 0))
- return err;
+ if (cur_state->has_backref)
+ {
+ err = transit_state_bkref (preg, &cur_state->nodes, mctx);
+ if (BE (err != REG_NOERROR, 0))
+ return err;
+ }
}
/* If the RE accepts NULL string. */
- if (cur_state->halt)
+ if (BE (cur_state->halt, 0))
{
if (!cur_state->has_constraint
|| check_halt_state_context (preg, cur_state, mctx, cur_str_idx))
@@ -1384,11 +1383,11 @@ update_regs (dfa, pmatch, cur_node, cur_
i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
away the node `a'.
ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
- throwed away, we throw away the node `a'.
+ thrown away, we throw away the node `a'.
3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
node `a'.
- ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is throwed away,
+ ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
we throw away the node `a'. */
#define STATE_NODE_CONTAINS(state,node) \
@@ -2053,7 +2052,7 @@ sift_states_iter_mb (preg, mctx, sctx, n
!STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
dfa->nexts[node_idx]))
/* The node can't accept the `multi byte', or the
- destination was already throwed away, then the node
+ destination was already thrown away, then the node
could't accept the current input `multi byte'. */
naccepted = 0;
/* Otherwise, it is sure that the node could accept
@@ -2200,24 +2199,24 @@ transit_state (err, preg, mctx, state)
}
}
- /* Check OP_OPEN_SUBEXP in the current state in case that we use them
- later. We must check them here, since the back references in the
- next state might use them. */
- if (dfa->nbackref && next_state/* && fl_process_bkref */)
+ if (BE (dfa->nbackref, 0) && next_state != NULL)
{
+ /* Check OP_OPEN_SUBEXP in the current state in case that we use them
+ later. We must check them here, since the back references in the
+ next state might use them. */
*err = check_subexp_matching_top (dfa, mctx, &next_state->nodes,
cur_idx);
if (BE (*err != REG_NOERROR, 0))
return NULL;
- }
- /* If the next state has back references. */
- if (next_state != NULL && next_state->has_backref)
- {
- *err = transit_state_bkref (preg, &next_state->nodes, mctx);
- if (BE (*err != REG_NOERROR, 0))
- return NULL;
- next_state = mctx->state_log[cur_idx];
+ /* If the next state has back references. */
+ if (next_state->has_backref)
+ {
+ *err = transit_state_bkref (preg, &next_state->nodes, mctx);
+ if (BE (*err != REG_NOERROR, 0))
+ return NULL;
+ next_state = mctx->state_log[cur_idx];
+ }
}
return next_state;
}
--- libc/posix/regcomp.c.jj 2003-11-27 14:22:56.000000000 +0100
+++ libc/posix/regcomp.c 2003-11-27 22:32:27.000000000 +0100
@@ -1711,28 +1711,28 @@ peek_token (token, input, syntax)
if (!(syntax & RE_NO_GNU_OPS))
{
token->type = ANCHOR;
- token->opr.idx = WORD_FIRST;
+ token->opr.ctx_type = WORD_FIRST;
}
break;
case '>':
if (!(syntax & RE_NO_GNU_OPS))
{
token->type = ANCHOR;
- token->opr.idx = WORD_LAST;
+ token->opr.ctx_type = WORD_LAST;
}
break;
case 'b':
if (!(syntax & RE_NO_GNU_OPS))
{
token->type = ANCHOR;
- token->opr.idx = WORD_DELIM;
+ token->opr.ctx_type = WORD_DELIM;
}
break;
case 'B':
if (!(syntax & RE_NO_GNU_OPS))
{
token->type = ANCHOR;
- token->opr.idx = INSIDE_WORD;
+ token->opr.ctx_type = INSIDE_WORD;
}
break;
case 'w':
@@ -1755,14 +1755,14 @@ peek_token (token, input, syntax)
if (!(syntax & RE_NO_GNU_OPS))
{
token->type = ANCHOR;
- token->opr.idx = BUF_FIRST;
+ token->opr.ctx_type = BUF_FIRST;
}
break;
case '\'':
if (!(syntax & RE_NO_GNU_OPS))
{
token->type = ANCHOR;
- token->opr.idx = BUF_LAST;
+ token->opr.ctx_type = BUF_LAST;
}
break;
case '(':
@@ -1858,7 +1858,7 @@ peek_token (token, input, syntax)
break;
}
token->type = ANCHOR;
- token->opr.idx = LINE_FIRST;
+ token->opr.ctx_type = LINE_FIRST;
break;
case '$':
if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
@@ -1872,7 +1872,7 @@ peek_token (token, input, syntax)
break;
}
token->type = ANCHOR;
- token->opr.idx = LINE_LAST;
+ token->opr.ctx_type = LINE_LAST;
break;
default:
break;
@@ -2217,7 +2217,9 @@ parse_expression (regexp, preg, token, s
}
break;
case ANCHOR:
- if (dfa->word_char == NULL)
+ if ((token->opr.ctx_type
+ & (WORD_DELIM | INSIDE_WORD | WORD_FIRST | WORD_LAST))
+ && dfa->word_char == NULL)
{
*err = init_word_char (dfa);
if (BE (*err != REG_NOERROR, 0))
--- libc/posix/bug-regex11.c.jj 2003-11-26 15:46:18.000000000 +0100
+++ libc/posix/bug-regex11.c 2003-11-28 21:16:39.000000000 +0100
@@ -71,10 +71,18 @@ struct
{ "(bb())\\2\\1", "bbbb", REG_EXTENDED, 3, { { 0, 4 }, { 0, 2 }, { 2, 2 } } },
{ "^(.?)(.?)(.?)(.?)(.?).?\\5\\4\\3\\2\\1$",
"level", REG_NOSUB | REG_EXTENDED, 0, { { -1, -1 } } },
+ { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$|^.?$",
+ "level", REG_NOSUB | REG_EXTENDED, 0, { { -1, -1 } } },
+ { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$|^.?$",
+ "abcdedcba", REG_EXTENDED, 1, { { 0, 9 } } },
#if 0
/* XXX Not used since they fail so far. */
+ { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$|^.?$",
+ "ababababa", REG_EXTENDED, 1, { { 0, 9 } } },
{ "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$",
"level", REG_NOSUB | REG_EXTENDED, 0, { { -1, -1 } } },
+ { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$",
+ "ababababa", REG_EXTENDED, 1, { { 0, 9 } } },
#endif
};
--- libc/posix/tst-regex.c.jj 2003-11-12 21:33:35.000000000 +0100
+++ libc/posix/tst-regex.c 2003-11-28 22:57:53.000000000 +0100
@@ -23,6 +23,7 @@
#include <errno.h>
#include <error.h>
#include <fcntl.h>
+#include <getopt.h>
#include <iconv.h>
#include <locale.h>
#include <mcheck.h>
@@ -45,6 +46,7 @@ static char *mem;
static char *umem;
static size_t memlen;
static size_t umemlen;
+static int timing;
static int test_expr (const char *expr, int expected, int expectedicase);
static int run_test (const char *expr, const char *mem, size_t memlen,
@@ -54,7 +56,7 @@ static int run_test_backwards (const cha
int
-main (void)
+main (int argc, char *argv[])
{
const char *file;
int fd;
@@ -64,9 +66,16 @@ main (void)
char *outmem;
size_t inlen;
size_t outlen;
+ static const struct option options[] =
+ {
+ {"timing",no_argument, &timing, 1 },
+ {NULL, 0, NULL, 0 }
+ };
mtrace ();
+ while (getopt_long (argc, argv, "", options, NULL) >= 0);
+
/* Make the content of the file available in memory. */
file = "../ChangeLog.8";
fd = open (file, O_RDONLY);
@@ -125,6 +134,8 @@ main (void)
result |= test_expr ("G.\\{1\\}ran", 2, 3);
result |= test_expr ("G.*ran", 3, 44);
result |= test_expr ("[äáà â]", 0, 0);
+ result |= test_expr ("Uddeborg", 2, 2);
+ result |= test_expr (".Uddeborg", 2, 2);
/* Free the resources. */
free (umem);
@@ -201,7 +212,7 @@ run_test (const char *expr, const char *
int cnt;
#ifdef _POSIX_CPUTIME
- if (use_clock)
+ if (use_clock && !timing)
use_clock = clock_gettime (cl, &start) == 0;
#endif
@@ -250,7 +261,7 @@ run_test (const char *expr, const char *
regfree (&re);
#ifdef _POSIX_CPUTIME
- if (use_clock)
+ if (use_clock && !timing)
{
use_clock = clock_gettime (cl, &finish) == 0;
if (use_clock)
@@ -270,6 +281,58 @@ run_test (const char *expr, const char *
finish.tv_sec, finish.tv_nsec);
}
}
+
+ if (use_clock && timing)
+ {
+ struct timespec mintime = { .tv_sec = 24 * 60 * 60 };
+
+ for (int i = 0; i < 10; ++i)
+ {
+ offset = 0;
+ use_clock = clock_gettime (cl, &start) == 0;
+
+ if (!use_clock)
+ continue;
+
+ err = regcomp (&re, expr, REG_NEWLINE | (icase ? REG_ICASE : 0));
+ if (err != REG_NOERROR)
+ continue;
+
+ while (offset < memlen)
+ {
+ regmatch_t ma[1];
+
+ err = regexec (&re, mem + offset, 1, ma, 0);
+ if (err != REG_NOERROR)
+ break;
+
+ offset += ma[0].rm_eo;
+ }
+
+ regfree (&re);
+
+ use_clock = clock_gettime (cl, &finish) == 0;
+ if (use_clock)
+ {
+ if (finish.tv_nsec < start.tv_nsec)
+ {
+ finish.tv_nsec -= start.tv_nsec - 1000000000;
+ finish.tv_sec -= 1 + start.tv_sec;
+ }
+ else
+ {
+ finish.tv_nsec -= start.tv_nsec;
+ finish.tv_sec -= start.tv_sec;
+ }
+ if (finish.tv_sec < mintime.tv_sec
+ || (finish.tv_sec == mintime.tv_sec
+ && finish.tv_nsec < mintime.tv_nsec))
+ mintime = finish;
+ }
+ }
+ printf ("elapsed time: %ld.%09ld sec\n",
+ mintime.tv_sec, mintime.tv_nsec);
+ }
#endif
/* Return an error if the number of matches found is not match we
@@ -292,7 +355,7 @@ run_test_backwards (const char *expr, co
int cnt;
#ifdef _POSIX_CPUTIME
- if (use_clock)
+ if (use_clock && !timing)
use_clock = clock_gettime (cl, &start) == 0;
#endif
@@ -344,7 +407,7 @@ run_test_backwards (const char *expr, co
regfree (&re);
#ifdef _POSIX_CPUTIME
- if (use_clock)
+ if (use_clock && !timing)
{
use_clock = clock_gettime (cl, &finish) == 0;
if (use_clock)
@@ -364,6 +427,74 @@ run_test_backwards (const char *expr, co
finish.tv_sec, finish.tv_nsec);
}
}
+
+ if (use_clock && timing)
+ {
+ struct timespec mintime = { .tv_sec = 24 * 60 * 60 };
+
+ for (int i = 0; i < 10; ++i)
+ {
+ offset = memlen;
+ use_clock = clock_gettime (cl, &start) == 0;
+
+ if (!use_clock)
+ continue;
+
+ memset (&re, 0, sizeof (re));
+ re.fastmap = malloc (256);
+ if (re.fastmap == NULL)
+ continue;
+
+ err = re_compile_pattern (expr, strlen (expr), &re);
+ if (err != NULL)
+ continue;
+
+ if (re_compile_fastmap (&re))
+ {
+ regfree (&re);
+ continue;
+ }
+
+ while (offset <= memlen)
+ {
+ int start;
+ const char *sp;
+
+ start = re_search (&re, mem, memlen, offset, -offset, NULL);
+ if (start < -1)
+ break;
+
+ sp = mem + start;
+ while (sp > mem && sp[-1] != '\n')
+ --sp;
+
+ offset = sp - 1 - mem;
+ }
+
+ regfree (&re);
+
+ use_clock = clock_gettime (cl, &finish) == 0;
+ if (use_clock)
+ {
+ if (finish.tv_nsec < start.tv_nsec)
+ {
+ finish.tv_nsec -= start.tv_nsec - 1000000000;
+ finish.tv_sec -= 1 + start.tv_sec;
+ }
+ else
+ {
+ finish.tv_nsec -= start.tv_nsec;
+ finish.tv_sec -= start.tv_sec;
+ }
+ if (finish.tv_sec < mintime.tv_sec
+ || (finish.tv_sec == mintime.tv_sec
+ && finish.tv_nsec < mintime.tv_nsec))
+ mintime = finish;
+ }
+ }
+ printf ("elapsed time: %ld.%09ld sec\n",
+ mintime.tv_sec, mintime.tv_nsec);
+ }
#endif
/* Return an error if the number of matches found is not match we
Jakub
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2003-11-28 22:41 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-11-29 4:38 [PATCH] Small regex optimizations Jakub Jelinek
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).