Click here to Skip to main content
Click here to Skip to main content
Search within:



 
Comments & Discussions

Fastest strstr-like Function in C!?

By , 20 Jan 2012
 
This is an old version of the currently published article.

Introduction

The C strstr-like function presented below (written by Georgi 'Kaze') is named Railgun_Quadruplet_6ppp and is based on well-known Boyer-Moore-Horspool and simplified Karp-Rabin algorithms. The main goal: to achieve fastest execution for all kinds of pattern/needle and string/haystack lengths (starting from 2 bytes).

Railgun_Quadruplet_6ppp is now obsolete due to the arrival of Railgun_Quadruplet_7 which boosts the BMH fragment by more than a percent. See further below for its commentless and tabulated source.

Railgun_Quadruplet_7 exploits the CPUs fast unaligned DWORD extract capability.
The heaviest and most precise test on 1+TB text (52 patterns vs 197MB English books text repeated 256 times results in 1000+ seconds, see strstr_SHORT-SHOWDOWN_r7_Heavy_Test_LOG.txt file for more information) gives:

[strstr_SHORT-SHOWDOWN_Microsoft_v16_Ox.exe:]
The variants returning the offset of first hit only:

  • Railgun_Quadruplet_6pp 52, i.e., average performance: 1584KB/clock
  • Railgun_Quadruplet_7 52, i.e., average performance: 1659KB/clock

The variants counting all hits:

  • Railgun_6pp 8x2, i.e., average performance: 1246KB/clock
  • Railgun_Quadruplet_7 8x2, i.e., average performance: 1266KB/clock

[strstr_SHORT-SHOWDOWN_Intel_v12_O3.exe:]
The variants returning the offset of first hit only:

  • Railgun_Quadruplet_6pp 52, i.e., average performance: 1773KB/clock
  • Railgun_Quadruplet_7 52, i.e., average performance: 1685KB/clock

The variants counting all hits:

  • Railgun_6pp 8x2, i.e., average performance: 1054KB/clock
  • Railgun_Quadruplet_7 8x2, i.e., average performance: 1076KB/clock

Note: For Railgun_Quadruplet_7 on CPUs with fast DWORD (compared to BYTE) memory fetching I expect significant boost, AFAIK the Intel i7 is one of those, unfortunately I lack the opportunity to play with it.

Or the two bottom-lines:
The FASTEST variant counting all hits:

  • Railgun_Quadruplet_7 8x2 with average performance: 1266KB/clock (best performance achieved with Microsoft_v16_Ox)!

The FASTEST variant returning the offset of first hit only:

  • Railgun_Quadruplet_6pp 52 with average performance: 1773KB/clock (1,943,883,635,456 bytes / 1,070,220 clocks = 1732 MB/s best performance achieved with Intel_v12_O3)!

An add-on from 2012-Jan-20:

[
Railgun_Quadruplet_7 vs Railgun_Quadruplet_7deuce vs Boyer_Moore vs Brute_Force: a face-off

Okay, nothing new, only a must-see benchmark against the original Boyer-Moore implementation.
Two tests were done - the first/second '6x2'/'52' searches 12/52 patterns (for all appearances i.e. counting all hits) into 206,908,949 bytes long English text.
Speed-Performance (measured in KB/clock, bigger-the-better) Summary:
Function                   6x2 test
Railgun_Quadruplet_7       2,039KB/clock / 137,568% / 006,454,416,320  BONBON
Boyer_Moore_Flensburg      1,239KB/clock / 139,168% / 006,428,115,568  Slow
Railgun_Quadruplet_7deuce  1,120KB/clock / 155,744% / 005,995,597,776  Slower
Brute_Force_Dummy          0,341KB/clock / 019,200% / 039,726,516,640  Slowest

Speed-Performance (measured in KB/clock, bigger-the-better) Summary:
Function                   52 test
Railgun_Quadruplet_7       1,645KB/clock / 708,768% / 025,368,049,712  BONBON
Boyer_Moore_Flensburg      0,987KB/clock / 720,272% / 025,227,312,176  Slow
Railgun_Quadruplet_7deuce  0,919KB/clock / 864,048% / 023,292,952,992  Slower
Brute_Force_Dummy          0,277KB/clock / 083,200% / 172,148,232,496  Slowest

Skip-Performance (measured in %, bigger-the-better) Summary:
Function                   6x2 test
Railgun_Quadruplet_7deuce  1,120KB/clock / 155,744% / 005,995,597,776  BONBON
Boyer_Moore_Flensburg      1,239KB/clock / 139,168% / 006,428,115,568  loopy
Railgun_Quadruplet_7       2,039KB/clock / 137,568% / 006,454,416,320  loopier
Brute_Force_Dummy          0,341KB/clock / 019,200% / 039,726,516,640  loopiest 

Skip-Performance (measured in %, bigger-the-better) Summary:
Function                   52 test
Railgun_Quadruplet_7deuce  0,919KB/clock / 864,048% / 023,292,952,992  BONBON
Boyer_Moore_Flensburg      0,987KB/clock / 720,272% / 025,227,312,176  loopy
Railgun_Quadruplet_7       1,645KB/clock / 708,768% / 025,368,049,712  loopier
Brute_Force_Dummy          0,277KB/clock / 083,200% / 172,148,232,496  loopiest
A very easy-to-the-eyes/mind article at http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/bm.htm
Here I say 'Triple THANKS' to Mr. Prof. Dr. Hans Werner Lang (Institut für Medieninformatik und Technische Informatik Fachhochschule Flensburg), I used your code (after a straightforward port). On his page (http://www.inf.fh-flensburg.de/lang/) there are very well presented algorithms - a very good resource indeed.
I see that Sunday algorithm has a potential, soon I will play with it.
I expect Railgun_Quadruplet_7deuce to become a gun of choice but only on CPUs with FAR more effective memory handling than my Pentium Merom.
]

Background

Function homepage:
http://www.sanmayce.com/Railgun/index.html

Note: In order to reproduce the tests shown on the picture (below) you need the test package (57.2 MB) downloadable at function's homepage, thanks Randor for pointing out.

Very informative resource on strstr search techniques at:

Tests done with 16 patterns with 197MB haystack (being a pure English book-like text).

Railgun_Benchmarked.png

The machine is a mainstream laptop on 2.1GHz with Intel Merom CPU.

Using the Code

The code is pretty simple and straightforward. 

// Here the strstr-like function Railgun_Quadruplet_6ppp is given,  
// written by Georgi 'Kaze', 2011-Sep-07.
//
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Horspool algorithm [
// Caution: For better speed the case 'if (cbPattern==1)' was removed, 
// so Pattern must be longer than 1 char.
char * Railgun_Quadruplet_6ppp (char * pbTarget,
     char * pbPattern,
     unsigned long cbTarget,
     unsigned long cbPattern)
{
    char * pbTargetMax = pbTarget + cbTarget;
    register unsigned long  ulHashPattern;
    unsigned long ulHashTarget;
    //unsigned long count; //r.6+
    signed long count;
    //unsigned long countSTATIC; //r.6+
    signed long countSTATIC;
//  unsigned long countRemainder;

/*
    const unsigned char SINGLET = *(char *)(pbPattern);
    const unsigned long Quadruplet2nd = SINGLET<<8;
    const unsigned long Quadruplet3rd = SINGLET<<16;
    const unsigned long Quadruplet4th = SINGLET<<24;
*/
    unsigned char SINGLET;
    unsigned long Quadruplet2nd;
    unsigned long Quadruplet3rd;
    unsigned long Quadruplet4th;

    unsigned long  AdvanceHopperGrass;

    long i; //BMH needed
    int a, j, bm_bc[ASIZE]; //BMH needed
    unsigned char ch; //BMH needed
//    unsigned char lastch, firstch; //BMH needed

    if (cbPattern > cbTarget)
        return(NULL);

// Doesn't work when cbPattern = 1
// The next IF-fragment works very well with cbPattern>1, 
// OBVIOUSLY IT MUST BE UNROLLED(but crippled with less functionality) 
// SINCE either cbPattern=2 or cbPattern=3!
if ( cbPattern<4) {     // This IF makes me unhappy: it slows down from 
            // 390KB/clock to 367KB/clock for 'fast' pattern. 
            // This fragment(for 2..3 pattern lengths) is needed 
            // because I need a function different than strchr, but 
            // sticking to strstr i.e. lengths above 1 are to be handled.
        pbTarget = pbTarget+cbPattern;
        ulHashPattern = ( (*(char *)(pbPattern))<<8 ) + *(pbPattern+(cbPattern-1));
//        countSTATIC = cbPattern-2;

if ( cbPattern==3) {
    for ( ;; )
    {
        if ( ulHashPattern == ( (*(char *)(pbTarget-3))<<8 ) + *(pbTarget-1) ) {
         if ( *(char *)(pbPattern+1) == *(char *)(pbTarget-2) ) return((pbTarget-3));
        }
        if ( (char)(ulHashPattern>>8) != *(pbTarget-2) ) pbTarget++;
        pbTarget++;
        if (pbTarget > pbTargetMax)
            return(NULL);
    }
} else {
}
    for ( ;; )
    {
        // The line below gives for 'cbPattern'>=1:
        // Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/543
        // Karp_Rabin_Kaze_4_OCTETS performance: 372KB/clock
/*
        if ( (ulHashPattern == ( (*(char *)(pbTarget-cbPattern))<<8 ) + 
        *(pbTarget-1)) && !memcmp(pbPattern, pbTarget-cbPattern, 
        (unsigned int)cbPattern) )
            return((long)(pbTarget-cbPattern));
*/

        // The fragment below gives for 'cbPattern'>=2:
        // Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/546
        // Karp_Rabin_Kaze_4_OCTETS performance: 370KB/clock

/*
//For 2 and 3 [
        if ( ulHashPattern == ( (*(char *)(pbTarget-cbPattern))<<8 ) + *(pbTarget-1) ) {
//         count = countSTATIC;
         count = cbPattern-2;
//         while ( count && *(char *)(pbPattern+1+(countSTATIC-count)) == 
//         *(char *)(pbTarget-cbPattern+1+(countSTATIC-count)) ) {
         while ( count && *(char *)(pbPattern+1) == *(char *)(pbTarget-2) ) 
            { // Crippling i.e. only 2 and 3 chars are allowed!
               count--;
         }
         if ( count == 0) return((pbTarget-cbPattern));
        }
        if ( (char)(ulHashPattern>>8) != *(pbTarget-cbPattern+1) ) pbTarget++;
//For 2 and 3 ]
*/


        if ( ulHashPattern == ( (*(char *)(pbTarget-2))<<8 ) + *(pbTarget-1) )
            return((pbTarget-2));
        if ( (char)(ulHashPattern>>8) != *(pbTarget-1) ) pbTarget++;


        // The fragment below gives for 'cbPattern'>=2:
    // Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/554
    // Karp_Rabin_Kaze_4_OCTETS performance: 364KB/clock
/*
        if ( ulHashPattern == ( (*(char *)(pbTarget-cbPattern))<<8 ) + *(pbTarget-1) ) {
         count = countSTATIC>>2;
         countRemainder = countSTATIC % 4;

         while ( count && *(unsigned long *)(pbPattern+1+((count-1)<<2)) == 
        *(unsigned long *)(pbTarget-cbPattern+1+((count-1)<<2)) ) {
               count--;
         }
     //if (count == 0) {      // Disastrous degradation only from this line
                // (317KB/clock when 1+2x4+2+1 bytes pattern: 
                // 'skillessness'; 312KB/clock when 1+1x4+2+1 bytes 
                // pattern: 'underdog'), otherwise 368KB/clock.
         while ( countRemainder && *(char *)(pbPattern+1+
        (countSTATIC-countRemainder)) == *(char *)(pbTarget-cbPattern+1+
        (countSTATIC-countRemainder)) ) {
               countRemainder--;
         }
         //if ( countRemainder == 0) return((long)(pbTarget-cbPattern));
         if ( count+countRemainder == 0) return((long)(pbTarget-cbPattern));
         //}
        }
*/

        pbTarget++;
        if (pbTarget > pbTargetMax)
            return(NULL);
    }
} else { //if ( cbPattern<4)
if (cbTarget<961) // This value is arbitrary(don't know how exactly), 
        // it ensures(at least must) 
        // better performance than 'Boyer_Moore_Horspool'.
{
        pbTarget = pbTarget+cbPattern;
        ulHashPattern = *(unsigned long *)(pbPattern);
//        countSTATIC = cbPattern-1;

    //SINGLET = *(char *)(pbPattern);
    SINGLET = ulHashPattern & 0xFF;
    Quadruplet2nd = SINGLET<<8;
    Quadruplet3rd = SINGLET<<16;
    Quadruplet4th = SINGLET<<24;

    for ( ;; )
    {
    AdvanceHopperGrass = 0;
    ulHashTarget = *(unsigned long *)(pbTarget-cbPattern);

        if ( ulHashPattern == ulHashTarget ) { // Three unnecessary comparisons here, 
        // but 'AdvanceHopperGrass' must be calculated - it has a higher priority.
//         count = countSTATIC;
//         while ( count && *(char *)(pbPattern+1+(countSTATIC-count)) == 
//        *(char *)(pbTarget-cbPattern+1+(countSTATIC-count)) ) {
//           if ( countSTATIC==AdvanceHopperGrass+count && SINGLET != 
//         *(char *)(pbTarget-cbPattern+1+(countSTATIC-count)) ) 
//        AdvanceHopperGrass++;
//               count--;
//         }
         count = cbPattern-1;
         while ( count && *(char *)(pbPattern+(cbPattern-count)) == 
                    *(char *)(pbTarget-count) ) {
           if ( cbPattern-1==AdvanceHopperGrass+count && SINGLET != 
            *(char *)(pbTarget-count) ) AdvanceHopperGrass++;
               count--;
         }
         if ( count == 0) return((pbTarget-cbPattern));
        } else { // The goal here: to avoid memory accesses by stressing the registers.
    if ( Quadruplet2nd != (ulHashTarget & 0x0000FF00) ) {
         AdvanceHopperGrass++;
         if ( Quadruplet3rd != (ulHashTarget & 0x00FF0000) ) {
              AdvanceHopperGrass++;
              if ( Quadruplet4th != (ulHashTarget & 0xFF000000) ) AdvanceHopperGrass++;
         }
    }
    }

    AdvanceHopperGrass++;

    pbTarget = pbTarget + AdvanceHopperGrass;
        if (pbTarget > pbTargetMax)
            return(NULL);
    }
} else { //if (cbTarget<961)
        //countSTATIC = cbPattern-2; //r.6+
        //countSTATIC = cbPattern-2-3; //r.6++
        countSTATIC = cbPattern-2-2; //r.6+++ This line fixes the bug from r.6++!
        ulHashPattern = *(unsigned long *)(pbPattern);
    /* Preprocessing */
    for (a=0; a < ASIZE; a++) bm_bc[a]=cbPattern;
    for (j=0; j < cbPattern-1; j++) bm_bc[pbPattern[j]]=cbPattern-j-1;

    /* Searching */
    //lastch=pbPattern[cbPattern-1];
    //firstch=pbPattern[0];
    i=0;
    while (i <= cbTarget-cbPattern) {
       ch=pbTarget[i+cbPattern-1];
       //if (ch ==lastch)
          //if (memcmp(&pbTarget[i],pbPattern,cbPattern-1) == 0) OUTPUT(i);
          //if (ch == lastch && pbTarget[i] == firstch && 
     //memcmp(&pbTarget[i],pbPattern,cbPattern-1) == 0) return(i);  
          // Kaze: The idea(to prevent execution of slower 'memcmp') 
          // is borrowed from Karp-Rabin i.e. to perform a slower check only 
          // when the target "looks like".
          //if (ch == pbPattern[cbPattern-1] && pbTarget[i] == pbPattern[0]) // r.6+
          //if (ch == pbPattern[cbPattern-1] && *(long *)&pbTarget[i] 
          // == *(long *)&pbPattern[0]) // No problema here since we have 4[+] 
          // long pattern here. Overlapping (1 byte recompared) when length=4, grmbl.
          if (ch == pbPattern[cbPattern-1] && 
        *(long *)&pbTarget[i] == ulHashPattern) // No problema here since 
            // we have 4[+] long pattern here. Overlapping 
            // (1 byte recompared) when length=4, grmbl.
             {
         count = countSTATIC;
         //while ( count && *(char *)(pbPattern+1+(countSTATIC-count)) == 
    //*(char *)(&pbTarget[i]+1+(countSTATIC-count)) ) { // r.6+
         while ( count !=0 && *(char *)(pbPattern+1+3+(countSTATIC-count)) == 
        *(char *)(&pbTarget[i]+1+3+(countSTATIC-count)) ) 
        {     // if pattern length is 4 or 5 we have count=-1 and count=0 
            // respectively i.e. no need of comparing in-between chars.
               count--;
         }
         if ( count <= 0) return(pbTarget+i);
         }
       i+=bm_bc[ch];
    }
    return(NULL);
} //if (cbTarget<961)
} //if ( cbPattern<4)
}
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Horspool algorithm ]

Stomp stomp I arrived, here comes the Railgun_Quadruplet revision 7: 

// Caution: For better speed the case 'if (cbPattern==1)' was removed, 
// so Pattern must be longer than 1 char.
char * Railgun_Quadruplet_7 (char * pbTarget, char * pbPattern, 
        unsigned long cbTarget, unsigned long cbPattern)
{
    char * pbTargetMax = pbTarget + cbTarget;
    register unsigned long ulHashPattern;
    unsigned long ulHashTarget;
    signed long count;
    signed long countSTATIC;

    unsigned char SINGLET;
    unsigned long Quadruplet2nd;
    unsigned long Quadruplet3rd;
    unsigned long Quadruplet4th;
    unsigned long AdvanceHopperGrass;

    long i;
    int a, j, bm_bc[ASIZE];
    unsigned char ch;

    if (cbPattern > cbTarget) return(NULL);

    if (cbPattern<4) {
        pbTarget = pbTarget+cbPattern;
        ulHashPattern = ( (*(char *)(pbPattern))<<8 ) + 
                    *(pbPattern+(cbPattern-1));
        if (cbPattern==3) {
            for ( ;; ) {
                if ( ulHashPattern == 
                ( (*(char *)(pbTarget-3))<<8 ) + *(pbTarget-1) ) {
                    if ( *(char *)(pbPattern+1) == 
                    *(char *)(pbTarget-2) ) return((pbTarget-3));
                }
                if ( (char)(ulHashPattern>>8) != 
                        *(pbTarget-2) ) pbTarget++;
                pbTarget++;
                    if (pbTarget > pbTargetMax) return(NULL);
                }
        } else {
        }
            for ( ;; ) {
                if ( ulHashPattern == ( (*(char *)(pbTarget-2))<<8 ) 
                    + *(pbTarget-1) ) return((pbTarget-2));
                if ( (char)(ulHashPattern>>8) != *(pbTarget-1) ) 
                    pbTarget++;
                pbTarget++;
                if (pbTarget > pbTargetMax) return(NULL);
            }
    } else {
        if (cbTarget<961) {
            pbTarget = pbTarget+cbPattern;
            ulHashPattern = *(unsigned long *)(pbPattern);
            SINGLET = ulHashPattern & 0xFF;
            Quadruplet2nd = SINGLET<<8;
            Quadruplet3rd = SINGLET<<16;
            Quadruplet4th = SINGLET<<24;
            for ( ;; ) {
                AdvanceHopperGrass = 0;
                ulHashTarget = *(unsigned long *)(pbTarget-cbPattern);
                if ( ulHashPattern == ulHashTarget ) { 
                    count = cbPattern-1;
                    while ( count && *(char *)
                    (pbPattern+(cbPattern-count)) == 
                        *(char *)(pbTarget-count) ) {
                        if ( cbPattern-1==
                        AdvanceHopperGrass+count && 
                        SINGLET != *(char *)(pbTarget-count)
                             ) AdvanceHopperGrass++;
                        count--;
                    }
                    if ( count == 0) 
                        return((pbTarget-cbPattern));
                } else {
                    if ( Quadruplet2nd != (ulHashTarget 
                            & 0x0000FF00) ) {
                        AdvanceHopperGrass++;
                        if ( Quadruplet3rd != 
                        (ulHashTarget & 0x00FF0000) ) {
                            AdvanceHopperGrass++;
                            if ( Quadruplet4th != 
                            (ulHashTarget & 0xFF000000)
                             ) AdvanceHopperGrass++;
                        }
                    }
                }
                AdvanceHopperGrass++;
                pbTarget = pbTarget + AdvanceHopperGrass;
                if (pbTarget > pbTargetMax) return(NULL);
            }
        } else {
            countSTATIC = cbPattern-2-2; 
            ulHashPattern = *(unsigned long *)(pbPattern);
            for (a=0; a < ASIZE; a++) bm_bc[a]=cbPattern;
            for (j=0; j < cbPattern-1; j++) bm_bc[pbPattern[j]]=
                                cbPattern-j-1;
            i=0;
            while (i <= cbTarget-cbPattern) {
                if ( *(unsigned long *)&pbTarget[i] == 
                    ulHashPattern ) {
                    count = countSTATIC;
                    while ( count !=0 && *(char *)
                    (pbPattern+1+3+(countSTATIC-count)) == 
                    *(char *)(&pbTarget[i]+1+3+
                    (countSTATIC-count)) ) count--;
                    if ( count == 0) return(pbTarget+i);
                }
                i= i + bm_bc[(unsigned char)pbTarget[i+cbPattern-1]];
            }
            return(NULL);
        }
    }
}

The tweak (in BMH fragment) which speeds-up significantly the obsolete (already) r.6+++ is this: 

        //countSTATIC = cbPattern-2; //r.6+
        //countSTATIC = cbPattern-2-3;
        //countSTATIC = cbPattern-2-2; // r.6+++ I suppose that the awful degradation 
            // comes from 2bytes more (from either 'if (countSTATIC<0) 
            // countSTATIC=0;' or 'count >0' fixes) which make the 
            // function unfittable in code cache lines?!
        //countSTATIC = cbPattern-2-3;     // r.7- At last no recompared bytes 
                    // in-between chars
        countSTATIC = cbPattern-2-2; // r.7 
        ulHashPattern = *(unsigned long *)(pbPattern);
        //chPTR=(unsigned char *)&chchchch+3;
// Next line fixes the BUG from r.6++: but with awful speed degradation! 
// So the bug is fixed in the definitions by setting 'countSTATIC = cbPattern-2-2;', 
// bug appears only for patterns with lengths of 4, The setback is one unnecessary 
// comparison for 5bytes patterns, stupidly such setback exists (from before) for 
// 4bytes as well.
//if (countSTATIC<0) countSTATIC=0;
    /* Preprocessing */
    for (a=0; a < ASIZE; a++) bm_bc[a]=cbPattern;
    for (j=0; j < cbPattern-1; j++) bm_bc[pbPattern[j]]=cbPattern-j-1;

    /* Searching */
    //lastch=pbPattern[cbPattern-1];
    //firstch=pbPattern[0];
    i=0;
    while (i <= cbTarget-cbPattern) {
       //ch=pbTarget[i+cbPattern-1];
       //ch=pbTarget[i];
          //if ( pbTarget[i] == pbPattern[0] && *(unsigned long *)
    //&pbTarget[i+cbPattern-1-3] == ulHashPattern) // No problema here since 
            // we have 4[+] long pattern here. Overlapping 
            // (1 byte recompared) when length=4, grmbl.
          if ( *(unsigned long *)&pbTarget[i] == ulHashPattern ) // The lesson I learned 
            // from r.7- now applied in r.7: instead of extracting 'ch' 
            // having higher address now the lower address is extracted 
            // first in order (hopefully, the test confirms it) the next 
            // 32bytes (including 'ch') to be cached i.e. to comparison 
            // part is faster.
             {
         count = countSTATIC;
         while ( count !=0 && *(char *)(pbPattern+(countSTATIC-count)+4) == 
        *(char *)(&pbTarget[i]+(countSTATIC-count)+4) ) { // if pattern length 
        // is 4 or 5 we have count=-1 and count=0 respectively i.e. no need of 
        // comparing in-between chars.
               count--;
         }
         if ( count == 0) return(pbTarget+i);
         }
       i= i + bm_bc[(unsigned char)pbTarget[i+cbPattern-1]];
    }
    return(NULL);

In order to see what path I had to traverse to make this tweak, you may see the discussion board (r.7m thread). The tests below show NOT the full boost simply because they average times for all lengths thus losing/diminishing the high speeds times (being 4-3-2 times lesser compared with pattern lengths 2-3-4-5-6). 

D:\_KAZE_new-stuff>strstr_SHORT-SHOWDOWN_Microsoft_v16_Ox.exe
strstr_SHORT-SHOWDOWN, revision 7, written by Kaze.
Input Pattern(up to 19+2000 chars): frustration

Doing Search for Pattern(11bytes) into String(206908949bytes) as-one-line ...
WARNING! The next line works with BMH only for pattern 4[+] long, 
otherwise (for 2 and 3) other searcher takes over!
Railgun_6pp_hits/Railgun_6pp_clocks: 1355/101
Railgun_6pp performance: 2000KB/clock

Doing Search for Pattern(11bytes) into String(206908949bytes) as-one-line ...
WARNING! The next line works with BMH only for pattern 4[+] long, 
otherwise (for 2 and 3) other searcher takes over!
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 1355/91
Railgun_Quadruplet_7 performance: 2220KB/clock

Note: Executing the next two tests 256 times i.e. the search is for 256x8x2 patterns!

Doing Search for 8x2 Patterns into String(206908949bytes) as-one-line ... 
Not-Counting-Hits-Just-Returns-First-One
Found ('an') at 157 position, Railgun_Quadruplet_6pp performance: 0KB/clock
Found ('to') at 853 position, Railgun_Quadruplet_6pp performance: 0KB/clock
Found ('TDK') at -4325408 position, Railgun_Quadruplet_6pp performance: 922KB/clock
Found ('the') at 511 position, Railgun_Quadruplet_6pp performance: 0KB/clock
Found ('fast') at 42381 position, Railgun_Quadruplet_6pp performance: 41KB/clock
Found ('easy') at 30163 position, Railgun_Quadruplet_6pp performance: 29KB/clock
Found ('grmbl') at -4325408 position, Railgun_Quadruplet_6pp performance: 1167KB/clock
Found ('email') at 69587982 position, Railgun_Quadruplet_6pp performance: 1078KB/clock
Found ('pasting') at 134600126 position, Railgun_Quadruplet_6pp performance: 1383KB/clock
Found ('amazing') at 1629806 position, Railgun_Quadruplet_6pp performance: 93KB/clock
Found ('underdog') at 137424498 position, 
            Railgun_Quadruplet_6pp performance: 1698KB/clock
Found ('superdog') at -4325408 position, Railgun_Quadruplet_6pp performance: 1603KB/clock
Found ('participants') at 16060 position, Railgun_Quadruplet_6pp performance: 15KB/clock
Found ('skillessness') at -4325408 position, 
    Railgun_Quadruplet_6pp performance: 1836KB/clock
Found ('I should have known') at 41831880 position, 
    Railgun_Quadruplet_6pp performance: 2403KB/clock
Found ('human consciousness') at 3863 position, 
    Railgun_Quadruplet_6pp performance: 3KB/clock
Railgun_Quadruplet_6pp 8x2 i.e. average performance: 1342KB/clock
ReallyTraversed: 310,477,846,528 bytes

Doing Search for 8x2 Patterns into String(206908949bytes) as-one-line ... 
Not-Counting-Hits-Just-Returns-First-One
Found ('an') at 157 position, Railgun_Quadruplet_7 performance: 0KB/clock
Found ('to') at 853 position, Railgun_Quadruplet_7 performance: 0KB/clock
Found ('TDK') at -4325408 position, Railgun_Quadruplet_7 performance: 990KB/clock
Found ('the') at 511 position, Railgun_Quadruplet_7 performance: 0KB/clock
Found ('fast') at 42381 position, Railgun_Quadruplet_7 performance: 41KB/clock
Found ('easy') at 30163 position, Railgun_Quadruplet_7 performance: 29KB/clock
Found ('grmbl') at -4325408 position, Railgun_Quadruplet_7 performance: 1069KB/clock
Found ('email') at 69587982 position, Railgun_Quadruplet_7 performance: 1078KB/clock
Found ('pasting') at 134600126 position, Railgun_Quadruplet_7 performance: 1383KB/clock
Found ('amazing') at 1629806 position, Railgun_Quadruplet_7 performance: 1591KB/clock
Found ('underdog') at 137424498 position, Railgun_Quadruplet_7 performance: 1698KB/clock
Found ('superdog') at -4325408 position, Railgun_Quadruplet_7 performance: 1422KB/clock
Found ('participants') at 16060 position, Railgun_Quadruplet_7 performance: 15KB/clock
Found ('skillessness') at -4325408 position, 
    Railgun_Quadruplet_7 performance: 2149KB/clock
Found ('I should have known') at 41831880 position, 
    Railgun_Quadruplet_7 performance: 2403KB/clock
Found ('human consciousness') at 3863 position, 
    Railgun_Quadruplet_7 performance: 3KB/clock
Railgun_Quadruplet_7 8x2 i.e. average performance: 1354KB/clock
ReallyTraversed: 310,477,846,528 bytes

Doing Search for 8x2 Patterns into String(206908949bytes) as-one-line ...
Found ('an') 1987797 time(s), BM_HORSPOOL performance: 293KB/clock
Found ('to') 1076629 time(s), BM_HORSPOOL performance: 293KB/clock
Found ('TDK') 0 time(s), BM_HORSPOOL performance: 516KB/clock
Found ('the') 2114180 time(s), BM_HORSPOOL performance: 379KB/clock
Found ('fast') 5945 time(s), BM_HORSPOOL performance: 585KB/clock
Found ('easy') 5191 time(s), BM_HORSPOOL performance: 585KB/clock
Found ('grmbl') 0 time(s), BM_HORSPOOL performance: 759KB/clock
Found ('email') 1 time(s), BM_HORSPOOL performance: 756KB/clock
Found ('pasting') 2 time(s), BM_HORSPOOL performance: 918KB/clock
Found ('amazing') 323 time(s), BM_HORSPOOL performance: 1074KB/clock
Found ('underdog') 4 time(s), BM_HORSPOOL performance: 1069KB/clock
Found ('superdog') 0 time(s), BM_HORSPOOL performance: 1074KB/clock
Found ('participants') 147 time(s), BM_HORSPOOL performance: 1603KB/clock
Found ('skillessness') 0 time(s), BM_HORSPOOL performance: 1422KB/clock
Found ('I should have known') 1 time(s), BM_HORSPOOL performance: 1433KB/clock
Found ('human consciousness') 519 time(s), BM_HORSPOOL performance: 1820KB/clock
BM_HORSPOOL 8x2 i.e. average performance: 666KB/clock

Doing Search for 8x2 Patterns into String(206908949bytes) as-one-line ...
Found ('an') 1987797 time(s), Railgun_6pp performance: 678KB/clock
Found ('to') 1076629 time(s), Railgun_6pp performance: 643KB/clock
Found ('TDK') 0 time(s), Railgun_6pp performance: 1174KB/clock
Found ('the') 2114180 time(s), Railgun_6pp performance: 678KB/clock
Found ('fast') 5945 time(s), Railgun_6pp performance: 918KB/clock
Found ('easy') 5191 time(s), Railgun_6pp performance: 990KB/clock
Found ('grmbl') 0 time(s), Railgun_6pp performance: 1287KB/clock
Found ('email') 1 time(s), Railgun_6pp performance: 1167KB/clock
Found ('pasting') 2 time(s), Railgun_6pp performance: 1603KB/clock
Found ('amazing') 323 time(s), Railgun_6pp performance: 1603KB/clock
Found ('underdog') 4 time(s), Railgun_6pp performance: 1603KB/clock
Found ('superdog') 0 time(s), Railgun_6pp performance: 1820KB/clock
Found ('participants') 147 time(s), Railgun_6pp performance: 2149KB/clock
Found ('skillessness') 0 time(s), Railgun_6pp performance: 2126KB/clock
Found ('I should have known') 1 time(s), Railgun_6pp performance: 2557KB/clock
Found ('human consciousness') 519 time(s), Railgun_6pp performance: 2126KB/clock
Railgun_6pp 8x2 i.e. average performance: 1218KB/clock

Doing Search for 8x2 Patterns into String(206908949bytes) as-one-line ...
Found ('an') 1987797 time(s), Railgun_Quadruplet_7 performance: 643KB/clock
Found ('to') 1076629 time(s), Railgun_Quadruplet_7 performance: 678KB/clock
Found ('TDK') 0 time(s), Railgun_Quadruplet_7 performance: 1074KB/clock
Found ('the') 2114180 time(s), Railgun_Quadruplet_7 performance: 643KB/clock
Found ('fast') 5945 time(s), Railgun_Quadruplet_7 performance: 1074KB/clock
Found ('easy') 5191 time(s), Railgun_Quadruplet_7 performance: 1074KB/clock
Found ('grmbl') 0 time(s), Railgun_Quadruplet_7 performance: 1287KB/clock
Found ('email') 1 time(s), Railgun_Quadruplet_7 performance: 1167KB/clock
Found ('pasting') 2 time(s), Railgun_Quadruplet_7 performance: 1603KB/clock
Found ('amazing') 323 time(s), Railgun_Quadruplet_7 performance: 1603KB/clock
Found ('underdog') 4 time(s), Railgun_Quadruplet_7 performance: 1820KB/clock
Found ('superdog') 0 time(s), Railgun_Quadruplet_7 performance: 1603KB/clock
Found ('participants') 147 time(s), Railgun_Quadruplet_7 performance: 2557KB/clock
Found ('skillessness') 0 time(s), Railgun_Quadruplet_7 performance: 2126KB/clock
Found ('I should have known') 1 time(s), Railgun_Quadruplet_7 performance: 2557KB/clock
Found ('human consciousness') 519 time(s), 
        Railgun_Quadruplet_7 performance: 2557KB/clock
Railgun_Quadruplet_7 8x2 i.e. average performance: 1232KB/clock

^C
D:\_KAZE_new-stuff>

In my opinion, it is one of the seven commandments of speed: do not put the cart before the horse, i.e., for adjacent (32?) memory accesses first extract the byte with lowest address. strstr_SHORT-SHOWDOWN_Microsoft_v16_Ox.exe, revision 7, some quick inputs: 

D:\_KAZE_new-stuff>strstr_SHORT-SHOWDOWN_Microsoft_v16_Ox.exe
strstr_SHORT-SHOWDOWN, revision 7, written by Kaze.
Input Pattern(up to 19+2000 chars): fast

Doing Search for Pattern(4bytes) into String(206908949bytes) as-one-line ...
WARNING! The next line works with BMH only for pattern 4[+] long, 
otherwise (for 2 and 3) other searcher takes over!
Railgun_6pp_hits/Railgun_6pp_clocks: 5945/215
Railgun_6pp performance: 939KB/clock

Doing Search for Pattern(4bytes) into String(206908949bytes) as-one-line ...
WARNING! The next line works with BMH only for pattern 4[+] long, 
otherwise (for 2 and 3) other searcher takes over!
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 5945/193
Railgun_Quadruplet_7 performance: 1046KB/clock

^C

...

Input Pattern(up to 19+2000 chars): from
Railgun_6pp_hits/Railgun_6pp_clocks: 83155/196
Railgun_6pp performance: 1030KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 83155/194
Railgun_Quadruplet_7 performance: 1041KB/clock

Input Pattern(up to 19+2000 chars): rabea
Railgun_6pp_hits/Railgun_6pp_clocks: 0/176
Railgun_6pp performance: 1148KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/162
Railgun_Quadruplet_7 performance: 1247KB/clock

Input Pattern(up to 19+2000 chars): makes
Railgun_6pp_hits/Railgun_6pp_clocks: 9281/172
Railgun_6pp performance: 1174KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 9281/162
Railgun_Quadruplet_7 performance: 1247KB/clock

Input Pattern(up to 19+2000 chars): monkey
Railgun_6pp_hits/Railgun_6pp_clocks: 1691/141
Railgun_6pp performance: 1433KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 1691/139
Railgun_Quadruplet_7 performance: 1453KB/clock

Input Pattern(up to 19+2000 chars): punny
Railgun_6pp_hits/Railgun_6pp_clocks: 0/156
Railgun_6pp performance: 1295KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/155
Railgun_Quadruplet_7 performance: 1303KB/clock

Input Pattern(up to 19+2000 chars): funny
Railgun_6pp_hits/Railgun_6pp_clocks: 179/157
Railgun_6pp performance: 1287KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 179/156
Railgun_Quadruplet_7 performance: 1295KB/clock

Input Pattern(up to 19+2000 chars): ramjet
Railgun_6pp_hits/Railgun_6pp_clocks: 0/152
Railgun_6pp performance: 1329KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/137
Railgun_Quadruplet_7 performance: 1474KB/clock

Input Pattern(up to 19+2000 chars): fallen
Railgun_6pp_hits/Railgun_6pp_clocks: 2578/151
Railgun_6pp performance: 1338KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 2578/138
Railgun_Quadruplet_7 performance: 1464KB/clock

Input Pattern(up to 19+2000 chars): elephant
Railgun_6pp_hits/Railgun_6pp_clocks: 1198/124
Railgun_6pp performance: 1629KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 1198/112
Railgun_Quadruplet_7 performance: 1804KB/clock

Input Pattern(up to 19+2000 chars): layalina
Railgun_6pp_hits/Railgun_6pp_clocks: 0/121
Railgun_6pp performance: 1669KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/110
Railgun_Quadruplet_7 performance: 1836KB/clock

Input Pattern(up to 19+2000 chars): I should have known
Railgun_6pp_hits/Railgun_6pp_clocks: 1/89
Railgun_6pp performance: 2270KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 1/84
Railgun_Quadruplet_7 performance: 2405KB/clock

Input Pattern(up to 19+2000 chars): human consciousness
Railgun_6pp_hits/Railgun_6pp_clocks: 519/80
Railgun_6pp performance: 2525KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 519/75
Railgun_Quadruplet_7 performance: 2694KB/clock

Input Pattern(up to 19+2000 chars): But he's looking right through me
Railgun_6pp_hits/Railgun_6pp_clocks: 0/84
Railgun_6pp performance: 2405KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/76
Railgun_Quadruplet_7 performance: 2658KB/clock

Input Pattern(up to 19+2000 chars): I'm living in an age that calls darkness light
Railgun_6pp_hits/Railgun_6pp_clocks: 0/72
Railgun_6pp performance: 2806KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/67
Railgun_Quadruplet_7 performance: 3015KB/clock

Input Pattern(up to 19+2000 chars): Following the wanderings of a dream - 
a dream that keeps my soul alive
Railgun_6pp_hits/Railgun_6pp_clocks: 0/69
Railgun_6pp performance: 2928KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/63
Railgun_Quadruplet_7 performance: 3207KB/clock

Input Pattern(up to 19+2000 chars): I notice what matters and 
I got nothing to lose but darkness and shadows
Railgun_6pp_hits/Railgun_6pp_clocks: 0/66
Railgun_6pp performance: 3061KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/63
Railgun_Quadruplet_7 performance: 3207KB/clock

Input Pattern(up to 19+2000 chars): Beth Ditto
Railgun_6pp_hits/Railgun_6pp_clocks: 0/118
Railgun_6pp performance: 1712KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/107
Railgun_Quadruplet_7 performance: 1888KB/clock

Input Pattern(up to 19+2000 chars): SR71
Railgun_6pp_hits/Railgun_6pp_clocks: 0/175
Railgun_6pp performance: 1154KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/182
Railgun_Quadruplet_7 performance: 1110KB/clock

Input Pattern(up to 19+2000 chars): Apache
Railgun_6pp_hits/Railgun_6pp_clocks: 1/162
Railgun_6pp performance: 1247KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 1/133
Railgun_Quadruplet_7 performance: 1519KB/clock

Input Pattern(up to 19+2000 chars): Fibonacci
Railgun_6pp_hits/Railgun_6pp_clocks: 0/106
Railgun_6pp performance: 1906KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/98
Railgun_Quadruplet_7 performance: 2061KB/clock

Input Pattern(up to 19+2000 chars): Tesla
Railgun_6pp_hits/Railgun_6pp_clocks: 0/175
Railgun_6pp performance: 1154KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/160
Railgun_Quadruplet_7 performance: 1262KB/clock

Input Pattern(up to 19+2000 chars): Albert
Railgun_6pp_hits/Railgun_6pp_clocks: 932/154
Railgun_6pp performance: 1312KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 932/137
Railgun_Quadruplet_7 performance: 1474KB/clock

Input Pattern(up to 19+2000 chars): Toshiba
Railgun_6pp_hits/Railgun_6pp_clocks: 0/130
Railgun_6pp performance: 1554KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 0/121
Railgun_Quadruplet_7 performance: 1669KB/clock

Input Pattern(up to 19+2000 chars): Orion
Railgun_6pp_hits/Railgun_6pp_clocks: 1/175
Railgun_6pp performance: 1154KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 1/160
Railgun_Quadruplet_7 performance: 1262KB/clock

Input Pattern(up to 19+2000 chars): pharaoh
Railgun_6pp_hits/Railgun_6pp_clocks: 26/129
Railgun_6pp performance: 1566KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 26/122
Railgun_Quadruplet_7 performance: 1656KB/clock

Input Pattern(up to 19+2000 chars): lemon
Railgun_6pp_hits/Railgun_6pp_clocks: 33/178
Railgun_6pp performance: 1135KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 33/161
Railgun_Quadruplet_7 performance: 1255KB/clock

Input Pattern(up to 19+2000 chars): grammar
Railgun_6pp_hits/Railgun_6pp_clocks: 218/123
Railgun_6pp performance: 1642KB/clock
Railgun_Quadruplet_7_hits/Railgun_Quadruplet_7_clocks: 218/117
Railgun_Quadruplet_7 performance: 1727KB/clock

D:\_KAZE_new-stuff>

Grmbl, pattern 'SR71' compared to 'fast' gives me a hint how things are far from 'fastest'.

Points of Interest

The interesting part about tests I have done: 'memcmp' and 'memcpy' when inlined (properly) give much better results. The thing which pop-ups again-and-again: Never take anything for granted. A bug (which doesn't affect the previous results, correct) was crushed, now r.6+++ is ready to go/hit.

As you can see from the C (commentless and tabulated) and ASM sources (see the top of the page for downloading):
The Microsoft 16.00.30319.01 compiled Railgun_Quadruplet_6ppp is 00c6b-00a00+5 = 624 bytes long.
The Quadruplet (where cbTarget<961) fragment loop is 00bc3-00b17+5 = 177 bytes long.
The Boyer-Moore-Horspool (where cbTarget>=961) fragment loop is 00c61-00c20+2 = 67 bytes long.
An interesting question for more experienced coders:
In case of reducing the BMH loop down by 3 bytes (i.e. to 64 bytes), can we obtain some additional/significant boost?

History

  • Revision 6+++ written 2011-Sep-07
  • Revision 7 written 2011-Sep-25

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

 Sanmayce
Other
Bulgaria Bulgaria
Member
A Bulgarian old boy interested in search techniques, nothing special.

Article Top
 
Sign Up to vote   Poor Excellent
Add a reason or comment to your vote: x
Votes of 3 or less require a comment

Comments and Discussions


Discussions posted for the Published version of this article. Posting a message here will take you to the publicly available article in order to continue your conversation in public.
 
Hint: For improved responsiveness ensure Javascript is enabled and choose 'Normal' from the Layout dropdown and hit 'Update'.
You must Sign In to use this message board.
Search this forum  
    Spacing  Noise  Layout  Per page   
First PrevNext
QuestionSuperfast 16-threaded exact searcher: 16 Railguns in action and more [modified]memberSanmayce9 Feb '13 - 6:16 
QuestionFastest 32bit hash function in CmemberSanmayce29 Sep '12 - 7:25 
QuestionMy latest Windows benchmark packagememberSanmayce20 Mar '12 - 7:26 
QuestionHorspool vs BNDMmemberMischa Sandberg4 Mar '12 - 18:06 
AnswerRe: Horspool vs BNDMmemberSanmayce5 Mar '12 - 5:35 
GeneralRe: UnixmemberMischa Sandberg5 Mar '12 - 14:40 
AnswerRe: Horspool vs BNDMmemberSanmayce7 Mar '12 - 3:23 
AnswerBNDM_64 vs 'Tridentx64'memberSanmayce7 Mar '12 - 5:05 
AnswerThe best practical on-line resource on String MatchingmemberSanmayce7 Mar '12 - 5:41 
QuestionRailgun_Doublet_x64: the fastest mini-memmem known to mememberSanmayce26 Feb '12 - 4:47 
AnswerRe: Railgun_Doublet_x64: the fastest mini-memmem known to mememberMischa Sandberg4 Mar '12 - 17:52 
GeneralRe: Railgun_Doublet_x64: the fastest mini-memmem known to mememberSanmayce5 Mar '12 - 5:02 
QuestionDecision threshold for switching to 2byte horspoolmemberMischa Sandberg20 Feb '12 - 19:38 
AnswerRe: Decision threshold for switching to 2byte horspoolmemberSanmayce21 Feb '12 - 5:30 
QuestionTry this test ...memberMischa Sandberg17 Feb '12 - 10:14 
AnswerRe: Try this test ...memberSanmayce18 Feb '12 - 6:07 
GeneralRe: Try this test ...memberMischa Sandberg19 Feb '12 - 12:43 
QuestionHasherezadememberMischa Sandberg1 Feb '12 - 10:45 
AnswerRe: HasherezadememberMischa Sandberg1 Feb '12 - 11:36 
AnswerRe: HasherezadememberSanmayce3 Feb '12 - 5:13 
AnswerBNDM: more than a Top Gun [modified]memberSanmayce7 Feb '12 - 6:25 
Answer'Gulliver' with Order 3 presence checkmemberSanmayce9 Feb '12 - 1:20 
AnswerGNU's strstr strikes backmemberSanmayce16 Feb '12 - 1:53 
GeneralRe: GNU's strstr strikes back [modified]memberMischa Sandberg16 Feb '12 - 11:39 
GeneralRailgun_Quadruplet_r8Triplet fastest for 3bytes patternsmemberSanmayce18 Feb '12 - 4:10 
GeneralRe: Railgun_Quadruplet_r8Triplet fastest for 3bytes patternsmemberMischa Sandberg21 Feb '12 - 8:47 
GeneralRe: Railgun_Quadruplet_r8Triplet fastest for 3bytes patternsmemberSanmayce23 Feb '12 - 6:51 
GeneralRe: Railgun_Quadruplet_r8Triplet fastest for 3bytes patternsmemberMischa Sandberg23 Feb '12 - 7:37 
GeneralRe: Railgun_Quadruplet_r8Triplet fastest for 3bytes patternsmemberSanmayce23 Feb '12 - 8:47 
GeneralRe: Railgun_Quadruplet_r8Triplet fastest for 3bytes patternsmemberMischa Sandberg23 Feb '12 - 9:56 
AnswerHomo sapiens chromosome 1 under 'Hasherezade' firememberSanmayce21 Feb '12 - 4:25 
Answer32bit vs 64bit: my first knock-downmemberSanmayce24 Feb '12 - 7:24 
GeneralRe: 32bit vs 64bit: my first knock-downmemberMischa Sandberg24 Feb '12 - 11:31 
GeneralRe: 32bit vs 64bit: my first knock-downmemberSanmayce26 Feb '12 - 4:36 
AnswerTrident_x64 SHINES i.e. outspeeds all hitters for short 16-chars patterns and long stringsmemberSanmayce26 Feb '12 - 4:43 
Answer'Trident' vs BNDM_64 vs 'Elsiane' vs 'Hasherezade'memberSanmayce1 Mar '12 - 6:05 
GeneralMy vote of 2memberRick York1 Feb '12 - 6:26 
GeneralRe: My vote of 2memberSanmayce1 Feb '12 - 6:46 
QuestionStatistical analysis of Railgun points to some improvementsmemberMischa Sandberg25 Jan '12 - 14:28 
AnswerRe: Statistical analysis of Railgun points to some improvementsmemberSanmayce25 Jan '12 - 22:46 
GeneralRe: Statistical analysis of Railgun points to some improvementsmemberMischa Sandberg26 Jan '12 - 17:25 
GeneralRe: Statistical analysis of Railgun points to some improvementsmemberSanmayce28 Jan '12 - 7:23 
GeneralRe: Statistical analysis of Railgun points to some improvementsmemberMischa Sandberg29 Jan '12 - 19:54 
GeneralRe: Statistical analysis of Railgun points to some improvementsmemberSanmayce30 Jan '12 - 6:34 
GeneralMy vote of 2memberJonathan [Darka]25 Jan '12 - 3:34 
GeneralRe: My vote of 2memberSanmayce25 Jan '12 - 22:19 
GeneralRe: My vote of 2memberJonathan [Darka]26 Jan '12 - 0:07 
GeneralRe: My vote of 2memberRick York1 Feb '12 - 6:19 
GeneralRe: My vote of 2memberJonathan [Darka]1 Feb '12 - 23:45 
GeneralMy vote of 5memberJF201524 Jan '12 - 18:32 
Last Visit: 31 Dec '99 - 18:00     Last Update: 25 May '13 - 14:08Refresh12 Next »

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

About Article
Tuned function for searching a needle in a haystack
Type Article
Licence CPOL
Version  13
First Posted 9 Sep 2011
Views 40,471
Downloads 650
Bookmarked 16 times

, +
Top News

Old Japanese Man Creates Amazing Art Using Excel (Wait, Excel?)

Get the Insider News free each morning.
Related Videos
Introducing Javascript Functions
JavaScript: Nesting and Invoking Functions Part 2
String Search Using Generated Search Logic
Case-Insensitive String Search
Strings Obfuscation System
Win32 Listview Class
The Impossibly Fast C++ Delegates
How to get the BcdOSLoaderBoolean_KernelDebuggerEnabled value of BcdOSLoaderElementTypes
API Hooking with MS Detours
MultiCopier Software
Secure Function Pointer and Callbacks in Windows Programming
Finding Printers in a Network
Mathemathics Framework
Keyboard Spy: implementation and counter measures
a File Switch Tabbar for Source Insight
Member Function Pointers and the Fastest Possible C++ Delegates
Hiding a text file in a bmp file
An Adventure: How to implement a Firewall-Hook Driver?
How to write a Super compact Super Fast C++ Dll for Visual Basic
Lightweight Generic C++ Callbacks (or, Yet Another Delegate Implementation)
Driver to hide files in Linux OS
Fast C++ Delegate: Boost.Function 'drop-in' replacement and multicast
Permalink | Advertise | Privacy | Mobile
Web04 | 2.6.130523.1 | Last Updated 20 Jan 2012
Article Copyright 2011 by Sanmayce
Everything else Copyright © CodeProject, 1999-2013
Terms of Use
Layout: fixed | fluid