strstr szybciej niż algorytmy?

Mam plik, który ma 21056 bajtów.

Napisałem program w języku C, który wczytuje cały plik do bufora, a następnie używa wielu algorytmów wyszukiwania, aby przeszukać plik w poszukiwaniu tokena, który ma 82 znaki.

Użyłem wszystkich implementacji algorytmów ze strony "Exact String Matching Algorithms". Używałem: KMP, BM, TBM i Horspool. A potem użyłem strstr i porównałem każdy z nich.

Zastanawiam się, czy za każdym razem strstr przewyższa wszystkie inne algorytmy. Jedynym, który jest szybszy czasami jest BM.

Nie powinno być najwolniej?

Oto Mój kod benchmarkingowy z przykładem benchmarkingu BM: 

double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}

before = get_time();
BM(token, strlen(token), buffer, len);
after = get_time();
printf("Time: %f\n\n", after - before);

Mógłby mi ktoś wyjaśnić dlaczego strstr przewyższa inne algorytmy wyszukiwania? W razie potrzeby wyślę więcej kodu.

Author: Konrad Rudolph, 2011-09-28
Source

4 answers

Dlaczego uważasz, że {[0] } powinny być wolniejsze niż wszystkie inne? Czy wiesz jakiego algorytmu strstr używa? Myślę, że jest całkiem prawdopodobne, że strstr używa dopracowanego, specyficznego dla procesora, kodowanego asemblerem algorytmu typu KMP lub lepszego. W takim przypadku nie masz szans na wykonanie tego w C dla tak małych benchmarków.

(powodem, dla którego myślę, że jest to prawdopodobne, jest to, że programiści uwielbiają implementować takie rzeczy.)

 27
Author: TonyK,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-09-29 11:07:04

Horspool, KMP i inni są optymalne pod względem minimalizacji liczby porównań bajtów.

Jednak to nie jest wąskie gardło w nowoczesnym procesorze. Na procesorze x86/64 Twój ciąg jest ładowany do L1 cache w kawałkach Cache-line-width (zazwyczaj 64 bajty). Bez względu na to, jak sprytny jest Twój algorytm, o ile nie daje Ci kroków, które są większe, nic nie zyskujesz; a bardziej skomplikowany kod Horspool jest (przynajmniej jedno wyszukiwanie tabeli) nie może konkurować.

Ponadto, utknąłeś z ograniczeniem " C " ciągu null-termination: gdzieś kod musi zbadać każdy bajt.

strstr() oczekuje się, że będzie optymalny dla szerokiego zakresu przypadków; np. szukanie małych ciągów, takich jak "\r\n" w krótkim łańcuchu, a także znacznie dłuższych, w których jakiś mądrzejszy algorytm może mieć nadzieję. Podstawowa pętla strchr / memcmp jest dość trudna do pokonania w całym zakresie prawdopodobnych wejść.

Prawie wszystkie kompatybilne z x86 procesory od 2003 roku obsługują SSE2. Jeśli zdemontowałeś strlen()/x86 dla glibc, być może zauważyłeś, że używa on pewnych operacji SSE2 PCMPEQ i MOVMASK do wyszukiwania terminatora null po 16 bajtów na raz. Rozwiązanie jest tak wydajne, że bije oczywistą super-prostą pętlę, na coś dłuższego niż pusty ciąg.

Wziąłem ten pomysł i wymyśliłem strstr(), który bije strstr() glibc dla wszystkich przypadków większych niż 1 bajt - - - gdzie względna różnica jest dość wiele wątpliwości. Jeśli jesteś zainteresowany, Sprawdź:

  • Konwergencja SSE2 i strstr()

  • Lepszy strstr() bez kodu ASM

    Jeśli chcesz zobaczyć rozwiązanie inne niż SSE2, które dominuje strstr() dla ciągów docelowych o długości większej niż 15 bajtów, Sprawdź:

    , który używa porównań wielobajtowych zamiast strchr(), aby znaleźć punkt, w którym można wykonać memcmp.

BTW pewnie już się domyśliłeś, że x86 REP SCASB / REP CMPSB Ops spadają na tyłek na coś dłuższego niż 32 bajty i nie są dużo lepsze dla krótszych ciągów. Szkoda, że Intel nie poświęcił na to trochę więcej uwagi, niż na dodanie ops "string" SSE4. 2.

Dla strun wystarczająco dużych, aby mieć znaczenie, moje testy perf pokazują, że BNDM jest lepszy niż Horspool, w całej rozciągłości. Bndm jest bardziej tolerancyjny dla "patologicznych" przypadków, takich jak cele, które mocno powtarzają ostatni bajt wzorca. BNDM może również korzystać z rejestrów SSE2 (128bit) w sposób, który konkuruje z rejestrami 32-bitowymi pod względem wydajności i kosztów rozruchu. Kod źródłowy tutaj .

 14
Author: Mischa,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-10-03 15:26:47

Nie widząc Twojego kodu, trudno powiedzieć dokładnie. strstr jest mocno zoptymalizowany i zazwyczaj napisany w języku asemblera. Robi takie rzeczy, jak odczytywanie danych 4 bajty na raz i porównywanie ich (bit-twidling, jeśli to konieczne, jeśli wyrównanie nie jest właściwe) w celu zminimalizowania opóźnienia pamięci. Może również skorzystać z rzeczy takich jak SSE, aby załadować 16 bajtów na raz. Jeśli twój kod ładuje tylko jeden bajt na raz, prawdopodobnie zostanie zabity przez opóźnienie pamięci.

Użyj debuggera i krok poprzez demontaż strstr -- prawdopodobnie znajdziesz tam kilka ciekawych rzeczy.

 3
Author: Adam Rosenfield,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-09-28 17:21:56

Wyobraź sobie, że chcesz coś wyczyścić. Możesz po prostu wyczyścić to sam, lub możesz wynająć dziesięciu profesjonalnych sprzątaczy, aby to wyczyścić. Jeśli sprzątanie to budynek biurowy, to drugie rozwiązanie byłoby preferowane. Jeśli zadanie czyszczenia było jedno okno, to pierwsze byłoby lepsze.

Nigdy nie otrzymasz żadnej rekompensaty za czas spędzony na przygotowywaniu się do pracy efektywnie, ponieważ praca nie trwa zbyt długo.

 2
Author: David Schwartz,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-09-28 17:19:39