[QUEUED scylladb next] compatible_ring_position_or_view: make it cheap to copy

[Commit Bot]

From: Botond Dénes <bde...@scylladb.com>
Committer: Avi Kivity <a...@scylladb.com>
Branch: next

compatible_ring_position_or_view: make it cheap to copy

This class exists for one purpose only: to serve as glue code between
dht::ring_position and boost::icl::interval_map. The latter requires
that keys in its intervals are:
* default constructible
* copyable
* have standalone compare operations

For this reason we have to wrap `dht::ring_position` in a class,
together with a schema to provide all this. This is
`compatible_ring_position`. There is one further requirement by code
using the interval map: it wants to do lookups without copying the
lookup key(s). To solve this, we came up with
`compatible_ring_position_or_view` which is a union of a key or a key
view + schema. As we recently found out, boost::icl copies its keys **a
lot**. It seems to assume these keys are cheap to copy and carelessly
copies them around even when iterating over the map. But
`compatible_ring_position_or_view` is not cheap to copy as it copies a
`dht::ring_position` which allocates, and it does that via an
`std::optional` and `std::variant` to add insult to injury.
This patch make said class cheap to copy, by getting rid of the variant
and storing the `dht::ring_position` via a shared pointer. The view is
stored separately and either points to the ring position stored in the
shared pointer or to an outside ring position (for lookups).

Fixes: #11669

Closes #11670

---
diff --git a/compatible_ring_position.hh b/compatible_ring_position.hh
--- a/compatible_ring_position.hh
+++ b/compatible_ring_position.hh
@@ -10,126 +10,29 @@
#pragma once

#include "dht/i_partitioner.hh"
-#include <optional>
-#include <variant>
-
-// Wraps ring_position_view so it is compatible with old-style C++: default
-// constructor, stateless comparators, yada yada.
-class compatible_ring_position_view {
- const ::schema* _schema = nullptr;
- // Optional to supply a default constructor, no more.
- std::optional<dht::ring_position_view> _rpv;
-public:
- constexpr compatible_ring_position_view() = default;
- compatible_ring_position_view(const schema& s, dht::ring_position_view rpv)
- : _schema(&s), _rpv(rpv) {
- }
- const dht::ring_position_view& position() const {
- return *_rpv;
- }
- const ::schema& schema() const {
- return *_schema;
- }
- friend std::strong_ordering tri_compare(const compatible_ring_position_view& x, const compatible_ring_position_view& y) {
- return dht::ring_position_tri_compare(*x._schema, *x._rpv, *y._rpv);
- }
- friend bool operator<(const compatible_ring_position_view& x, const compatible_ring_position_view& y) {
- return tri_compare(x, y) < 0;
- }
- friend bool operator<=(const compatible_ring_position_view& x, const compatible_ring_position_view& y) {
- return tri_compare(x, y) <= 0;
- }
- friend bool operator>(const compatible_ring_position_view& x, const compatible_ring_position_view& y) {
- return tri_compare(x, y) > 0;
- }
- friend bool operator>=(const compatible_ring_position_view& x, const compatible_ring_position_view& y) {
- return tri_compare(x, y) >= 0;
- }
- friend bool operator==(const compatible_ring_position_view& x, const compatible_ring_position_view& y) {
- return tri_compare(x, y) == 0;
- }
- friend bool operator!=(const compatible_ring_position_view& x, const compatible_ring_position_view& y) {
- return tri_compare(x, y) != 0;
- }
-};
-
-// Wraps ring_position so it is compatible with old-style C++: default
-// constructor, stateless comparators, yada yada.
-class compatible_ring_position {
- schema_ptr _schema;
- // Optional to supply a default constructor, no more.
- std::optional<dht::ring_position> _rp;
-public:
- constexpr compatible_ring_position() = default;
- compatible_ring_position(schema_ptr s, dht::ring_position rp)
- : _schema(std::move(s)), _rp(std::move(rp)) {
- }
- dht::ring_position_view position() const {
- return *_rp;
- }
- const ::schema& schema() const {
- return *_schema;
- }
- friend std::strong_ordering tri_compare(const compatible_ring_position& x, const compatible_ring_position& y) {
- return dht::ring_position_tri_compare(*x._schema, *x._rp, *y._rp);
- }
- friend bool operator<(const compatible_ring_position& x, const compatible_ring_position& y) {
- return tri_compare(x, y) < 0;
- }
- friend bool operator<=(const compatible_ring_position& x, const compatible_ring_position& y) {
- return tri_compare(x, y) <= 0;
- }
- friend bool operator>(const compatible_ring_position& x, const compatible_ring_position& y) {
- return tri_compare(x, y) > 0;
- }
- friend bool operator>=(const compatible_ring_position& x, const compatible_ring_position& y) {
- return tri_compare(x, y) >= 0;
- }
- friend bool operator==(const compatible_ring_position& x, const compatible_ring_position& y) {
- return tri_compare(x, y) == 0;
- }
- friend bool operator!=(const compatible_ring_position& x, const compatible_ring_position& y) {
- return tri_compare(x, y) != 0;
- }
-};

// Wraps ring_position or ring_position_view so either is compatible with old-style C++: default
// constructor, stateless comparators, yada yada.
// The motivations for supporting both types are to make containers self-sufficient by not relying
// on callers to keep ring position alive, allow lookup on containers that don't support different
// key types, and also avoiding unnecessary copies.
class compatible_ring_position_or_view {
- // Optional to supply a default constructor, no more.
- std::optional<std::variant<compatible_ring_position, compatible_ring_position_view>> _crp_or_view;
+ schema_ptr _schema;
+ lw_shared_ptr<dht::ring_position> _rp;
+ dht::ring_position_view_opt _rpv; // optional only for default ctor, nothing more
public:
- constexpr compatible_ring_position_or_view() = default;
+ compatible_ring_position_or_view() = default;
explicit compatible_ring_position_or_view(schema_ptr s, dht::ring_position rp)
- : _crp_or_view(compatible_ring_position(std::move(s), std::move(rp))) {
+ : _schema(std::move(s)), _rp(make_lw_shared<dht::ring_position>(std::move(rp))), _rpv(dht::ring_position_view(*_rp)) {
}
explicit compatible_ring_position_or_view(const schema& s, dht::ring_position_view rpv)
- : _crp_or_view(compatible_ring_position_view(s, rpv)) {
+ : _schema(s.shared_from_this()), _rpv(rpv) {
}
- dht::ring_position_view position() const {
- struct rpv_accessor {
- dht::ring_position_view operator()(const compatible_ring_position& crp) {
- return crp.position();
- }
- dht::ring_position_view operator()(const compatible_ring_position_view& crpv) {
- return crpv.position();
- }
- };
- return std::visit(rpv_accessor{}, *_crp_or_view);
+ const dht::ring_position_view& position() const {
+ return *_rpv;
}
friend std::strong_ordering tri_compare(const compatible_ring_position_or_view& x, const compatible_ring_position_or_view& y) {
- struct schema_accessor {
- const ::schema& operator()(const compatible_ring_position& crp) {
- return crp.schema();
- }
- const ::schema& operator()(const compatible_ring_position_view& crpv) {
- return crpv.schema();
- }
- };
- return dht::ring_position_tri_compare(std::visit(schema_accessor{}, *x._crp_or_view), x.position(), y.position());
+ return dht::ring_position_tri_compare(*x._schema, x.position(), y.position());
}
friend bool operator<(const compatible_ring_position_or_view& x, const compatible_ring_position_or_view& y) {
return tri_compare(x, y) < 0;
diff --git a/dht/i_partitioner.hh b/dht/i_partitioner.hh
--- a/dht/i_partitioner.hh
+++ b/dht/i_partitioner.hh
@@ -11,6 +11,7 @@

#include <seastar/core/shared_ptr.hh>
#include <seastar/core/sstring.hh>
+#include <seastar/util/optimized_optional.hh>
#include "types.hh"
#include "keys.hh"
#include "utils/managed_bytes.hh"
@@ -317,6 +318,9 @@ class ring_position_view {
const dht::token* _token; // always not nullptr
const partition_key* _key; // Can be nullptr
int8_t _weight;
+private:
+ ring_position_view() noexcept : _token(nullptr), _key(nullptr), _weight(0) { }
+ explicit operator bool() const noexcept { return bool(_token); }
public:
using token_bound = ring_position::token_bound;
struct after_key_tag {};
@@ -404,9 +408,11 @@ public:
after_key is_after_key() const { return after_key(_weight == 1); }

friend std::ostream& operator<<(std::ostream&, ring_position_view);
+ friend class optimized_optional<ring_position_view>;
};

using ring_position_ext_view = ring_position_view;
+using ring_position_view_opt = optimized_optional<ring_position_view>;

//
// Represents position in the ring of partitions, where partitions are ordered
diff --git a/test/boost/sstable_datafile_test.cc b/test/boost/sstable_datafile_test.cc
--- a/test/boost/sstable_datafile_test.cc
+++ b/test/boost/sstable_datafile_test.cc
@@ -2840,7 +2840,7 @@ static dht::token token_from_long(int64_t value) {

SEASTAR_TEST_CASE(basic_interval_map_testing_for_sstable_set) {
using value_set = std::unordered_set<int64_t>;
- using interval_map_type = boost::icl::interval_map<compatible_ring_position, value_set>;
+ using interval_map_type = boost::icl::interval_map<compatible_ring_position_or_view, value_set>;
using interval_type = interval_map_type::interval_type;

interval_map_type map;
@@ -2850,8 +2850,8 @@ SEASTAR_TEST_CASE(basic_interval_map_testing_for_sstable_set) {
.with_column("value", int32_type);
auto s = builder.build();

- auto make_pos = [&] (int64_t token) -> compatible_ring_position {
- return compatible_ring_position(s, dht::ring_position::starting_at(token_from_long(token)));
+ auto make_pos = [&] (int64_t token) -> compatible_ring_position_or_view {
+ return compatible_ring_position_or_view(s, dht::ring_position::starting_at(token_from_long(token)));
};

auto add = [&] (int64_t start, int64_t end, int gen) {

[Commit Bot]

From: Botond Dénes <bde...@scylladb.com>
Committer: Avi Kivity <a...@scylladb.com>

Branch: master