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

 
 

You are not allowed to post comments on this tracker with your current authentification 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: NoneSeverity: 3 - Normal
Item Group: NoneStatus: None
Privacy: PublicAssigned 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():

..
done:
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)
{
freelist(mp[i].in);
ifree((char *) mp[i].in);
ifree(mp[i].left);
ifree(mp[i].right);
ifree(mp[i].is);
}
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
  • -unavailable- added by bonzini (Posted a comment)
  •  

    Do you think this task is very important?
    If so, you can click here to 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
    Sun 07 Aug 2005 07:39:44 PM UTCpurpleCarbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup