summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--benchmarks/include/standard_benchmarks.h39
-rw-r--r--benchmarks/include/triespline_bsm.h31
-rw-r--r--benchmarks/vldb/ts_bsm_bench.cpp19
3 files changed, 78 insertions, 11 deletions
diff --git a/benchmarks/include/standard_benchmarks.h b/benchmarks/include/standard_benchmarks.h
index 76b5f7c..1261a4c 100644
--- a/benchmarks/include/standard_benchmarks.h
+++ b/benchmarks/include/standard_benchmarks.h
@@ -22,6 +22,19 @@
static size_t g_deleted_records = 0;
static double delete_proportion = 0.05;
+static volatile size_t total = 0;
+
+template<typename DE, typename QP, typename R>
+static void run_queries(DE *extension, DE *ghost, std::vector<QP> &queries) {
+ for (size_t i=0; i<queries.size(); i++) {
+ std::vector<R> res = extension->query(&queries[i]);
+ std::vector<R> negres = ghost->query(&queries[i]);
+ auto result = res[0].first - negres[0].first;
+ total = result;
+ }
+}
+
+
template<typename DE, typename QP, bool BSM=false>
static void run_queries(DE *extension, std::vector<QP> &queries) {
for (size_t i=0; i<queries.size(); i++) {
@@ -63,6 +76,7 @@ static void run_queries(DE *extension, std::vector<QP> &queries) {
fflush(stdout);
#endif
} else {
+ total = res.size();
#ifdef BENCH_PRINT_RESULTS
fprintf(stdout, "\n\n");
for (int i=res.size()-1; i>=0; i--) {
@@ -123,7 +137,6 @@ static void insert_records(psudb::bsm::BentleySaxe<R, DS, MDSP> *extension,
size_t start, size_t stop, std::vector<R> &records) {
psudb::progress_update(0, "Insert Progress");
- size_t reccnt = 0;
for (size_t i=start; i<stop; i++) {
extension->insert(records[i]);
}
@@ -132,6 +145,30 @@ static void insert_records(psudb::bsm::BentleySaxe<R, DS, MDSP> *extension,
}
+template<typename DS, typename R, bool MDSP=false>
+static void insert_records(psudb::bsm::BentleySaxe<R, DS, MDSP> *extension,
+ psudb::bsm::BentleySaxe<R, DS, MDSP> *ghost,
+ size_t start, size_t stop, std::vector<R> &records,
+ std::vector<size_t> &to_delete, size_t &delete_idx,
+ gsl_rng *rng) {
+
+ psudb::progress_update(0, "Insert Progress");
+ size_t reccnt = 0;
+ for (size_t i=start; i<stop; i++) {
+
+ extension->insert(records[i]);
+
+ if (gsl_rng_uniform(rng) <= delete_proportion && to_delete[delete_idx] <= i) {
+ ghost->insert(records[to_delete[delete_idx]]);
+ delete_idx++;
+ g_deleted_records++;
+ }
+
+ }
+
+}
+
+
template<typename DE, typename R>
static void insert_records(DE *structure, size_t start, size_t stop,
std::vector<R> &records, std::vector<size_t> &to_delete,
diff --git a/benchmarks/include/triespline_bsm.h b/benchmarks/include/triespline_bsm.h
index dfddc43..eaf1079 100644
--- a/benchmarks/include/triespline_bsm.h
+++ b/benchmarks/include/triespline_bsm.h
@@ -18,11 +18,19 @@ public:
public:
static BSMTrieSpline *build(std::vector<R> &records) {
+ if (records.size() == 0) {
+ return nullptr;
+ }
+
std::sort(records.begin(), records.end());
return new BSMTrieSpline(records);
}
static BSMTrieSpline *build_presorted(std::vector<R> &records) {
+ if (records.size() == 0) {
+ return nullptr;
+ }
+
return new BSMTrieSpline(records);
}
@@ -44,8 +52,9 @@ public:
size_t idx = lower_bound(parms->lower_bound);
size_t cnt = 0;
- while (idx < m_data.size() && m_data[idx].first < parms->upper_bound) {
+ while (idx < m_data.size() && m_data[idx].first <= parms->upper_bound) {
cnt++;
+ idx++;
}
rs.push_back({cnt, 0});
@@ -54,6 +63,10 @@ public:
}
std::vector<R> query_merge(std::vector<R> &rsa, std::vector<R> &rsb, void *parms) {
+ /* initialize rsa on the first merge */
+ if (rsa.size() == 0) {
+ rsa.push_back({0, 0});
+ }
rsa[0].first += rsb[0].first;
return std::move(rsa);
}
@@ -75,6 +88,10 @@ private:
m_min_key = m_data[0].first;
m_max_key = m_data[m_data.size() - 1].first;
+ if (m_data.size() < 50) {
+ return;
+ }
+
auto bldr = ts::Builder<K>(m_min_key, m_max_key, E);
for (size_t i=0; i<m_data.size(); i++) {
bldr.AddKey(m_data[i].first);
@@ -88,12 +105,14 @@ private:
size_t lower_bound(K key) {
if (m_data.size() == 0) {
return 1;
- } else if (m_data.size() == 1) {
- if (m_data[0].first < key) {
- return 1;
- } else {
- return 0;
+ } else if (m_data.size() < 50) {
+ for (size_t i=0; i<m_data.size(); i++) {
+ if (m_data[i].first >= key) {
+ return i;
+ }
}
+
+ return m_data.size();
}
auto bound = m_ts.GetSearchBound(key);
diff --git a/benchmarks/vldb/ts_bsm_bench.cpp b/benchmarks/vldb/ts_bsm_bench.cpp
index 941e3da..049fd35 100644
--- a/benchmarks/vldb/ts_bsm_bench.cpp
+++ b/benchmarks/vldb/ts_bsm_bench.cpp
@@ -37,26 +37,37 @@ int main(int argc, char **argv) {
std::string q_fname = std::string(argv[3]);
auto extension = new psudb::bsm::BentleySaxe<Rec, Shard>();
+ auto ghost = new psudb::bsm::BentleySaxe<Rec, Shard>();
gsl_rng *rng = gsl_rng_alloc(gsl_rng_mt19937);
auto data = read_sosd_file_pair<uint64_t, uint64_t>(d_fname, n);
- auto queries = read_range_queries<QP>(q_fname, .001);
+ std::vector<size_t> to_delete(n * delete_proportion);
+ size_t j=0;
+ for (size_t i=0; i<data.size() && j<to_delete.size(); i++) {
+ if (gsl_rng_uniform(rng) <= delete_proportion) {
+ to_delete[j++] = i;
+ }
+ }
+ auto queries = read_range_queries<QP>(q_fname, .0001);
/* warmup structure w/ 10% of records */
size_t warmup = .1 * n;
- insert_records<Shard, Rec>(extension, 0, warmup, data);
+ size_t delete_idx = 0;
+ insert_records<Shard, Rec>(extension, ghost, 0, warmup, data, to_delete,
+ delete_idx, rng);
TIMER_INIT();
TIMER_START();
- insert_records<Shard, Rec>(extension, warmup, data.size(), data);
+ insert_records<Shard, Rec>(extension, ghost, warmup, data.size(), data,
+ to_delete, delete_idx, rng);
TIMER_STOP();
auto insert_latency = TIMER_RESULT();
size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9);
TIMER_START();
- run_queries<Ext, QP, true>(extension, queries);
+ run_queries<Ext, QP, Rec>(extension, ghost, queries);
TIMER_STOP();
auto query_latency = TIMER_RESULT() / queries.size();