Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: mockingbirdnest/Principia
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: f3bc21b1ed26
Choose a base ref
...
head repository: mockingbirdnest/Principia
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 5c398a992b85
Choose a head ref
  • 2 commits
  • 3 files changed
  • 1 contributor

Commits on Feb 19, 2019

  1. Copy the full SHA
    8fa603a View commit details

Commits on Mar 5, 2019

  1. Merge pull request #2084 from pleroy/ContinuousLocking

    Make ContinuousTrajectory thread-safe
    pleroy authored Mar 5, 2019
    Copy the full SHA
    5c398a9 View commit details
Showing with 108 additions and 57 deletions.
  1. +43 −31 physics/continuous_trajectory.hpp
  2. +43 −16 physics/continuous_trajectory_body.hpp
  3. +22 −10 physics/continuous_trajectory_test.cpp
74 changes: 43 additions & 31 deletions physics/continuous_trajectory.hpp
Original file line number Diff line number Diff line change
@@ -6,6 +6,7 @@
#include <utility>
#include <vector>

#include "absl/synchronization/mutex.h"
#include "base/not_null.hpp"
#include "base/status.hpp"
#include "geometry/named_quantities.hpp"
@@ -32,6 +33,9 @@ using numerics::Polynomial;
template<typename Frame>
class TestableContinuousTrajectory;

// This class is thread-safe, but the client must be aware that if, for
// instance, the trajectory is appended to asynchronously, successive calls to
// |t_max()| may return different values.
template<typename Frame>
class ContinuousTrajectory : public Trajectory<Frame> {
public:
@@ -57,46 +61,49 @@ class ContinuousTrajectory : public Trajectory<Frame> {
ContinuousTrajectory& operator=(ContinuousTrajectory&&) = delete;

// Returns true iff this trajectory cannot be evaluated for any time.
bool empty() const;
bool empty() const EXCLUDES(lock_);

// The average degree of the polynomials for the trajectory. Only useful for
// benchmarking or analyzing performance. Do not use in real code.
double average_degree() const;
double average_degree() const EXCLUDES(lock_);

// Appends one point to the trajectory. |time| must be after the last time
// passed to |Append| if the trajectory is not empty. The |time|s passed to
// successive calls to |Append| must be equally spaced with the |step| given
// at construction.
Status Append(Instant const& time,
DegreesOfFreedom<Frame> const& degrees_of_freedom);
DegreesOfFreedom<Frame> const& degrees_of_freedom)
EXCLUDES(lock_);

// Removes all data for times strictly less than |time|.
void ForgetBefore(Instant const& time);
void ForgetBefore(Instant const& time) EXCLUDES(lock_);

// Implementation of the interface |Trajectory|.

// |t_max| may be less than the last time passed to Append. For an empty
// trajectory, an infinity with the proper sign is returned.
Instant t_min() const override;
Instant t_max() const override;
Instant t_min() const override EXCLUDES(lock_);
Instant t_max() const override EXCLUDES(lock_);

Position<Frame> EvaluatePosition(Instant const& time) const override;
Velocity<Frame> EvaluateVelocity(Instant const& time) const override;
Position<Frame> EvaluatePosition(Instant const& time) const override
EXCLUDES(lock_);
Velocity<Frame> EvaluateVelocity(Instant const& time) const override
EXCLUDES(lock_);
DegreesOfFreedom<Frame> EvaluateDegreesOfFreedom(
Instant const& time) const override;
Instant const& time) const override EXCLUDES(lock_);

// End of the implementation of the interface.

// Returns a checkpoint for the current state of this object.
Checkpoint GetCheckpoint() const;
Checkpoint GetCheckpoint() const EXCLUDES(lock_);

// Serializes the current state of this object.
void WriteToMessage(
not_null<serialization::ContinuousTrajectory*> message) const;
void WriteToMessage(not_null<serialization::ContinuousTrajectory*> message)
const EXCLUDES(lock_);
// Serializes the state of this object as it existed when the checkpoint was
// taken.
void WriteToMessage(not_null<serialization::ContinuousTrajectory*> message,
Checkpoint const& checkpoint) const;
Checkpoint const& checkpoint) const EXCLUDES(lock_);
static not_null<std::unique_ptr<ContinuousTrajectory>> ReadFromMessage(
serialization::ContinuousTrajectory const& message);

@@ -152,7 +159,10 @@ class ContinuousTrajectory : public Trajectory<Frame> {
};
using InstantPolynomialPairs = std::vector<InstantPolynomialPair>;

// May be overridden for testing.
Instant t_min_locked() const REQUIRES_SHARED(lock_);
Instant t_max_locked() const REQUIRES_SHARED(lock_);

// Really a static method, but may be overridden for testing.
virtual not_null<std::unique_ptr<Polynomial<Displacement<Frame>, Instant>>>
NewhallApproximationInMonomialBasis(
int degree,
@@ -169,30 +179,32 @@ class ContinuousTrajectory : public Trajectory<Frame> {
Status ComputeBestNewhallApproximation(
Instant const& time,
std::vector<Displacement<Frame>> const& q,
std::vector<Velocity<Frame>> const& v);
std::vector<Velocity<Frame>> const& v) REQUIRES(lock_);

// Returns an iterator to the polynomial applicable for the given |time|, or
// |begin()| if |time| is before the first polynomial or |end()| if |time| is
// after the last polynomial. Time complexity is O(N Log N).
typename InstantPolynomialPairs::const_iterator
FindPolynomialForInstant(Instant const& time) const;
FindPolynomialForInstant(Instant const& time) const REQUIRES_SHARED(lock_);

mutable absl::Mutex lock_;

// Construction parameters;
Time const step_;
Length const tolerance_;

// Initially set to the construction parameters, and then adjusted when we
// choose the degree.
Length adjusted_tolerance_;
bool is_unstable_;
Length adjusted_tolerance_ GUARDED_BY(lock_);
bool is_unstable_ GUARDED_BY(lock_);

// The degree of the approximation and its age in number of Newhall
// approximations.
int degree_;
int degree_age_;
int degree_ GUARDED_BY(lock_);
int degree_age_ GUARDED_BY(lock_);

// The polynomials are in increasing time order.
InstantPolynomialPairs polynomials_;
InstantPolynomialPairs polynomials_ GUARDED_BY(lock_);

// Lookups into |polynomials_| are expensive because they entail a binary
// search into a vector that grows over time. In benchmarks, this can be as
@@ -201,22 +213,22 @@ class ContinuousTrajectory : public Trajectory<Frame> {
// advantage of this, we keep track of the index of the last accessed
// polynomial and first try to see if the new lookup is for the same
// polynomial. This makes us O(1) instead of O(Log N) most of the time and it
// speeds up the lookup by a factor of 7. This member is atomic because of
// multithreading in the ephemeris, and is mutable to maintain the fiction
// that evaluation has no side effects. In the presence of multithreading it
// may be that different threads would want to access polynomials at different
// indices, but by and large the threads progress in parallel, and benchmarks
// show that there is no adverse performance effects. Any value in the range
// of |polynomials_| or 0 is correct.
mutable std::atomic_int last_accessed_polynomial_ = 0;
// speeds up the lookup by a factor of 7. This member is mutable to maintain
// the fiction that evaluation has no side effects. In the presence of
// multithreading it may be that different threads would want to access
// polynomials at different indices, but by and large the threads progress in
// parallel, and benchmarks show that there is no adverse performance effects.
// Any value in the range of |polynomials_| or 0 is correct.
mutable std::int64_t last_accessed_polynomial_ GUARDED_BY(lock_) = 0;

// The time at which this trajectory starts. Set for a nonempty trajectory.
std::optional<Instant> first_time_;
std::optional<Instant> first_time_ GUARDED_BY(lock_);

// The points that have not yet been incorporated in a polynomial. Nonempty
// for a nonempty trajectory.
// |last_points_.begin()->first == polynomials_.back().t_max|
std::vector<std::pair<Instant, DegreesOfFreedom<Frame>>> last_points_;
std::vector<std::pair<Instant, DegreesOfFreedom<Frame>>> last_points_
GUARDED_BY(lock_);

friend class TestableContinuousTrajectory<Frame>;
};
59 changes: 43 additions & 16 deletions physics/continuous_trajectory_body.hpp
Original file line number Diff line number Diff line change
@@ -53,11 +53,13 @@ ContinuousTrajectory<Frame>::ContinuousTrajectory(Time const& step,

template<typename Frame>
bool ContinuousTrajectory<Frame>::empty() const {
absl::ReaderMutexLock l(&lock_);
return polynomials_.empty();
}

template<typename Frame>
double ContinuousTrajectory<Frame>::average_degree() const {
absl::ReaderMutexLock l(&lock_);
if (polynomials_.empty()) {
return 0;
} else {
@@ -73,6 +75,8 @@ template<typename Frame>
Status ContinuousTrajectory<Frame>::Append(
Instant const& time,
DegreesOfFreedom<Frame> const& degrees_of_freedom) {
absl::MutexLock l(&lock_);

// Consistency checks.
if (first_time_) {
Instant const t0;
@@ -119,11 +123,13 @@ Status ContinuousTrajectory<Frame>::Append(

template<typename Frame>
void ContinuousTrajectory<Frame>::ForgetBefore(Instant const& time) {
if (time < t_min()) {
absl::MutexLock l(&lock_);
if (time < t_min_locked()) {
// TODO(phl): test for this case, it yielded a check failure in
// |FindPolynomialForInstant|.
return;
}

polynomials_.erase(polynomials_.begin(), FindPolynomialForInstant(time));

// If there are no |polynomials_| left, clear everything. Otherwise, update
@@ -140,25 +146,22 @@ void ContinuousTrajectory<Frame>::ForgetBefore(Instant const& time) {

template<typename Frame>
Instant ContinuousTrajectory<Frame>::t_min() const {
if (polynomials_.empty()) {
return astronomy::InfiniteFuture;
}
return *first_time_;
absl::ReaderMutexLock l(&lock_);
return t_min_locked();
}

template<typename Frame>
Instant ContinuousTrajectory<Frame>::t_max() const {
if (polynomials_.empty()) {
return astronomy::InfinitePast;
}
return polynomials_.crbegin()->t_max;
absl::ReaderMutexLock l(&lock_);
return t_max_locked();
}

template<typename Frame>
Position<Frame> ContinuousTrajectory<Frame>::EvaluatePosition(
Instant const& time) const {
CHECK_LE(t_min(), time);
CHECK_GE(t_max(), time);
absl::ReaderMutexLock l(&lock_);
CHECK_LE(t_min_locked(), time);
CHECK_GE(t_max_locked(), time);
auto const it = FindPolynomialForInstant(time);
CHECK(it != polynomials_.end());
auto const& polynomial = it->polynomial;
@@ -168,8 +171,9 @@ Position<Frame> ContinuousTrajectory<Frame>::EvaluatePosition(
template<typename Frame>
Velocity<Frame> ContinuousTrajectory<Frame>::EvaluateVelocity(
Instant const& time) const {
CHECK_LE(t_min(), time);
CHECK_GE(t_max(), time);
absl::ReaderMutexLock l(&lock_);
CHECK_LE(t_min_locked(), time);
CHECK_GE(t_max_locked(), time);
auto const it = FindPolynomialForInstant(time);
CHECK(it != polynomials_.end());
auto const& polynomial = it->polynomial;
@@ -179,8 +183,9 @@ Velocity<Frame> ContinuousTrajectory<Frame>::EvaluateVelocity(
template<typename Frame>
DegreesOfFreedom<Frame> ContinuousTrajectory<Frame>::EvaluateDegreesOfFreedom(
Instant const& time) const {
CHECK_LE(t_min(), time);
CHECK_GE(t_max(), time);
absl::ReaderMutexLock l(&lock_);
CHECK_LE(t_min_locked(), time);
CHECK_GE(t_max_locked(), time);
auto const it = FindPolynomialForInstant(time);
CHECK(it != polynomials_.end());
auto const& polynomial = it->polynomial;
@@ -191,7 +196,8 @@ DegreesOfFreedom<Frame> ContinuousTrajectory<Frame>::EvaluateDegreesOfFreedom(
template<typename Frame>
typename ContinuousTrajectory<Frame>::Checkpoint
ContinuousTrajectory<Frame>::GetCheckpoint() const {
return {t_max(),
absl::ReaderMutexLock l(&lock_);
return {t_max_locked(),
adjusted_tolerance_,
is_unstable_,
degree_,
@@ -209,6 +215,7 @@ template<typename Frame>
void ContinuousTrajectory<Frame>::WriteToMessage(
not_null<serialization::ContinuousTrajectory*> const message,
Checkpoint const& checkpoint) const {
absl::ReaderMutexLock l(&lock_);
step_.WriteToMessage(message->mutable_step());
tolerance_.WriteToMessage(message->mutable_tolerance());
checkpoint.adjusted_tolerance_.WriteToMessage(
@@ -333,6 +340,24 @@ ContinuousTrajectory<Frame>::InstantPolynomialPair::InstantPolynomialPair(
: t_max(t_max),
polynomial(std::move(polynomial)) {}

template<typename Frame>
Instant ContinuousTrajectory<Frame>::t_min_locked() const {
lock_.AssertReaderHeld();
if (polynomials_.empty()) {
return astronomy::InfiniteFuture;
}
return *first_time_;
}

template<typename Frame>
Instant ContinuousTrajectory<Frame>::t_max_locked() const {
lock_.AssertReaderHeld();
if (polynomials_.empty()) {
return astronomy::InfinitePast;
}
return polynomials_.crbegin()->t_max;
}

template<typename Frame>
not_null<std::unique_ptr<Polynomial<Displacement<Frame>, Instant>>>
ContinuousTrajectory<Frame>::NewhallApproximationInMonomialBasis(
@@ -354,6 +379,7 @@ Status ContinuousTrajectory<Frame>::ComputeBestNewhallApproximation(
Instant const& time,
std::vector<Displacement<Frame>> const& q,
std::vector<Velocity<Frame>> const& v) {
lock_.AssertHeld();
Length const previous_adjusted_tolerance = adjusted_tolerance_;

// If the degree is too old, restart from the lowest degree. This ensures
@@ -455,6 +481,7 @@ template<typename Frame>
typename ContinuousTrajectory<Frame>::InstantPolynomialPairs::const_iterator
ContinuousTrajectory<Frame>::FindPolynomialForInstant(
Instant const& time) const {
lock_.AssertReaderHeld();
// This returns the first polynomial |p| such that |time <= p.t_max|.
{
auto const begin = polynomials_.begin();
Loading