buggrep - Bugs: bug #14060, Max one keyword is used for...


You are not allowed to post comments on this tracker with your current authentication level.

bug #14060: Max one keyword is used for multiple string patterns - results in poor performance

Submitted by:  Johannes T. Prinz <purple>
Submitted on:  Sun 07 Aug 2005 07:39:44 PM UTC  
Category:  None Severity:  3 - Normal
Item Group:  None Status:  None
Privacy:  Public Assigned to:  None
Open/Closed:  Open

Sat 06 Feb 2010 01:20:09 PM UTC, comment #1: 

See also #16305 for another example.

Paolo Bonzini <bonzini>
Sun 07 Aug 2005 07:39:44 PM UTC, original submission:  

When searching patterns like e.g. "Bloom|Dedalus" or in general "s1|s2|.." the fast commentz-walter algorithm is not used at all.

Analyzing the source code shows that in function dfamust() in dfa.c one string at maximum (!) is computed as keyword for dfa->must (s. attached code excerpt). So all string pattern matching in kwset.c uses at maximum one string.

excerpt from dfamust():

  if (strlen(result))
      MALLOC(dm, struct dfamust, 1);
      dm->exact = exact;
      MALLOC(dm->must, char, strlen(result) + 1);
      strcpy(dm->must, result);
      dm->next = dfa->musts;
      dfa->musts = dm;
  mp = musts;
  for (i = 0; i <= dfa->tindex; ++i)
      ifree((char *) mp[i].in);
  free((char *) mp);


Johannes T. Prinz <purple>


No files currently attached


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by bonzini (Posted a comment)

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.




    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2005-08-07 purple Carbon-Copy- => Added -email is unavailable-

    Back to the top

    Powered by Savane 3.7