Skip to content

GitLab

P
pgrep
Open
Opened by Bernhard Scheirle@scheirleOwner
Report abuse New issue

EBOM is realy slow in some cases

EBOM is realy slow in some cases (more than 10 times slower than other StringMatchers)

See speedtest:

  • Big Almost match, Short pattern, pattern = (ab)^15 c, text = (ab)*
  • Big Almost match, Short pattern, pattern = c (ab)^15, text = (ab)*

My Output:

======== Run benchmark: Big Almost match, Short pattern, pattern = (ab)^15 c, text = (ab)* ========
Time:  190ms [ 178ms,  236ms] { 278ns [  52ns,  341ns]} NaiveStringMatcher (0 matches)
Time:  161ms [ 161ms,  161ms] { 282ns [ 139ns,  348ns]} NaiveSIMDStringMatcher (0 matches)
Time:   53ms [  53ms,   53ms] { 249ns [  41ns,  342ns]} VeryNaiveStringMatcher (0 matches)
Time:   24ms [  24ms,   25ms] { 652ns [ 368ns,  803ns]} KnuthMorrisPrattStringMatcher (0 matches)
Time:   75ms [  75ms,   75ms] {4184ns [3656ns, 4643ns]} BoyerMooreStringMatcher (0 matches)
Time:   20ms [  20ms,   20ms] {1075ns [ 874ns, 1220ns]} ShiftOrStringMatcher (0 matches)
Time:   97ms [  97ms,   98ms] { 275ns [ 133ns,  348ns]} TestSIMDStringMatcher (0 matches)
Time:  537ms [ 537ms,  537ms] {  48us [  37us,   90us]} EBOMStringMatcher (0 matches)
Time: 1205ms [1205ms, 1206ms] {2009ns [1753ns, 2163ns]} FSBNDMStringMatcher (0 matches)
Time:   45ms [  45ms,   45ms] { 668ns [ 364ns,  987ns]} Hash3StringMatcher (0 matches)
Time:  539ms [ 539ms,  539ms] {  38us [  37us,   40us]} SelectingStringMatcher {LSIMD | EBOM | SSEF | Hash3} (0 matches)
Time:  239ms [ 236ms,  241ms] { 491ns [  73ns,  754ns]} ThreadedStringMatcher using NaiveStringMatcher (0 matches)
Time:   61ms [  55ms,   63ms] { 379ns [  63ns,  622ns]} PackagedStringMatcher using NaiveStringMatcher (0 matches)
Fastest: (Preprocess + Matching)
   ShiftOrStringMatcher (  20ms, 100%)
   KnuthMorrisPrattStringMatcher (  24ms, 123%)
   Hash3StringMatcher (  45ms, 225%)
======== Run benchmark: Big Almost match, Short pattern, pattern = c (ab)^15, text = (ab)* ========
Time:   20ms [  19ms,   20ms] { 295ns [  89ns,  390ns]} NaiveStringMatcher (0 matches)
Time:   22ms [  21ms,   22ms] { 351ns [ 132ns,  550ns]} NaiveSIMDStringMatcher (0 matches)
Time:   15ms [  14ms,   15ms] { 323ns [  58ns,  467ns]} VeryNaiveStringMatcher (0 matches)
Time:   35ms [  35ms,   35ms] { 655ns [ 593ns,  766ns]} KnuthMorrisPrattStringMatcher (0 matches)
Time:   16ms [  16ms,   17ms] {4146ns [3774ns, 4365ns]} BoyerMooreStringMatcher (0 matches)
Time:   20ms [  20ms,   20ms] {1093ns [ 813ns, 1321ns]} ShiftOrStringMatcher (0 matches)
Time:   33ms [  33ms,   33ms] { 294ns [ 153ns,  339ns]} TestSIMDStringMatcher (0 matches)
Time:  542ms [ 539ms,  553ms] {  39us [  38us,   40us]} EBOMStringMatcher (0 matches)
Time:   83ms [  83ms,   83ms] {1935ns [1753ns, 2082ns]} FSBNDMStringMatcher (0 matches)
Time:   51ms [  51ms,   52ms] { 540ns [ 358ns,  689ns]} Hash3StringMatcher (0 matches)
Time:  537ms [ 537ms,  537ms] {  37us [  36us,   38us]} SelectingStringMatcher {LSIMD | EBOM | SSEF | Hash3} (0 matches)
Time:   20ms [  20ms,   20ms] { 444ns [  68ns,  556ns]} ThreadedStringMatcher using NaiveStringMatcher (0 matches)
Time:   10ms [8892us,   14ms] { 406ns [  68ns,  531ns]} PackagedStringMatcher using NaiveStringMatcher (0 matches)
Fastest: (Preprocess + Matching)
   PackagedStringMatcher using NaiveStringMatcher (  10ms, 100%)
   VeryNaiveStringMatcher (  15ms, 139%)
   BoyerMooreStringMatcher (  16ms, 156%)

Problem:

In these cases the SelectingStringMatcher selects the EBOMStringMatcher.

I assume BM_BigAlmostMatch (on http://www.ipd.kit.edu/~pfaffe/results.html) is a test of this kind.