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.


    Please enter the title of George Orwell's famous dystopian book (it's a date):



    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.3