memcmp, ale trzeba porównać blok o ustalonej wartości

Question

Potrzebuję porównać blok pamięci do stałej wartości w C. Czy mogę to zrobić z memcmp? Coś jak:

memcmp (starting_address, fixed_value, num_byte)

muszę fixed_value być ustalona wartość nie adres początkowy bloku.

1. Zapisywanie stałej wartości do całego bloku pamięci tymczasowej nie jest opcją, ponieważ mam ograniczoną przestrzeń.
2. Używanie pętli do zapisywania i sprawdzania pamięci jeden po drugim nie jest opcją, ponieważ jest bardzo powolne.

Jeśli nie jest możliwe, czy ktoś może mi powiedzieć rozwiązanie, które jest tak szybkie (lub szybsze) niż memcmp?

Dzięki,

EDIT: załóżmy, że mam 5GB pamięci, który przechowuje 0 tych. Próbuję się upewnić, że wszystkie są zerowe. Czy można bezpiecznie sprawdzić pierwszy bajt bloku, wykonaj następujące czynności:

memcmp (adres początkowy, adres_początkowy + ONE_BYTE, FIVE_GB); ?

EDIT: To dlatego muszę korzystać memcmp a nie zdefiniowane przez użytkownika pętli:

Kod ten wziął 546 zegar tyka uruchomić:

memset(0x80000000 , 0x1 , 0x10000000); 
memset(0x90000000 , 0x1 , 0x10000000); 
memcmp(0x80000000 , 0x90000000 , 0x10000000); 

vs tego, które miało 7669 zegar tyka:

unsigned int i; 
int flag = 0; 
int *p = 0x80000000; 
int *q = 0x90000000; 
while(p < 0x90000000) 
{ 
    if(*p++ != *q++) 
    { 
     flag = 1; 
    } 
} 

Answer 1

właśnie testowane tej pętli na moim Macu i bije memcmp:

uint64_t *p = (uint64_t *)buffer1; 
uint64_t compare; 
memset(&compare, 1, sizeof compare); 
for (i = 0; i < length/sizeof compare; i++) 
{ 
    if (p[i] != compare) 
     break; 
} 

Kompletny przykładowy kod:

#include <stdio.h> 
#include <string.h> 
#include <sys/resource.h> 
#include <time.h> 
#include <stdlib.h> 
#include <stdint.h> 

// from: http://www.gnu.org/software/libc/manual/html_node/Elapsed-Time.html 
void timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y) 
{ 
    /* Perform the carry for the later subtraction by updating y. */ 
    if (x->tv_usec < y->tv_usec) 
    { 
     int nsec = (y->tv_usec - x->tv_usec)/1000000 + 1; 
     y->tv_usec -= 1000000 * nsec; 
     y->tv_sec += nsec; 
    } 

    if (x->tv_usec - y->tv_usec > 1000000) 
    { 
     int nsec = (x->tv_usec - y->tv_usec)/1000000; 
     y->tv_usec += 1000000 * nsec; 
     y->tv_sec -= nsec; 
    } 

    /* Compute the time remaining to wait. tv_usec is certainly positive. */ 
    result->tv_sec = x->tv_sec - y->tv_sec; 
    result->tv_usec = x->tv_usec - y->tv_usec; 
} 

int main(int argc, char **argv) 
{ 
    struct rusage before; 
    struct rusage after; 
    struct timeval diff; 
    size_t i; 

    size_t length = strtoull(argv[1], NULL, 0); 

    char *buffer1 = malloc(length); 
    char *buffer2 = malloc(length); 

    printf("filling..."); 
    fflush(stdout); 
    memset(buffer1, 1, length); 
    memset(buffer2, 1, length); 
    printf(" done\n"); 

    getrusage(RUSAGE_SELF, &before); 
    uint64_t *p = (uint64_t *)buffer1; 
    uint64_t compare; 
    memset(&compare, 1, sizeof compare); 
    for (i = 0; i < length/sizeof compare; i++) 
    { 
     if (p[i] != compare) 
      break; 
    } 
    if (i == length/sizeof compare) 
     i = 0; 
    getrusage(RUSAGE_SELF, &after); 

    printf("\nloop (returned %zu):\n", i); 
    timeval_subtract(&diff, &after.ru_utime, &before.ru_utime); 
    printf("User: %ld.%06d s\n", diff.tv_sec, diff.tv_usec); 

    timeval_subtract(&diff, &after.ru_stime, &before.ru_stime); 
    printf("System: %ld.%06d s\n", diff.tv_sec, diff.tv_usec); 

    getrusage(RUSAGE_SELF, &before); 
    i = memcmp(buffer1, buffer2, length); 
    getrusage(RUSAGE_SELF, &after); 

    printf("\nmemcmp (returned %zu):\n", i); 
    timeval_subtract(&diff, &after.ru_utime, &before.ru_utime); 
    printf("User: %ld.%06d s\n", diff.tv_sec, diff.tv_usec); 

    timeval_subtract(&diff, &after.ru_stime, &before.ru_stime); 
    printf("System: %ld.%06d s\n", diff.tv_sec, diff.tv_usec); 

    return 0; 
} 

i uruchomić wyniki:

$ make 
clang -Wall -Wextra -Werror -O3 -g -o example example.c 
./example 0x10000000 
filling... done 

loop (returned 0): 
User: 0.024078 s 
System: 0.000011 s 

memcmp (returned 0): 
User: 0.036752 s 
System: 0.000017 s 

Może ty zrobić coś podobnego?

Uwaga: Dla osób zainteresowanych ociepleniem pamięci podręcznej próbowałem również z memcmp przed pętlą i otrzymałem takie same wyniki.

Answer 2

memcmp z adresem jest najlepszym rozwiązaniem dla porównania bloków pamięci. Niezależnie od tego, czy użyto bloku inline, czy użył adresu pamięci bloku, nadal musiałbyś gdzieś przechowywać blok.

Można utworzyć taki blok w czasie kompilacji z czymś takim:

int block[] = {3, 1, 4, 1, 5, 9}; 

a potem po prostu korzystać block w memcmp.

Jeśli chcesz tylko upewnić się, że blok pamięci jest ustawiony na określone wartości, użyj rozwiązania pętli for. Każde inne rozwiązanie, które wymyślisz, będzie musiało zrobić to samo, sprawdź cały blok.

Alternatywą, jeśli jest to naprawdę duży blok pamięci i trwa zbyt długo, jest całkowite usunięcie tego wymogu. Mam na myśli przebudować twoje algorytmy, aby stały się niepotrzebne. Załóżmy, że masz blok 1G.

Przykład: nie ustawiaj ich wszystkich na zera. Zamiast tego ustaw tylko bit z przodu, który aktywnie używasz i zachowaj oddzielną zmienną, aby wskazać, ile używasz.

Mocno zoptymalizowany memcmpmoże prześcignąć pętlę użytkownika, ale można również stwierdzić, że tak nie jest, po prostu dlatego, że musi zaspokoić ogólnym przypadku - konkretnego przypadku sprawdzania przeciwko zera może pozwolić na wprowadzenie kompilator optymalizacje, które pokonują memcmp.

Tak jak przy wszystkich optymalizacjach, miara , nie zgaduj!

Answer 3

Jedną opcją byłoby rozpoczęcie od kodu źródłowego memcmp i modyfikowanie go w celu porównania ze stałym buforem, iteracyjnie. W ten sposób zachowujesz optymalizacje wbudowane w memcmp, unikniesz narzutu zewnętrznej pętli i nadal osiągasz swój cel. Możesz mieć funkcję podobną do poniższej:

int memcmp2(const void *s1, size_t n1, const void *s2, size_t n2); 

Gdzie n1 to rozmiar bufora s1, a n2 tej z s2.

Answer 4

Jeśli nie masz kontroli nad tym, kto zapisuje do tego bloku pamięci, to nie może istnieć inteligentny algorytm, który umożliwiłby efektywne porównanie z jedną wartością. Będziesz musiał powtórzyć cały blok i nie możesz pominąć nawet jednego słowa. Jedyne, co możesz zrobić, to porównać więcej danych naraz, w miarę możliwości korzystając z instrukcji maszynowych, które mogą przetwarzać wiele słów naraz.

Jeśli masz kontrolę nad tą pamięcią i tylko Ty możesz do niej pisać, możesz być mądrzejszy w ustalaniu, co tam jest. Na przykład "marnując" trochę przestrzeni, aby utrzymać wzór bitowy, który określa, które słowa są zerami. Na przykład, jeśli twoje słowa są 32-bitowe, będziesz miał oddzielny blok pamięci, w którym zachowasz tyle słów, które sumują się do tej samej liczby bitów, ile słów w twoim rzeczywistym bloku pamięci. W tym przypadku będzie cię to kosztować 1 bajt na 32 bajty użytecznej pamięci, co nie jest straszne. Jeśli naprawdę potrzebujesz cząstkowej granulacji, koszt jest znacznie wyższy: 1 na 8. Ale zwykle tego nie potrzebujesz; możesz zawęzić wyszukiwanie po znalezieniu słowa, które nie jest wyzerowane, i wyszukiwać tylko w tym dla pierwszego niezerowego bajtu.

Answer 5

Jedno rozwiązanie:

Utwórz bufor zawierający wszystkie te same wartości i porównać przeciwko niemu iteracyjnie. W ten sposób można uzyskać korzystając z efektywnego memcmp realizacji bez konieczności pisania zbyt dużo kod:

static char val[4096]; // tune the size of the buffer if desired 
/* at initialization: memset(val, 0x01, sizeof(val)) */ 

char *start, *ptr, *end; 
// initialize start and end 
for(ptr = start; ptr < end-sizeof(val); ptr += sizeof(val)) { 
    if(memcmp(ptr, val, sizeof(val)) 
     goto not_all_val; 
} 
if(memcmp(ptr, val, end - ptr)) 
    goto not_all_val; 

/* all val */ 
puts("all val"); 
return; 

not_all_val: 
puts("not all val"); 
return; 

Porównanie wydajności:

10000 iteracji memcmp(buf, buf2, 4000000) (dwa bufory o tej samej długości, tak samo jak w pierwszej metodzie na pytanie)

real 0m7.480s 
user 0m7.375s 
sys 0m0.103s 

10000 iteracji porównaniu znak po znaku ponad 4000000 bajty (taki sam jak w drugim sposobie

):

real 0m27.004s 
user 0m26.908s 
sys 0m0.094s 

10000 iteracji proponowanej metody Powyższe ponad 4.000.000 bajtów:

real 0m3.194s 
user 0m3.151s 
sys 0m0.042s 

YMMV (jestem na trzy-letniego MacBook Pro), ale ta metoda jest dwukrotnie szybciej niż porównanie kompletny bufor (prawdopodobnie ze względu na lepszą wydajność pamięci podręcznej) i prawie dziesięć razy szybciej niż porównanie znaków po znaku.

Answer 6

Jeśli po uruchomieniu memcmp(), dlaczego miałbyś oczekiwać zmian pamięci? Jeśli pamięć należy tylko do twojego procesu, nic jej nie zmodyfikuje. Jeśli jest to pamięć współdzielona, ​​problem staje się zupełnie inny.

Jako alternatywna sugestia myślałem o używaniu memset(), aby umieścić całą pamięć w znanej wartości - którą już wykonałeś w mniej niż 546 kleszczach.

Powód: memset() ustawi pamięć na znaną wartość w jednym przejściu - wykonanie drugiego przejścia przez tę samą pamięć do sprawdzenia zajmuje około dwa razy dłużej.