strstr challenge

create the fastest C strstr function implementation.
Rules:
1.Must be portable between different architectures(ARM,x86/x86-64,MIPS)
2.Must handle strings of any length that C standard library strstr can handle.
3.Cannot rely on undefined behavior or platform specific code.
strstr reference: http://www.cplusplus.com/reference/cstring/strstr/

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
O(n)

how the fuck do you scan a string faster than O(N)

>>3
Can't do that without relying on platform specific behavior. Casting to a larger integer type is one way, but it is dependent on the width of the larger integer, and char on that platform.

>>4
those are all constant time improvements, they're still O(N)

>>5
I dont think you understand computational complexity.

>>6
I don't think you do. Casting from a pointer to char to a pointer to int is still yielding an operation whose time complexity is directly proportional the the input N, that is to say asymptotic to O(N)

>>7
I dont think you understand my email field.

>>8
oh wow egin gro lol
>egin
>mfw u eginned me
>truly egin

>>9
The only e/g/in one here is you.

dubs

Store strings as ropes. ``Le pseudocode'' implementation.
data Meta = { count :: [256]Int, len :: Int }
data String = Piece {data :: []Char, meta:: Meta} | Cons {left :: Ptr String, right :: Ptr String, meta :: Meta}

Unsurprisingly the default library strstr in assembly is fastest
http://pastebin.com/zy5T3EHC
AMD Athlon II x2 240(2812mhz) results:
strstr:NATURAM EXPELLERE: found in 95590036 cycles
subseq-memchr/memcmp:NATURAM EXPELLERE: found in 407098643 cycles
gulliver:NATURAM EXPELLERE: found in 151668168 cycles
bndm32:NATURAM EXPELLERE: found in 189011120 cycles
bndm128:NATURAM EXPELLERE: found in 211098657 cycles
bergstrstr:NATURAM EXPELLERE: found in 740284100 cycles
blakestrstr:NATURAM EXPELLERE: found in 9768790570 cycles
BMH algo:NATURAM EXPELLERE: found in 200122114 cycles
BM algo:NATURAM EXPELLERE: found in 305910734 cycles
bitap algo:NATURAM EXPELLERE: found in 1822449601 cycles
subseq2-fvmemchr/memcmp:NATURAM EXPELLERE: found in 329496931 cycles
subseq3-skiplist:NATURAM EXPELLERE: found in 294845552 cycles(iters:0)
naivestr:NATURAM EXPELLERE: found in 1028853208 cycles
VCRstrstr.c:NATURAM EXPELLERE: found in 2190247531 cycles
scanstr:NATURAM EXPELLERE: found in 1806460840 cycles
Hasherezade:NATURAM EXPELLERE: found in 282196856 cycles

Fastest versions on x86/x86-64 use the SSE 4.2 PCMPISTRI instruction.

http://www.strchr.com/strcmp_and_strlen_using_sse_4.2

>>14
I cannot benchmark that. My CPU doesn't have  SSE 4.2.

>>14-15
Its against the rules to use nonportable code.

>>16
It should be against the rules to force people to constrain themselves to portable versions that run slow. It's because of people like you that most of today's software runs like shit.

>>17
That's the compiler's job. It's not >>16's fault that most of today's compilers are shit. If you want fast non-portable code get out an instruction timing table and write it in assembly.

non portable code should be allowed, but there shouldn't be a winner.

>>18
That's the compiler's job.
Use luajit.

write scheme jit.

Write a script that checks these dubs.

if {
$dubs == 'yes';
check(them)
};

>>22
I did that some months ago. Am I supposed to run it on Amazon's EC2 now? Because I could totally do that.


char * strstr(char * str1, char * str2){
     while (str1 != "\0"){
           int i=0;
           char * c2 = str2;
           while (str1[i]==c2){
                 c2++;
                 i++;
                 if (c2 == "\0"){
                    return str1;      
                 }
           }
           str1++;     
     }
     return NULL;
}

>>25
http://pastebin.com/bi98Rczj v1.22 results
strstr:NATURAM EXPELLERE: found in 95082151 cycles
subseq-memchr/memcmp:NATURAM EXPELLERE: found in 404754234 cycles
gulliver:NATURAM EXPELLERE: found in 151067325 cycles
bndm32:NATURAM EXPELLERE: found in 188375505 cycles
bndm128:NATURAM EXPELLERE: found in 208229229 cycles
bergstrstr:NATURAM EXPELLERE: found in 740798798 cycles
blakestrstr:NATURAM EXPELLERE: found in 9311335647 cycles
BMH algo:NATURAM EXPELLERE: found in 199111346 cycles
BM algo:NATURAM EXPELLERE: found in 303730580 cycles
bitap algo:NATURAM EXPELLERE: found in 1822850743 cycles
subseq2-fvmemchr/memcmp:NATURAM EXPELLERE: found in 326454376 cycles
subseq3-skiplist:NATURAM EXPELLERE: found in 293218741 cycles(iters:0)
naivestr:NATURAM EXPELLERE: found in 1878574347 cycles
VCRstrstr.c:NATURAM EXPELLERE: found in 2174908637 cycles
scanstr:NATURAM EXPELLERE: found in 1797771263 cycles
Hasherezade:NATURAM EXPELLERE: found in 279621715 cycles
strstr25:NATURAM EXPELLERE: found in 1271949425 cycles   <--this is >>25

>>25 is naïve and wrong.

>>27
I know, that why i change the code for benchmarks so they work.
See the code in >>26 function strstr25 and compare it to >>25 strstr

can I write mine in lisp?

>>28
You know you can accidentally introduce performance-sapping mistakes that way?

Holy fucking shit FrozenVoid is back.

>>25
while (str1 != "\0")

oh shit nigger
what are you doing

With respect to size of data to search through yes, you won't find better algorithmic time complexity than O(n). That doesn't mean you can't make genuine speed improvements.

It's high-time somebody wrote a C implementation of the Knuth-Morris-Pratt algorithm and got this over and done with, that's all the author wanted.


char * Super_Fast_String_Search ( char * string1 , char * string2 ) {
long size = strlen ( string1 ) ;
char * end_of_string = string1 + size ;
long size2 = strlen ( string2 ) ;
long skip_chars = size2 - 1 ;
long i ;
char start_char = string2 [0] ;
char skipchars[256] = {0};
char * first;
char * last;
  for( i = 0 ; i < size2 ; i++ ) {
        skipchars[string2[i]]=1;
        };
  while ( string1 < end_of_string ) {
  first = memchr ( string1 , start_char , size ) ;
        if ( !first ) return NULL;
  last = first + skip_chars;
        if( !skipchars[*last] ){
        string1 += skip_chars;
        size -= skip_chars;
         continue ;
        };
        if ( !memcmp ( first , string2 , size2) ) {
         return  first;
        ;}
   string1++ ;
  size-- ;
        }
}

update with 3 new algorithms http://pastebin.com/zbZKVCY7
AMD Athlon II x2 240(2812mhz) results:
strstr:NATURAM EXPELLERE: found in 93770321 cycles
subseq-memchr/memcmp:NATURAM EXPELLERE: found in 404744564 cycles
gulliver:NATURAM EXPELLERE: found in 151661916 cycles
bndm32:NATURAM EXPELLERE: found in 194297905 cycles
bndm128:NATURAM EXPELLERE: found in 237864800 cycles
bergstrstr:NATURAM EXPELLERE: found in 742368932 cycles
blakestrstr:NATURAM EXPELLERE: found in 9658897885 cycles
BMH algo:NATURAM EXPELLERE: found in 199778772 cycles
BM algo:NATURAM EXPELLERE: found in 303879126 cycles
bitap algo:NATURAM EXPELLERE: found in 1820884930 cycles
subseq2-fvmemchr/memcmp:NATURAM EXPELLERE: found in 327922174 cycles
subseq3-skiplist:NATURAM EXPELLERE: found in 294126707 cycles
naivestr:NATURAM EXPELLERE: found in 1758646225 cycles
VCRstrstr.c:NATURAM EXPELLERE: found in 2167614075 cycles
scanstr:NATURAM EXPELLERE: found in 1799854110 cycles
Hasherezade:NATURAM EXPELLERE: found in 279051410 cycles
strstr25:NATURAM EXPELLERE: found in 1274442951 cycles
volnitsky:NATURAM EXPELLERE: found in 173423516 cycles
kmp_search:NATURAM EXPELLERE: found in 4321391607 cycles
Super_Fast_String_Search:NATURAM EXPELLERE: found in 75488330113 cycles (ironically the slowest)


#include <string.h>

string main(void) {
    string wat = "egin";
    return wat;
}

>>33
Consider them checked.