pasta::bit_vector  v1.0.0
Compact and Fast Rank and Select Data Structure for Bit Vectors
rank.hpp
1/*******************************************************************************
2 * This file is part of pasta::bit_vector.
3 *
4 * Copyright (C) 2021 Florian Kurpicz <florian@kurpicz.org>
5 *
6 * pasta::bit_vector is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * pasta::bit_vector is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with pasta::bit_vector. If not, see <http://www.gnu.org/licenses/>.
18 *
19 ******************************************************************************/
20
21/*
22 * Based on
23 *
24 * @inproceedings{ZhouAK2013PopcountRankSelect,
25 * author = {Dong Zhou and David G. Andersen and Michael Kaminsky},
26 * title = {Space-Efficient, High-Performance Rank and Select Structures
27 * on Uncompressed Bit Sequences},
28 * booktitle = {12th International Symposium on Experimental Algorithms
29 * ({SEA})},
30 * series = {LNCS},
31 * volume = {7933},
32 * pages = {151--163},
33 * publisher = {Springer},
34 * year = {2013},
35 * doi = {10.1007/978-3-642-38527-8\_15},
36 * }
37 */
38
39#pragma once
40
41#include "pasta/bit_vector/bit_vector.hpp"
42#include "pasta/bit_vector/support/l12_type.hpp"
43#include "pasta/bit_vector/support/optimized_for.hpp"
44#include "pasta/bit_vector/support/popcount.hpp"
45
46#include <cstddef>
47#include <cstdint>
48#include <limits>
49#include <pasta/utils/container/aligned_vector.hpp>
50#include <pasta/utils/debug_asserts.hpp>
51#include <tlx/container/simple_vector.hpp>
52
53namespace pasta {
54
55/*!
56 * \ingroup pasta_bit_vector_configuration
57 * \brief Static configuration for \c Rank and
58 * \c RankSelect.
59 */
61 //! Bits covered by an L2-block.
62 static constexpr size_t L2_BIT_SIZE = 512;
63 //! Bits covered by an L1-block.
64 static constexpr size_t L1_BIT_SIZE = 4 * L2_BIT_SIZE;
65 //! Bits covered by an L0-block.
66 static constexpr size_t L0_BIT_SIZE =
67 static_cast<uint32_t>(std::numeric_limits<int32_t>::max()) + 1;
68
69 //! Number of 64-bit words covered by an L2-block.
70 static constexpr size_t L2_WORD_SIZE = L2_BIT_SIZE / (sizeof(uint64_t) * 8);
71 //! Number of 64-bit words covered by an L1-block.
72 static constexpr size_t L1_WORD_SIZE = L1_BIT_SIZE / (sizeof(uint64_t) * 8);
73 //! Number of 64-bit words covered by an L0-block.
74 static constexpr size_t L0_WORD_SIZE = L0_BIT_SIZE / (sizeof(uint64_t) * 8);
75
76 //! Sample rate of positions for faster select queries.
77 static constexpr size_t SELECT_SAMPLE_RATE = 8192;
78}; // struct PopcountRankSelectConfiguration
79
80//! \addtogroup pasta_bit_vector_rank
81//! \{
82
83/*!
84 * \brief Rank support for \c BitVector.
85 *
86 * The rank support is based on popcount and described in detail by
87 * Zhou et al. \cite ZhouAK2013PopcountRankSelect. The data structure consists
88 * of three levels (L0, L1, and L2) that contain different information
89 * regarding the popcount of the current block or all previous blocks.
90 *
91 * *Note* that rank support is also provided in addition to select support by
92 * \c RankSelect, which uses this rank support implementation
93 * internally.
94 *
95 * \tparam OptimizedFor Compile time option to optimize data structure for
96 * either 0, 1, or no specific type of query.
97 * \tparam VectorType Type of the vector the rank data structure is constructed
98 * for, e.g., plain \c BitVector or a compressed bit vector.
99 */
100template <OptimizedFor optimized_for = OptimizedFor::DONT_CARE,
101 typename VectorType = BitVector>
102class Rank {
103public:
104 //! Size of the bit vector the rank support is constructed for.
106 //! Pointer to the data of the bit vector.
107 VectorType::RawDataConstAccess data_;
108 //! Size of the bit vector in bits (only used for debug asserts)
109 size_t const bit_size_;
110
111 //! Array containing the number of set bits in the L0-blocks.
112 tlx::SimpleVector<uint64_t, tlx::SimpleVectorMode::NoInitNoDestroy> l0_;
113
114 //! Array containing the information about the L1- and L2-blocks.
115 tlx::SimpleVector<L12Type, tlx::SimpleVectorMode::NoInitNoDestroy> l12_;
116
117public:
118 //! Default constructor w/o parameter.
119 Rank() = default;
120
121 /*!
122 * \brief Constructor. Creates the auxiliary information for efficient rank
123 * queries.
124 * \param bv \c Vector of type \c VectorType the rank structure is created
125 * for.
126 */
127 Rank(VectorType& bv)
128 : data_size_(bv.size_),
129 data_(bv.data_.data()),
130 bit_size_(bv.size()),
131 l0_((data_size_ / PopcntRankSelectConfig::L0_WORD_SIZE) + 2),
132 l12_((data_size_ / PopcntRankSelectConfig::L1_WORD_SIZE) + 1) {
133 init();
134 }
135
136 /*!
137 * \brief Default move constructor.
138 * \param other Other rank data structure.
139 */
140 Rank(Rank&& other) = default;
141
142 /*!
143 * \brief Default move assignment.
144 * \param other Other rank data structure.
145 */
146 Rank& operator=(Rank&& other) = default;
147
148 //! Destructor. Deleting manually created arrays.
149 ~Rank() = default;
150
151 /*!
152 * \brief Computes rank of zeros.
153 * \param index Index the rank of zeros is computed for.
154 * \return Number of zeros (rank) before position \c index.
155 */
156 [[nodiscard("rank0 computed but not used")]] inline size_t
157 rank0(size_t index) const {
158 PASTA_ASSERT(index <= bit_size_, "Index outside of bit vector");
159 return index - rank1(index);
160 }
161
162 /*!
163 * \brief Computes rank of ones.
164 * \param index Index the rank of ones is computed for.
165 * \return Numbers of ones (rank) before position \c index.
166 */
167 [[nodiscard("rank1 computed but not used")]] inline size_t
168 rank1(size_t index) const {
169 PASTA_ASSERT(index <= bit_size_, "Index outside of bit vector");
170 size_t offset = ((index / PopcntRankSelectConfig::L2_BIT_SIZE) * 8);
171 size_t const l1_pos = index / PopcntRankSelectConfig::L1_BIT_SIZE;
172 size_t const l2_pos = (index % PopcntRankSelectConfig::L1_BIT_SIZE) /
174 size_t result =
175 l0_[index / PopcntRankSelectConfig::L0_BIT_SIZE] + l12_[l1_pos].l1;
176
177 auto l2 = l12_[l1_pos].l2_values;
178 for (size_t i = 0; i < l2_pos; ++i) {
179 result += (l2 & uint16_t(0b1111111111));
180 l2 >>= 10;
181 }
182
183 // It is faster to not have a specialized rank0 function when
184 // optimized for zero queries, because there is no popcount for
185 // zero equivalent and for all popcounts in this code, the words
186 // would have to be bit-wise negated, which is more expensive than
187 // the computation below.
188 if constexpr (!optimize_one_or_dont_care(optimized_for)) {
189 result = ((l1_pos * PopcntRankSelectConfig::L1_BIT_SIZE) +
191 result;
192 }
194 PASTA_ASSERT(index < PopcntRankSelectConfig::L2_BIT_SIZE,
195 "Trying to access bits that should be "
196 "covered in an L1-block");
197 for (size_t i = 0; i < index / 64; ++i) {
198 result += std::popcount(data_[offset++]);
199 }
200 if (index %= 64; index > 0) [[likely]] {
201 uint64_t const remaining = data_[offset] << (64 - index);
202 result += std::popcount(remaining);
203 }
204 return result;
205 }
206
207 /*!
208 * \brief Estimate for the space usage.
209 * \return Number of bytes used by this data structure.
210 */
211 [[nodiscard("space usage computed but not used")]] virtual size_t
212 space_usage() const {
213 return l0_.size() * sizeof(uint64_t) + l12_.size() * sizeof(L12Type) +
214 sizeof(*this);
215 }
216
217private:
218 //! Function used for initializing data structure to reduce LOCs of
219 //! constructor.
220 void init() {
221 l0_[0] = 0;
222
223 size_t l0_pos = 1;
224 size_t l12_pos = 0;
225 uint32_t l1_entry = 0UL;
226
227 uint64_t const* data = data_;
228 uint64_t const* const data_end = data_ + data_size_;
229
230 // For each full L12-Block
231 std::array<uint16_t, 3> l2_entries = {0, 0, 0};
232 while (data + 32 <= data_end) {
233 uint32_t new_l1_entry = l1_entry;
234 for (size_t i = 0; i < 3; ++i) {
235 if constexpr (optimize_one_or_dont_care(optimized_for)) {
236 l2_entries[i] = popcount<8>(data);
237 } else {
238 l2_entries[i] = popcount_zeros<8>(data);
239 }
240 data += 8;
241 new_l1_entry += l2_entries[i];
242 }
243 l12_[l12_pos++] = L12Type(l1_entry, l2_entries);
244 if constexpr (optimize_one_or_dont_care(optimized_for)) {
245 new_l1_entry += popcount<8>(data);
246 } else {
247 new_l1_entry += popcount_zeros<8>(data);
248 }
249 data += 8;
250 l1_entry = new_l1_entry;
251
254 0) [[unlikely]] {
255 l0_[l0_pos] = (l0_[l0_pos - 1] + l1_entry);
256 ++l0_pos;
257 l1_entry = 0;
258 }
259 }
260 // For the last not full L12-Block
261 l2_entries = {0, 0, 0};
262 size_t l2_pos = 0;
263 while (data + 8 < data_end) {
264 if constexpr (optimize_one_or_dont_care(optimized_for)) {
265 l2_entries[l2_pos++] = popcount<8>(data);
266 } else {
267 l2_entries[l2_pos++] = popcount_zeros<8>(data);
268 }
269 data += 8;
270 }
271 if (l2_pos < 3) {
272 while (data < data_end) {
273 if constexpr (optimize_one_or_dont_care(optimized_for)) {
274 l2_entries[l2_pos] += popcount<1>(data++);
275 } else {
276 l2_entries[l2_pos] += popcount_zeros<1>(data++);
277 }
278 }
279 }
280 l12_[l12_pos] = L12Type(l1_entry, l2_entries);
283 0) [[unlikely]] {
284 l0_[l0_pos] += (l0_[l0_pos - 1] + l1_entry);
285 ++l0_pos;
286 l1_entry = 0;
287 } else {
288 // Append sentinel (max uint64_t value) to l0_, as this makes some
289 // loop-conditions in during select queries easier
290 l0_[l0_pos] = std::numeric_limits<uint64_t>::max();
291 }
292 }
293}; // class Rank
294
295//! \}
296
297} // namespace pasta
298
299/******************************************************************************/
Uncompressed, highly tuned, fixed size bit vector.
Definition: bit_vector.hpp:179
Rank support for BitVector.
Definition: rank.hpp:102
tlx::SimpleVector< uint64_t, tlx::SimpleVectorMode::NoInitNoDestroy > l0_
Array containing the number of set bits in the L0-blocks.
Definition: rank.hpp:112
VectorType::RawDataConstAccess data_
Pointer to the data of the bit vector.
Definition: rank.hpp:107
Rank(Rank &&other)=default
Default move constructor.
size_t rank1(size_t index) const
Computes rank of ones.
Definition: rank.hpp:168
virtual size_t space_usage() const
Estimate for the space usage.
Definition: rank.hpp:212
Rank & operator=(Rank &&other)=default
Default move assignment.
~Rank()=default
Destructor. Deleting manually created arrays.
size_t const bit_size_
Size of the bit vector in bits (only used for debug asserts)
Definition: rank.hpp:109
Rank()=default
Default constructor w/o parameter.
Rank(VectorType &bv)
Constructor. Creates the auxiliary information for efficient rank queries.
Definition: rank.hpp:127
size_t data_size_
Size of the bit vector the rank support is constructed for.
Definition: rank.hpp:105
tlx::SimpleVector< L12Type, tlx::SimpleVectorMode::NoInitNoDestroy > l12_
Array containing the information about the L1- and L2-blocks.
Definition: rank.hpp:115
size_t rank0(size_t index) const
Computes rank of zeros.
Definition: rank.hpp:157
OptimizedFor
Enum used to specify which queries the rank (and select) data structures should be optimized for.
Definition: optimized_for.hpp:40
constexpr bool optimize_one_or_dont_care(OptimizedFor const optimized_for)
Helper function indicating if queries should be optimized for one queries or the caller does not care...
Definition: optimized_for.hpp:59
@ DONT_CARE
It does not matter (both types are called equally often).
Struct used to store L1- and L2-blocks for BitVectorRank and BitVectorSelect.
Definition: l12_type.hpp:37
Static configuration for Rank and RankSelect.
Definition: rank.hpp:60
static constexpr size_t L0_WORD_SIZE
Number of 64-bit words covered by an L0-block.
Definition: rank.hpp:74
static constexpr size_t SELECT_SAMPLE_RATE
Sample rate of positions for faster select queries.
Definition: rank.hpp:77
static constexpr size_t L2_WORD_SIZE
Number of 64-bit words covered by an L2-block.
Definition: rank.hpp:70
static constexpr size_t L2_BIT_SIZE
Bits covered by an L2-block.
Definition: rank.hpp:62
static constexpr size_t L0_BIT_SIZE
Bits covered by an L0-block.
Definition: rank.hpp:66
static constexpr size_t L1_BIT_SIZE
Bits covered by an L1-block.
Definition: rank.hpp:64
static constexpr size_t L1_WORD_SIZE
Number of 64-bit words covered by an L1-block.
Definition: rank.hpp:72