4 ms·

Maybe i'm blind - but i'm not seeing where the benchmark results are? Also, is this code the same code that you actually ran? For ruby, i notice you are outputt

• srgpqt 8y ago
  Results are in the black rectangles above the code
• revel 8y ago
  I also had a hard time finding performance. It's listed in the grey bar at the top of each language. I'd love to see this comparison expanded to a few other languages (particularly C/C++ with custom memory allocation).
  • quickben 8y ago
    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?
    • 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.
  • blackflame7000 8y ago
    I once wrote a scanner similar to this for Symantec in C++. As I recall it used a hybrid between the Wu-Manber and Boyer-Moore search algorithms to search a million lines of text for thousands of signatures simultaneously in approx 0.004s as I recall.