Branch data Line data Source code
1 : : #include <mutable/storage/DataLayout.hpp>
2 : :
3 : : #include <mutable/catalog/Schema.hpp>
4 : : #include <mutable/catalog/Type.hpp>
5 : :
6 : :
7 : : using namespace m;
8 : : using namespace m::storage;
9 : :
10 : :
11 : : /*----------------------------------------------------------------------------------------------------------------------
12 : : * DataLayout::Node
13 : : *--------------------------------------------------------------------------------------------------------------------*/
14 : :
15 : 2813 : DataLayout::Node::~Node() { }
16 : :
17 : :
18 : : /*----------------------------------------------------------------------------------------------------------------------
19 : : * DataLayout::Leaf
20 : : *--------------------------------------------------------------------------------------------------------------------*/
21 : :
22 : 0 : void DataLayout::Leaf::accept(ConstDataLayoutVisitor &v) const { v(*this); };
23 : :
24 : :
25 : : /*----------------------------------------------------------------------------------------------------------------------
26 : : * DataLayout::INode
27 : : *--------------------------------------------------------------------------------------------------------------------*/
28 : :
29 : 1286 : DataLayout::Leaf & DataLayout::INode::add_leaf(const m::Type *type, size_type idx,
30 : : uint64_t offset_in_bits, uint64_t stride_in_bits)
31 : : {
32 [ + + ]: 1286 : M_insist(this->num_tuples() != 1 or stride_in_bits == 0, "no stride without repetition");
33 [ + + + + ]: 1286 : M_insist(stride_in_bits % 8 == 0 or type->is_boolean() or type->is_bitmap(),
34 : : "only booleans and bitmaps may not be byte aligned");
35 [ + + + + ]: 1286 : M_insist(offset_in_bits % 8 == 0 or type->is_boolean() or type->is_bitmap(),
36 : : "only booleans and bitmaps may not be byte aligned");
37 : :
38 [ + - ]: 1286 : auto leaf = new Leaf(type, idx);
39 [ + - + - : 5144 : children_.emplace_back(child_t{
+ - + - ]
40 : 1286 : .ptr = std::unique_ptr<DataLayout::Node>(as<Node>(leaf)),
41 : 1286 : .offset_in_bits = offset_in_bits,
42 : 1286 : .stride_in_bits = stride_in_bits,
43 : : });
44 : 1286 : return *leaf;
45 : 0 : }
46 : :
47 : 4 : DataLayout::INode & DataLayout::INode::add_inode(size_type num_tuples, uint64_t offset_in_bits, uint64_t stride_in_bits)
48 : : {
49 : 4 : M_insist(num_tuples != 0, "the new INode must be large enough for at least one tuple");
50 [ + - ]: 4 : M_insist(this->num_tuples() != 1 or stride_in_bits == 0, "no stride without repetition");
51 : 4 : M_insist(this->num_tuples() % num_tuples == 0,
52 : : "the number of tuples in the parent must be a whole multiple of the number of tuples of the newly created "
53 : : "INode");
54 : 4 : M_insist(offset_in_bits % 8 == 0, "the offset of the newly created INode must be byte aligned");
55 : 4 : M_insist(stride_in_bits % 8 == 0, "the stride of the newly created INode must be byte aligned");
56 : :
57 [ + - ]: 4 : auto inode = new INode(num_tuples);
58 [ + - + - : 16 : children_.emplace_back(child_t{
+ - + - ]
59 : 4 : .ptr = std::unique_ptr<DataLayout::Node>(as<Node>(inode)),
60 : 4 : .offset_in_bits = offset_in_bits,
61 : 4 : .stride_in_bits = stride_in_bits,
62 : : });
63 : 4 : return *inode;
64 : 0 : }
65 : :
66 : 0 : void DataLayout::INode::accept(ConstDataLayoutVisitor &v) const { v(*this); }
67 : :
68 : 26 : void DataLayout::INode::for_sibling_leaves(level_info_stack_t &level_info_stack, uint64_t inode_offset_in_bits,
69 : : const callback_leaves_t &callback) const
70 : : {
71 : 26 : std::vector<leaf_info_t> leaves;
72 [ + - + - ]: 26 : leaves.reserve(this->num_children());
73 : :
74 [ + - + - : 118 : for (auto &child : *this) {
+ - + + +
- + - ]
75 [ + - + + ]: 91 : if (auto child_leaf = cast<const Leaf>(child.ptr.get())) {
76 [ + - + - : 304 : leaves.emplace_back(leaf_info_t{
+ - + - ]
77 : 76 : .leaf = *child_leaf,
78 : 76 : .offset_in_bits = child.offset_in_bits,
79 : 76 : .stride_in_bits = child.stride_in_bits,
80 : : });
81 : 76 : } else {
82 [ + - ]: 15 : auto child_inode = as<const INode>(child.ptr.get());
83 [ + - ]: 30 : level_info_stack.emplace_back(level_info_t{
84 : 15 : .stride_in_bits = child.stride_in_bits,
85 [ + - ]: 15 : .num_tuples = child_inode->num_tuples(),
86 : : });
87 [ + - ]: 15 : child_inode->for_sibling_leaves(level_info_stack, inode_offset_in_bits + child.offset_in_bits, callback);
88 : 15 : level_info_stack.pop_back();
89 : : }
90 : : }
91 : :
92 [ + + ]: 26 : if (not leaves.empty())
93 [ + - ]: 13 : callback(leaves, level_info_stack, inode_offset_in_bits);
94 : 26 : }
95 : :
96 : : M_LCOV_EXCL_START
97 : : namespace {
98 : :
99 : : /** Start a new line with proper indentation. */
100 : : std::ostream & indent(std::ostream &out, unsigned indentation)
101 : : {
102 : : out << '\n' << std::string(4 * indentation, ' ');
103 : : return out;
104 : : }
105 : :
106 : : }
107 : :
108 : : void DataLayout::INode::print(std::ostream &out, unsigned int indentation) const
109 : : {
110 : : const std::size_t decimal_places = std::ceil(num_children() / Numeric::DECIMAL_TO_BINARY_DIGITS);
111 : :
112 : : auto it = cbegin();
113 : : for (std::size_t i = 0; i != num_children(); ++i, ++it) {
114 : : M_insist(it != cend());
115 : :
116 : : indent(out, indentation) << "[" << std::setw(decimal_places) << i << "]: ";
117 : :
118 : : auto &child = *it;
119 : : if (auto child_leaf = cast<const Leaf>(child.ptr.get())) {
120 : : out << "Leaf " << child_leaf->index() << " of type " << *child_leaf->type() << " with bit offset "
121 : : << child.offset_in_bits << " and bit stride " << child.stride_in_bits;
122 : : } else {
123 : : auto child_inode = as<const INode>(child.ptr.get());
124 : : out << "INode of " << child_inode->num_tuples() << " tuple(s) with bit offset " << child.offset_in_bits
125 : : << " and bit stride " << child.stride_in_bits;
126 : : child_inode->print(out, indentation + 1);
127 : : }
128 : : }
129 : : }
130 : : M_LCOV_EXCL_STOP
131 : :
132 : :
133 : : /*----------------------------------------------------------------------------------------------------------------------
134 : : * DataLayout
135 : : *--------------------------------------------------------------------------------------------------------------------*/
136 : :
137 : 0 : DataLayout::Leaf & DataLayout::add_leaf(const m::Type *type, size_type idx, uint64_t stride_in_bits)
138 : : {
139 : 0 : M_insist(inode_.num_children() == 0, "child already set");
140 : 0 : return inode_.add_leaf(type, idx, 0, stride_in_bits);
141 : : }
142 : :
143 : 344 : DataLayout::INode & DataLayout::add_inode(size_type num_tuples, uint64_t stride_in_bits)
144 : : {
145 : 344 : M_insist(inode_.num_children() == 0, "child already set");
146 : 344 : M_insist(num_tuples != 0, "the new INode must be large enough for at least one tuple");
147 [ + - ]: 344 : M_insist(inode_.num_tuples() != 1 or stride_in_bits == 0, "no stride without repetition");
148 : 344 : M_insist(stride_in_bits % 8 == 0, "the stride of the newly created INode must be byte aligned");
149 : :
150 [ + - ]: 344 : auto inode = new INode(num_tuples);
151 [ + - + - : 1032 : inode_.children_.emplace_back(INode::child_t{
+ - ]
152 : 344 : .ptr = std::unique_ptr<DataLayout::Node>(as<Node>(inode)),
153 : : .offset_in_bits = 0,
154 : 344 : .stride_in_bits = stride_in_bits,
155 : : });
156 : 344 : return *inode;
157 : 0 : }
158 : :
159 : 0 : void DataLayout::accept(ConstDataLayoutVisitor &v) const { v(*this); }
160 : :
161 : 11 : void DataLayout::for_sibling_leaves(DataLayout::callback_leaves_t callback) const
162 : : {
163 : 11 : level_info_stack_t level_info_stack;
164 [ + - ]: 11 : inode_.for_sibling_leaves(level_info_stack, 0, callback);
165 : 11 : }
166 : :
167 : :
168 : : /*======================================================================================================================
169 : : * Helper functions for SIMD support
170 : : *====================================================================================================================*/
171 : :
172 : 0 : bool m::storage::supports_simd(const DataLayout &layout, const Schema &layout_schema, const Schema &tuple_schema)
173 : : {
174 : 0 : const bool needs_null_bitmap = [&]() {
175 [ # # ]: 0 : for (auto &tuple_entry : tuple_schema) {
176 [ # # ]: 0 : if (layout_schema[tuple_entry.id].second.nullable())
177 : 0 : return true; // found an entry in `tuple_schema` that can be NULL according to `layout_schema`
178 : : }
179 : 0 : return false; // no attribute in `tuple_schema` can be NULL according to `layout_schema`
180 : 0 : }();
181 : :
182 : 0 : auto test_simd_support = [&](const DataLayout::INode& inode, auto &rec) {
183 [ # # ]: 0 : if (inode.num_children() == 0)
184 : 0 : return false; // invalid data layout
185 : :
186 [ # # ]: 0 : if (auto child_inode = cast<const DataLayout::INode>(inode[0].ptr.get());
187 [ # # ]: 0 : inode.num_children() == 1 and child_inode)
188 : : {
189 : 0 : return rec(*child_inode, rec); // recurse for single INode child
190 : : }
191 : :
192 : 0 : std::size_t num_simd_lanes = 1;
193 [ # # ]: 0 : for (auto &child : inode) {
194 [ # # ]: 0 : if (cast<const DataLayout::INode>(child.ptr.get()))
195 : 0 : return false; // multiple INode children or mixed Leaf and INode children
196 : :
197 : 0 : auto &child_leaf = as<const DataLayout::Leaf>(*child.ptr);
198 : 0 : const uint8_t bit_stride = child.stride_in_bits % 8;
199 [ # # ]: 0 : if (child_leaf.index() == layout_schema.num_entries()) { // NULL bitmap
200 [ # # ]: 0 : if (not needs_null_bitmap)
201 : 0 : continue; // no NULL bitmap needed
202 : :
203 [ # # ]: 0 : if (bit_stride) {
204 : 0 : return false; // NULL bitmap with bit stride currently not supported
205 : : } else {
206 [ # # ]: 0 : if (tuple_schema.num_entries() > 64)
207 : 0 : return false; // bytes containing a NULL bitmap must fit into scalar value
208 [ # # ]: 0 : if (std::max(ceil_to_pow_2(tuple_schema.num_entries()), 8UL) != child.stride_in_bits)
209 : 0 : return false; // distance between two NULL bits of a single attribute must be a power of 2
210 [ # # ]: 0 : if (child.offset_in_bits % 8 != 0)
211 : 0 : return false; // NULL bitmaps must not start with bit offset
212 : : }
213 : :
214 : 0 : num_simd_lanes = std::max<std::size_t>(num_simd_lanes, 16); // repeat 16 times for 128bit SIMD vectors
215 : 0 : } else { // regular entry
216 : 0 : auto tuple_it = tuple_schema.find(layout_schema[child_leaf.index()].id);
217 [ # # ]: 0 : if (tuple_it == tuple_schema.end())
218 : 0 : continue; // entry not contained in tuple schema
219 : 0 : M_insist(*tuple_it->type == *child_leaf.type());
220 : :
221 [ # # ]: 0 : if (bit_stride) {
222 [ # # ]: 0 : if (child.stride_in_bits != 1)
223 : 0 : return false; // stride must be 1 bit
224 : 0 : } else {
225 [ # # # # ]: 0 : if (tuple_it->type->is_boolean() and child.stride_in_bits != 8)
226 : 0 : return false; // booleans must be packed consecutively in bytes
227 [ # # ]: 0 : if (tuple_it->type->is_character_sequence())
228 : 0 : return false; // string SIMDfication currently not supported
229 : : }
230 : :
231 : 0 : const uint64_t size_in_bytes = (tuple_it->type->size() + 7) / 8;
232 : 0 : num_simd_lanes = std::max<std::size_t>(num_simd_lanes, 16 / size_in_bytes); // repeat to fill 128bit SIMD vector
233 : : }
234 : : }
235 : :
236 [ # # ]: 0 : if (inode.num_tuples() % num_simd_lanes != 0)
237 : 0 : return false; // number of tuples in INode must be a whole multiple of SIMD width
238 : :
239 : 0 : return true; // fallthrough
240 : 0 : };
241 : 0 : return test_simd_support(static_cast<const DataLayout::INode&>(layout), test_simd_support);
242 : : }
243 : :
244 : 0 : std::size_t m::storage::get_num_simd_lanes(const DataLayout &layout, const Schema &layout_schema,
245 : : const Schema &tuple_schema)
246 : : {
247 : 0 : M_insist(supports_simd(layout, layout_schema, tuple_schema),
248 : : "layout must support SIMD to retrieve its number of SIMD lanes");
249 : :
250 : 0 : std::size_t num_simd_lanes = 1;
251 [ # # ]: 0 : for (auto &tuple_entry : tuple_schema) {
252 [ # # ]: 0 : if (layout_schema[tuple_entry.id].second.nullable())
253 : 0 : return 16; // repeat 16 times for 128bit SIMD vector; return immediately since this is the max. #lanes
254 : :
255 : 0 : const uint64_t size_in_bytes = (tuple_entry.type->size() + 7) / 8;
256 : 0 : num_simd_lanes = std::max<std::size_t>(num_simd_lanes, 16 / size_in_bytes); // repeat to fill 128bit SIMD vector
257 : : }
258 : :
259 : 0 : return num_simd_lanes;
260 : 0 : }
|
