оптимизация скорости памяти strstr (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; 
} 

memstr последовательно 1us быстрее, чем при нахождении memstr2 строку 7 символов в диапазоне от 20 до 200 байт памяти. Например, найдя 7-значную строку в 110 байтах, memstr принимает 106us, а memstr2 принимает значение 107us. 1us может показаться неважным, но во встроенном приложении, где каждый тик имеет значение, это недостаток.

Вид вопроса о бонусе: Это также побудило меня написать мою собственную strstr, которая быстрее, чем фондовый strstr (например, поиск 7-символьной строки в 207-символьной строке принимает 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 то когда вы заметите, что a из 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 
} 

Необходимо проверить свои данные. Вы должны написать другой код, если вы ожидаете, что строка поиска появится раньше, если вы ожидаете, что она вообще не будет там.