From 4a1dde3148e0e84b47c884bc0bb69c60678b4558 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Mon, 22 Apr 2024 15:09:07 -0400 Subject: Benchmark update+reorganization The Alex benchmark isn't updated yet. --- CMakeLists.txt | 111 +++++++++++------ benchmarks/include/benchmark_types.h | 5 +- benchmarks/include/standard_benchmarks.h | 69 +++++++++-- benchmarks/irs_bench.cpp | 97 --------------- benchmarks/pgm_bench.cpp | 94 -------------- benchmarks/string_insertion_tput.cpp | 32 ++--- benchmarks/ts_bench.cpp | 94 -------------- benchmarks/ts_bsm_bench.cpp | 70 ----------- benchmarks/ts_mdsp_bench.cpp | 70 ----------- benchmarks/vldb/alex_bench.cpp | 205 +++++++++++++++++++++++++++++++ benchmarks/vldb/btree_bench.cpp | 90 ++++++++++++++ benchmarks/vldb/dynamic_pgm_bench.cpp | 77 ++++++++++++ benchmarks/vldb/irs_bench.cpp | 97 +++++++++++++++ benchmarks/vldb/mtree_bench.cpp | 80 ++++++++++++ benchmarks/vldb/pgm_bench.cpp | 94 ++++++++++++++ benchmarks/vldb/ts_bench.cpp | 94 ++++++++++++++ benchmarks/vldb/ts_bsm_bench.cpp | 70 +++++++++++ benchmarks/vldb/ts_mdsp_bench.cpp | 70 +++++++++++ benchmarks/vldb/vptree_bench.cpp | 100 +++++++++++++++ benchmarks/vptree_bench.cpp | 100 --------------- 20 files changed, 1123 insertions(+), 596 deletions(-) delete mode 100644 benchmarks/irs_bench.cpp delete mode 100644 benchmarks/pgm_bench.cpp delete mode 100644 benchmarks/ts_bench.cpp delete mode 100644 benchmarks/ts_bsm_bench.cpp delete mode 100644 benchmarks/ts_mdsp_bench.cpp create mode 100644 benchmarks/vldb/alex_bench.cpp create mode 100644 benchmarks/vldb/btree_bench.cpp create mode 100644 benchmarks/vldb/dynamic_pgm_bench.cpp create mode 100644 benchmarks/vldb/irs_bench.cpp create mode 100644 benchmarks/vldb/mtree_bench.cpp create mode 100644 benchmarks/vldb/pgm_bench.cpp create mode 100644 benchmarks/vldb/ts_bench.cpp create mode 100644 benchmarks/vldb/ts_bsm_bench.cpp create mode 100644 benchmarks/vldb/ts_mdsp_bench.cpp create mode 100644 benchmarks/vldb/vptree_bench.cpp delete mode 100644 benchmarks/vptree_bench.cpp diff --git a/CMakeLists.txt b/CMakeLists.txt index c62085f..8e6cdfc 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -11,7 +11,8 @@ project("Practical Dynamic Extension" VERSION 0.1.0) set(debug false) set(tests True) -set(bench true) +set(bench false) +set(vldb_bench true) set(CMAKE_EXPORT_COMPILE_COMMANDS ON) @@ -147,96 +148,136 @@ if (tests) target_include_directories(louds_tests PRIVATE include external/psudb-common/cpp/include external/PLEX/include external/fast_succinct_trie/include external/louds-patricia) endif() +if (vldb_bench) + set(CMAKE_RUNTIME_OUTPUT_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}/bin/benchmarks") + + add_executable(irs_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/irs_bench.cpp) + target_link_libraries(irs_bench PUBLIC gsl pthread atomic) + target_include_directories(irs_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(irs_bench PUBLIC -mcx16) + + add_executable(vptree_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/vptree_bench.cpp) + target_link_libraries(vptree_bench PUBLIC gsl pthread atomic) + target_include_directories(vptree_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(vptree_bench PUBLIC -mcx16) + + add_executable(ts_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/ts_bench.cpp) + target_link_libraries(ts_bench PUBLIC gsl pthread atomic) + target_include_directories(ts_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(ts_bench PUBLIC -mcx16) + + add_executable(ts_bsm_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/ts_bsm_bench.cpp) + target_link_libraries(ts_bsm_bench PUBLIC gsl pthread atomic) + target_include_directories(ts_bsm_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(ts_bsm_bench PUBLIC -mcx16) + + add_executable(ts_mdsp_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/ts_mdsp_bench.cpp) + target_link_libraries(ts_mdsp_bench PUBLIC gsl pthread atomic) + target_include_directories(ts_mdsp_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(ts_mdsp_bench PUBLIC -mcx16) + + add_executable(pgm_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/pgm_bench.cpp) + target_link_libraries(pgm_bench PUBLIC gsl pthread atomic gomp) + target_include_directories(pgm_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(pgm_bench PUBLIC -mcx16) + target_compile_options(pgm_bench PUBLIC -fopenmp) + + add_executable(dynamic_pgm_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/dynamic_pgm_bench.cpp) + target_link_libraries(dynamic_pgm_bench PUBLIC gsl pthread atomic gomp) + target_include_directories(dynamic_pgm_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(dynamic_pgm_bench PUBLIC -mcx16) + target_compile_options(dynamic_pgm_bench PUBLIC -fopenmp) + + add_executable(btree_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/btree_bench.cpp) + target_link_libraries(btree_bench PUBLIC gsl pthread atomic gomp) + target_include_directories(btree_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(btree_bench PUBLIC -mcx16) + target_compile_options(btree_bench PUBLIC -fopenmp) + + #add_executable(alex_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/alex_bench.cpp) + #target_link_libraries(alex_bench PUBLIC gsl pthread atomic gomp) + #target_include_directories(alex_bench PRIVATE include external/benchmarks/include external/psudb-common/cpp/include external/alex/src/core/) + #target_link_options(alex_bench PUBLIC -mcx16) + #target_compile_options(alex_bench PUBLIC -fopenmp -std=c++17) + + add_executable(mtree_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vldb/mtree_bench.cpp) + target_link_libraries(mtree_bench PUBLIC gsl pthread atomic gomp) + target_include_directories(mtree_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) + target_link_options(mtree_bench PUBLIC -mcx16) + target_compile_options(mtree_bench PUBLIC -fopenmp) +endif() + + + if (bench) set(CMAKE_RUNTIME_OUTPUT_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}/bin/benchmarks") add_executable(reconstruction_interference ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/reconstruction_interference.cpp) target_link_libraries(reconstruction_interference PUBLIC gsl pthread atomic) target_link_options(reconstruction_interference PUBLIC -mcx16) - target_include_directories(reconstruction_interference PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + target_include_directories(reconstruction_interference PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) add_executable(insertion_tput ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/insertion_tput.cpp) target_link_libraries(insertion_tput PUBLIC gsl pthread atomic) - target_include_directories(insertion_tput PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + target_include_directories(insertion_tput PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) target_link_options(insertion_tput PUBLIC -mcx16) add_executable(string_insertion_tput ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/string_insertion_tput.cpp) target_link_libraries(string_insertion_tput PUBLIC gsl pthread atomic) - target_include_directories(string_insertion_tput PRIVATE include external external/fast_succinct_trie/include external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + target_include_directories(string_insertion_tput PRIVATE include external external/fast_succinct_trie/include external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) target_link_options(string_insertion_tput PUBLIC -mcx16) add_executable(louds_insertion_tput ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/louds_insertion_tput.cpp) target_link_libraries(louds_insertion_tput PUBLIC gsl pthread atomic) - target_include_directories(louds_insertion_tput PRIVATE include external external/fast_succinct_trie/include external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include external/louds-patricia) + target_include_directories(louds_insertion_tput PRIVATE include external external/fast_succinct_trie/include external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include external/louds-patricia) target_link_options(louds_insertion_tput PUBLIC -mcx16) add_executable(query_workload_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/query_workload_bench.cpp) target_link_libraries(query_workload_bench PUBLIC gsl pthread atomic) - target_include_directories(query_workload_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + target_include_directories(query_workload_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) target_link_options(query_workload_bench PUBLIC -mcx16) add_executable(insert_query_tput ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/insert_query_tput.cpp) target_link_libraries(insert_query_tput PUBLIC gsl pthread atomic) - target_include_directories(insert_query_tput PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + target_include_directories(insert_query_tput PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) target_link_options(insert_query_tput PUBLIC -mcx16) add_executable(poplar_trie ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/poplar_trie.cpp) target_link_libraries(poplar_trie PUBLIC gsl pthread atomic) - target_include_directories(poplar_trie PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include external/poplar-trie/include) + target_include_directories(poplar_trie PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include external/poplar-trie/include) target_link_options(poplar_trie PUBLIC -mcx16) add_executable(hat_trie ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/hat_trie.cpp) target_link_libraries(hat_trie PUBLIC gsl pthread atomic) target_include_directories(hat_trie PRIVATE include external - external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include external/hat-trie/include/tsl) + external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include external/hat-trie/include/tsl) target_link_options(hat_trie PUBLIC -mcx16) add_executable(cedar_trie ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/cedar_trie.cpp) target_link_libraries(cedar_trie PUBLIC gsl pthread atomic) - target_include_directories(cedar_trie PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include external/hat-trie/include/tsl) + target_include_directories(cedar_trie PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include external/hat-trie/include/tsl) target_link_options(cedar_trie PUBLIC -mcx16) #add_executable(btree_insert_query_tput ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/btree_insert_query_tput.cpp) #target_link_libraries(btree_insert_query_tput PUBLIC gsl cblas pthread atomic) - #target_include_directories(btree_insert_query_tput PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + #target_include_directories(btree_insert_query_tput PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) #target_link_options(btree_insert_query_tput PUBLIC -mcx16) add_executable(watermark_testing ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/watermark_testing.cpp) target_link_libraries(watermark_testing PUBLIC gsl pthread atomic) - target_include_directories(watermark_testing PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + target_include_directories(watermark_testing PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) target_link_options(watermark_testing PUBLIC -mcx16) - add_executable(irs_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/irs_bench.cpp) - target_link_libraries(irs_bench PUBLIC gsl pthread atomic) - target_include_directories(irs_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) - target_link_options(irs_bench PUBLIC -mcx16) - - add_executable(vptree_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/vptree_bench.cpp) - target_link_libraries(vptree_bench PUBLIC gsl pthread atomic) - target_include_directories(vptree_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) - target_link_options(vptree_bench PUBLIC -mcx16) - - add_executable(ts_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/ts_bench.cpp) - target_link_libraries(ts_bench PUBLIC gsl pthread atomic) - target_include_directories(ts_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) - target_link_options(ts_bench PUBLIC -mcx16) - - add_executable(pgm_bench ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/pgm_bench.cpp) - target_link_libraries(pgm_bench PUBLIC gsl pthread atomic gomp) - target_include_directories(pgm_bench PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) - target_link_options(pgm_bench PUBLIC -mcx16) - target_compile_options(pgm_bench PUBLIC -fopenmp) - #add_executable(static_dynamic_comp ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/static_dynamic_comp.cpp) #target_link_libraries(static_dynamic_comp PUBLIC gsl cblas pthread atomic) - #target_include_directories(static_dynamic_comp PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + #target_include_directories(static_dynamic_comp PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) #target_link_options(static_dynamic_comp PUBLIC -mcx16) add_executable(insert_tail_latency ${CMAKE_CURRENT_SOURCE_DIR}/benchmarks/insert_tail_latency.cpp) target_link_libraries(insert_tail_latency PUBLIC gsl pthread atomic) - target_include_directories(insert_tail_latency PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include bench/include external/psudb-common/cpp/include) + target_include_directories(insert_tail_latency PRIVATE include external external/m-tree/cpp external/PGM-index/include external/PLEX/include benchmarks/include external/psudb-common/cpp/include) target_link_options(insert_tail_latency PUBLIC -mcx16) endif() diff --git a/benchmarks/include/benchmark_types.h b/benchmarks/include/benchmark_types.h index fcdeac6..13964e8 100644 --- a/benchmarks/include/benchmark_types.h +++ b/benchmarks/include/benchmark_types.h @@ -3,8 +3,9 @@ #include #include "psu-ds/BTree.h" #include "framework/interface/Record.h" +#include "pgm/pgm_index_dynamic.hpp" -/* TLX BTree definitions*/ +/* BTree definitions*/ template struct btree_record { K key; @@ -50,3 +51,5 @@ struct euclidean_distance { typedef mt::mtree MTree; #endif +typedef pgm::DynamicPGMIndex> PGM; + diff --git a/benchmarks/include/standard_benchmarks.h b/benchmarks/include/standard_benchmarks.h index 74bf93f..aaef679 100644 --- a/benchmarks/include/standard_benchmarks.h +++ b/benchmarks/include/standard_benchmarks.h @@ -14,6 +14,7 @@ #include "framework/DynamicExtension.h" #include "framework/interface/Query.h" +#include "query/irs.h" #include "psu-util/progress.h" #include "benchmark_types.h" #include "psu-util/bentley-saxe.h" @@ -24,15 +25,41 @@ static double delete_proportion = 0.05; template static void run_queries(DE *extension, std::vector &queries) { for (size_t i=0; iquery(q); - if constexpr (!BSM) { - auto r = res.get(); + if constexpr (std::is_same_v) { + std::vector result; + auto res = extension->get_nearest_by_limit(queries[i].point, queries[i].k); + + auto itr = res.begin(); + while (itr != res.end()) { + result.emplace_back(itr->data); + itr++; + } + } else if constexpr (std::is_same_v) { + size_t tot = 0; + auto ptr = extension->find(queries[i].lower_bound); + while (ptr != extension->end() && ptr->first <= queries[i].upper_bound) { + tot++; + ++ptr; + } + } else { + auto res = extension->query(&queries[i]); + if constexpr (!BSM) { + auto r = res.get(); + } } } } +template +static void run_btree_queries(BenchBTree *btree, std::vector> &queries) { + std::vector sample_set; + sample_set.reserve(queries[0].sample_size); + + for (size_t i=0; irange_sample(queries[i].lower_bound, queries[i].upper_bound, queries[i].sample_size, sample_set, queries[i].rng); + } +} + template static void run_static_queries(S *shard, std::vector &queries) { @@ -68,26 +95,42 @@ static void insert_records(psudb::bsm::BentleySaxe *extension, } -template -static void insert_records(DE *extension, size_t start, size_t stop, +template +static void insert_records(DE *structure, size_t start, size_t stop, std::vector &records, std::vector &to_delete, size_t &delete_idx, bool delete_records, gsl_rng *rng) { psudb::progress_update(0, "Insert Progress"); size_t reccnt = 0; for (size_t i=start; iinsert(records[i])) { - psudb::progress_update((double) i / (double)(stop - start), "Insert Progress"); - usleep(1); + + if constexpr (std::is_same_v) { + structure->insert(records[i]); + } else if constexpr (std::is_same_v) { + structure->add(records[i]); + } else if constexpr (std::is_same_v) { + structure->insert_or_assign(records[i].key, records[i].value); + } else { + while (!structure->insert(records[i])) { + psudb::progress_update((double) i / (double)(stop - start), "Insert Progress"); + usleep(1); + } } if (delete_records && gsl_rng_uniform(rng) <= delete_proportion && to_delete[delete_idx] <= i) { - while (!extension->erase(records[to_delete[delete_idx]])) { - usleep(1); + if constexpr (std::is_same_v) { + structure->erase_one(records[to_delete[delete_idx]].key); + } else if constexpr (std::is_same_v) { + structure->remove(records[to_delete[delete_idx]]); + } else if constexpr (std::is_same_v) { + structure->erase(records[to_delete[delete_idx]].key); + } else { + while (!structure->erase(records[to_delete[delete_idx]])) { + usleep(1); + } } - delete_idx++; g_deleted_records++; } diff --git a/benchmarks/irs_bench.cpp b/benchmarks/irs_bench.cpp deleted file mode 100644 index 36d88f6..0000000 --- a/benchmarks/irs_bench.cpp +++ /dev/null @@ -1,97 +0,0 @@ -/* - * - */ - -#define ENABLE_TIMER - -#include "framework/DynamicExtension.h" -#include "shard/ISAMTree.h" -#include "query/irs.h" -#include "framework/interface/Record.h" -#include "include/file_util.h" - -#include - -#include "psu-util/timer.h" -#include "include/standard_benchmarks.h" - - -typedef de::Record Rec; -typedef de::ISAMTree Shard; -typedef de::irs::Query Q; -typedef de::DynamicExtension Ext; -typedef de::irs::Parms QP; - -void usage(char *progname) { - fprintf(stderr, "%s reccnt datafile queryfile", progname); -} - -int main(int argc, char **argv) { - - if (argc < 4) { - usage(argv[0]); - exit(EXIT_FAILURE); - } - - size_t n = atol(argv[1]); - std::string d_fname = std::string(argv[2]); - std::string q_fname = std::string(argv[3]); - - auto extension = new Ext(12000, 12001, 8, 0, 64); - gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); - - auto data = read_sosd_file(d_fname, n); - std::vector to_delete(n * delete_proportion); - size_t j=0; - for (size_t i=0; i(q_fname, .001); - for (auto &q : queries) { - q.sample_size = 1000; - q.rng = rng; - } - - /* warmup structure w/ 10% of records */ - size_t warmup = .3 * n; - size_t delete_idx = 0; - insert_records(extension, 0, warmup, data, to_delete, delete_idx, false, rng); - - extension->await_next_epoch(); - - TIMER_INIT(); - - TIMER_START(); - insert_records(extension, warmup, data.size(), data, to_delete, delete_idx, true, 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(extension, queries); - TIMER_STOP(); - - auto query_latency = TIMER_RESULT() / queries.size(); - - auto shard = extension->create_static_structure(); - - TIMER_START(); - run_static_queries(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; - fflush(stderr); -} - diff --git a/benchmarks/pgm_bench.cpp b/benchmarks/pgm_bench.cpp deleted file mode 100644 index e0baab4..0000000 --- a/benchmarks/pgm_bench.cpp +++ /dev/null @@ -1,94 +0,0 @@ -/* - * - */ - -#define ENABLE_TIMER - -#include - -#include "framework/DynamicExtension.h" -#include "shard/PGM.h" -#include "query/rangecount.h" -#include "framework/interface/Record.h" -#include "include/file_util.h" -#include "include/standard_benchmarks.h" - -#include - -#include "psu-util/timer.h" - - -typedef de::Record Rec; -typedef de::PGM Shard; -typedef de::rc::Query Q; -typedef de::DynamicExtension Ext; -typedef de::rc::Parms QP; - -void usage(char *progname) { - fprintf(stderr, "%s reccnt datafile queryfile", progname); -} - -int main(int argc, char **argv) { - - if (argc < 4) { - usage(argv[0]); - exit(EXIT_FAILURE); - } - - size_t n = atol(argv[1]); - std::string d_fname = std::string(argv[2]); - std::string q_fname = std::string(argv[3]); - - auto extension = new Ext(12000, 12001, 8, 0, 64); - gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); - - auto data = read_sosd_file(d_fname, n); - std::vector to_delete(n * delete_proportion); - size_t j=0; - for (size_t i=0; i(q_fname, .001); - - /* warmup structure w/ 10% of records */ - size_t warmup = .1 * n; - size_t delete_idx = 0; - insert_records(extension, 0, warmup, data, to_delete, delete_idx, false, rng); - - extension->await_next_epoch(); - - TIMER_INIT(); - - TIMER_START(); - insert_records(extension, warmup, data.size(), data, to_delete, delete_idx, true, 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(extension, queries); - TIMER_STOP(); - - auto query_latency = TIMER_RESULT() / queries.size(); - - auto shard = extension->create_static_structure(); - - TIMER_START(); - run_static_queries(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; - fflush(stderr); -} - diff --git a/benchmarks/string_insertion_tput.cpp b/benchmarks/string_insertion_tput.cpp index f4a519a..8fa7f44 100644 --- a/benchmarks/string_insertion_tput.cpp +++ b/benchmarks/string_insertion_tput.cpp @@ -69,7 +69,13 @@ int main(int argc, char **argv) { fprintf(stderr, "Finished reading from file.\n"); } - auto extension = new Ext(1000, 12000, 8); + std::vector scale_factors = {2, 4, 6, 8, 10, 12}; + std::vector buffer_sizes = {1000, 2000, 5000, 10000, 12000, 15000}; + + for (auto &sf : scale_factors) { + for (auto &bf_sz : buffer_sizes) { + + auto extension = new Ext(bf_sz, bf_sz, sf); TIMER_INIT(); TIMER_START(); @@ -97,33 +103,15 @@ int main(int argc, char **argv) { auto query_time = TIMER_RESULT(); - - auto shard = extension->create_static_structure(); - TIMER_START(); - for (size_t i=0; i parms = {strings[j].get()}; - - auto res = Q::query(shard, nullptr, &parms); - - if (res[0].rec.value != j) { - fprintf(stderr, "static:\t%ld %ld %s\n", res[0].rec.value, j, strings[j].get()); - } - } - TIMER_STOP(); - - auto shard_query_time = TIMER_RESULT(); - double i_tput = (double) n / (double) total_time * 1e9; size_t q_lat = query_time / m; - size_t s_q_lat = shard_query_time / m; - fprintf(stdout, "%ld\t\t%lf\t%ld\t%ld\t%ld\t%ld\n", extension->get_record_count(), - i_tput, q_lat, s_q_lat, extension->get_memory_usage(), shard->get_memory_usage()); + fprintf(stdout, "%ld\t%ld\t%ld\t%lf\t%ld\t%ld\n", extension->get_record_count(), + bf_sz, sf, i_tput, q_lat, extension->get_memory_usage()); delete extension; - delete shard; + }} fflush(stderr); } diff --git a/benchmarks/ts_bench.cpp b/benchmarks/ts_bench.cpp deleted file mode 100644 index 3d44ac5..0000000 --- a/benchmarks/ts_bench.cpp +++ /dev/null @@ -1,94 +0,0 @@ -/* - * - */ - -#define ENABLE_TIMER - -#include - -#include "framework/DynamicExtension.h" -#include "shard/TrieSpline.h" -#include "query/rangecount.h" -#include "framework/interface/Record.h" -#include "include/file_util.h" -#include "include/standard_benchmarks.h" - -#include - -#include "psu-util/timer.h" - - -typedef de::Record Rec; -typedef de::TrieSpline Shard; -typedef de::rc::Query Q; -typedef de::DynamicExtension Ext; -typedef de::rc::Parms QP; - -void usage(char *progname) { - fprintf(stderr, "%s reccnt datafile queryfile", progname); -} - -int main(int argc, char **argv) { - - if (argc < 4) { - usage(argv[0]); - exit(EXIT_FAILURE); - } - - size_t n = atol(argv[1]); - std::string d_fname = std::string(argv[2]); - std::string q_fname = std::string(argv[3]); - - auto extension = new Ext(12000, 12001, 8, 0, 64); - gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); - - auto data = read_sosd_file(d_fname, n); - std::vector to_delete(n * delete_proportion); - size_t j=0; - for (size_t i=0; i(q_fname, .001); - - /* warmup structure w/ 10% of records */ - size_t warmup = .1 * n; - size_t delete_idx = 0; - insert_records(extension, 0, warmup, data, to_delete, delete_idx, false, rng); - - extension->await_next_epoch(); - - TIMER_INIT(); - - TIMER_START(); - insert_records(extension, warmup, data.size(), data, to_delete, delete_idx, true, 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(extension, queries); - TIMER_STOP(); - - auto query_latency = TIMER_RESULT() / queries.size(); - - auto shard = extension->create_static_structure(); - - TIMER_START(); - run_static_queries(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; - fflush(stderr); -} - diff --git a/benchmarks/ts_bsm_bench.cpp b/benchmarks/ts_bsm_bench.cpp deleted file mode 100644 index 366abce..0000000 --- a/benchmarks/ts_bsm_bench.cpp +++ /dev/null @@ -1,70 +0,0 @@ -/* - * - */ - -#define ENABLE_TIMER - -#include - -#include "include/triespline_bsm.h" -#include "psu-util/bentley-saxe.h" -#include "framework/interface/Record.h" -#include "include/file_util.h" -#include "query/rangecount.h" -#include "psu-util/timer.h" -#include "include/standard_benchmarks.h" - -typedef std::pair Rec; -typedef de::Record FRec; - -typedef BSMTrieSpline Shard; -typedef de::rc::Parms QP; -typedef psudb::bsm::BentleySaxe Ext; - -void usage(char *progname) { - fprintf(stderr, "%s reccnt datafile queryfile", progname); -} - -int main(int argc, char **argv) { - - if (argc < 4) { - usage(argv[0]); - exit(EXIT_FAILURE); - } - - size_t n = atol(argv[1]); - std::string d_fname = std::string(argv[2]); - std::string q_fname = std::string(argv[3]); - - auto extension = new psudb::bsm::BentleySaxe(); - gsl_rng *rng = gsl_rng_alloc(gsl_rng_mt19937); - - auto data = read_sosd_file_pair(d_fname, n); - auto queries = read_range_queries(q_fname, .001); - - /* warmup structure w/ 10% of records */ - size_t warmup = .1 * n; - insert_records(extension, 0, warmup, data); - - TIMER_INIT(); - - TIMER_START(); - insert_records(extension, warmup, data.size(), data); - TIMER_STOP(); - - auto insert_latency = TIMER_RESULT(); - size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9); - - TIMER_START(); - run_queries(extension, queries); - TIMER_STOP(); - - auto query_latency = TIMER_RESULT() / queries.size(); - - fprintf(stdout, "%ld\t%ld\n", insert_throughput, query_latency); - - gsl_rng_free(rng); - delete extension; - fflush(stderr); -} - diff --git a/benchmarks/ts_mdsp_bench.cpp b/benchmarks/ts_mdsp_bench.cpp deleted file mode 100644 index 5e5001d..0000000 --- a/benchmarks/ts_mdsp_bench.cpp +++ /dev/null @@ -1,70 +0,0 @@ -/* - * - */ - -#define ENABLE_TIMER - -#include - -#include "include/triespline_bsm.h" -#include "psu-util/bentley-saxe.h" -#include "framework/interface/Record.h" -#include "include/file_util.h" -#include "query/rangecount.h" -#include "psu-util/timer.h" -#include "include/standard_benchmarks.h" - -typedef std::pair Rec; -typedef de::Record FRec; - -typedef BSMTrieSpline Shard; -typedef de::rc::Parms QP; -typedef psudb::bsm::BentleySaxe Ext; - -void usage(char *progname) { - fprintf(stderr, "%s reccnt datafile queryfile", progname); -} - -int main(int argc, char **argv) { - - if (argc < 4) { - usage(argv[0]); - exit(EXIT_FAILURE); - } - - size_t n = atol(argv[1]); - std::string d_fname = std::string(argv[2]); - std::string q_fname = std::string(argv[3]); - - auto extension = new psudb::bsm::BentleySaxe(); - gsl_rng *rng = gsl_rng_alloc(gsl_rng_mt19937); - - auto data = read_sosd_file_pair(d_fname, n); - auto queries = read_range_queries(q_fname, .001); - - /* warmup structure w/ 10% of records */ - size_t warmup = .1 * n; - insert_records(extension, 0, warmup, data); - - TIMER_INIT(); - - TIMER_START(); - insert_records(extension, warmup, data.size(), data); - TIMER_STOP(); - - auto insert_latency = TIMER_RESULT(); - size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9); - - TIMER_START(); - run_queries(extension, queries); - TIMER_STOP(); - - auto query_latency = TIMER_RESULT() / queries.size(); - - fprintf(stdout, "%ld\t%ld\n", insert_throughput, query_latency); - - gsl_rng_free(rng); - delete extension; - fflush(stderr); -} - diff --git a/benchmarks/vldb/alex_bench.cpp b/benchmarks/vldb/alex_bench.cpp new file mode 100644 index 0000000..f75afa6 --- /dev/null +++ b/benchmarks/vldb/alex_bench.cpp @@ -0,0 +1,205 @@ +#include "alex.h" +#include "include/standalone_utility.h" + +typedef uint64_t key_type; +typedef uint64_t value_type; + +typedef alex::Alex Alex; + +struct record { + key_type key; + value_type value; +}; + +struct query { + key_type lower_bound; + key_type upper_bound; +}; + +template +static bool build_insert_vec(std::fstream &file, std::vector &vec, size_t n, + double delete_prop, std::vector &to_delete, bool binary=false) { + vec.clear(); + for (size_t i=0; i to_delete, bool progress=true, bool binary=false) { + size_t batch = std::min(.1 * count, 25000.0); + + std::pair *insert_vec = new std::pair[count]; + Alex *alex = new Alex(); + + size_t cnt = 0; + record rec; + while (cnt < count && next_record(file, rec)) { + insert_vec[cnt] = {rec.key, rec.value}; + cnt++; + } + + std::sort(insert_vec, insert_vec + count); + + alex->bulk_load(insert_vec, count); + delete[] insert_vec; + + return alex; +} + + +static void alex_rq_insert(Alex &alex, std::fstream &file, size_t insert_cnt, double delete_prop, std::vector &to_delete, bool binary=false) { + size_t delete_cnt = insert_cnt * delete_prop; + + size_t applied_deletes = 0; + size_t applied_inserts = 0; + + size_t BATCH=1000; + + std::vector insert_vec; + std::vector delete_vec; + insert_vec.reserve(BATCH); + delete_vec.reserve(BATCH*delete_prop); + + size_t delete_idx = 0; + + bool continue_benchmark = true; + + size_t total_time = 0; + + while (applied_inserts < insert_cnt && continue_benchmark) { + continue_benchmark = build_insert_vec(file, insert_vec, BATCH, delete_prop, to_delete, binary); + progress_update((double) applied_inserts / (double) insert_cnt, "inserting:"); + if (applied_deletes < delete_cnt) { + build_delete_vec(to_delete, delete_vec, BATCH*delete_prop); + delete_idx = 0; + } + + if (insert_vec.size() == 0) { + break; + } + + auto insert_start = std::chrono::high_resolution_clock::now(); + for (size_t i=0; i(insert_stop - insert_start).count(); + } + + progress_update(1.0, "inserting:"); + + size_t throughput = (((double) (applied_inserts + applied_deletes) / (double) total_time) * 1e9); + + fprintf(stdout, "%ld\t", throughput); +} + + + +static void alex_rq_bench(Alex &alex, std::vector queries, size_t trial_cnt=1) +{ + char progbuf[25]; + sprintf(progbuf, "sampling:"); + + size_t batch_size = 100; + size_t batches = trial_cnt / batch_size; + size_t total_time = 0; + + std::vector result_set; + + for (int i=0; i(stop - start).count(); + } + + size_t latency = total_time / (trial_cnt * queries.size()); + + fprintf(stdout, "%ld\t", latency); +} + +int main(int argc, char **argv) +{ + if (argc < 5) { + fprintf(stderr, "Usage: alex_rq_bench \n"); + exit(EXIT_FAILURE); + } + + std::string filename = std::string(argv[1]); + size_t record_count = atol(argv[2]); + double delete_prop = atof(argv[3]); + std::string qfilename = std::string(argv[4]); + + size_t buffer_cap = 12000; + size_t scale_factor = 6; + double max_delete_prop = delete_prop; + bool use_osm = false; + + double insert_batch = 0.8; + + init_bench_env(record_count, true, use_osm); + auto queries = read_range_queries(qfilename, .0001); + + std::fstream datafile; + datafile.open(filename, std::ios::in | std::ios::binary); + + std::vector to_delete; + + // warm up the tree with initial_insertions number of initially inserted + // records + size_t warmup_cnt = insert_batch * record_count; + auto alex = warmup(datafile, warmup_cnt, delete_prop, to_delete, true, true); + + fprintf(stderr, "Size: %ld\n", alex->size()); + size_t insert_cnt = record_count - warmup_cnt; + + alex_rq_insert(*alex, datafile, insert_cnt, delete_prop, to_delete, true); + size_t memory_usage = alex->model_size() + alex->data_size(); + + fprintf(stderr, "Size: %ld\n", alex->size()); + fprintf(stdout, "%ld\t", memory_usage); + + alex_rq_bench(*alex, queries); + fprintf(stdout, "\n"); + + delete_bench_env(); + delete alex; + fflush(stdout); + fflush(stderr); + + exit(EXIT_SUCCESS); +} diff --git a/benchmarks/vldb/btree_bench.cpp b/benchmarks/vldb/btree_bench.cpp new file mode 100644 index 0000000..12107c6 --- /dev/null +++ b/benchmarks/vldb/btree_bench.cpp @@ -0,0 +1,90 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include "shard/ISAMTree.h" +#include "query/irs.h" +#include "framework/interface/Record.h" +#include "file_util.h" +#include "benchmark_types.h" + +#include + +#include "psu-util/timer.h" +#include "standard_benchmarks.h" +#include "psu-ds/BTree.h" + +typedef btree_record Rec; + +typedef de::ISAMTree Shard; +typedef de::irs::Query Q; +typedef de::irs::Parms QP; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + auto btree = BenchBTree(); + + gsl_rng *rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto data = read_sosd_file(d_fname, n); + std::vector to_delete(n * delete_proportion); + size_t j=0; + for (size_t i=0; i(q_fname, .001); + for (auto &q : queries) { + q.sample_size = 1000; + q.rng = rng; + } + + /* warmup structure w/ 10% of records */ + size_t warmup = .3 * n; + size_t delete_idx = 0; + insert_records(&btree, 0, warmup, data, to_delete, delete_idx, false, rng); + + TIMER_INIT(); + + TIMER_START(); + insert_records(&btree, warmup, data.size(), data, to_delete, delete_idx, true, rng); + TIMER_STOP(); + + auto insert_latency = TIMER_RESULT(); + size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9); + + TIMER_START(); + run_btree_queries(&btree, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + auto btree_size = btree.get_stats().inner_nodes * psudb::btree_default_traits::inner_slots * (sizeof(int64_t) + sizeof(void*)); + + /* account for memory wasted on gaps in the structure */ + btree_size += btree.get_stats().leaves * psudb::btree_default_traits::leaf_slots * sizeof(Rec); + btree_size -= btree.size() * sizeof(Rec); + + fprintf(stdout, "%ld\t%ld\t%ld\n", insert_throughput, query_latency, btree_size); + + gsl_rng_free(rng); + fflush(stderr); +} + diff --git a/benchmarks/vldb/dynamic_pgm_bench.cpp b/benchmarks/vldb/dynamic_pgm_bench.cpp new file mode 100644 index 0000000..249bc92 --- /dev/null +++ b/benchmarks/vldb/dynamic_pgm_bench.cpp @@ -0,0 +1,77 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include + +#include "query/rangecount.h" +#include "framework/interface/Record.h" +#include "file_util.h" +#include "standard_benchmarks.h" +#include + +#include "psu-util/timer.h" + + +typedef de::Record Rec; +typedef de::rc::Parms QP; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + std::vector> tmp_data; + PGM pgm(tmp_data.begin(), tmp_data.end()); + gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto data = read_sosd_file(d_fname, n); + std::vector to_delete(n * delete_proportion); + size_t j=0; + for (size_t i=0; i(q_fname, .001); + + /* warmup structure w/ 10% of records */ + size_t warmup = .1 * n; + size_t delete_idx = 0; + insert_records(&pgm, 0, warmup, data, to_delete, delete_idx, false, rng); + + TIMER_INIT(); + + TIMER_START(); + insert_records(&pgm, warmup, data.size(), data, to_delete, delete_idx, true, 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(&pgm, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + auto ext_size = pgm.size_in_bytes(); + + fprintf(stdout, "%ld\t%ld\t%ld\n", insert_throughput, query_latency, ext_size); + + gsl_rng_free(rng); + fflush(stderr); +} + diff --git a/benchmarks/vldb/irs_bench.cpp b/benchmarks/vldb/irs_bench.cpp new file mode 100644 index 0000000..ca1e555 --- /dev/null +++ b/benchmarks/vldb/irs_bench.cpp @@ -0,0 +1,97 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include "framework/DynamicExtension.h" +#include "shard/ISAMTree.h" +#include "query/irs.h" +#include "framework/interface/Record.h" +#include "file_util.h" + +#include + +#include "psu-util/timer.h" +#include "standard_benchmarks.h" + + +typedef de::Record Rec; +typedef de::ISAMTree Shard; +typedef de::irs::Query Q; +typedef de::DynamicExtension Ext; +typedef de::irs::Parms QP; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + auto extension = new Ext(12000, 12001, 8, 0, 64); + gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto data = read_sosd_file(d_fname, n); + std::vector to_delete(n * delete_proportion); + size_t j=0; + for (size_t i=0; i(q_fname, .001); + for (auto &q : queries) { + q.sample_size = 1000; + q.rng = rng; + } + + /* warmup structure w/ 10% of records */ + size_t warmup = .3 * n; + size_t delete_idx = 0; + insert_records(extension, 0, warmup, data, to_delete, delete_idx, false, rng); + + extension->await_next_epoch(); + + TIMER_INIT(); + + TIMER_START(); + insert_records(extension, warmup, data.size(), data, to_delete, delete_idx, true, 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(extension, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + auto shard = extension->create_static_structure(); + + TIMER_START(); + run_static_queries(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; + fflush(stderr); +} + diff --git a/benchmarks/vldb/mtree_bench.cpp b/benchmarks/vldb/mtree_bench.cpp new file mode 100644 index 0000000..35f56be --- /dev/null +++ b/benchmarks/vldb/mtree_bench.cpp @@ -0,0 +1,80 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include "query/knn.h" +#include "file_util.h" +#include "standard_benchmarks.h" + +#include + +#include "psu-util/timer.h" + + +typedef Word2VecRec Rec; +typedef de::knn::Parms QP; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile\n", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + auto mtree = new MTree(); + gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); + + fprintf(stderr, "[I] Reading data file...\n"); + auto data = read_vector_file(d_fname, n); + + fprintf(stderr, "[I] Generating delete vector\n"); + std::vector to_delete(n * delete_proportion); + size_t j=0; + for (size_t i=0; i(q_fname, 10); + + fprintf(stderr, "[I] Warming up structure...\n"); + /* warmup structure w/ 10% of records */ + size_t warmup = .1 * n; + size_t delete_idx = 0; + insert_records(mtree, 0, warmup, data, to_delete, delete_idx, false, rng); + + TIMER_INIT(); + + fprintf(stderr, "[I] Running Insertion Benchmark\n"); + TIMER_START(); + insert_records(mtree, warmup, data.size(), data, to_delete, delete_idx, true, rng); + TIMER_STOP(); + + auto insert_latency = TIMER_RESULT(); + size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9); + + fprintf(stderr, "[I] Running Query Benchmark\n"); + TIMER_START(); + run_queries(mtree, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + fprintf(stdout, "%ld\t%ld\n", insert_throughput, query_latency); + + gsl_rng_free(rng); + delete mtree; + fflush(stderr); +} + diff --git a/benchmarks/vldb/pgm_bench.cpp b/benchmarks/vldb/pgm_bench.cpp new file mode 100644 index 0000000..f63ec8e --- /dev/null +++ b/benchmarks/vldb/pgm_bench.cpp @@ -0,0 +1,94 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include + +#include "framework/DynamicExtension.h" +#include "shard/PGM.h" +#include "query/rangecount.h" +#include "framework/interface/Record.h" +#include "file_util.h" +#include "standard_benchmarks.h" + +#include + +#include "psu-util/timer.h" + + +typedef de::Record Rec; +typedef de::PGM Shard; +typedef de::rc::Query Q; +typedef de::DynamicExtension Ext; +typedef de::rc::Parms QP; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + auto extension = new Ext(12000, 12001, 8, 0, 64); + gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto data = read_sosd_file(d_fname, n); + std::vector to_delete(n * delete_proportion); + size_t j=0; + for (size_t i=0; i(q_fname, .001); + + /* warmup structure w/ 10% of records */ + size_t warmup = .1 * n; + size_t delete_idx = 0; + insert_records(extension, 0, warmup, data, to_delete, delete_idx, false, rng); + + extension->await_next_epoch(); + + TIMER_INIT(); + + TIMER_START(); + insert_records(extension, warmup, data.size(), data, to_delete, delete_idx, true, 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(extension, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + auto shard = extension->create_static_structure(); + + TIMER_START(); + run_static_queries(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; + fflush(stderr); +} + diff --git a/benchmarks/vldb/ts_bench.cpp b/benchmarks/vldb/ts_bench.cpp new file mode 100644 index 0000000..a84635f --- /dev/null +++ b/benchmarks/vldb/ts_bench.cpp @@ -0,0 +1,94 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include + +#include "framework/DynamicExtension.h" +#include "shard/TrieSpline.h" +#include "query/rangecount.h" +#include "framework/interface/Record.h" +#include "file_util.h" +#include "standard_benchmarks.h" + +#include + +#include "psu-util/timer.h" + + +typedef de::Record Rec; +typedef de::TrieSpline Shard; +typedef de::rc::Query Q; +typedef de::DynamicExtension Ext; +typedef de::rc::Parms QP; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + auto extension = new Ext(12000, 12001, 8, 0, 64); + gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto data = read_sosd_file(d_fname, n); + std::vector to_delete(n * delete_proportion); + size_t j=0; + for (size_t i=0; i(q_fname, .001); + + /* warmup structure w/ 10% of records */ + size_t warmup = .1 * n; + size_t delete_idx = 0; + insert_records(extension, 0, warmup, data, to_delete, delete_idx, false, rng); + + extension->await_next_epoch(); + + TIMER_INIT(); + + TIMER_START(); + insert_records(extension, warmup, data.size(), data, to_delete, delete_idx, true, 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(extension, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + auto shard = extension->create_static_structure(); + + TIMER_START(); + run_static_queries(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; + fflush(stderr); +} + diff --git a/benchmarks/vldb/ts_bsm_bench.cpp b/benchmarks/vldb/ts_bsm_bench.cpp new file mode 100644 index 0000000..706433d --- /dev/null +++ b/benchmarks/vldb/ts_bsm_bench.cpp @@ -0,0 +1,70 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include + +#include "triespline_bsm.h" +#include "psu-util/bentley-saxe.h" +#include "framework/interface/Record.h" +#include "file_util.h" +#include "query/rangecount.h" +#include "psu-util/timer.h" +#include "standard_benchmarks.h" + +typedef std::pair Rec; +typedef de::Record FRec; + +typedef BSMTrieSpline Shard; +typedef de::rc::Parms QP; +typedef psudb::bsm::BentleySaxe Ext; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + auto extension = new psudb::bsm::BentleySaxe(); + gsl_rng *rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto data = read_sosd_file_pair(d_fname, n); + auto queries = read_range_queries(q_fname, .001); + + /* warmup structure w/ 10% of records */ + size_t warmup = .1 * n; + insert_records(extension, 0, warmup, data); + + TIMER_INIT(); + + TIMER_START(); + insert_records(extension, warmup, data.size(), data); + TIMER_STOP(); + + auto insert_latency = TIMER_RESULT(); + size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9); + + TIMER_START(); + run_queries(extension, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + fprintf(stdout, "%ld\t%ld\n", insert_throughput, query_latency); + + gsl_rng_free(rng); + delete extension; + fflush(stderr); +} + diff --git a/benchmarks/vldb/ts_mdsp_bench.cpp b/benchmarks/vldb/ts_mdsp_bench.cpp new file mode 100644 index 0000000..4c5bf1e --- /dev/null +++ b/benchmarks/vldb/ts_mdsp_bench.cpp @@ -0,0 +1,70 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include + +#include "triespline_bsm.h" +#include "psu-util/bentley-saxe.h" +#include "framework/interface/Record.h" +#include "file_util.h" +#include "query/rangecount.h" +#include "psu-util/timer.h" +#include "standard_benchmarks.h" + +typedef std::pair Rec; +typedef de::Record FRec; + +typedef BSMTrieSpline Shard; +typedef de::rc::Parms QP; +typedef psudb::bsm::BentleySaxe Ext; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + auto extension = new psudb::bsm::BentleySaxe(); + gsl_rng *rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto data = read_sosd_file_pair(d_fname, n); + auto queries = read_range_queries(q_fname, .001); + + /* warmup structure w/ 10% of records */ + size_t warmup = .1 * n; + insert_records(extension, 0, warmup, data); + + TIMER_INIT(); + + TIMER_START(); + insert_records(extension, warmup, data.size(), data); + TIMER_STOP(); + + auto insert_latency = TIMER_RESULT(); + size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9); + + TIMER_START(); + run_queries(extension, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + fprintf(stdout, "%ld\t%ld\n", insert_throughput, query_latency); + + gsl_rng_free(rng); + delete extension; + fflush(stderr); +} + diff --git a/benchmarks/vldb/vptree_bench.cpp b/benchmarks/vldb/vptree_bench.cpp new file mode 100644 index 0000000..613c556 --- /dev/null +++ b/benchmarks/vldb/vptree_bench.cpp @@ -0,0 +1,100 @@ +/* + * + */ + +#define ENABLE_TIMER + +#include "framework/DynamicExtension.h" +#include "shard/VPTree.h" +#include "query/knn.h" +#include "framework/interface/Record.h" +#include "file_util.h" +#include "standard_benchmarks.h" + +#include + +#include "psu-util/timer.h" + + +typedef Word2VecRec Rec; + +typedef de::VPTree Shard; +typedef de::knn::Query Q; +typedef de::DynamicExtension Ext; +typedef de::knn::Parms QP; + +void usage(char *progname) { + fprintf(stderr, "%s reccnt datafile queryfile", progname); +} + +int main(int argc, char **argv) { + + if (argc < 4) { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + size_t n = atol(argv[1]); + std::string d_fname = std::string(argv[2]); + std::string q_fname = std::string(argv[3]); + + auto extension = new Ext(100, 1000, 8, 0, 64); + gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); + + fprintf(stderr, "[I] Reading data file...\n"); + auto data = read_vector_file(d_fname, n); + + fprintf(stderr, "[I] Generating delete vector\n"); + std::vector to_delete(n * delete_proportion); + size_t j=0; + for (size_t i=0; i(q_fname, 10); + + fprintf(stderr, "[I] Warming up structure...\n"); + /* warmup structure w/ 10% of records */ + size_t warmup = .1 * n; + size_t delete_idx = 0; + insert_records(extension, 0, warmup, data, to_delete, delete_idx, false, rng); + + extension->await_next_epoch(); + + TIMER_INIT(); + + fprintf(stderr, "[I] Running Insertion Benchmark\n"); + TIMER_START(); + insert_records(extension, warmup, data.size(), data, to_delete, delete_idx, true, rng); + TIMER_STOP(); + + auto insert_latency = TIMER_RESULT(); + size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9); + + fprintf(stderr, "[I] Running Query Benchmark\n"); + TIMER_START(); + run_queries(extension, queries); + TIMER_STOP(); + + auto query_latency = TIMER_RESULT() / queries.size(); + + auto shard = extension->create_static_structure(); + + TIMER_START(); + run_static_queries(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; + fflush(stderr); +} + diff --git a/benchmarks/vptree_bench.cpp b/benchmarks/vptree_bench.cpp deleted file mode 100644 index 1219076..0000000 --- a/benchmarks/vptree_bench.cpp +++ /dev/null @@ -1,100 +0,0 @@ -/* - * - */ - -#define ENABLE_TIMER - -#include "framework/DynamicExtension.h" -#include "shard/VPTree.h" -#include "query/knn.h" -#include "framework/interface/Record.h" -#include "include/file_util.h" -#include "include/standard_benchmarks.h" - -#include - -#include "psu-util/timer.h" - - -typedef Word2VecRec Rec; - -typedef de::VPTree Shard; -typedef de::knn::Query Q; -typedef de::DynamicExtension Ext; -typedef de::knn::Parms QP; - -void usage(char *progname) { - fprintf(stderr, "%s reccnt datafile queryfile", progname); -} - -int main(int argc, char **argv) { - - if (argc < 4) { - usage(argv[0]); - exit(EXIT_FAILURE); - } - - size_t n = atol(argv[1]); - std::string d_fname = std::string(argv[2]); - std::string q_fname = std::string(argv[3]); - - auto extension = new Ext(100, 1000, 8, 0, 64); - gsl_rng * rng = gsl_rng_alloc(gsl_rng_mt19937); - - fprintf(stderr, "[I] Reading data file...\n"); - auto data = read_vector_file(d_fname, n); - - fprintf(stderr, "[I] Generating delete vector\n"); - std::vector to_delete(n * delete_proportion); - size_t j=0; - for (size_t i=0; i(q_fname, 10); - - fprintf(stderr, "[I] Warming up structure...\n"); - /* warmup structure w/ 10% of records */ - size_t warmup = .1 * n; - size_t delete_idx = 0; - insert_records(extension, 0, warmup, data, to_delete, delete_idx, false, rng); - - extension->await_next_epoch(); - - TIMER_INIT(); - - fprintf(stderr, "[I] Running Insertion Benchmark\n"); - TIMER_START(); - insert_records(extension, warmup, data.size(), data, to_delete, delete_idx, true, rng); - TIMER_STOP(); - - auto insert_latency = TIMER_RESULT(); - size_t insert_throughput = (size_t) ((double) (n - warmup) / (double) insert_latency * 1e9); - - fprintf(stderr, "[I] Running Query Benchmark\n"); - TIMER_START(); - run_queries(extension, queries); - TIMER_STOP(); - - auto query_latency = TIMER_RESULT() / queries.size(); - - auto shard = extension->create_static_structure(); - - TIMER_START(); - run_static_queries(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; - fflush(stderr); -} - -- cgit v1.2.3