From 0cf96983011bc05a2ed275d3588e41aa4fe3c7a1 Mon Sep 17 00:00:00 2001
From: Douglas Rumbaugh <dbr4@psu.edu>
Date: Mon, 15 Apr 2024 10:22:21 -0400
Subject: Added a dynamic trie benchmark

---
 benchmarks/poplar_trie.cpp | 98 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 98 insertions(+)
 create mode 100644 benchmarks/poplar_trie.cpp

(limited to 'benchmarks/poplar_trie.cpp')

diff --git a/benchmarks/poplar_trie.cpp b/benchmarks/poplar_trie.cpp
new file mode 100644
index 0000000..6a04cb9
--- /dev/null
+++ b/benchmarks/poplar_trie.cpp
@@ -0,0 +1,98 @@
+/*
+ *
+ */
+
+#define ENABLE_TIMER
+
+#include <fstream>
+#include <sstream>
+
+#include "poplar.hpp"
+
+#include "psu-util/timer.h"
+#include "psu-util/progress.h"
+
+std::vector<std::string> strings;
+
+typedef poplar::plain_bonsai_map<int> Trie;
+
+void insert_thread(int64_t start, int64_t end, Trie * trie) {
+    for (uint64_t i=start; i<end; i++) {
+        auto res = trie->update(strings[i]);
+        *res = i+1;
+    }
+}
+
+void read_data(std::string fname, size_t n=10000000) {
+    strings.reserve(n);
+
+    std::fstream file;
+    file.open(fname, std::ios::in);
+
+    size_t i=0;
+    std::string line;
+    while (i < n && std::getline(file, line, '\n')) {
+        strings.emplace_back(line);
+        i++;
+        psudb::progress_update((double) i / (double) n, "Reading file:");
+    }
+}
+
+void usage(char *name) {
+    fprintf(stderr, "Usage:\n%s datafile record_count\n", name);
+}
+
+int main(int argc, char **argv) {
+
+    if (argc < 3) {
+        usage(argv[0]);
+        exit(EXIT_FAILURE);
+    }
+
+    std::string fname = std::string(argv[1]);
+    size_t n = atol(argv[2]);
+
+    read_data(fname, n);
+
+    if (strings.size() == 0) {
+        fprintf(stderr, "[E]: No string data read from file. Aborting execution.\n");
+    } else {
+        fprintf(stderr, "Finished reading from file.\n");
+    }
+
+    auto trie = new Trie();
+
+    TIMER_INIT();
+    TIMER_START();
+    insert_thread(0, strings.size(), trie);
+    TIMER_STOP();
+
+    auto total_time = TIMER_RESULT();
+
+    size_t m = 100;
+    TIMER_START();
+    for (size_t i=0; i<m; i++) {
+        size_t j = rand() % strings.size();
+
+        auto res = trie->find(strings[j]);
+        if (*res != j-1) {
+            fprintf(stderr, "%ld %d %s\n", j, *res, strings[j].c_str());
+        }
+        assert(*(res)+1 == j);
+    }
+    TIMER_STOP();
+
+    auto query_time = TIMER_RESULT();
+    
+
+    double i_tput = (double) n / (double) total_time * 1e9;
+    size_t q_lat = query_time / m;
+
+    fprintf(stdout, "%ld\t\t%lf\t%ld\n", trie->size(), 
+            i_tput, q_lat);
+
+    delete trie;
+
+    fflush(stderr);
+}
+
-- 
cgit v1.2.3


From 428658bc76b5b9eec46d3b7e415b5d114ddd3f79 Mon Sep 17 00:00:00 2001
From: Douglas Rumbaugh <dbr4@psu.edu>
Date: Mon, 15 Apr 2024 12:50:26 -0400
Subject: Print size statistics

---
 benchmarks/poplar_trie.cpp | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

(limited to 'benchmarks/poplar_trie.cpp')

diff --git a/benchmarks/poplar_trie.cpp b/benchmarks/poplar_trie.cpp
index 6a04cb9..c85e718 100644
--- a/benchmarks/poplar_trie.cpp
+++ b/benchmarks/poplar_trie.cpp
@@ -75,10 +75,10 @@ int main(int argc, char **argv) {
         size_t j = rand() % strings.size();
 
         auto res = trie->find(strings[j]);
-        if (*res != j-1) {
+        if (*res != (j+1)) {
             fprintf(stderr, "%ld %d %s\n", j, *res, strings[j].c_str());
         }
-        assert(*(res)+1 == j);
+        //assert(*(res)+1 == j);
     }
     TIMER_STOP();
 
@@ -91,6 +91,8 @@ int main(int argc, char **argv) {
     fprintf(stdout, "%ld\t\t%lf\t%ld\n", trie->size(), 
             i_tput, q_lat);
 
+    trie->show_stats(std::cerr, 1);
+
     delete trie;
 
     fflush(stderr);
-- 
cgit v1.2.3


From 764a9c41cad220513523afb6b610b2bdf74e5476 Mon Sep 17 00:00:00 2001
From: Douglas Rumbaugh <dbr4@psu.edu>
Date: Tue, 14 May 2024 16:00:17 -0400
Subject: Poplar Trie: updated benchmark to standard format

---
 benchmarks/poplar_trie.cpp | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

(limited to 'benchmarks/poplar_trie.cpp')

diff --git a/benchmarks/poplar_trie.cpp b/benchmarks/poplar_trie.cpp
index c85e718..6c47465 100644
--- a/benchmarks/poplar_trie.cpp
+++ b/benchmarks/poplar_trie.cpp
@@ -61,10 +61,12 @@ int main(int argc, char **argv) {
     }
 
     auto trie = new Trie();
+    size_t warmup = strings.size()*.1;
+    insert_thread(0, warmup, trie);
 
     TIMER_INIT();
     TIMER_START();
-    insert_thread(0, strings.size(), trie);
+    insert_thread(warmup, strings.size(), trie);
     TIMER_STOP();
 
     auto total_time = TIMER_RESULT();
-- 
cgit v1.2.3