KMP vs. Naive substring search algorithms

[darnoceloc]

Why would a brute force/naive algorithm outperform a KMP substring search algorithm?
Are there known specific/prototypical scenarios, (i.e., the pattern substring contains no suffix which is also a prefix) in which this is the case?
See coded example via link below.

https://github.com/darnoceloc/Algorithms/blob/master/KMP_Algorithm.cpp

[poteto]

on a web compiler my modifications makes them have the same result.

The big difference is that heap memory allocation takes less than 1~ish milliseconds, which is gigantic, while stack memory can be allocated ~1000x times faster.

My results say that they are pretty close to each other, so close it is negligible (with optimizations). Sometimes it gives the exact same result.

But I never saw KMP go lower than naive, and at most I saw KMP be 2x slower but that improvement is negligible considering the measurement. The main reason is probably the fact that KMP is using more memory and that is all it takes to have a memory bound problem. There is also branch prediction, compiler optimizations, and linear memory reading too, but I didn't really dig deeper into it.

On -O3, the time on naive is zero.

#include<iostream>
//#include <string_view>
#include <boost/utility/string_ref.hpp>

//or std::string_view, std::experimental::string_view
//note boost string_ref does have tiny differences with std::string_view, 
//but I want to believe that it is mostly forward compatible with string_view.
typedef boost::string_ref sview;

//note that there is also std::chrono::high_resolution_clock, this is an afterthought after already writing this...

#ifdef _WIN32
#include <Windows.h>

typedef LARGE_INTEGER TIMER_U;
typedef double TIME_RESULT_U;


TIMER_U time()
{
  LARGE_INTEGER counter;
  ::QueryPerformanceCounter(&counter);
  return counter;
}

//in milliseconds
TIME_RESULT_U time_result(TIMER_U first, TIMER_U last)
{
    LARGE_INTEGER frequency;
    ::QueryPerformanceFrequency(&frequency);
    return TIME_RESULT_U((last.QuadPart - first.QuadPart) * 1000) / TIME_RESULT_U(frequency.QuadPart);
}

#else
#include <time.h>

typedef clock_t TIMER_U;
typedef double TIME_RESULT_U;

TIMER_U time(){return clock();}

//in milliseconds
TIME_RESULT_U time_result(TIMER_U first, TIMER_U last)
{
    return (TIME_RESULT_U)(last - first) / TIME_RESULT_U(CLOCKS_PER_SEC/1000);
}

#endif



using namespace std;

//Simple (brute force/naive) match algorithm
bool has_substring(sview input_string, sview pattern){
    int j=0;
    int i=0;
    int k = 0;
    while(i<static_cast<int>(input_string.length()) && j<static_cast<int>(pattern.length())){
        if(input_string[i] == pattern[j]){
        i++;
        j++;}
        else{j=0; k++ ; i=k;}
    }
    if(j==static_cast<int>(pattern.length())){
        return true;
    }
    return false;
}

//Function to compute temporary integer array for prefix/suffix matches
///note I could probably quickly replace the buffer with a std::array, but too late.
void temp_array(sview pattern, int* buffer, int buf_size){
    int index = 0;
    for(int i=1; i<buf_size;){
        if(pattern[i] == pattern[index]){
            buffer[i]= buffer[index]+1;
            index++;
            i++;
        }
        else{
            if(index != 0){
            index = buffer[index-1];}
            else{buffer[i]=0;
            i++;}
        }
    }
}

//Function to implement KMP Algorithm for pattern match
bool KMP_alg(sview input_string, sview pattern, int* buffer, int buf_size){
    //vector<int> tmp_kmp = 
    temp_array(pattern, buffer, buf_size);
    int i=0;
    int j=0;
    while(i < static_cast<int>(input_string.length()) && j < static_cast<int>(pattern.length())){
        if(input_string[i] == pattern[j]){
            i++;
            j++;}
        else{
            if(j!=0){
            j = buffer[j-1];}
            else{
            i++;}
        }
    }
    if(j == static_cast<int>(pattern.length())){
        //cout << "Match begins at char. " << i-pattern.length()+1 << " of input" << endl;
        //cout << "Match ends at char. " << i << " of input" << endl;
        return true;}
    else {
        //cout <<"No match found" << endl;
        return false;}
}

int main(){
    const char *input = "darnoc76elocbergdarnoc78darnoc77";
    char pattern[] = "darnoc77";
    
    TIMER_U t1 = time();
    int buffer[sizeof(pattern)-1];    //sizeof is in bytes, luckily chars are only 1 byte.
    int buf_size = sizeof(pattern)-1;
    bool result = KMP_alg(input, pattern, buffer, buf_size);
    TIMER_U t2 = time();
    
    cout << "KMP algorithm took " << time_result(t1,t2) << " ms." << endl;
    
    t1 = time();
    bool check = has_substring(input, pattern);
    t2 = time();
    
    cout << "Naive algorithm took "  << time_result(t1,t2) << " ms." << endl;
    
    cout << result << endl;
    cout << check << endl;
    return 0;
}

edit for using clock_t instead of int(should be indifferent?), and fixed the win32 code to print milliseconds instead of nanoseconds or whatever.

[jonnin]

have you tried to tune the kmp any yet? It seems like it has some potential for optimizations.