OILS / vendor / souffle / datastructure / RecordTableImpl.h View on Github | oilshell.org

599 lines, 373 significant
1/*
2 * Souffle - A Datalog Compiler
3 * Copyright (c) 2022, The Souffle Developers. All rights reserved
4 * Licensed under the Universal Permissive License v 1.0 as shown at:
5 * - https://opensource.org/licenses/UPL
6 * - <souffle root>/licenses/SOUFFLE-UPL.txt
7 */
8
9/**
10 * @file RecordTableImpl.h
11 *
12 * RecordTable definition
13 */
14
15#pragma once
16
17#include "souffle/RamTypes.h"
18#include "souffle/RecordTable.h"
19#include "souffle/datastructure/ConcurrentFlyweight.h"
20#include "souffle/utility/span.h"
21
22#include <cassert>
23#include <cstddef>
24#include <limits>
25#include <memory>
26#include <utility>
27#include <vector>
28
29namespace souffle {
30
31namespace details {
32
33// Helper to unroll for loop
34template <auto Start, auto End, auto Inc, class F>
35constexpr void constexpr_for(F&& f) {
36 if constexpr (Start < End) {
37 f(std::integral_constant<decltype(Start), Start>());
38 constexpr_for<Start + Inc, End, Inc>(f);
39 }
40}
41
42/// @brief The data-type of RamDomain records of any size.
43using GenericRecord = std::vector<RamDomain>;
44
45/// @brief The data-type of RamDomain records of specialized size.
46template <std::size_t Arity>
47using SpecializedRecord = std::array<RamDomain, Arity>;
48
49/// @brief A view in a sequence of RamDomain value.
50// TODO: use a `span`.
51struct GenericRecordView {
52 explicit GenericRecordView(const RamDomain* Data, const std::size_t Arity) : Data(Data), Arity(Arity) {}
53 GenericRecordView(const GenericRecordView& Other) : Data(Other.Data), Arity(Other.Arity) {}
54 GenericRecordView(GenericRecordView&& Other) : Data(Other.Data), Arity(Other.Arity) {}
55
56 const RamDomain* const Data;
57 const std::size_t Arity;
58
59 const RamDomain* data() const {
60 return Data;
61 }
62
63 const RamDomain& operator[](int I) const {
64 assert(I >= 0 && static_cast<std::size_t>(I) < Arity);
65 return Data[I];
66 }
67};
68
69template <std::size_t Arity>
70struct SpecializedRecordView {
71 explicit SpecializedRecordView(const RamDomain* Data) : Data(Data) {}
72 SpecializedRecordView(const SpecializedRecordView& Other) : Data(Other.Data) {}
73 SpecializedRecordView(SpecializedRecordView&& Other) : Data(Other.Data) {}
74
75 const RamDomain* const Data;
76
77 const RamDomain* data() const {
78 return Data;
79 }
80
81 const RamDomain& operator[](int I) const {
82 assert(I >= 0 && static_cast<std::size_t>(I) < Arity);
83 return Data[I];
84 }
85};
86
87/// @brief Hash function object for a RamDomain record.
88struct GenericRecordHash {
89 explicit GenericRecordHash(const std::size_t Arity) : Arity(Arity) {}
90 GenericRecordHash(const GenericRecordHash& Other) : Arity(Other.Arity) {}
91 GenericRecordHash(GenericRecordHash&& Other) : Arity(Other.Arity) {}
92
93 const std::size_t Arity;
94 std::hash<RamDomain> domainHash;
95
96 template <typename T>
97 std::size_t operator()(const T& Record) const {
98 std::size_t Seed = 0;
99 for (std::size_t I = 0; I < Arity; ++I) {
100 Seed ^= domainHash(Record[(int)I]) + 0x9e3779b9U + (Seed << 6U) + (Seed >> 2U);
101 }
102 return Seed;
103 }
104};
105
106template <std::size_t Arity>
107struct SpecializedRecordHash {
108 explicit SpecializedRecordHash() {}
109 SpecializedRecordHash(const SpecializedRecordHash& Other) : DomainHash(Other.DomainHash) {}
110 SpecializedRecordHash(SpecializedRecordHash&& Other) : DomainHash(Other.DomainHash) {}
111
112 std::hash<RamDomain> DomainHash;
113
114 template <typename T>
115 std::size_t operator()(const T& Record) const {
116 std::size_t Seed = 0;
117 constexpr_for<0, Arity, 1>([&](auto I) {
118 Seed ^= DomainHash(Record[(int)I]) + 0x9e3779b9U + (Seed << 6U) + (Seed >> 2U);
119 });
120 return Seed;
121 }
122};
123
124template <>
125struct SpecializedRecordHash<0> {
126 explicit SpecializedRecordHash() {}
127 SpecializedRecordHash(const SpecializedRecordHash&) {}
128 SpecializedRecordHash(SpecializedRecordHash&&) {}
129
130 template <typename T>
131 std::size_t operator()(const T&) const {
132 return 0;
133 }
134};
135
136/// @brief Equality function object for RamDomain records.
137struct GenericRecordEqual {
138 explicit GenericRecordEqual(const std::size_t Arity) : Arity(Arity) {}
139 GenericRecordEqual(const GenericRecordEqual& Other) : Arity(Other.Arity) {}
140 GenericRecordEqual(GenericRecordEqual&& Other) : Arity(Other.Arity) {}
141
142 const std::size_t Arity;
143
144 template <typename T, typename U>
145 bool operator()(const T& A, const U& B) const {
146 return (std::memcmp(A.data(), B.data(), Arity * sizeof(RamDomain)) == 0);
147 }
148};
149
150template <std::size_t Arity>
151struct SpecializedRecordEqual {
152 explicit SpecializedRecordEqual() {}
153 SpecializedRecordEqual(const SpecializedRecordEqual&) {}
154 SpecializedRecordEqual(SpecializedRecordEqual&&) {}
155
156 template <typename T, typename U>
157 bool operator()(const T& A, const U& B) const {
158 constexpr std::size_t Len = Arity * sizeof(RamDomain);
159 return (std::memcmp(A.data(), B.data(), Len) == 0);
160 }
161};
162
163template <>
164struct SpecializedRecordEqual<0> {
165 explicit SpecializedRecordEqual() {}
166 SpecializedRecordEqual(const SpecializedRecordEqual&) {}
167 SpecializedRecordEqual(SpecializedRecordEqual&&) {}
168
169 template <typename T, typename U>
170 bool operator()(const T&, const U&) const {
171 return true;
172 }
173};
174
175/// @brief Less function object for RamDomain records.
176struct GenericRecordLess {
177 explicit GenericRecordLess(const std::size_t Arity) : Arity(Arity) {}
178 GenericRecordLess(const GenericRecordLess& Other) : Arity(Other.Arity) {}
179 GenericRecordLess(GenericRecordLess&& Other) : Arity(Other.Arity) {}
180
181 const std::size_t Arity;
182
183 template <typename T, typename U>
184 bool operator()(const T& A, const U& B) const {
185 return (std::memcmp(A.data(), B.data(), Arity * sizeof(RamDomain)) < 0);
186 }
187};
188
189template <std::size_t Arity>
190struct SpecializedRecordLess {
191 explicit SpecializedRecordLess() {}
192 SpecializedRecordLess(const SpecializedRecordLess&) {}
193 SpecializedRecordLess(SpecializedRecordLess&&) {}
194
195 template <typename T, typename U>
196 bool operator()(const T& A, const U& B) const {
197 constexpr std::size_t Len = Arity * sizeof(RamDomain);
198 return (std::memcmp(A.data(), B.data(), Len) < 0);
199 }
200};
201
202template <>
203struct SpecializedRecordLess<0> {
204 explicit SpecializedRecordLess() {}
205 SpecializedRecordLess(const SpecializedRecordLess&) {}
206 SpecializedRecordLess(SpecializedRecordLess&&) {}
207
208 template <typename T, typename U>
209 bool operator()(const T&, const U&) const {
210 return false;
211 }
212};
213
214/// @brief Compare function object for RamDomain records.
215struct GenericRecordCmp {
216 explicit GenericRecordCmp(const std::size_t Arity) : Arity(Arity) {}
217 GenericRecordCmp(const GenericRecordCmp& Other) : Arity(Other.Arity) {}
218 GenericRecordCmp(GenericRecordCmp&& Other) : Arity(Other.Arity) {}
219
220 const std::size_t Arity;
221
222 template <typename T, typename U>
223 int operator()(const T& A, const U& B) const {
224 return std::memcmp(A.data(), B.data(), Arity * sizeof(RamDomain));
225 }
226};
227
228template <std::size_t Arity>
229struct SpecializedRecordCmp {
230 explicit SpecializedRecordCmp() {}
231 SpecializedRecordCmp(const SpecializedRecordCmp&) {}
232 SpecializedRecordCmp(SpecializedRecordCmp&&) {}
233
234 template <typename T, typename U>
235 bool operator()(const T& A, const U& B) const {
236 constexpr std::size_t Len = Arity * sizeof(RamDomain);
237 return std::memcmp(A.data(), B.data(), Len);
238 }
239};
240
241template <>
242struct SpecializedRecordCmp<0> {
243 explicit SpecializedRecordCmp() {}
244 SpecializedRecordCmp(const SpecializedRecordCmp&) {}
245 SpecializedRecordCmp(SpecializedRecordCmp&&) {}
246
247 template <typename T, typename U>
248 bool operator()(const T&, const U&) const {
249 return 0;
250 }
251};
252
253/// @brief Factory of RamDomain record.
254struct GenericRecordFactory {
255 using value_type = GenericRecord;
256 using pointer = GenericRecord*;
257 using reference = GenericRecord&;
258
259 explicit GenericRecordFactory(const std::size_t Arity) : Arity(Arity) {}
260 GenericRecordFactory(const GenericRecordFactory& Other) : Arity(Other.Arity) {}
261 GenericRecordFactory(GenericRecordFactory&& Other) : Arity(Other.Arity) {}
262
263 const std::size_t Arity;
264
265 reference replace(reference Place, const std::vector<RamDomain>& V) {
266 assert(V.size() == Arity);
267 Place = V;
268 return Place;
269 }
270
271 reference replace(reference Place, const GenericRecordView& V) {
272 Place.clear();
273 Place.insert(Place.begin(), V.data(), V.data() + Arity);
274 return Place;
275 }
276
277 reference replace(reference Place, const RamDomain* V) {
278 Place.clear();
279 Place.insert(Place.begin(), V, V + Arity);
280 return Place;
281 }
282};
283
284template <std::size_t Arity>
285struct SpecializedRecordFactory {
286 using value_type = SpecializedRecord<Arity>;
287 using pointer = SpecializedRecord<Arity>*;
288 using reference = SpecializedRecord<Arity>&;
289
290 explicit SpecializedRecordFactory() {}
291 SpecializedRecordFactory(const SpecializedRecordFactory&) {}
292 SpecializedRecordFactory(SpecializedRecordFactory&&) {}
293
294 reference replace(reference Place, const SpecializedRecord<Arity>& V) {
295 assert(V.size() == Arity);
296 Place = V;
297 return Place;
298 }
299
300 reference replace(reference Place, const SpecializedRecordView<Arity>& V) {
301 constexpr std::size_t Len = Arity * sizeof(RamDomain);
302 std::memcpy(Place.data(), V.data(), Len);
303 return Place;
304 }
305
306 reference replace(reference Place, const RamDomain* V) {
307 constexpr std::size_t Len = Arity * sizeof(RamDomain);
308 std::memcpy(Place.data(), V, Len);
309 return Place;
310 }
311};
312
313template <>
314struct SpecializedRecordFactory<0> {
315 using value_type = SpecializedRecord<0>;
316 using pointer = SpecializedRecord<0>*;
317 using reference = SpecializedRecord<0>&;
318
319 explicit SpecializedRecordFactory() {}
320 SpecializedRecordFactory(const SpecializedRecordFactory&) {}
321 SpecializedRecordFactory(SpecializedRecordFactory&&) {}
322
323 reference replace(reference Place, const SpecializedRecord<0>&) {
324 return Place;
325 }
326
327 reference replace(reference Place, const SpecializedRecordView<0>&) {
328 return Place;
329 }
330
331 reference replace(reference Place, const RamDomain*) {
332 return Place;
333 }
334};
335
336} // namespace details
337
338/** @brief Interface of bidirectional mappping between records and record references. */
339class RecordMap {
340public:
341 virtual ~RecordMap() {}
342 virtual void setNumLanes(const std::size_t NumLanes) = 0;
343 virtual RamDomain pack(const std::vector<RamDomain>& Vector) = 0;
344 virtual RamDomain pack(const RamDomain* Tuple) = 0;
345 virtual RamDomain pack(const std::initializer_list<RamDomain>& List) = 0;
346 virtual const RamDomain* unpack(RamDomain index) const = 0;
347};
348
349/** @brief Bidirectional mappping between records and record references, for any record arity. */
350class GenericRecordMap : public RecordMap,
351 protected FlyweightImpl<details::GenericRecord, details::GenericRecordHash,
352 details::GenericRecordEqual, details::GenericRecordFactory> {
353 using Base = FlyweightImpl<details::GenericRecord, details::GenericRecordHash,
354 details::GenericRecordEqual, details::GenericRecordFactory>;
355
356 const std::size_t Arity;
357
358public:
359 explicit GenericRecordMap(const std::size_t lane_count, const std::size_t arity)
360 : Base(lane_count, 8, true, details::GenericRecordHash(arity), details::GenericRecordEqual(arity),
361 details::GenericRecordFactory(arity)),
362 Arity(arity) {}
363
364 virtual ~GenericRecordMap() {}
365
366 void setNumLanes(const std::size_t NumLanes) override {
367 Base::setNumLanes(NumLanes);
368 }
369
370 /** @brief converts record to a record reference */
371 RamDomain pack(const std::vector<RamDomain>& Vector) override {
372 return findOrInsert(Vector).first;
373 };
374
375 /** @brief converts record to a record reference */
376 RamDomain pack(const RamDomain* Tuple) override {
377 details::GenericRecordView View{Tuple, Arity};
378 return findOrInsert(View).first;
379 }
380
381 /** @brief converts record to a record reference */
382 RamDomain pack(const std::initializer_list<RamDomain>& List) override {
383 details::GenericRecordView View{std::data(List), Arity};
384 return findOrInsert(View).first;
385 }
386
387 /** @brief convert record reference to a record pointer */
388 const RamDomain* unpack(RamDomain Index) const override {
389 return fetch(Index).data();
390 }
391};
392
393/** @brief Bidirectional mappping between records and record references, specialized for a record arity. */
394template <std::size_t Arity>
395class SpecializedRecordMap
396 : public RecordMap,
397 protected FlyweightImpl<details::SpecializedRecord<Arity>, details::SpecializedRecordHash<Arity>,
398 details::SpecializedRecordEqual<Arity>, details::SpecializedRecordFactory<Arity>> {
399 using Record = details::SpecializedRecord<Arity>;
400 using RecordView = details::SpecializedRecordView<Arity>;
401 using RecordHash = details::SpecializedRecordHash<Arity>;
402 using RecordEqual = details::SpecializedRecordEqual<Arity>;
403 using RecordFactory = details::SpecializedRecordFactory<Arity>;
404 using Base = FlyweightImpl<Record, RecordHash, RecordEqual, RecordFactory>;
405
406public:
407 SpecializedRecordMap(const std::size_t LaneCount)
408 : Base(LaneCount, 8, true, RecordHash(), RecordEqual(), RecordFactory()) {}
409
410 virtual ~SpecializedRecordMap() {}
411
412 void setNumLanes(const std::size_t NumLanes) override {
413 Base::setNumLanes(NumLanes);
414 }
415
416 /** @brief converts record to a record reference */
417 RamDomain pack(const std::vector<RamDomain>& Vector) override {
418 assert(Vector.size() == Arity);
419 RecordView View{Vector.data()};
420 return Base::findOrInsert(View).first;
421 };
422
423 /** @brief converts record to a record reference */
424 RamDomain pack(const RamDomain* Tuple) override {
425 RecordView View{Tuple};
426 return Base::findOrInsert(View).first;
427 }
428
429 /** @brief converts record to a record reference */
430 RamDomain pack(const std::initializer_list<RamDomain>& List) override {
431 assert(List.size() == Arity);
432 RecordView View{std::data(List)};
433 return Base::findOrInsert(View).first;
434 }
435
436 /** @brief convert record reference to a record pointer */
437 const RamDomain* unpack(RamDomain Index) const override {
438 return Base::fetch(Index).data();
439 }
440};
441
442/** Record map specialized for arity 0 */
443template <>
444class SpecializedRecordMap<0> : public RecordMap {
445 // The empty record always at index 1
446 // The index 0 of each map is reserved.
447 static constexpr RamDomain EmptyRecordIndex = 1;
448
449 // To comply with previous behavior, the empty record
450 // has no data:
451 const RamDomain* EmptyRecordData = nullptr;
452
453public:
454 SpecializedRecordMap(const std::size_t /* LaneCount */) {}
455
456 virtual ~SpecializedRecordMap() {}
457
458 void setNumLanes(const std::size_t) override {}
459
460 /** @brief converts record to a record reference */
461 RamDomain pack([[maybe_unused]] const std::vector<RamDomain>& Vector) override {
462 assert(Vector.size() == 0);
463 return EmptyRecordIndex;
464 };
465
466 /** @brief converts record to a record reference */
467 RamDomain pack(const RamDomain*) override {
468 return EmptyRecordIndex;
469 }
470
471 /** @brief converts record to a record reference */
472 RamDomain pack([[maybe_unused]] const std::initializer_list<RamDomain>& List) override {
473 assert(List.size() == 0);
474 return EmptyRecordIndex;
475 }
476
477 /** @brief convert record reference to a record pointer */
478 const RamDomain* unpack([[maybe_unused]] RamDomain Index) const override {
479 assert(Index == EmptyRecordIndex);
480 return EmptyRecordData;
481 }
482};
483
484/** A concurrent Record Table with some specialized record maps. */
485template <std::size_t... SpecializedArities>
486class SpecializedRecordTable : public RecordTable {
487private:
488 // The current size of the Maps vector.
489 std::size_t Size;
490
491 // The record maps, indexed by arity.
492 std::vector<RecordMap*> Maps;
493
494 // The concurrency manager.
495 mutable ConcurrentLanes Lanes;
496
497 template <std::size_t Arity, std::size_t... Arities>
498 void CreateSpecializedMaps() {
499 if (Arity >= Size) {
500 Size = Arity + 1;
501 Maps.reserve(Size);
502 Maps.resize(Size);
503 }
504 Maps[Arity] = new SpecializedRecordMap<Arity>(Lanes.lanes());
505 if constexpr (sizeof...(Arities) > 0) {
506 CreateSpecializedMaps<Arities...>();
507 }
508 }
509
510public:
511 /** @brief Construct a record table with the number of concurrent access lanes. */
512 SpecializedRecordTable(const std::size_t LaneCount) : Size(0), Lanes(LaneCount) {
513 CreateSpecializedMaps<SpecializedArities...>();
514 }
515
516 SpecializedRecordTable() : SpecializedRecordTable(1) {}
517
518 virtual ~SpecializedRecordTable() {
519 for (auto Map : Maps) {
520 delete Map;
521 }
522 }
523
524 /**
525 * @brief set the number of concurrent access lanes.
526 * Not thread-safe, use only when the datastructure is not being used.
527 */
528 virtual void setNumLanes(const std::size_t NumLanes) override {
529 Lanes.setNumLanes(NumLanes);
530 for (auto& Map : Maps) {
531 if (Map) {
532 Map->setNumLanes(NumLanes);
533 }
534 }
535 }
536
537 /** @brief convert tuple to record reference */
538 virtual RamDomain pack(const RamDomain* Tuple, const std::size_t Arity) override {
539 auto Guard = Lanes.guard();
540 return lookupMap(Arity).pack(Tuple);
541 }
542
543 /** @brief convert tuple to record reference */
544 virtual RamDomain pack(const std::initializer_list<RamDomain>& List) override {
545 auto Guard = Lanes.guard();
546 return lookupMap(List.size()).pack(std::data(List));
547 }
548
549 /** @brief convert record reference to a record */
550 virtual const RamDomain* unpack(const RamDomain Ref, const std::size_t Arity) const override {
551 auto Guard = Lanes.guard();
552 return lookupMap(Arity).unpack(Ref);
553 }
554
555private:
556 /** @brief lookup RecordMap for a given arity; the map for that arity must exist. */
557 RecordMap& lookupMap(const std::size_t Arity) const {
558 assert(Arity < Size && "Lookup for an arity while there is no record for that arity.");
559 auto* Map = Maps[Arity];
560 assert(Map != nullptr && "Lookup for an arity while there is no record for that arity.");
561 return *Map;
562 }
563
564 /** @brief lookup RecordMap for a given arity; if it does not exist, create new RecordMap */
565 RecordMap& lookupMap(const std::size_t Arity) {
566 if (Arity < Size) {
567 auto* Map = Maps[Arity];
568 if (Map) {
569 return *Map;
570 }
571 }
572
573 createMap(Arity);
574 return *Maps[Arity];
575 }
576
577 /** @brief create the RecordMap for the given arity. */
578 void createMap(const std::size_t Arity) {
579 Lanes.beforeLockAllBut();
580 if (Arity < Size && Maps[Arity] != nullptr) {
581 // Map of required arity has been created concurrently
582 Lanes.beforeUnlockAllBut();
583 return;
584 }
585 Lanes.lockAllBut();
586
587 if (Arity >= Size) {
588 Size = Arity + 1;
589 Maps.reserve(Size);
590 Maps.resize(Size);
591 }
592 Maps[Arity] = new GenericRecordMap(Lanes.lanes(), Arity);
593
594 Lanes.beforeUnlockAllBut();
595 Lanes.unlockAllBut();
596 }
597};
598
599} // namespace souffle