Benchmark updates

16 files changed, 97 insertions, 40 deletions

diff --git a/.gitmodules b/.gitmodules
index a18695a..0cb5e92 100644
--- a/.gitmodules
+++ b/.gitmodules
@@ -28,3 +28,6 @@
 [submodule "external/poplar-trie"]
 	path = external/poplar-trie
 	url = git@github.com:kampersanda/poplar-trie.git
+[submodule "external/hat-trie"]
+	path = external/hat-trie
+	url = git@github.com:Tessil/hat-trie.git
diff --git a/benchmarks/include/standard_benchmarks.h b/benchmarks/include/standard_benchmarks.h
index 5fc549d..fe53d62 100644
--- a/benchmarks/include/standard_benchmarks.h
+++ b/benchmarks/include/standard_benchmarks.h
@@ -21,7 +21,7 @@ static size_t g_deleted_records = 0;
 static double delete_proportion = 0.05;
 
 template<typename DE, typename QP>
-static void run_queries(DE *extension, std::vector<QP> &queries, gsl_rng *rng) {
+static void run_queries(DE *extension, std::vector<QP> &queries) {
     size_t total;
     for (size_t i=0; i<queries.size(); i++) {
         auto q = &queries[i];
@@ -33,6 +33,22 @@ static void run_queries(DE *extension, std::vector<QP> &queries, gsl_rng *rng) {
 }
 
 
+template<typename S, typename QP, typename Q>
+static void run_static_queries(S *shard, std::vector<QP> &queries) {
+    size_t total;
+    for (size_t i=0; i<queries.size(); i++) {
+        auto q = &queries[i];
+
+        auto state = Q::get_query_state(shard, q);
+        auto res = Q::query(shard, state, q);
+
+        total += res.size();
+    }
+}
+
+
+
+
 template<typename DE, de::RecordInterface R>
 static void insert_records(DE *extension, size_t start, size_t stop, 
                            std::vector<R> &records, std::vector<size_t> &to_delete, 
diff --git a/benchmarks/irs_bench.cpp b/benchmarks/irs_bench.cpp
index 9895295..84cd8b2 100644
--- a/benchmarks/irs_bench.cpp
+++ b/benchmarks/irs_bench.cpp
@@ -72,12 +72,23 @@ int main(int argc, char **argv) {
     size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9);
 
     TIMER_START();
-    run_queries<Ext, QP>(extension, queries, rng);
+    run_queries<Ext, QP>(extension, queries);
     TIMER_STOP();
 
     auto query_latency = TIMER_RESULT() / queries.size();
 
-    fprintf(stdout, "T\t%ld\t%ld\t%ld\n", insert_throughput, query_latency, g_deleted_records);
+    auto shard = extension->create_static_structure();
+
+    TIMER_START();
+    run_static_queries<Shard, QP, Q>(shard, queries);
+    TIMER_STOP();
+
+    auto static_latency = TIMER_RESULT() / queries.size();
+
+    auto ext_size = extension->get_memory_usage() + extension->get_aux_memory_usage();
+    auto static_size = shard->get_memory_usage();// + shard->get_aux_memory_usage();
+
+    fprintf(stdout, "%ld\t%ld\t%ld\t%ld\t%ld\n", insert_throughput, query_latency, ext_size, static_latency, static_size);
 
     gsl_rng_free(rng);
     delete extension;
diff --git a/benchmarks/pgm_bench.cpp b/benchmarks/pgm_bench.cpp
index 3643abb..ac3ed1b 100644
--- a/benchmarks/pgm_bench.cpp
+++ b/benchmarks/pgm_bench.cpp
@@ -69,12 +69,23 @@ int main(int argc, char **argv) {
     size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9);
 
     TIMER_START();
-    run_queries<Ext, QP>(extension, queries, rng);
+    run_queries<Ext, QP>(extension, queries);
     TIMER_STOP();
 
     auto query_latency = TIMER_RESULT() / queries.size();
 
-    fprintf(stdout, "T\t%ld\t%ld\t%ld\n", insert_throughput, query_latency, g_deleted_records);
+    auto shard = extension->create_static_structure();
+
+    TIMER_START();
+    run_static_queries<Shard, QP, Q>(shard, queries);
+    TIMER_STOP();
+
+    auto static_latency = TIMER_RESULT() / queries.size();
+
+    auto ext_size = extension->get_memory_usage() + extension->get_aux_memory_usage();
+    auto static_size = shard->get_memory_usage(); // + shard->get_aux_memory_usage();
+
+    fprintf(stdout, "%ld\t%ld\t%ld\t%ld\t%ld\n", insert_throughput, query_latency, ext_size, static_latency, static_size);
 
     gsl_rng_free(rng);
     delete extension;
diff --git a/benchmarks/ts_bench.cpp b/benchmarks/ts_bench.cpp
index 3dc619e..93e7616 100644
--- a/benchmarks/ts_bench.cpp
+++ b/benchmarks/ts_bench.cpp
@@ -19,9 +19,9 @@
 
 
 typedef de::Record<uint64_t, uint64_t> Rec;
-typedef de::TrieSpline<Rec> PGM;
-typedef de::rc::Query<Rec, PGM> Q;
-typedef de::DynamicExtension<Rec, PGM, Q, de::LayoutPolicy::TEIRING, de::DeletePolicy::TAGGING, de::SerialScheduler> Ext;
+typedef de::TrieSpline<Rec> Shard;
+typedef de::rc::Query<Rec, Shard> Q;
+typedef de::DynamicExtension<Rec, Shard, Q, de::LayoutPolicy::TEIRING, de::DeletePolicy::TAGGING, de::SerialScheduler> Ext;
 typedef de::rc::Parms<Rec> QP;
 
 void usage(char *progname) {
@@ -69,12 +69,23 @@ int main(int argc, char **argv) {
     size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9);
 
     TIMER_START();
-    run_queries<Ext, QP>(extension, queries, rng);
+    run_queries<Ext, QP>(extension, queries);
     TIMER_STOP();
 
     auto query_latency = TIMER_RESULT() / queries.size();
 
-    fprintf(stdout, "T\t%ld\t%ld\t%ld\n", insert_throughput, query_latency, g_deleted_records);
+    auto shard = extension->create_static_structure();
+
+    TIMER_START();
+    run_static_queries<Shard, QP, Q>(shard, queries);
+    TIMER_STOP();
+
+    auto static_latency = TIMER_RESULT() / queries.size();
+
+    auto ext_size = extension->get_memory_usage() + extension->get_aux_memory_usage();
+    auto static_size = shard->get_memory_usage(); //+ shard->get_aux_memory_usage();
+
+    fprintf(stdout, "%ld\t%ld\t%ld\t%ld\t%ld\n", insert_throughput, query_latency, ext_size, static_latency, static_size);
 
     gsl_rng_free(rng);
     delete extension;
diff --git a/benchmarks/vptree_bench.cpp b/benchmarks/vptree_bench.cpp
index f4c7d0e..1219076 100644
--- a/benchmarks/vptree_bench.cpp
+++ b/benchmarks/vptree_bench.cpp
@@ -75,12 +75,23 @@ int main(int argc, char **argv) {
 
     fprintf(stderr, "[I] Running Query Benchmark\n");
     TIMER_START();
-    run_queries<Ext, QP>(extension, queries, rng);
+    run_queries<Ext, QP>(extension, queries);
     TIMER_STOP();
 
     auto query_latency = TIMER_RESULT() / queries.size();
 
-    fprintf(stdout, "T\t%ld\t%ld\t%ld\n", insert_throughput, query_latency, g_deleted_records);
+    auto shard = extension->create_static_structure();
+
+    TIMER_START();
+    run_static_queries<Shard, QP, Q>(shard, queries);
+    TIMER_STOP();
+
+    auto static_latency = TIMER_RESULT() / queries.size();
+
+    auto ext_size = extension->get_memory_usage() + extension->get_aux_memory_usage();
+    auto static_size = shard->get_memory_usage(); // + shard->get_aux_memory_usage();
+
+    fprintf(stdout, "%ld\t%ld\t%ld\t%ld\t%ld\n", insert_throughput, query_latency, ext_size, static_latency, static_size);
 
     gsl_rng_free(rng);
     delete extension;
diff --git a/external/hat-trie b/external/hat-trie
new file mode 160000
+Subproject 906e6abd1e7063f1dacd3a6b270aa654b525eb0
diff --git a/include/framework/DynamicExtension.h b/include/framework/DynamicExtension.h
index 9e1b8fa..9d54777 100644
--- a/include/framework/DynamicExtension.h
+++ b/include/framework/DynamicExtension.h
@@ -204,6 +204,8 @@ public:
         auto t = m_buffer->get_memory_usage() + epoch->get_structure()->get_memory_usage();
         end_job(epoch);
 
+        fprintf(stderr, "total: %ld\n", t);
+
         return t;
     }
 
@@ -214,7 +216,7 @@ public:
      */
     size_t get_aux_memory_usage() {
         auto epoch = get_active_epoch();
-        auto t = epoch->get_buffer().get_aux_memory_usage() + epoch->get_structure()->get_aux_memory_usage();
+        auto t = m_buffer->get_memory_usage() + epoch->get_structure()->get_aux_memory_usage();
         end_job(epoch);
 
         return t;
diff --git a/include/framework/structure/ExtensionStructure.h b/include/framework/structure/ExtensionStructure.h
index ffba1c1..6ad7aad 100644
--- a/include/framework/structure/ExtensionStructure.h
+++ b/include/framework/structure/ExtensionStructure.h
@@ -161,9 +161,11 @@ public:
     size_t get_memory_usage() {
         size_t cnt = 0;
         for (size_t i=0; i<m_levels.size(); i++) {
+            fprintf(stderr, "%ld\t%ld\n", i, m_levels[i]->get_memory_usage());
             if (m_levels[i]) cnt += m_levels[i]->get_memory_usage();
         }
 
+        fprintf(stderr, "%ld\n", cnt);
         return cnt;
     }
 
diff --git a/include/shard/Alias.h b/include/shard/Alias.h
index 9275952..72147d7 100644
--- a/include/shard/Alias.h
+++ b/include/shard/Alias.h
@@ -148,7 +148,7 @@ public:
 
 
     size_t get_memory_usage() {
-        return m_alloc_size;
+        return 0;
     }
 
     size_t get_aux_memory_usage() {
diff --git a/include/shard/AugBTree.h b/include/shard/AugBTree.h
index 54931bd..c60cbcd 100644
--- a/include/shard/AugBTree.h
+++ b/include/shard/AugBTree.h
@@ -148,7 +148,7 @@ public:
     }
 
     size_t get_memory_usage() {
-        return m_alloc_size + m_node_cnt * sizeof(AugBTreeNode<Wrapped<R>>);
+        return m_node_cnt * sizeof(AugBTreeNode<Wrapped<R>>);
     }
 
     size_t get_aux_memory_usage() {
diff --git a/include/shard/FSTrie.h b/include/shard/FSTrie.h
index be678ff..3783b38 100644
--- a/include/shard/FSTrie.h
+++ b/include/shard/FSTrie.h
@@ -74,7 +74,7 @@ public:
 
         m_reccnt = cnt;
         if (m_reccnt > 0) {
-            m_fst = new fst::Trie(keys);
+            m_fst = new fst::Trie(keys, true, 1);
         }
 
         delete[] temp_buffer;
@@ -135,7 +135,7 @@ public:
         }
 
         if (m_reccnt > 0) {
-            m_fst = new fst::Trie(keys);
+            m_fst = new fst::Trie(keys, true, 1);
         }
     }
 
@@ -180,11 +180,11 @@ public:
 
 
     size_t get_memory_usage() {
-        return m_fst->getMemoryUsage() + m_alloc_size;
+        return m_fst->getMemoryUsage();
     }
 
     size_t get_aux_memory_usage() {
-        return 0;
+        return m_alloc_size;
     }
 
     size_t get_lower_bound(R &rec) {return 0;}
diff --git a/include/shard/ISAMTree.h b/include/shard/ISAMTree.h
index af62c92..1cca506 100644
--- a/include/shard/ISAMTree.h
+++ b/include/shard/ISAMTree.h
@@ -51,7 +51,7 @@ constexpr static size_t LEAF_FANOUT = NODE_SZ / sizeof(R);
 
 public:
     ISAMTree(BufferView<R> buffer)
-        : m_bf(new BloomFilter<R>(BF_FPR, buffer.get_tombstone_count(), BF_HASH_FUNCS))
+        : m_bf(nullptr)
         , m_isam_nodes(nullptr)
         , m_root(nullptr)
         , m_reccnt(0)
@@ -59,19 +59,12 @@ public:
         , m_internal_node_cnt(0)
         , m_deleted_cnt(0)
         , m_alloc_size(0)
-        , m_data(nullptr)
     {
         m_alloc_size = psudb::sf_aligned_alloc(CACHELINE_SIZE, 
                                                buffer.get_record_count() * 
                                                  sizeof(Wrapped<R>), 
                                                (byte**) &m_data);
 
-        /* 
-         * without this, gcc seems to hoist the building of the array
-         * _above_ its allocation under -O3, resulting in memfaults.
-         */
-        //asm volatile ("" ::: "memory");
-
         auto res = sorted_array_from_bufferview(std::move(buffer), m_data, m_bf);
         m_reccnt = res.record_count;
         m_tombstone_cnt = res.tombstone_count;
@@ -90,13 +83,12 @@ public:
         , m_internal_node_cnt(0)
         , m_deleted_cnt(0)
         , m_alloc_size(0)
-        , m_data(nullptr)
     {
         size_t attemp_reccnt = 0;
         size_t tombstone_count = 0;
         auto cursors = build_cursor_vec<R, ISAMTree>(shards, &attemp_reccnt, &tombstone_count);
 
-        m_bf = new BloomFilter<R>(BF_FPR, tombstone_count, BF_HASH_FUNCS);
+        m_bf = nullptr;
         m_alloc_size = psudb::sf_aligned_alloc(CACHELINE_SIZE, 
                                                attemp_reccnt * sizeof(Wrapped<R>),
                                                (byte **) &m_data);
@@ -149,7 +141,7 @@ public:
 
 
     size_t get_memory_usage() {
-        return m_alloc_size + m_internal_node_cnt * NODE_SZ;
+        return m_internal_node_cnt * NODE_SZ;
     }
 
     size_t get_aux_memory_usage() {
diff --git a/include/shard/PGM.h b/include/shard/PGM.h
index ff9ce2d..a3f9749 100644
--- a/include/shard/PGM.h
+++ b/include/shard/PGM.h
@@ -39,8 +39,7 @@ private:
 
 public:
     PGM(BufferView<R> buffer)
-        : m_data(nullptr)
-        , m_bf(new BloomFilter<R>(BF_FPR, buffer.get_tombstone_count(), BF_HASH_FUNCS))
+        : m_bf(nullptr)
         , m_reccnt(0)
         , m_tombstone_cnt(0)
         , m_alloc_size(0) {
@@ -49,6 +48,7 @@ public:
                                                buffer.get_record_count() * 
                                                  sizeof(Wrapped<R>), 
                                                (byte**) &m_data);
+
         auto res = sorted_array_from_bufferview<R>(std::move(buffer), m_data, m_bf);
         m_reccnt = res.record_count;
         m_tombstone_cnt = res.tombstone_count;
@@ -132,7 +132,7 @@ public:
 
 
     size_t get_memory_usage() {
-        return m_pgm.size_in_bytes() + m_alloc_size;
+        return m_pgm.size_in_bytes();
     }
 
     size_t get_aux_memory_usage() {
diff --git a/include/shard/TrieSpline.h b/include/shard/TrieSpline.h
index 2a432e8..023390e 100644
--- a/include/shard/TrieSpline.h
+++ b/include/shard/TrieSpline.h
@@ -36,13 +36,12 @@ private:
 
 public:
     TrieSpline(BufferView<R> buffer)
-        : m_data(nullptr)
-        , m_reccnt(0)
+        : m_reccnt(0)
         , m_tombstone_cnt(0)
         , m_alloc_size(0)
         , m_max_key(0)
         , m_min_key(0)
-        , m_bf(new BloomFilter<R>(BF_FPR, buffer.get_tombstone_count(), BF_HASH_FUNCS))
+        , m_bf(nullptr)
     {
         m_alloc_size = psudb::sf_aligned_alloc(CACHELINE_SIZE, 
                                                buffer.get_record_count() * 
@@ -79,7 +78,6 @@ public:
         size_t tombstone_count = 0;
         auto cursors = build_cursor_vec<R, TrieSpline>(shards, &attemp_reccnt, &tombstone_count);
         
-        m_bf = new BloomFilter<R>(BF_FPR, tombstone_count, BF_HASH_FUNCS);
         m_alloc_size = psudb::sf_aligned_alloc(CACHELINE_SIZE, 
                                                attemp_reccnt * sizeof(Wrapped<R>),
                                                (byte **) &m_data);
@@ -107,7 +105,7 @@ public:
     }
 
     Wrapped<R> *point_lookup(const R &rec, bool filter=false) {
-        if (filter && !m_bf->lookup(rec)) {
+        if (filter && m_bf && !m_bf->lookup(rec)) {
             return nullptr;
         }
 
@@ -144,7 +142,7 @@ public:
 
 
     size_t get_memory_usage() {
-        return m_ts.GetSize() + m_alloc_size;
+        return m_ts.GetSize();
     }
 
     size_t get_aux_memory_usage() {
diff --git a/include/shard/VPTree.h b/include/shard/VPTree.h
index 62857ce..d5a2393 100644
--- a/include/shard/VPTree.h
+++ b/include/shard/VPTree.h
@@ -175,7 +175,7 @@ public:
     }
 
     size_t get_memory_usage() {
-        return m_node_cnt * sizeof(vpnode) + m_reccnt * sizeof(R*) + m_alloc_size;
+        return m_node_cnt * sizeof(vpnode) + m_reccnt * sizeof(R*);
     }
 
     size_t get_aux_memory_usage() {