#ifndef POLY_COST_INTEGER_MERGE_TEMPLATE_TEST_LINK_H_ #define POLY_COST_INTEGER_MERGE_TEMPLATE_TEST_LINK_H_ #include "common.h" #include "codecs.h" #include "time.h" #include "bit_read.h" #include "bit_write.h" #include "caltime.h" #include "lr.h" #define INF 0x7f7fffff #include "stx-btree/btree.h" #include "stx-btree/btree_map.h" #include "ALEX/alex.h" #include "art/art32.h" #include "sdlp.hpp" #include "polynomial_regression.hpp" using namespace Eigen; namespace Codecset { template <typename S> struct Segment_pol { // [start, end], this maintains delta information int start_index; int end_index; int double_delta_next; int estimate_bit; Segment_pol *prev; Segment_pol *next; Segment_pol(int start, int end, int bit_next, int est_bit) { start_index = start; end_index = end; double_delta_next = bit_next; estimate_bit = est_bit; } }; template <typename T, int degree> int64_t solve_lp(T* y_val, int number) { if(number<=degree+1){ return 0; } int m = number * 2; Eigen::Matrix<double, degree + 2, 1> x; Eigen::Matrix<double, degree + 2, 1> c; Eigen::Matrix<double, -1, degree + 2> A(m + 1, degree + 2); Eigen::VectorXd b(m + 1); for (int i = 0; i < degree + 1; i++) { c(i) = 0; } c(degree + 1) = 1.0; for (int i = 0; i < number; i++) { for (int j = 0; j < degree + 1; j++) { A(2 * i, j) = pow(i, degree - j); A(2 * i + 1, j) = -pow(i, degree - j); } A(2 * i, degree + 1) = -1; A(2 * i + 1, degree + 1) = -1; b(2 * i) = (int64_t)y_val[i]; b(2 * i + 1) = -(int64_t)y_val[i]; } for (int i = 0; i < degree + 1; i++) { A(m, i) = 0; } A(m, degree + 1) = -1; b(m) = 0; double minobj = sdlp::linprog<degree + 2>(c, A, b, x); return int64_t(ceil(minobj)); } template <typename T, int degree> class Poly_cost_merge_test_link { public: std::vector<uint32_t> segment_index; std::vector<uint32_t> segment_length; std::vector<uint8_t *> block_start_vec_total; std::vector<uint32_t> segment_index_total; std::vector<uint32_t> segment_length_total; std::vector<KeyValue<uint32_t>> art_build_vec; std::vector<std::pair<int, int>> alex_build_vec; std::vector<ART32::Node *> search_node; double split_time = 0; double merge_time = 0; uint64_t total_byte_total = 0; uint64_t total_byte = 0; int overhead = 0; T *array; int block_num; int block_size; int segment_index_total_idx = 0; // start_index + bit + theta0 + theta1 + numbers + delta void init(int blocks, int blocksize, uint64_t delta) { block_num = blocks; block_size = blocksize; overhead = delta; // add some punishing item } // stx::btree_map<int, int> btree_total; alex::Alex<int, int> alex_tree; ART32 art; uint32_t lower_bound(uint64_t v, uint32_t len, std::vector<uint32_t> &index) { uint32_t m; uint32_t x = 0; uint32_t y = len - 1; while (x <= y) { m = x + (y - x) / 2; if (v < index[m]) y = m - 1; else x = m + 1; } return y; } uint64_t newsegment_size(uint32_t origin_index, uint32_t end_index) { if (origin_index == end_index) { return 9; } if (end_index == origin_index + 1) { return 13; } uint8_t *descriptor = (uint8_t *)malloc((end_index - origin_index + 1) * sizeof(T) * 4 + 200); uint8_t *out = descriptor; int length = end_index - origin_index + 1; std::vector<T> data_vec = std::vector<T>(array+origin_index, array + end_index + 1); auto simple_fixed = andviane::polynomial_regression<degree>(data_vec); std::vector<T> delta; std::vector<bool> signvec; T max_error = 0; for (auto i = 0; i < length; i++) { T tmp_val; int64_t pred = simple_fixed(i); if ((int64_t)data_vec[i] > pred) { tmp_val = (int64_t)data_vec[i] - pred; signvec.emplace_back(true); // means positive } else { tmp_val = pred - (int64_t)data_vec[i]; signvec.emplace_back(false); // means negative } delta.emplace_back(tmp_val); if (tmp_val > max_error) { max_error = tmp_val; } } uint8_t delta_final_max_bit = 0; if (max_error) { delta_final_max_bit = bits_int_T(max_error) + 1; } if (delta_final_max_bit > sizeof(T) * 8) { delta_final_max_bit = sizeof(T) * 8; } int start_ind =origin_index; memcpy(out, &start_ind, sizeof(start_ind)); out += sizeof(start_ind); memcpy(out, &delta_final_max_bit, sizeof(delta_final_max_bit)); out += sizeof(delta_final_max_bit); if (delta_final_max_bit == sizeof(T) * 8) { for (auto i = origin_index; i <= end_index; i++) { memcpy(out, &array[i], sizeof(T)); out += sizeof(T); } uint64_t segment_size = out - descriptor; return segment_size; } for(auto a: simple_fixed){ memcpy(out, &a, sizeof(double)); out += sizeof(double); } if (delta_final_max_bit) { out = write_delta_int_T(delta, signvec, out, delta_final_max_bit, (end_index - origin_index + 1)); } uint64_t segment_size = out - descriptor; free(descriptor); return segment_size; } // uint64_t newsegment_size(uint32_t origin_index, uint32_t end_index) // { // if (origin_index == end_index) // { // return 9; // } // if (end_index == origin_index + 1) // { // return 13; // } // uint64_t overhead = sizeof(double) * (degree+1) + 5; // int length = end_index - origin_index + 1; // int delta_final_max_bit = cal_bits_range(solve_lp<T, degree>(array + origin_index, length)); // if (delta_final_max_bit >= sizeof(T) * 8) // { // delta_final_max_bit = sizeof(T) * 8; // overhead = 5 + sizeof(T) * length; // return overhead; // } // overhead += ceil((delta_final_max_bit * length) / 8.0); // return overhead; // } void newsegment(uint32_t origin_index, uint32_t end_index, int nvalue) { if (origin_index == end_index) { return newsegment_1(origin_index, origin_index,nvalue); } if (end_index == origin_index + 1) { return newsegment_2(origin_index, end_index,nvalue); } uint8_t *descriptor = (uint8_t *)malloc((end_index - origin_index + 1) * sizeof(T) * 4 + 200); uint8_t *out = descriptor; int length = end_index - origin_index + 1; std::vector<T> data_vec = std::vector<T>(array+origin_index, array + end_index + 1); auto simple_fixed = andviane::polynomial_regression<degree>(data_vec); std::vector<T> delta; std::vector<bool> signvec; T max_error = 0; for (auto i = 0; i < length; i++) { T tmp_val; int64_t pred = simple_fixed(i); if ((int64_t)data_vec[i] > pred) { tmp_val = (int64_t)data_vec[i] - pred; signvec.emplace_back(true); // means positive } else { tmp_val = pred - (int64_t)data_vec[i]; signvec.emplace_back(false); // means negative } delta.emplace_back(tmp_val); if (tmp_val > max_error) { max_error = tmp_val; } } uint8_t delta_final_max_bit = 0; if (max_error) { delta_final_max_bit = bits_int_T(max_error) + 1; } if (delta_final_max_bit > sizeof(T) * 8) { delta_final_max_bit = sizeof(T) * 8; } int start_ind = nvalue * block_size+origin_index; memcpy(out, &start_ind, sizeof(start_ind)); out += sizeof(start_ind); memcpy(out, &delta_final_max_bit, sizeof(delta_final_max_bit)); out += sizeof(delta_final_max_bit); if (delta_final_max_bit == sizeof(T) * 8) { for (auto i = origin_index; i <= end_index; i++) { memcpy(out, &array[i], sizeof(T)); out += sizeof(T); } uint64_t segment_size = out - descriptor; descriptor = (uint8_t *)realloc(descriptor, segment_size); block_start_vec_total.push_back(descriptor); segment_index_total.push_back(origin_index+nvalue*block_size); segment_length_total.push_back(segment_size); total_byte_total += segment_size; return; } for(auto a: simple_fixed){ memcpy(out, &a, sizeof(double)); out += sizeof(double); } if (delta_final_max_bit) { out = write_delta_int_T(delta, signvec, out, delta_final_max_bit, (end_index - origin_index + 1)); } uint64_t segment_size = out - descriptor; descriptor = (uint8_t *)realloc(descriptor, segment_size); block_start_vec_total.push_back(descriptor); segment_index_total.push_back(origin_index+nvalue*block_size); segment_length_total.push_back(segment_size); total_byte_total += segment_size; } void newsegment_2(uint32_t origin_index, uint32_t end_index,int nvalue) { uint8_t *descriptor = (uint8_t *)malloc((end_index - origin_index + 1) * sizeof(T) * 2); uint8_t *out = descriptor; int start_ind = nvalue * block_size+origin_index; memcpy(out, &start_ind, sizeof(start_ind)); out += sizeof(start_ind); out[0] = (uint8_t)254; // this means that this segment only has two points out++; memcpy(out, &array[origin_index], sizeof(T)); out += sizeof(T); memcpy(out, &(array[origin_index + 1]), sizeof(T)); out += sizeof(T); uint64_t segment_size = out - descriptor; descriptor = (uint8_t *)realloc(descriptor, segment_size); block_start_vec_total.push_back(descriptor); segment_index_total.push_back(origin_index+nvalue*block_size); segment_length_total.push_back(segment_size); total_byte_total += segment_size; } void newsegment_1(uint32_t origin_index, uint32_t end_index,int nvalue) { uint8_t *descriptor = (uint8_t *)malloc(10 * sizeof(T)); uint8_t *out = descriptor; int start_ind = nvalue * block_size+origin_index; memcpy(out, &start_ind, sizeof(start_ind)); out += sizeof(start_ind); out[0] = (uint8_t)255; // this means that this segment only has one point out++; memcpy(out, &array[origin_index], sizeof(T)); out += sizeof(T); uint64_t segment_size = out - descriptor; descriptor = (uint8_t *)realloc(descriptor, segment_size); block_start_vec_total.push_back(descriptor); segment_length_total.push_back(segment_size); segment_index_total.push_back(origin_index+nvalue*block_size); total_byte_total += segment_size; } uint32_t cal_bits_range(int64_t data_range) { uint32_t bits = 0; if (data_range) { bits = bits_int_T<T>(data_range) + 1; } return bits; } uint8_t *encodeArray8_int(T *in, const size_t length, uint8_t *res, size_t nvalue) { array = in + nvalue * block_size; Segment_pol<int64_t> head(0, 0, 10000, 0); Segment_pol<int64_t> tail(0, 0, 0, 0); Segment_pol<int64_t> *current = &head; int min_second_bit = 10000; int max_second_bit = -1; std::vector<int64_t> first_order_delta; for(int i=0;i<length-1;i++){ first_order_delta.push_back(int64_t(array[i+1])-int64_t(array[i])); } std::vector<int64_t> second_order_delta; for(int i=0;i<first_order_delta.size()-2;i++){ second_order_delta.push_back(first_order_delta[i+1]-first_order_delta[i]); } std::vector<int64_t> third_order_delta; for(int i=0;i<first_order_delta.size()-3;i++){ third_order_delta.push_back(second_order_delta[i+1]-second_order_delta[i]); } for (int i = 0; i <third_order_delta.size() - 1; i++) { int64_t delta = abs(third_order_delta[i + 1] - third_order_delta[i]); int second_delta_bit = cal_bits_range(delta); if (second_delta_bit < min_second_bit) { min_second_bit = second_delta_bit; } if (second_delta_bit > max_second_bit) { max_second_bit = second_delta_bit; } Segment_pol<int64_t> *newseg = new Segment_pol<int64_t>(i, i, second_delta_bit, 0); current->next = newseg; newseg->prev = current; current = newseg; } Segment_pol<int64_t> *newseg = new Segment_pol<int64_t>(length - 3, length - 3, 10000, 0); current->next = newseg; newseg->prev = current; current = newseg; current->next = &tail; tail.prev = current; bool flag = false; double start_timer = getNow(); for (int aim_bit = min_second_bit; aim_bit <= min_second_bit+1; aim_bit++) { current = (&head)->next; while (current != &tail && current->next != &tail) { if (current->double_delta_next == aim_bit) { Segment_pol<int64_t> *next = current->next; int former_index = current->start_index; // former_index ~ start_index - 1 int start_index = next->start_index; int now_index = next->end_index; // start_index ~ now_index int left_bit_origin = current->estimate_bit; int right_bit_origin = next->estimate_bit; int new_bit = cal_bits_range(solve_lp<T, degree>(array+former_index, now_index - former_index+1)); int origin_cost = (start_index - former_index) * left_bit_origin + (now_index - start_index + 1) * right_bit_origin; int merged_cost = new_bit * (now_index - former_index + 1); if (merged_cost - origin_cost < overhead) { // merge current->end_index = now_index; current->next = next->next; next->next->prev = current; current->double_delta_next = next->double_delta_next; current->estimate_bit = new_bit; delete next; } else { current = current->next; continue; } // look left Segment_pol<int64_t> *prev = current->prev; while (prev != &head ) { int left_index = prev->start_index; int new_bit = cal_bits_range(solve_lp<T, degree>(array+left_index, current->end_index - left_index+1)); int origin_left_delta_bit = prev->estimate_bit; int origin_right_delta_bit = current->estimate_bit; int origin_cost = (current->start_index - left_index) * origin_left_delta_bit + (current->end_index - current->start_index + 1) * origin_right_delta_bit; int merged_cost = new_bit * (current->end_index - left_index + 1); if (merged_cost - origin_cost < overhead) { // merge current->start_index = left_index; current->prev = prev->prev; prev->prev->next = current; current->estimate_bit = new_bit; delete prev; prev = current->prev; } else { break; } } next = current->next; while (next != &tail && next->next != &tail) { int right_index = next->end_index; int new_bit = cal_bits_range(solve_lp<T, degree>(array+current->start_index, right_index - current->start_index+1)); int origin_left_delta_bit = current->estimate_bit; int origin_right_delta_bit = next->estimate_bit; int origin_cost = (right_index - next->start_index + 1) * origin_right_delta_bit + (next->start_index - current->start_index) * origin_left_delta_bit; int merged_cost = new_bit * (right_index - current->start_index + 1); if (merged_cost - origin_cost < overhead) { // merge current->end_index = right_index; current->next = next->next; next->next->prev = current; current->double_delta_next = next->double_delta_next; current->estimate_bit = new_bit; delete next; next = current->next; } else { break; } } current = current->next; } else { current = current->next; } } } double end_timer = getNow(); split_time += (end_timer - start_timer); current = (&head)->next; while (current->next != &tail) { segment_index.push_back(current->start_index); // std::cout << current->start_index << " " << current->end_index << " " << current->estimate_bit << std::endl; current = current->next; } if(nvalue==70){ std::cout<<segment_index.size()<<std::endl; } int segment_total = segment_index.size(); segment_index.push_back(length); total_byte = 0; for (int i = 0; i < segment_total; i++) { uint64_t tmp_size = newsegment_size(segment_index[i], segment_index[i + 1] - 1); total_byte += tmp_size; // std::cout<<segment_index[i]<<" "<<segment_index[i + 1] - 1<<" "<<total_byte<<std::endl; segment_length.emplace_back(tmp_size); } segment_index.pop_back(); // std::cout << total_byte << std::endl; start_timer = getNow(); int iter = 0; uint64_t cost_decline = total_byte; while (cost_decline > 0) { iter++; cost_decline = total_byte; merge(nvalue,length); // merge_both_direction(nvalue, length); double compressrate = (total_byte) * 100.0 / (sizeof(T) * block_size * 1.0); // std::cout << "try " << iter << " segment number " << (int)segment_index.size() << " resulting compression rate: " << std::setprecision(4) << compressrate << std::endl; cost_decline = cost_decline - total_byte; double cost_decline_percent = cost_decline * 100.0 / (sizeof(T) * block_size * 1.0); if (cost_decline_percent < 0.01) { break; } } int segment_number = (int)segment_index.size(); if (segment_number <= 1) { segment_index.clear(); segment_index.push_back(0); segment_index.push_back(length); newsegment(0,length - 1, nvalue); // std::cout<<nvalue<<" "<<segment_index[1]-segment_index[0]<<" "<< start_key[0]<<" "<< slope[0]<<std::endl; } else { segment_index.push_back(length); for (int i = 0; i < segment_number; i++) { newsegment(segment_index[i], segment_index[i + 1] - 1, nvalue); // std::cout<<nvalue<< " "<<segment_index[i]<<" "<<segment_index[i+1]-1<<std::endl; // std::cout<<nvalue<<" "<<segment_index[i + 1]-segment_index[i]<<" "<< start_key[i]<<" "<< slope[i]<<std::endl; } } segment_index.pop_back(); end_timer = getNow(); merge_time += (end_timer - start_timer); for (auto item : segment_index) { art_build_vec.push_back((KeyValue<uint32_t>){nvalue*block_size + item, segment_index_total_idx}); // std::cout<<item<<std::endl; // auto tmp = btree_total.insert(std::make_pair(item, segment_index_total_idx)); // auto tmp = alex_tree.insert(item, segment_index_total_idx); alex_build_vec.push_back(std::make_pair(nvalue*block_size +item, segment_index_total_idx)); segment_index_total_idx++; } if (nvalue == block_num - 1) { // auto tmp = btree_total.insert(std::make_pair(block_num * block_size, segment_index_total_idx)); // std::cout<<block_num * block_size<<" "<<segment_index_total_idx<<std::endl; // auto tmp = alex_tree.insert(block_num * block_size, segment_index_total_idx); art_build_vec.push_back((KeyValue<uint32_t>){block_num * block_size, segment_index_total_idx}); alex_build_vec.push_back(std::make_pair(block_num * block_size, segment_index_total_idx)); } segment_index.clear(); segment_length.clear(); total_byte = 0; current = (&head)->next; Segment_pol<int64_t> *next = current->next; while (current != &tail && current->next != &tail) { next = current->next; delete current; current = next; } (&head)->next = &tail; (&tail)->prev = &head; // for(int i=0; i< segment_index_total.size()-1; i++){ // std::cout<<segment_index_total[i]<<" "<< (double)newsegment_size(segment_index_total[i], segment_index_total[i+1]-1) / (double)((segment_index_total[i+1] - segment_index_total[i])*8)<<std::endl; // } return res; } void merge(int nvalue, int length) { // this function is to merge blocks in block_start_vec to large blocks int start_index = segment_index[0]; // before the start_index is the finished blocks int segment_num = 0; // the current segment index int newsegment_num = 0; int total_segments = segment_index.size(); // the total number of segments uint64_t totalbyte_after_merge = 0; segment_index.push_back(length); std::vector<uint32_t> new_segment_index; std::vector<uint32_t> new_segment_length; while (segment_num < total_segments) { // std::cout<<"segment_num: "<<segment_num <<" / "<<total_segments<<std::endl; if (segment_num == total_segments - 1) { // std::cout <<segment_num<<"///"<<total_segments<<" "<< block_start_vec[segment_num] << std::endl; new_segment_index.emplace_back(segment_index[segment_num]); new_segment_length.emplace_back(segment_length[segment_num]); totalbyte_after_merge += segment_length[segment_num]; start_index = block_size * (nvalue + 1); segment_num++; break; } uint32_t init_cost = segment_length[segment_num] + segment_length[segment_num + 1]; uint32_t merge_cost = newsegment_size(start_index, segment_index[segment_num + 2] - 1); if (init_cost > merge_cost) { // merge the two segments new_segment_index.emplace_back(start_index); new_segment_length.emplace_back(merge_cost); totalbyte_after_merge += merge_cost; start_index = segment_index[segment_num + 2]; segment_num += 2; // std::cout<<segment_num<<std::endl; newsegment_num++; } else { // if(start_index==199999979){ // std::cout<<"hi"<<std::endl; // } // std::cout <<segment_num<<"/"<<total_segments<<" "<< block_start_vec[segment_num] << std::endl; new_segment_index.emplace_back(segment_index[segment_num]); new_segment_length.emplace_back(segment_length[segment_num]); totalbyte_after_merge += segment_length[segment_num]; start_index = segment_index[segment_num + 1]; segment_num++; newsegment_num++; } } segment_index.swap(new_segment_index); segment_length.swap(new_segment_length); total_byte = totalbyte_after_merge; // std::cout<<total_byte<<std::endl; } void merge_both_direction(int nvalue, int length) { // this function is to merge blocks in block_start_vec to large blocks int start_index = segment_index[0]; // before the start_index is the finished blocks int segment_num = 0; // the current segment index int total_segments = segment_index.size(); // the total number of segments uint64_t totalbyte_after_merge = 0; segment_index.push_back(length); std::vector<uint32_t> new_segment_index; std::vector<uint32_t> new_segment_length; new_segment_index.emplace_back(segment_index[segment_num]); new_segment_length.emplace_back(segment_length[segment_num]); totalbyte_after_merge += segment_length[segment_num]; segment_num++; while (segment_num < total_segments) { // std::cout<<"segment_num: "<<segment_num <<" / "<<total_segments<<std::endl; if (segment_num == total_segments - 1) { // only can try merging with former one int last_merged_segment = new_segment_length.size() - 1; uint32_t init_cost_front = segment_length[segment_num] + new_segment_length[last_merged_segment]; uint32_t merge_cost_front = newsegment_size(new_segment_index[last_merged_segment], segment_index[segment_num + 1] - 1); int saved_cost_front = init_cost_front - merge_cost_front; if (saved_cost_front > 0) { totalbyte_after_merge -= new_segment_length[new_segment_length.size() - 1]; new_segment_length[new_segment_length.size() - 1] = merge_cost_front; totalbyte_after_merge += merge_cost_front; segment_num++; } else { new_segment_index.emplace_back(segment_index[segment_num]); new_segment_length.emplace_back(segment_length[segment_num]); totalbyte_after_merge += segment_length[segment_num]; segment_num++; } break; } int last_merged_segment = new_segment_length.size() - 1; uint32_t init_cost_front = segment_length[segment_num] + new_segment_length[last_merged_segment]; uint32_t merge_cost_front = newsegment_size(new_segment_index[last_merged_segment], segment_index[segment_num + 1] - 1); int saved_cost_front = init_cost_front - merge_cost_front; // std::cout<<init_cost_front<<" "<<merge_cost_front<<std::endl; uint32_t init_cost_back = segment_length[segment_num] + segment_length[segment_num + 1]; uint32_t merge_cost_back = newsegment_size(segment_index[segment_num], segment_index[segment_num + 2] - 1); int saved_cost_back = init_cost_back - merge_cost_back; // std::cout<<init_cost_back<<" "<<merge_cost_back<<std::endl; int saved_cost = std::max(saved_cost_front, saved_cost_back); if (saved_cost <= 0) { // do not merge new_segment_index.emplace_back(segment_index[segment_num]); new_segment_length.emplace_back(segment_length[segment_num]); totalbyte_after_merge += segment_length[segment_num]; start_index = segment_index[segment_num + 1]; segment_num++; continue; } if (saved_cost_back > saved_cost_front) { // merge with back new_segment_index.emplace_back(segment_index[segment_num]); new_segment_length.emplace_back(merge_cost_back); totalbyte_after_merge += merge_cost_back; start_index = segment_index[segment_num + 2]; segment_num += 2; // std::cout<<segment_num<<std::endl; } else { // merge with front totalbyte_after_merge -= new_segment_length[new_segment_length.size() - 1]; new_segment_length[new_segment_length.size() - 1] = merge_cost_front; totalbyte_after_merge += merge_cost_front; start_index = segment_index[segment_num + 1]; segment_num += 1; } } total_byte = totalbyte_after_merge; segment_index.clear(); segment_length.clear(); segment_index.swap(new_segment_index); segment_length.swap(new_segment_length); // std::cout<<totalbyte_after_merge<<std::endl; } T *decodeArray8(const size_t length, T *out, size_t nvalue) { T *res = out; // start_index + bit + theta0 + theta1 + numbers + delta segment_index_total.push_back(length); std::array<double, degree + 1> theta; uint8_t maxerror; for (int i = 0; i < block_start_vec_total.size(); i++) { int segment_length = segment_index_total[i + 1] - segment_index_total[i]; uint8_t *tmpin = block_start_vec_total[i]; // debug int start_ind = 0; memcpy(&start_ind, tmpin, sizeof(int)); // debug tmpin += sizeof(uint32_t); maxerror = tmpin[0]; tmpin++; if (maxerror == 255) { T tmp_val; memcpy(&tmp_val, tmpin, sizeof(tmp_val)); res[0] = tmp_val; res++; continue; } if (maxerror == 254) { T tmp_val; memcpy(&tmp_val, tmpin, sizeof(tmp_val)); res[0] = tmp_val; res++; memcpy(&tmp_val, tmpin + sizeof(T), sizeof(tmp_val)); res[0] = tmp_val; res++; continue; } if (maxerror == sizeof(T) * 8) { memcpy(res, tmpin, sizeof(T) * segment_length); res += segment_length; continue; } for (auto i = 0; i < degree + 1; i++) { memcpy(&theta[i], tmpin, sizeof(double)); tmpin += sizeof(double); } andviane::Polynomial<degree> poly(theta); if (maxerror) { read_all_bit_fix_poly<T,degree,double>(tmpin, 0, 0, segment_length, maxerror, res, &poly); } else { for (int j = 0; j < segment_length; j++) { res[j] = (long long)(poly(j)); } } res += segment_length; } return out; } int get_segment_id(int to_find) { // int segment_id = art.upper_bound_new(to_find, search_node) - 1; // int segment_id = lower_bound(to_find, segment_index_total.size(), segment_index_total); int segment_id = alex_tree.upper_bound(to_find).payload() - 1; __builtin_prefetch(block_start_vec_total.data() + segment_id, 0, 3); return segment_id; } T randomdecodeArray8(int segment_id, uint8_t *in, int to_find, uint32_t *out, size_t nvalue) { uint8_t *this_block = block_start_vec_total[segment_id]; uint8_t *tmpin = this_block; uint32_t start_ind; memcpy(&start_ind, tmpin, 4); tmpin += 4; uint8_t maxerror; memcpy(&maxerror, tmpin, 1); tmpin++; if (maxerror == sizeof(T) * 8) { T tmp_val = reinterpret_cast<T *>(tmpin)[to_find - start_ind]; return tmp_val; } T tmp_val = 0; if (maxerror == 255) { memcpy(&tmp_val, tmpin, sizeof(tmp_val)); return tmp_val; } if (maxerror == 254) { if (to_find - start_ind == 0) { memcpy(&tmp_val, tmpin, sizeof(tmp_val)); } else { tmpin += sizeof(tmp_val); memcpy(&tmp_val, tmpin, sizeof(tmp_val)); } return tmp_val; } std::array<double, degree + 1> theta; for (auto i = 0; i < degree + 1; i++) { memcpy(&theta[i], tmpin, sizeof(double)); tmpin += sizeof(double); } andviane::Polynomial<degree> poly(theta); if (maxerror) { tmp_val = read_bit_fix_int_wo_round_poly<T,degree,double>(tmpin, maxerror, to_find-start_ind, &poly); } else { tmp_val = (int64_t)poly(to_find-start_ind); } return tmp_val; } uint64_t summation(uint8_t *in, const size_t l, size_t nvalue) { return 0; } uint32_t *encodeArray(uint32_t *in, const size_t length, uint32_t *out, size_t nvalue) { std::cout << "Haven't implement. Please try uint8_t one..." << std::endl; return out; } uint32_t *decodeArray(uint32_t *in, const size_t length, uint32_t *out, size_t nvalue) { std::cout << "Haven't implement. Please try uint8_t one..." << std::endl; return out; } uint32_t randomdecodeArray(uint32_t *in, const size_t l, uint32_t *out, size_t nvalue) { std::cout << "Haven't implement. Please try uint8_t one..." << std::endl; return 1; } uint32_t get_total_byte() { return total_byte_total; } uint32_t get_total_blocks() { // std::cout << "split time " << split_time << std::endl; // std::cout << "merge time " << merge_time << std::endl; return block_start_vec_total.size(); } }; } // namespace FastPFor #endif /* SIMDFASTPFOR_H_ */