Below is some stripped down code from a physics simulation. The classes
Vector2
,Line
andPolygon
are probably self explanatory.I will focus here on the fact that
Polygon
stores itsVector2
vertices, as well as itsLine
s. The reason is that the calling code, here justoperator<<
, benefits from the convenience of simple ranged-for looping overLine
s as well asVec2
points. Also, theLine
s pre-calculate and cache their lengths and normal vectors, which were found to be performance bottlenecks in the full application, which accesses these many times in the hot inner loop.EDIT
Just to clarify what the code calling the classes below does – not shown for simplicity. It mainly does collision detection of thePolygon
s withParticles
. Essentially this amounts to:for (auto&& p: polys) { for (auto&& l: p.lines) { // access the pre-cached length and normal vector of `line` l.len // some fast maths l.norm // more fast maths } }
There are typically less than 10
Polygon
s and typically around 600 particles. The simulation runs at 20,000 frames per seconds, which means the above nested loop is called ~12’000’000 per second. This is why caching thestd::hypot
calls inVector2::mag()
insideLine::len
is really worthwhile.END OF EDIT
It was tempting to make
Line::start
andLine::end
references to elements in thePolygon::points
vector, to ensure consistency, reduce the size ofLine
slightly, allow future modification ofpoints
etc. The code below has these references.However, the references cause somewhat subtle dangling problems as explored here. TLDR, in the original code, when
polys
inmain()
reallocates for growth, it does so by copying (!) thePolygon
elements. This happens because the 3rd party typesf::ConvexShape
is not movable. This makes theLine::start/end
reference dangle, after a deep copy ofPolygon::points
.The code below addresses this problem in 3 ways:
- It makes the
Polygon::shape
astd::unique_ptr
which makesPolygon
a movable type again. This means, that whenpolys
inmain()
reallocates it will do so using move-construction and that is guaranteed to keep the references inPolygon::Line
in tact, because thePolygon::points
(the heap memory part) won’t move.- For safety we
delete
thePolygon
copy constructor and copy assignment operator- For protection against future code refactoring we
static_assert
thatPolygon
must be nothrow move constructible, which is the conditionstd::vector
cares about.So here is the design query:
This all seems very awkward and brittle for a simple set of classes. Can we do better, more simply?
The obvious answer seems to be: Don’t use references. Make copies of the points and store them inside
Line
. C++ is good at “value-types”. This works and actually that’s how the code was originally.Another possibility is to store indices (rather than references) to the
points
vector insidelines
, but then eachLine
is useless without a reference to its parent class,Polygon
.A possible, but not very good IMO, solution is to use a
std::deque
orstd::list
inmain()
, so that adding to it, does not copy/move things around in the first place. I think this is a bad solution, because the calling code must concern itself with the internals ofPolygon
.The other question is: Should
sf::ConvexShape
be a member ofPolygon
, after all, it is this external coupling that, arguably, causes all the problems – because it is not a movable type.Are there other alternatives? Discuss?
#include <SFML/Graphics.hpp> #include <cmath> #include <iostream> #include <memory> #include <ostream> #include <type_traits> template <typename T> class Vector2 { public: T x{}; T y{}; constexpr Vector2(T x_, T y_) : x(x_), y(y_) {} constexpr Vector2() = default; [[nodiscard]] T mag() const { return std::hypot(x, y); } [[nodiscard]] Vector2 norm() const { return *this / this->mag(); } [[nodiscard]] constexpr double dot(const Vector2& rhs) const { return x * rhs.x + y * rhs.y; } // clang-format off constexpr Vector2& operator+=(const Vector2& obj) { x += obj.x; y += obj.y; return *this; } constexpr Vector2& operator-=(const Vector2& obj) { x -= obj.x; y -= obj.y; return *this; } constexpr Vector2& operator*=(double scale) { x *= scale; y *= scale; return *this; } constexpr Vector2& operator/=(double scale) { x /= scale; y /= scale; return *this; } // clang-format on constexpr bool operator==(const Vector2& rhs) const = default; constexpr friend Vector2 operator+(Vector2 lhs, const Vector2& rhs) { return lhs += rhs; } constexpr friend Vector2 operator-(Vector2 lhs, const Vector2& rhs) { return lhs -= rhs; } constexpr friend Vector2 operator*(Vector2 lhs, double scale) { return lhs *= scale; } constexpr friend Vector2 operator*(double scale, Vector2 rhs) { return rhs *= scale; } constexpr friend Vector2 operator/(Vector2 lhs, double scale) { return lhs /= scale; } friend std::ostream& operator<<(std::ostream& os, const Vector2& v) { return os << '[' << v.x << ", " << v.y << ']'; } }; using Vec2 = Vector2<double>; template <typename Number> struct Line { // references on start and end can dangle if the std::vector<Vec2> points in Polygon is copied const Vector2<Number>& start; const Vector2<Number>& end; // and Polygon::shape is not a unique_ptr const double len; // used for performance caching (sqrt is expensive) const Vector2<Number> norm; // more performance caching Line(const Vector2<Number>& start_, const Vector2<Number>& end_) // NOLINT similar params : start(start_), end(end_), len((end - start).mag()), norm((end - start) / len) {} friend std::ostream& operator<<(std::ostream& os, const Line& l) { return os << l.start << "=>" << l.end << "(" << l.len << ")"; } }; static constexpr float vsScale = 125.0F; sf::Vector2f visualize(const Vec2& v) { return sf::Vector2f(static_cast<float>(v.x), static_cast<float>(v.y)) * vsScale; } class Polygon { public: std::unique_ptr<sf::ConvexShape> shape; // has to be a uniq_ptr to make Polygon movable std::vector<Vec2> points; std::vector<Line<double>> lines; explicit Polygon(std::vector<Vec2> points_) : shape(new sf::ConvexShape), points(std::move(points_)) { shape->setPointCount(points.size()); lines.reserve(points.size()); for (std::size_t x = 0; x != points.size(); x++) { shape->setPoint(x, visualize(points[x])); // modulo wraps end around to start lines.emplace_back(points[x], points[(x + 1) % points.size()]); } } Polygon(const Polygon&) = delete; // copying would invalidate references in Lines Polygon& operator=(const Polygon&) = delete; // no copying // reinstate the default move constructor, move assignment operator and destructor Polygon(Polygon&&) = default; // move only type to protect references Polygon& operator=(Polygon&&) = default; // move only ~Polygon() = default; void draw(sf::RenderWindow& window) { for (std::size_t x = 0; x < points.size(); x++) shape->setPoint(x, visualize(points[x])); window.draw(*shape); } // helpers static Polygon Square(Vec2 pos, double tilt) { return Polygon({Vec2(4, 0.5) + pos, Vec2(-4, 0.5) + pos, Vec2(-4, -0.5 + tilt) + pos, Vec2(4, -0.5 - tilt) + pos}); } static Polygon Triangle(Vec2 pos) { return Polygon({Vec2(1, 1) + pos, Vec2(-1, 1) + pos, Vec2(0, -1) + pos}); } friend std::ostream& operator<<(std::ostream& os, const Polygon& p) { for (auto&& v: p.points) os << v; os << " : "; for (auto&& l: p.lines) os << l; return os; } }; static_assert(std::is_nothrow_move_constructible_v<Polygon>, "Polygon must be nothrow move constructible"); int main() { std::vector<Polygon> polys; polys.push_back(Polygon::Square(Vec2(6.01, 10), -0.75)); polys.push_back(Polygon::Square(Vec2(14, 10), 0.75)); // reallocates, but safely polys.push_back(Polygon::Triangle(Vec2(100, 100))); for (auto&& p: polys) std::cout << p << "\n"; }
Answer
Missing #include
s
You are using std::vector
, but did not #include <vector>
. The code compiles, but that is because SFML happens to include these things for you. Do not rely on that though.
Polygon
stores too much
Polygon
has both a shape
, points
and lines
. These three things all represent the same polygon. Redundant information not only costs more memory to store, but also adds the burden of keeping everything in sync. I suggest that you only store points
. This also matches the input to the constructor.
Reduce the responsibilities of Polygon
Your Polygon
does multiple things. Apart from storing the points that make up a polygon, it also stores sf::ConvexShape
, has a draw()
function that will draw that shape, and has static
convenience functions for creating squares and triangles. I would rather keep everything to the bare essentials for representing polygons, and move the drawing functions and convenience functions out of Polygon
. Consider creating a free function to_shape()
to convert a Polygon
to a sf::ConvexShape
:
sf::ConvexShape to_shape(const Polygon& polygon) {
sf::ConvexShape shape;
auto point_count = polygon.points.size();
shape.setPointCount(point_count);
for (std::size_t i = 0; i < point_count; ++i)
shape.setPoint(i, visualize(polygon.points[i]));
return shape;
}
And for example Triangle()
can be trivially converted to a free function as well:
Polygon Triangle(Vec2 pos) {
return {Vec2(1, 1) + pos, Vec2(-1, 1) + pos, Vec2(0, -1) + pos};
}
And then you can still write things like:
std::vector<Polygon> polys;
polys.push_back(Triangle({100, 100}));
...
for (const auto& poly: polys)
window.draw(to_shape(poly));
Note how this completely avoids having to use std::unique_ptr
to store sf::ConvexShape
s. There is also no need to store lines
, the only user of it is operator<<()
, and it could simply create Line
s on the fly if really desired.
Attribution
Source : Link , Question Author : Oliver Schönrock , Answer Author : G. Sliepen