Avoid all needless memory copies when computing consensus diffs.

Previously, we operated on smartlists of NUL-terminated strings,
which required us to copy both inputs to produce the NUL-terminated
strings.  Then we copied parts of _those_ inputs to produce an
output smartlist of NUL-terminated strings.  And finally, we
concatenated everything into a final resulting string.

This implementation, instead, uses a pointer-and-extent pattern to
represent each line as a pointer into the original inputs and a
length.  These line objects are then added by reference into the
output. No actual bytes are copied from the original strings until
we finally concatenate the final result together.

Bookkeeping structures and newly allocated strings (like ed
commands) are allocated inside a memarea, to avoid needless mallocs
or complicated should-I-free-this-or-not bookkeeping.

In my measurements, this improves CPU performance by something like
18%.  The memory savings should be much, much higher.

1 files changed, 22 insertions, 0 deletions

diff --git a/src/test/bench.c b/src/test/bench.c
index 99bc686f30..ee39f0b582 100644
--- a/src/test/bench.c
+++ b/src/test/bench.c
@@ -28,6 +28,7 @@ const char tor_git_revision[] = "";
 #include "crypto_curve25519.h"
 #include "onion_ntor.h"
 #include "crypto_ed25519.h"
+#include "consdiff.h"
 
 #if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_PROCESS_CPUTIME_ID)
 static uint64_t nanostart;
@@ -674,6 +675,27 @@ main(int argc, const char **argv)
 
   tor_threads_init();
 
+  if (argc == 4 && !strcmp(argv[1], "diff")) {
+    init_logging(1);
+    const int N = 200;
+    char *f1 = read_file_to_str(argv[2], RFTS_BIN, NULL);
+    char *f2 = read_file_to_str(argv[3], RFTS_BIN, NULL);
+    if (! f1 || ! f2) {
+      perror("X");
+      return 1;
+    }
+    for (i = 0; i < N; ++i) {
+      char *diff = consensus_diff_generate(f1, f2);
+      tor_free(diff);
+    }
+    char *diff = consensus_diff_generate(f1, f2);
+    printf("%s", diff);
+    tor_free(f1);
+    tor_free(f2);
+    tor_free(diff);
+    return 0;
+  }
+
   for (i = 1; i < argc; ++i) {
     if (!strcmp(argv[i], "--list")) {
       list = 1;