/Users/deen/code/yugabyte-db/src/yb/rocksdb/util/heap.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | |
21 | | #ifndef YB_ROCKSDB_UTIL_HEAP_H |
22 | | #define YB_ROCKSDB_UTIL_HEAP_H |
23 | | |
24 | | #pragma once |
25 | | |
26 | | #include <algorithm> |
27 | | |
28 | | #include <boost/container/small_vector.hpp> |
29 | | |
30 | | namespace rocksdb { |
31 | | |
32 | | // Binary heap implementation optimized for use in multi-way merge sort. |
33 | | // Comparison to std::priority_queue: |
34 | | // - In libstdc++, std::priority_queue::pop() usually performs just over logN |
35 | | // comparisons but never fewer. |
36 | | // - std::priority_queue does not have a replace-top operation, requiring a |
37 | | // pop+push. If the replacement element is the new top, this requires |
38 | | // around 2logN comparisons. |
39 | | // - This heap's pop() uses a "schoolbook" downheap which requires up to ~2logN |
40 | | // comparisons. |
41 | | // - This heap provides a replace_top() operation which requires [1, 2logN] |
42 | | // comparisons. When the replacement element is also the new top, this |
43 | | // takes just 1 or 2 comparisons. |
44 | | // |
45 | | // The last property can yield an order-of-magnitude performance improvement |
46 | | // when merge-sorting real-world non-random data. If the merge operation is |
47 | | // likely to take chunks of elements from the same input stream, only 1 |
48 | | // comparison per element is needed. In RocksDB-land, this happens when |
49 | | // compacting a database where keys are not randomly distributed across L0 |
50 | | // files but nearby keys are likely to be in the same L0 file. |
51 | | // |
52 | | // The container uses the same counterintuitive ordering as |
53 | | // std::priority_queue: the comparison operator is expected to provide the |
54 | | // less-than relation, but top() will return the maximum. |
55 | | |
56 | | template<typename T, typename Compare = std::less<T>> |
57 | | class BinaryHeap { |
58 | | public: |
59 | | BinaryHeap() { } |
60 | 38.7M | explicit BinaryHeap(Compare cmp) : cmp_(std::move(cmp)) { } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::BinaryHeap(rocksdb::MinIteratorComparator) Line | Count | Source | 60 | 38.1M | explicit BinaryHeap(Compare cmp) : cmp_(std::move(cmp)) { } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::BinaryHeap(rocksdb::MaxIteratorComparator) Line | Count | Source | 60 | 598k | explicit BinaryHeap(Compare cmp) : cmp_(std::move(cmp)) { } |
|
61 | | |
62 | | void push(const T& value) { |
63 | | data_.push_back(std::move(value)); |
64 | | std::push_heap(data_.begin(), data_.end(), cmp_); |
65 | | } |
66 | | |
67 | 85.2M | void push(T&& value) { |
68 | 85.2M | data_.push_back(std::move(value)); |
69 | 85.2M | std::push_heap(data_.begin(), data_.end(), cmp_); |
70 | 85.2M | } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::push(rocksdb::IteratorWrapper*&&) Line | Count | Source | 67 | 81.9M | void push(T&& value) { | 68 | 81.9M | data_.push_back(std::move(value)); | 69 | 81.9M | std::push_heap(data_.begin(), data_.end(), cmp_); | 70 | 81.9M | } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::push(rocksdb::IteratorWrapper*&&) Line | Count | Source | 67 | 3.26M | void push(T&& value) { | 68 | 3.26M | data_.push_back(std::move(value)); | 69 | 3.26M | std::push_heap(data_.begin(), data_.end(), cmp_); | 70 | 3.26M | } |
|
71 | | |
72 | 1.70G | const T& top() const { |
73 | 1.70G | assert(!empty()); |
74 | 0 | return data_.front(); |
75 | 1.70G | } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::top() const Line | Count | Source | 72 | 1.69G | const T& top() const { | 73 | 1.69G | assert(!empty()); | 74 | 0 | return data_.front(); | 75 | 1.69G | } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::top() const Line | Count | Source | 72 | 15.4M | const T& top() const { | 73 | 15.4M | assert(!empty()); | 74 | 0 | return data_.front(); | 75 | 15.4M | } |
|
76 | | |
77 | 839M | void replace_top(const T& value) { |
78 | 839M | assert(!empty()); |
79 | 0 | data_.front() = value; |
80 | 839M | downheap(get_root()); |
81 | 839M | } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::replace_top(rocksdb::IteratorWrapper* const&) Line | Count | Source | 77 | 832M | void replace_top(const T& value) { | 78 | 832M | assert(!empty()); | 79 | 0 | data_.front() = value; | 80 | 832M | downheap(get_root()); | 81 | 832M | } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::replace_top(rocksdb::IteratorWrapper* const&) Line | Count | Source | 77 | 7.13M | void replace_top(const T& value) { | 78 | 7.13M | assert(!empty()); | 79 | 0 | data_.front() = value; | 80 | 7.13M | downheap(get_root()); | 81 | 7.13M | } |
|
82 | | |
83 | | void replace_top(T&& value) { |
84 | | assert(!empty()); |
85 | | data_.front() = std::move(value); |
86 | | downheap(get_root()); |
87 | | } |
88 | | |
89 | 410k | void pop() { |
90 | 410k | assert(!empty()); |
91 | 0 | std::pop_heap(data_.begin(), data_.end(), cmp_); |
92 | 410k | data_.pop_back(); |
93 | 410k | } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::pop() Line | Count | Source | 89 | 350k | void pop() { | 90 | 350k | assert(!empty()); | 91 | 0 | std::pop_heap(data_.begin(), data_.end(), cmp_); | 92 | 350k | data_.pop_back(); | 93 | 350k | } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::pop() Line | Count | Source | 89 | 59.6k | void pop() { | 90 | 59.6k | assert(!empty()); | 91 | 0 | std::pop_heap(data_.begin(), data_.end(), cmp_); | 92 | 59.6k | data_.pop_back(); | 93 | 59.6k | } |
|
94 | | |
95 | | void swap(BinaryHeap &other) { |
96 | | std::swap(cmp_, other.cmp_); |
97 | | data_.swap(other.data_); |
98 | | } |
99 | | |
100 | 35.7M | void clear() { |
101 | 35.7M | data_.clear(); |
102 | 35.7M | } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::clear() Line | Count | Source | 100 | 31.6M | void clear() { | 101 | 31.6M | data_.clear(); | 102 | 31.6M | } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::clear() Line | Count | Source | 100 | 4.15M | void clear() { | 101 | 4.15M | data_.clear(); | 102 | 4.15M | } |
|
103 | | |
104 | 4.28G | bool empty() const { |
105 | 4.28G | return data_.empty(); |
106 | 4.28G | } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::empty() const Line | Count | Source | 104 | 4.24G | bool empty() const { | 105 | 4.24G | return data_.empty(); | 106 | 4.24G | } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::empty() const Line | Count | Source | 104 | 38.0M | bool empty() const { | 105 | 38.0M | return data_.empty(); | 106 | 38.0M | } |
|
107 | | |
108 | | size_t size() const { |
109 | | return data_.size(); |
110 | | } |
111 | | |
112 | | private: |
113 | 840M | static inline size_t get_root() { return 0; } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::get_root() Line | Count | Source | 113 | 833M | static inline size_t get_root() { return 0; } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::get_root() Line | Count | Source | 113 | 7.13M | static inline size_t get_root() { return 0; } |
|
114 | 905M | static inline size_t get_left(size_t index) { return 2 * index + 1; } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::get_left(unsigned long) Line | Count | Source | 114 | 891M | static inline size_t get_left(size_t index) { return 2 * index + 1; } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::get_left(unsigned long) Line | Count | Source | 114 | 14.4M | static inline size_t get_left(size_t index) { return 2 * index + 1; } |
|
115 | 818M | static inline size_t get_right(size_t index) { return 2 * index + 2; } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::get_right(unsigned long) Line | Count | Source | 115 | 805M | static inline size_t get_right(size_t index) { return 2 * index + 2; } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::get_right(unsigned long) Line | Count | Source | 115 | 12.3M | static inline size_t get_right(size_t index) { return 2 * index + 2; } |
|
116 | | |
117 | 840M | void downheap(size_t index) { |
118 | 840M | T* data = data_.data(); |
119 | 840M | T v = std::move(data[index]); |
120 | 840M | size_t size = data_.size(); |
121 | 906M | for(;;) { |
122 | 906M | const size_t left_child = get_left(index); |
123 | 906M | if (left_child >= size) { |
124 | 86.1M | break; |
125 | 86.1M | } |
126 | 820M | const size_t right_child = left_child + 1; |
127 | 820M | DCHECK_EQ(right_child, get_right(index)); |
128 | 820M | T* picked_child = data + left_child; |
129 | 820M | if (right_child < size) { |
130 | 681M | T* right_ptr = data + right_child; |
131 | 681M | if (cmp_(*picked_child, *right_ptr)) { |
132 | 593M | picked_child = right_ptr; |
133 | 593M | } |
134 | 681M | } |
135 | 820M | if (!cmp_(v, *picked_child)) { |
136 | 754M | break; |
137 | 754M | } |
138 | 65.8M | data[index] = std::move(*picked_child); |
139 | 65.8M | index = picked_child - data; |
140 | 65.8M | } |
141 | 840M | data[index] = std::move(v); |
142 | 840M | } rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MinIteratorComparator>::downheap(unsigned long) Line | Count | Source | 117 | 833M | void downheap(size_t index) { | 118 | 833M | T* data = data_.data(); | 119 | 833M | T v = std::move(data[index]); | 120 | 833M | size_t size = data_.size(); | 121 | 892M | for(;;) { | 122 | 892M | const size_t left_child = get_left(index); | 123 | 892M | if (left_child >= size) { | 124 | 84.0M | break; | 125 | 84.0M | } | 126 | 808M | const size_t right_child = left_child + 1; | 127 | 808M | DCHECK_EQ(right_child, get_right(index)); | 128 | 808M | T* picked_child = data + left_child; | 129 | 808M | if (right_child < size) { | 130 | 670M | T* right_ptr = data + right_child; | 131 | 670M | if (cmp_(*picked_child, *right_ptr)) { | 132 | 588M | picked_child = right_ptr; | 133 | 588M | } | 134 | 670M | } | 135 | 808M | if (!cmp_(v, *picked_child)) { | 136 | 749M | break; | 137 | 749M | } | 138 | 58.5M | data[index] = std::move(*picked_child); | 139 | 58.5M | index = picked_child - data; | 140 | 58.5M | } | 141 | 833M | data[index] = std::move(v); | 142 | 833M | } |
rocksdb::BinaryHeap<rocksdb::IteratorWrapper*, rocksdb::MaxIteratorComparator>::downheap(unsigned long) Line | Count | Source | 117 | 7.13M | void downheap(size_t index) { | 118 | 7.13M | T* data = data_.data(); | 119 | 7.13M | T v = std::move(data[index]); | 120 | 7.13M | size_t size = data_.size(); | 121 | 14.4M | for(;;) { | 122 | 14.4M | const size_t left_child = get_left(index); | 123 | 14.4M | if (left_child >= size) { | 124 | 2.14M | break; | 125 | 2.14M | } | 126 | 12.3M | const size_t right_child = left_child + 1; | 127 | 12.3M | DCHECK_EQ(right_child, get_right(index)); | 128 | 12.3M | T* picked_child = data + left_child; | 129 | 12.3M | if (right_child < size) { | 130 | 11.0M | T* right_ptr = data + right_child; | 131 | 11.0M | if (cmp_(*picked_child, *right_ptr)) { | 132 | 5.20M | picked_child = right_ptr; | 133 | 5.20M | } | 134 | 11.0M | } | 135 | 12.3M | if (!cmp_(v, *picked_child)) { | 136 | 4.98M | break; | 137 | 4.98M | } | 138 | 7.31M | data[index] = std::move(*picked_child); | 139 | 7.31M | index = picked_child - data; | 140 | 7.31M | } | 141 | 7.13M | data[index] = std::move(v); | 142 | 7.13M | } |
|
143 | | |
144 | | Compare cmp_; |
145 | | boost::container::small_vector<T, 8> data_; |
146 | | }; |
147 | | |
148 | | } // namespace rocksdb |
149 | | |
150 | | #endif // YB_ROCKSDB_UTIL_HEAP_H |