自定義memstr（strstr）速度優化

Question

我正在編寫一個例程以在嵌入式（ARM Cortex M0 @ 16MHz）應用程序中的指定內存塊中查找字符串，並且想知道爲什麼我編寫的兩個不同版本運行在不同的速度。

char* memstr(char* mem, uint32_t n, char* str) { 

    if((str[0] == '\0') || (n == 0)) return NULL; 

    uint32_t i = 0; 
    char* max_mem; 

    max_mem = mem + n; 

    while(mem < max_mem) { 
     if(*mem != str[i]) { 
      mem -= i; 
      i = 0; 
     } else { 
      if(str[i+1] == '\0') return mem - i; 
      i++; 
     } 
     mem++; 
    } 

    return NULL; 
} 


char* memstr2(char* mem, uint32_t n, char* str) { 

    if((str[0] == '\0') || (n == 0)) return NULL; 

    uint32_t c = 0; 
    uint32_t i = 0; 

    while(c < n) { 
     if(mem[c] != str[i]) { 
      c -= i; 
      i = 0; 
     } else { 
      i++; 
      if(str[i] == '\0') return &mem[c - i + 1]; 
     } 
     c++; 
    } 

    return NULL; 
} 

當在20和200字節的內存之間找到7個字符的字符串時，memstr始終比memstr2快1us。例如在110個字節中找到7個字符的字符串，memstr需要106us，memstr2需要107us。 1us可能聽起來並不是什麼大不了的事情，但在嵌入式應用程序中，每個tick都有問題，這是一個缺點。

一種獎勵問題：這也促使我編寫自己比strstr更快的strstr（例如，在207字符串中查找7個字符的字符串需要my_strstr 236us和strstr 274us）。這有什麼不對，因爲strstr必須相當優化？

char* my_strstr(char* str1, char* str2) { 
    uint32_t i = 0; 

    if(str2[0] == '\0') return NULL; 

    while(*str1 != '\0') { 
     if(*str1 != str2[i]) { 
      str1 -= i; 
      i = 0; 
     } else { 
      i++; 
      if(str2[i] == '\0') return (str1 - i - 1); 
     } 
     str1++; 
    } 

    return NULL; 
} 

Answer 1

在我看來，該差異是由於這樣的事實：在你的第二個版本取消引用指針（return &mem[c - i - 1];）當您從功能上可導致訪問在內存中是昂貴的，是返回在你的第一個功能中不可能發生的事情（mem - i）。
但唯一確定的方法是查看每個案例正在創建的組件。
我不認爲這是關於C，但有關編譯器和平臺

Answer 2

首先，如果搜索開始的兩個相等的字符的字符串兩種功能不起作用：如果您搜索xxabcde和字符串包含xxxabcde那麼當你注意到一個xxabcde與第三個x不匹配時，你已經跳過了兩個x並且不匹配該字符串。

您也不檢查是否搜索空字符串，在這種情況下，您的代碼會產生未定義的行爲。

您將內存與內存進行比較。但是，將內存與單個字符進行比較，你可以做很多工作。如果您搜索「abcde」，首先您必須找到字母a。所以我會先檢查一個空字符串，然後閱讀第一個字符。然後首先檢查該字符。

char first = str2 [0]; 
if (first == '\0') return mem; 

for (; mem < maxmem; ++mem) if (*mem == first) { 
    ... check whether there is a match 
} 

您應該檢查您的數據。如果您期望搜索字符串提前出現，您會編寫不同的代碼，而如果您期望它通常不在那裏。