This is the mail archive of the libc-alpha@sources.redhat.com mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] More speedups, this time in build_trtable


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;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]