Akumuli
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
search.h
1 #pragma once
2 #include "util.h"
3 #include <mutex>
4 
5 namespace Akumuli {
6 
7 struct SearchRange {
8  uint32_t begin; //< Begin index
9  uint32_t end; //< End index
10 };
11 
16 template <class Derived, int SEARCH_QUOTA = 4> struct InterpolationSearch {
17  // Derived class must implement:
18  // - bool read_at(aku_TimeStamp* out_timestamp, uint32_t ix);
19  // - bool is_small(SearchRange range);
20  // - get_search_stats();
21 
23  enum I10nState { NONE, UNDERSHOOT, OVERSHOOT };
24 
30  bool run(aku_Timestamp key, SearchRange* prange) {
31  SearchRange& range = *prange;
32  if (range.begin == range.end) {
33  return true;
34  }
35  const Derived* cderived = static_cast<const Derived*>(this);
36  Derived* derived = static_cast<Derived*>(this);
37  aku_Timestamp search_lower_bound;
38  aku_Timestamp search_upper_bound;
39  bool success = cderived->read_at(&search_lower_bound, range.begin) &&
40  cderived->read_at(&search_upper_bound, range.end - 1);
41  if (!success) {
42  return false;
43  }
44  uint32_t probe_index = 0u;
45  int interpolation_search_quota = SEARCH_QUOTA;
46  int steps_count = 0;
47  int small_range_finish = 0;
48  int page_scan_steps_num = 0;
49  int page_scan_errors = 0;
50  int page_scan_success = 0;
51  int page_miss = 0;
52 
53  uint64_t overshoot = 0u;
54  uint64_t undershoot = 0u;
55  uint64_t exact_match = 0u;
56  aku_Timestamp prev_step_err = 0u;
57  I10nState state = NONE;
58 
59  while (steps_count++ < interpolation_search_quota) {
60  // On small distances - fallback to binary search
61  bool range_is_small = cderived->is_small(range);
62  if (range_is_small || search_lower_bound == search_upper_bound) {
63  small_range_finish = 1;
64  break;
65  }
66 
67  uint64_t numerator = 0u;
68 
69  switch (state) {
70  case UNDERSHOOT:
71  numerator = key - search_lower_bound + (prev_step_err >> steps_count);
72  break;
73  case OVERSHOOT:
74  numerator = key - search_lower_bound - (prev_step_err >> steps_count);
75  break;
76  default:
77  numerator = key - search_lower_bound;
78  }
79 
80  probe_index = range.begin + ((numerator * (range.end - range.begin)) /
81  (search_upper_bound - search_lower_bound));
82 
83  if (probe_index > range.begin && probe_index < range.end) {
84 
85  aku_Timestamp probe;
86  success = cderived->read_at(&probe, probe_index);
87  if (!success) {
88  return false;
89  }
90 
91  if (probe < key) {
92  undershoot++;
93  state = UNDERSHOOT;
94  prev_step_err = key - probe;
95  range.begin = probe_index;
96  success = cderived->read_at(&search_lower_bound, range.begin);
97  if (!success) {
98  return false;
99  }
100  } else if (probe > key) {
101  overshoot++;
102  state = OVERSHOOT;
103  prev_step_err = probe - key;
104  range.end = probe_index;
105  success = cderived->read_at(&search_upper_bound, range.end);
106  if (!success) {
107  return false;
108  }
109  } else {
110  // probe == key
111  exact_match = 1;
112  range.begin = probe_index;
113  range.end = probe_index;
114  break;
115  }
116  } else {
117  break;
118  }
119  }
120  auto& stats = derived->get_search_stats();
121  std::lock_guard<std::mutex> lock(stats.mutex);
122  stats.stats.istats.n_matches += exact_match;
123  stats.stats.istats.n_overshoots += overshoot;
124  stats.stats.istats.n_undershoots += undershoot;
125  stats.stats.istats.n_times += 1;
126  stats.stats.istats.n_steps += steps_count;
127  stats.stats.istats.n_reduced_to_one_page += small_range_finish;
128  stats.stats.istats.n_page_in_core_checks += page_scan_steps_num;
129  stats.stats.istats.n_page_in_core_errors += page_scan_errors;
130  stats.stats.istats.n_pages_in_core_found += page_scan_success;
131  stats.stats.istats.n_pages_in_core_miss += page_miss;
132  return true;
133  }
134 };
135 } // namespace Akumuli
Definition: search.h:16
bool run(aku_Timestamp key, SearchRange *prange)
Definition: search.h:30
Definition: search.h:7
I10nState
Interpolation search state.
Definition: search.h:23