4 ms·

A c++ implementation gives 5.7[ms] for searching through 200MB of vector<string> on a Ryzen 1700x. EDIT: Reworking the code.

jotto 8y ago
Incredible! Will you post a code snippet?
prewett 8y ago
I did some benchmarking for a dictionary app a while back, and the fastest I could get was strstr(), if I recall correctly. It substantially beat std::string::find(). Using a loop is bound to give terrible performance; for large data you should be using one of the string-search algorithms (which strstr() surely does). And given the very large search string, those string-search algorithms should be able to skip large chunks at a time. Here's a small version that allocates 200 MB of uninitialized memory. #include <stdlib.h> #include <string.h> int main(int argc, char *argv[]) { int size = 200 * 1024 * 1024; char *bytes = malloc(size); bytes[size - 1] = '\0'; strstr(bytes, "788bbd6b12d79a4ee18e36a8a264fb496465c71b7932a965ed731397b7c97d14"); return 0; } > gcc test.c > time ./a.out real 0m0.006s user 0m0.002s sys 0m0.002s (Since the author ignores time to read off disk, I figure uninitialized memory should be comparable. The chances of strstr() actually finding anything are pretty slim, but I ran it a number of times just to be sure, with the same results.) This is on a 2012 MacBook Pro.
- vardump 8y ago
  Reading uninitialized allocation triggers undefined behavior. The compiler is free to do whatever it pleases. Don't do that.
- cozzyd 8y ago
  Note that strstr will stop as soon as you have a 0 byte so this is not a fair comparison. Uninitialized (practically often zeroed) also produces different results from random and explicitly zeroed, since I assume it affects how often it can fail fast. #define _GNU_SOURCE #include <stdlib.h> #include <stdio.h> #include <string.h> #include <time.h> int main(int nargs, char ** args) { struct timespec start; struct timespec end; int mode = atoi(args[1]); const char * needle = "788bbd6b12d79a4ee18e36a8a264fb496465c71b7932a965ed731397b7c97d14"; const int N = 200*1024*1024 ; char * haystack = malloc(N + sizeof(needle)); strcpy(haystack+N,needle); printf("Mode is %s\n" , mode == 0 ? "zeroed" : mode == 1 ? "random" : "uninitialized"); if (mode == 0) { memset(haystack,0,N); } if (mode == 1) { FILE * urandom = fopen("/dev/urandom","r"); int nread = fread(haystack,1,N,urandom); fclose(urandom); if (nread < N) { fprintf(stderr,"read returned %d\n",nread); } } clock_gettime(CLOCK_REALTIME, &start); void * found = memmem(haystack,N+sizeof(needle),needle,sizeof(needle)); clock_gettime(CLOCK_REALTIME, &end); printf("Took %g secs to find string at offset of %llu\n", end.tv_sec - start.tv_sec + 1e-9*(end.tv_nsec - start.tv_nsec), found-(void*)haystack); return 0; } $ gcc test_find.c -o test_find $ ./test_find 0 Mode is zeroed Took 0.0147023 secs to find string at offset of 209715200 $ ./test_find 1 Mode is random Took 0.129951 secs to find string at offset of 209715200 $ ./test_find 2 Mode is uninitialized Took 0.0371922 secs to find string at offset of 209715200
  - kazinator 8y ago
    Note that if you malloc that big of a block, it's going to come directly from a MAP_ANONYMOUS mmap, and so it will be zero initialized! Your uninitialized mode is slower than zeroed, but nowhere near as slow as random. The difference between initialized and uninitialized may be due to page faults: in the uninitialized case, the search is touching the memory for the first time. Maybe we're seeing TLB misses?
    - cozzyd 8y ago
      Yeah I was expecting the uninitialized to be the same as the zeroed case for that reason, but was surprised to see a (slightly) different result. Edit: you are almost certainly right. I added a getrusage call before and after, and we have ~50k soft page faults in the uninitialized case and ~2 in the zeroed case during the memmem.
danbruc 8y ago
- 3276800 entries (to match authors 200 MB of ascii) Sounds like you implicitly assumed the match will be aligned at a 64 byte boundary which makes the task much easier and 4 GiB/s a pretty slow result.
- quickben 8y ago
  I asked the compiled to align what it can on 16 bytes and updated the results. Unsure why the previous result was way off, but I am lacking time for fun tonight :)
  - vardump 8y ago
    You have a vector of 64 char strings, while others have just 200 MB byte array. IOW, your code is not doing remotely same task as the blog post ones. Edit: "Typoed" 1 GB instead of 200 MB. Oops. The point holds.
  - danbruc 8y ago
    I meant something different, your implementation is unable to find the pattern if it does not start at an index divisible by 64. You are effectively only searching through 3,125 MiB instead of 200 MiB.

jotto 8y ago

Incredible! Will you post a code snippet?

prewett 8y ago

I did some benchmarking for a dictionary app a while back, and the fastest I could get was strstr(), if I recall correctly. It substantially beat std::string::find(). Using a loop is bound to give terrible performance; for large data you should be using one of the string-search algorithms (which strstr() surely does). And given the very large search string, those string-search algorithms should be able to skip large chunks at a time. Here's a small version that allocates 200 MB of uninitialized memory. #include <stdlib.h> #include <string.h> int main(int argc, char *argv[]) { int size = 200 * 1024 * 1024; char *bytes = malloc(size); bytes[size - 1] = '\0'; strstr(bytes, "788bbd6b12d79a4ee18e36a8a264fb496465c71b7932a965ed731397b7c97d14"); return 0; } > gcc test.c > time ./a.out real 0m0.006s user 0m0.002s sys 0m0.002s (Since the author ignores time to read off disk, I figure uninitialized memory should be comparable. The chances of strstr() actually finding anything are pretty slim, but I ran it a number of times just to be sure, with the same results.) This is on a 2012 MacBook Pro.

vardump 8y ago
Reading uninitialized allocation triggers undefined behavior. The compiler is free to do whatever it pleases. Don't do that.
cozzyd 8y ago
Note that strstr will stop as soon as you have a 0 byte so this is not a fair comparison. Uninitialized (practically often zeroed) also produces different results from random and explicitly zeroed, since I assume it affects how often it can fail fast. #define _GNU_SOURCE #include <stdlib.h> #include <stdio.h> #include <string.h> #include <time.h> int main(int nargs, char ** args) { struct timespec start; struct timespec end; int mode = atoi(args[1]); const char * needle = "788bbd6b12d79a4ee18e36a8a264fb496465c71b7932a965ed731397b7c97d14"; const int N = 200*1024*1024 ; char * haystack = malloc(N + sizeof(needle)); strcpy(haystack+N,needle); printf("Mode is %s\n" , mode == 0 ? "zeroed" : mode == 1 ? "random" : "uninitialized"); if (mode == 0) { memset(haystack,0,N); } if (mode == 1) { FILE * urandom = fopen("/dev/urandom","r"); int nread = fread(haystack,1,N,urandom); fclose(urandom); if (nread < N) { fprintf(stderr,"read returned %d\n",nread); } } clock_gettime(CLOCK_REALTIME, &start); void * found = memmem(haystack,N+sizeof(needle),needle,sizeof(needle)); clock_gettime(CLOCK_REALTIME, &end); printf("Took %g secs to find string at offset of %llu\n", end.tv_sec - start.tv_sec + 1e-9*(end.tv_nsec - start.tv_nsec), found-(void*)haystack); return 0; } $ gcc test_find.c -o test_find $ ./test_find 0 Mode is zeroed Took 0.0147023 secs to find string at offset of 209715200 $ ./test_find 1 Mode is random Took 0.129951 secs to find string at offset of 209715200 $ ./test_find 2 Mode is uninitialized Took 0.0371922 secs to find string at offset of 209715200
- kazinator 8y ago
  Note that if you malloc that big of a block, it's going to come directly from a MAP_ANONYMOUS mmap, and so it will be zero initialized! Your uninitialized mode is slower than zeroed, but nowhere near as slow as random. The difference between initialized and uninitialized may be due to page faults: in the uninitialized case, the search is touching the memory for the first time. Maybe we're seeing TLB misses?
  - cozzyd 8y ago
    Yeah I was expecting the uninitialized to be the same as the zeroed case for that reason, but was surprised to see a (slightly) different result. Edit: you are almost certainly right. I added a getrusage call before and after, and we have ~50k soft page faults in the uninitialized case and ~2 in the zeroed case during the memmem.

danbruc 8y ago

- 3276800 entries (to match authors 200 MB of ascii) Sounds like you implicitly assumed the match will be aligned at a 64 byte boundary which makes the task much easier and 4 GiB/s a pretty slow result.

quickben 8y ago
I asked the compiled to align what it can on 16 bytes and updated the results. Unsure why the previous result was way off, but I am lacking time for fun tonight :)
- vardump 8y ago
  You have a vector of 64 char strings, while others have just 200 MB byte array. IOW, your code is not doing remotely same task as the blog post ones. Edit: "Typoed" 1 GB instead of 200 MB. Oops. The point holds.
- danbruc 8y ago
  I meant something different, your implementation is unable to find the pattern if it does not start at an index divisible by 64. You are effectively only searching through 3,125 MiB instead of 200 MiB.