This is the mail archive of the
libc-alpha@sources.redhat.com
mailing list for the glibc project.
[PATCH] More speedups, this time in build_trtable
- From: Paolo Bonzini <paolo dot bonzini at polimi dot it>
- To: libc-alpha at sources dot redhat dot com
- Date: Tue, 16 Dec 2003 14:37:35 +0100
- Subject: [PATCH] More speedups, this time in build_trtable
- Reply-to: bonzini at gnu dot org
After Jakub's patch that disabled transit_state_sb, build_trtable
frequently shows up at the top of the profiles. This patch divides the
inner loop in two (for state->word_trtable == 0 or == 1 respectively)
and rewrites the iteration on bitsets so that it does not iterate on
empty items. The result is a 20% improvement in the time needed to run
the sed testsuite on my machine, with a top improvement of 2x on
madding.sed (which is a search for a very long string).
Thanks,
Paolo
2002-12-16 Paolo Bonzini <bonzini@gnu.org>
* posix/regexec.c (build_trtable): don't allocate the trtable
until state->word_trtable is known. Don't hardcode UINT_BITS
iterations on each bitset item.
Index: regexec.c
===================================================================
RCS file: /cvs/glibc/libc/posix/regexec.c,v
retrieving revision 1.44
diff -c -p -r1.44 regexec.c
*** regexec.c 16 Dec 2003 06:15:41 -0000 1.44
--- regexec.c 16 Dec 2003 12:39:43 -0000
*************** build_trtable (preg, state)
*** 3119,3125 ****
{
reg_errcode_t err;
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
! int i, j, k, ch;
int dests_node_malloced = 0, dest_states_malloced = 0;
int ndests; /* Number of the destination states from `state'. */
re_dfastate_t **trtable;
--- 3119,3126 ----
{
reg_errcode_t err;
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
! int i, j, ch;
! unsigned int elem, mask;
int dests_node_malloced = 0, dest_states_malloced = 0;
int ndests; /* Number of the destination states from `state'. */
re_dfastate_t **trtable;
*************** build_trtable (preg, state)
*** 3148,3161 ****
dests_ch = (bitset *) (dests_node + SBC_MAX);
/* Initialize transiton table. */
- trtable = (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
state->word_trtable = 0;
- if (BE (trtable == NULL, 0))
- {
- if (dests_node_malloced)
- free (dests_node);
- return NULL;
- }
/* At first, group all nodes belonging to `state' into several
destinations. */
--- 3149,3155 ----
*************** build_trtable (preg, state)
*** 3167,3176 ****
/* Return NULL in case of an error, trtable otherwise. */
if (ndests == 0)
{
! state->trtable = trtable;
! return trtable;
}
- free (trtable);
return NULL;
}
--- 3161,3170 ----
/* Return NULL in case of an error, trtable otherwise. */
if (ndests == 0)
{
! state->trtable = (re_dfastate_t **)
! calloc (sizeof (re_dfastate_t *), SBC_MAX);;
! return state->trtable;
}
return NULL;
}
*************** out_free:
*** 3196,3202 ****
re_node_set_free (&follows);
for (i = 0; i < ndests; ++i)
re_node_set_free (dests_node + i);
- free (trtable);
if (dests_node_malloced)
free (dests_node);
return NULL;
--- 3190,3195 ----
*************** out_free:
*** 3234,3244 ****
CONTEXT_WORD);
if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
goto out_free;
dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
CONTEXT_NEWLINE);
if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
goto out_free;
! }
else
{
dest_states_word[i] = dest_states[i];
--- 3227,3242 ----
CONTEXT_WORD);
if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
goto out_free;
+
+ if (dest_states[i] != dest_states_word[i]
+ && dfa->mb_cur_max > 1)
+ state->word_trtable = 1;
+
dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
CONTEXT_NEWLINE);
if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
goto out_free;
! }
else
{
dest_states_word[i] = dest_states[i];
*************** out_free:
*** 3247,3305 ****
bitset_merge (acceptable, dests_ch[i]);
}
! /* Update the transition table. */
! /* For all characters ch...: */
! for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
! for (j = 0; j < UINT_BITS; ++j, ++ch)
! if ((acceptable[i] >> j) & 1)
! {
! for (k = 0; k < ndests; ++k)
! if ((dests_ch[k][i] >> j) & 1)
! {
! /* k-th destination accepts the word character ch. */
! if (state->word_trtable)
! {
! trtable[ch] = dest_states[k];
! trtable[ch + SBC_MAX] = dest_states_word[k];
! }
! else if (dfa->mb_cur_max > 1
! && dest_states[k] != dest_states_word[k])
! {
! re_dfastate_t **new_trtable;
!
! new_trtable = (re_dfastate_t **)
! realloc (trtable,
! sizeof (re_dfastate_t *)
! * 2 * SBC_MAX);
! if (BE (new_trtable == NULL, 0))
! goto out_free;
! memcpy (new_trtable + SBC_MAX, new_trtable,
! sizeof (re_dfastate_t *) * SBC_MAX);
! trtable = new_trtable;
! state->word_trtable = 1;
! trtable[ch] = dest_states[k];
! trtable[ch + SBC_MAX] = dest_states_word[k];
! }
! else if (IS_WORD_CHAR (ch))
! trtable[ch] = dest_states_word[k];
! else
! trtable[ch] = dest_states[k];
! /* There must be only one destination which accepts
! character ch. See group_nodes_into_DFAstates. */
! break;
! }
! }
/* new line */
if (bitset_contain (acceptable, NEWLINE_CHAR))
{
/* The current state accepts newline character. */
! for (k = 0; k < ndests; ++k)
! if (bitset_contain (dests_ch[k], NEWLINE_CHAR))
{
/* k-th destination accepts newline character. */
! trtable[NEWLINE_CHAR] = dest_states_nl[k];
if (state->word_trtable)
! trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[k];
/* There must be only one destination which accepts
newline. See group_nodes_into_DFAstates. */
break;
--- 3245,3320 ----
bitset_merge (acceptable, dests_ch[i]);
}
! if (!BE (state->word_trtable, 0))
! {
! /* We don't care about whether the following character is a word
! character, or we are in a single-byte character set so we can
! discern by looking at the character code: allocate a
! 256-entry transition table. */
! trtable = (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
! if (BE (trtable == NULL, 0))
! goto out_free;
!
! /* For all characters ch...: */
! for (i = 0; i < BITSET_UINTS; ++i)
! for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
! elem;
! mask <<= 1, elem >>= 1, ++ch)
! if (BE (elem & 1, 0))
! {
! /* There must be exactly one destination which accepts
! character ch. See group_nodes_into_DFAstates. */
! for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
! ;
!
! /* j-th destination accepts the word character ch. */
! if (IS_WORD_CHAR (ch))
! trtable[ch] = dest_states_word[j];
! else
! trtable[ch] = dest_states[j];
! }
! }
! else
! {
! /* We care about whether the following character is a word
! character, and we are in a multi-byte character set: discern
! by looking at the character code: build two 256-entry
! transition tables, one starting at trtable[0] and one
! starting at trtable[SBC_MAX]. */
! trtable = (re_dfastate_t **) calloc (sizeof (re_dfastate_t *),
! 2 * SBC_MAX);
! if (BE (trtable == NULL, 0))
! goto out_free;
!
! /* For all characters ch...: */
! for (i = 0; i < BITSET_UINTS; ++i)
! for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
! elem;
! mask <<= 1, elem >>= 1, ++ch)
! if (BE (elem & 1, 0))
! {
! /* There must be exactly one destination which accepts
! character ch. See group_nodes_into_DFAstates. */
! for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
! ;
!
! /* j-th destination accepts the word character ch. */
! trtable[ch] = dest_states[j];
! trtable[ch + SBC_MAX] = dest_states_word[j];
! }
! }
!
/* new line */
if (bitset_contain (acceptable, NEWLINE_CHAR))
{
/* The current state accepts newline character. */
! for (j = 0; j < ndests; ++j)
! if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
{
/* k-th destination accepts newline character. */
! trtable[NEWLINE_CHAR] = dest_states_nl[j];
if (state->word_trtable)
! trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
/* There must be only one destination which accepts
newline. See group_nodes_into_DFAstates. */
break;