Benchmark for C++ PDQ index #1699

16BitNarwhal · 2024-11-28T04:47:59Z

Summary

Resolve #1697

C++ query benchmark program for brute force linear scan and mih (pdq/cpp/index/mih.h)
Benchmark implementation located in pdq/cpp/bin/benchmark-query.cpp
Benchmark results in pdq/cpp/index/README.md

To run:

cd pdq/cpp
make benchmark-query
./benchmark-query

Sample results (ran on Ubuntu 24.04.1 LTS, Intel Core i7-14700KF with 20 cores, 28 threads, 64GB RAM):

$ ./benchmark-query -m linear
METHOD: Linear query
QUERY COUNT:             1000
INDEX COUNT:             10000
TOTAL MATCH COUNT:       1000
TOTAL QUERY SECONDS:     0.258911
SECONDS PER QUERY:       0.000259

pdq/cpp/bin/benchmark-mih.cpp

Co-authored-by: ianwal <[email protected]>

Dcallies

Only some minor inline comments that I think will block extension. Otherwise looks good, thanks for doing it and for doing a README!

Dcallies · 2024-12-02T14:22:44Z

pdq/cpp/bin/benchmark-query.cpp

+// Helper declarations
+static facebook::pdq::hashing::Hash256 generateRandomHash(std::mt19937& gen);
+static facebook::pdq::hashing::Hash256 addNoise(
+    const facebook::pdq::hashing::Hash256& original,
+    int numBitsToFlip,
+    std::mt19937& gen);


These seem like generally useful function, and might be worth including in some kind of pdq/utils method. Some of your peers have ended up building the same functions in python.

Dcallies · 2024-12-02T14:23:39Z

pdq/cpp/bin/benchmark-query.cpp

+  fprintf(fp, "Usage: %s [options]\n", argv0);
+  fprintf(fp, "Options:\n");
+  fprintf(fp, "  -v               Verbose output\n");
+  fprintf(fp, "  --seed N         Random seed (default: 41)\n");


Thanks for providing a way to make this reproduceable

Dcallies · 2024-12-02T14:26:24Z

pdq/cpp/bin/benchmark-query.cpp

+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif


I originally thought you were including this for getopt. I'm a c++ dummy, what functions/functionalities are you including from GNU?

Dcallies · 2024-12-02T14:27:07Z

pdq/cpp/bin/benchmark-query.cpp

+        maxDistance, verbose, seed, indexSize, querySize, queries, index);
+  } else if (method == "mih") {
+    queryMIH(maxDistance, verbose, seed, indexSize, querySize, queries, index);
+  }


unsure: Is there an else fail missing here?

Dcallies · 2024-12-02T14:28:52Z

pdq/cpp/bin/benchmark-query.cpp

+  std::vector<std::pair<facebook::pdq::hashing::Hash256, std::string>> matches;
+
+  std::chrono::time_point<std::chrono::steady_clock> t1, t2;
+  std::chrono::duration<double> elapsedSeconds;
+
+  t1 = std::chrono::steady_clock::now();
+  for (const auto& it : queries) {
+    for (const auto& it2 : index) {
+      if (it.first.hammingDistance(it2.first) <= maxDistance) {
+        matches.push_back(it2);
+      }
+    }
+  }
+  t2 = std::chrono::steady_clock::now();
+  elapsedSeconds = t2 - t1;
+  double seconds = elapsedSeconds.count();


Is it better to pull the timing functionality outside of the query method itself, so you have something like:

auto lookupFn = ... // start timing lookupFn(index, queries); // End timing

Dcallies · 2024-12-02T14:34:07Z

pdq/cpp/bin/benchmark-query.cpp

+  size_t querySize = 1000;
+  std::string method = "linear";
+
+  // Parse command line arguments


ignorable: There are an abundance of command line helpers out there (I'm a fan of gflags), but none in the standard library, and I think it's better to handroll than to take another dependency.

Dcallies · 2024-12-02T14:40:37Z

pdq/cpp/bin/benchmark-query.cpp

+  for (int i = 0; i < numBitsToFlip; i++) {
+    int wordIndex = wordDist(gen);
+    int bitIndex = bitDist(gen);
+    // Flip bit with xor
+    noisy.w[wordIndex] ^= (1 << bitIndex);
+  }


blocking: Can you end up flipping the same bit twice and thus ending with less distance than you expect?

Why not do uniform random 256 and modulus instead of doing this in two passes?

A possible solution to blocker:

Assert distance is less than some amount (64?)

Copy the original

Create another PDQ that represents the xor

Repeat until X bits are flipped

Randomly select an index in the xor

If it's 0, flip it to 1
5 .return original XOR xor

Alternatively, create a sequence from 0-256 and then use https://en.cppreference.com/w/cpp/algorithm/ranges/sample, then flip those bits

Dcallies · 2024-12-02T14:40:54Z

pdq/cpp/index/README.md

@@ -0,0 +1,82 @@
+# Benchmark for index


Thanks for writing a readme!

Dcallies · 2024-12-02T14:42:01Z

pdq/cpp/bin/benchmark-query.cpp

+  printf("METHOD: Linear query\n");
+  printf("QUERY COUNT:             %d\n", (int)queries.size());
+  printf("INDEX COUNT:             %d\n", (int)index.size());
+  printf("TOTAL MATCH COUNT:       %d\n", (int)matches.size());
+  printf("TOTAL QUERY SECONDS:     %.6lf\n", seconds);
+  printf(
+      "SECONDS PER QUERY:       %.6lf\n",
+      querySize > 0 ? seconds / querySize : 0);
+  printf("\n");


blocking: Yeah, let's not force everyone to perfectly implement this print block, having this in shared code.

Dcallies · 2024-12-02T14:42:49Z

pdq/cpp/bin/benchmark-query.cpp

+  printf("TOTAL MATCH COUNT:       %d\n", (int)matches.size());
+  printf("TOTAL QUERY SECONDS:     %.6lf\n", seconds);
+  printf(
+      "SECONDS PER QUERY:       %.6lf\n",


I wonder if we want to do queries per second rather than seconds per query, given I think we'll be able to get at least 1 for most inputs, and our fastest approaches will have big numbers.

16BitNarwhal and others added 5 commits November 9, 2024 13:05

update README with note on dihedral pdq hashes

df83aae

copy benchmark over from test-mih.cpp

40795aa

needles based on noise

fef0970

Merge branch 'facebook:main' into main

4dc7daf

benchmark results

33683c4

16BitNarwhal requested a review from Dcallies as a code owner November 28, 2024 04:48

facebook-github-bot added the CLA Signed label Nov 28, 2024

ianwal reviewed Nov 29, 2024

View reviewed changes

pdq/cpp/bin/benchmark-mih.cpp Outdated Show resolved Hide resolved

16BitNarwhal and others added 6 commits November 29, 2024 15:57

Update pdq/cpp/bin/benchmark-mih.cpp

3799683

Co-authored-by: ianwal <[email protected]>

clang format

495cc8d

use steady_clock and rerun benchmark

7a8c9e1

big benchmark refactor

9ee1693

rerun benchmark

8684023

clang format

48f6c66

Dcallies requested changes Dec 2, 2024

View reviewed changes

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Benchmark for C++ PDQ index #1699

Benchmark for C++ PDQ index #1699

16BitNarwhal commented Nov 28, 2024 •

edited

Loading

Dcallies left a comment

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Dcallies Dec 2, 2024

Benchmark for C++ PDQ index #1699

Are you sure you want to change the base?

Benchmark for C++ PDQ index #1699

Conversation

16BitNarwhal commented Nov 28, 2024 • edited Loading

Summary

Dcallies left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

16BitNarwhal commented Nov 28, 2024 •

edited

Loading