summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitmodules3
-rw-r--r--benchmarks/include/standard_benchmarks.h18
-rw-r--r--benchmarks/irs_bench.cpp15
-rw-r--r--benchmarks/pgm_bench.cpp15
-rw-r--r--benchmarks/ts_bench.cpp21
-rw-r--r--benchmarks/vptree_bench.cpp15
m---------external/hat-trie0
-rw-r--r--include/framework/DynamicExtension.h4
-rw-r--r--include/framework/structure/ExtensionStructure.h2
-rw-r--r--include/shard/Alias.h2
-rw-r--r--include/shard/AugBTree.h2
-rw-r--r--include/shard/FSTrie.h8
-rw-r--r--include/shard/ISAMTree.h14
-rw-r--r--include/shard/PGM.h6
-rw-r--r--include/shard/TrieSpline.h10
-rw-r--r--include/shard/VPTree.h2
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() {