Sets iterator to the next element that is equal or larger to 'x', and returns the element. If no such element is found then return INT64_MAX. Incoming 'x' values must be in ascending order.
| 86 | // returns the element. If no such element is found then return INT64_MAX. |
| 87 | // Incoming 'x' values must be in ascending order. |
| 88 | uint64_t GetEqualOrLarger(uint64_t x) { |
| 89 | // MOVE_THRESHOLD was chosen empirically. If 10% of the data is deleted and |
| 90 | // if the distance is 30 then AdvanceAndGetEqualOrLarger() should find the next |
| 91 | // element in ~3 iterations. The point of it is we shouldn't use |
| 92 | // AdvanceAndGetEqualOrLarger() when the distance is large and the bitmap is |
| 93 | // dense. The distance is typically large when we start processing a new |
| 94 | // probe batch (we are in the middle of a file, but we have a new iterator). |
| 95 | constexpr int MOVE_THRESHOLD = 30; |
| 96 | // We need to choose between MoveAndGetEqualOrLarger() and |
| 97 | // AdvanceAndGetEqualOrLarger(). MoveAndGetEqualOrLarger() is more efficient |
| 98 | // when the distance between 'x' and iterator's current element is large. |
| 99 | // AdvanceAndGetEqualOrLarger() is more efficient when the distance is small. |
| 100 | // There are 5 possible cases: |
| 101 | // - We start a new probe batch: |
| 102 | // => For the first probe batch we likely choose AdvanceAndGetEqualOrLarger() |
| 103 | // (unless it starts with a high file position), but we choose |
| 104 | // MoveAndGetEqualOrLarger() for subsequent probe batches. Both should be |
| 105 | // efficient. |
| 106 | // - Incoming x values are sparse, Bitmap is sparse: |
| 107 | // => MoveAndGetEqualOrLarger() gets chosen most of the time. This sould give |
| 108 | // us OK performance, also this method won't be invoked that much in this |
| 109 | // case. |
| 110 | // - Incoming x values are dense, Bitmap is sparse: |
| 111 | // => AdvanceAndGetEqualOrLarger() gets chosen most of the time which should |
| 112 | // find the next element in 1-2 iterations (as input is dense, bitmap is |
| 113 | // sparse). Also, this won't be invoked that much since the bitmap is sparse. |
| 114 | // - Incoming x values are sparse, Bitmap is dense |
| 115 | // => MoveAndGetEqualOrLarger() gets chosen which is the efficient one for |
| 116 | // this case. |
| 117 | // - Incoming x values are dense, Bitmap is dense |
| 118 | // => AdvanceAndGetEqualOrLarger() gets chosen which is the optimal choice |
| 119 | // for this case. |
| 120 | if (HasValue() && x - Value() > MOVE_THRESHOLD) { |
| 121 | return MoveAndGetEqualOrLarger(x); |
| 122 | } else { |
| 123 | return AdvanceAndGetEqualOrLarger(x); |
| 124 | } |
| 125 | } |
| 126 | |
| 127 | ~Iterator() { |
| 128 | roaring64_iterator_free(it_); |