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: 838e08c745e9
Choose a base ref
...
head repository: mockingbirdnest/Principia
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 59e6ae5cdc07
Choose a head ref
  • 11 commits
  • 4 files changed
  • 2 contributors

Commits on Oct 28, 2020

  1. Changed ancestry_ to an InlinedVector.

    Previously it was a deque.
    This change elides allocations in most cases.
    
    Note that as part of the change, the direction of ancestry was reversed
    (i.e. front and back have been swapped). This is only a notational
    change and has no effect.
    rnlahaye committed Oct 28, 2020
    Copy the full SHA
    1a56650 View commit details
  2. Remove spurious TODOs.

    rnlahaye committed Oct 28, 2020
    Copy the full SHA
    7cf378c View commit details
  3. Lint fix.

    rnlahaye committed Oct 28, 2020
    Copy the full SHA
    242148e View commit details

Commits on Oct 29, 2020

  1. Copy the full SHA
    8b9fa2e View commit details
  2. Updated test to catch bug.

    rnlahaye committed Oct 29, 2020
    Copy the full SHA
    4a82830 View commit details
  3. Fixed bug.

    rnlahaye committed Oct 29, 2020
    Copy the full SHA
    371a195 View commit details
  4. Adressed PR comments.

    rnlahaye committed Oct 29, 2020
    Copy the full SHA
    67e61de View commit details
  5. Copy the full SHA
    591956f View commit details
  6. Copy the full SHA
    322ef52 View commit details

Commits on Oct 31, 2020

  1. Copy the full SHA
    3ff0c99 View commit details
  2. Merge pull request #2776 from rnlahaye/slow

    Changed Forkable::ancestry_ to an absl::InlinedVector.
    eggrobin authored Oct 31, 2020
    Copy the full SHA
    59e6ae5 View commit details
Showing with 227 additions and 36 deletions.
  1. +171 −0 benchmarks/discrete_trajectory.cpp
  2. +6 −4 physics/forkable.hpp
  3. +32 −32 physics/forkable_body.hpp
  4. +18 −0 physics/forkable_test.cpp
171 changes: 171 additions & 0 deletions benchmarks/discrete_trajectory.cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,171 @@

// .\Release\x64\benchmarks.exe --benchmark_filter=DiscreteTrajectory

#include "physics/discrete_trajectory.hpp"

#include "base/not_null.hpp"
#include "benchmark/benchmark.h"
#include "geometry/frame.hpp"
#include "ksp_plugin/frames.hpp"

namespace principia {
namespace physics {

using base::make_not_null_unique;
using base::not_null;
using geometry::Frame;
using geometry::Handedness;
using geometry::Inertial;
using geometry::Instant;
using geometry::Velocity;
using ksp_plugin::World;
using quantities::si::Second;

namespace {

// Creates a trajectory with the given number of steps.
not_null<std::unique_ptr<DiscreteTrajectory<World>>> CreateTrajectory(
int const steps) {
auto trajectory = make_not_null_unique<DiscreteTrajectory<World>>();
Instant t;
for (int i = 0; i < steps; i++, t += 1 * Second) {
trajectory->Append(t, {World::origin, World::unmoving});
}
return trajectory;
}

// Forks |parent| at a position |pos| of the way through.
// |parent| should be nonempty.
// |pos| should be in [0, 1].
not_null<DiscreteTrajectory<World>*> ForkAt(DiscreteTrajectory<World>& parent,
double const pos) {
CHECK(!parent.Empty());
CHECK_GE(pos, 0);
CHECK_LE(pos, 1);
Instant const desired_fork_time =
parent.t_min() + (parent.t_max() - parent.t_min()) * pos;
auto const fork_it = parent.LowerBound(desired_fork_time);
return parent.NewForkWithCopy(fork_it->time);
}

} // namespace

void BM_DiscreteTrajectoryFront(benchmark::State& state) {
not_null<std::unique_ptr<DiscreteTrajectory<World>>> const trajectory =
CreateTrajectory(4);
not_null<DiscreteTrajectory<World>*> const fork =
ForkAt(*ForkAt(*trajectory, 0.5), 0.75);

for (auto _ : state) {
fork->front();
}
}

void BM_DiscreteTrajectoryBack(benchmark::State& state) {
not_null<std::unique_ptr<DiscreteTrajectory<World>>> const trajectory =
CreateTrajectory(4);
not_null<DiscreteTrajectory<World>*> const fork =
ForkAt(*ForkAt(*trajectory, 0.5), 0.75);

for (auto _ : state) {
fork->back();
}
}

void BM_DiscreteTrajectoryBegin(benchmark::State& state) {
not_null<std::unique_ptr<DiscreteTrajectory<World>>> const trajectory =
CreateTrajectory(4);
not_null<DiscreteTrajectory<World>*> const fork =
ForkAt(*ForkAt(*trajectory, 0.5), 0.75);

for (auto _ : state) {
fork->begin();
}
}

void BM_DiscreteTrajectoryEnd(benchmark::State& state) {
not_null<std::unique_ptr<DiscreteTrajectory<World>>> const trajectory =
CreateTrajectory(4);
not_null<DiscreteTrajectory<World>*> const fork =
ForkAt(*ForkAt(*trajectory, 0.5), 0.75);

for (auto _ : state) {
fork->end();
}
}

void BM_DiscreteTrajectoryCreateDestroy(benchmark::State& state) {
int const steps = state.range(0);
for (auto _ : state) {
CreateTrajectory(steps);
}
}

void BM_DiscreteTrajectoryIterate(benchmark::State& state) {
int const steps = state.range(0);
not_null<std::unique_ptr<DiscreteTrajectory<World>>> const trajectory =
CreateTrajectory(steps);
not_null<DiscreteTrajectory<World>*> const fork =
ForkAt(*ForkAt(*trajectory, 0.5), 0.75);

for (auto _ : state) {
for (auto it = fork->begin(); it != fork->end(); ++it) {
}
}
}

void BM_DiscreteTrajectoryReverseIterate(benchmark::State& state) {
int const steps = state.range(0);
not_null<std::unique_ptr<DiscreteTrajectory<World>>> const trajectory =
CreateTrajectory(steps);
not_null<DiscreteTrajectory<World>*> const fork =
ForkAt(*ForkAt(*trajectory, 0.5), 0.75);

for (auto _ : state) {
for (auto it = fork->end(); it != fork->begin(); --it) {
}
}
}

void BM_DiscreteTrajectoryFind(benchmark::State& state) {
int const steps = state.range(0);
not_null<std::unique_ptr<DiscreteTrajectory<World>>> const trajectory =
CreateTrajectory(steps);
not_null<DiscreteTrajectory<World>*> const fork =
ForkAt(*ForkAt(*trajectory, 0.5), 0.75);

for (auto _ : state) {
// These times are in different segments of the fork.
fork->Find(Instant() + 333 * Second);
fork->Find(Instant() + 667 * Second);
fork->Find(Instant() + 833 * Second);
}
}

void BM_DiscreteTrajectoryLowerBound(benchmark::State& state) {
int const steps = state.range(0);
not_null<std::unique_ptr<DiscreteTrajectory<World>>> const trajectory =
CreateTrajectory(steps);
not_null<DiscreteTrajectory<World>*> const fork =
ForkAt(*ForkAt(*trajectory, 0.5), 0.75);

for (auto _ : state) {
// These times are in different segments of the fork.
fork->LowerBound(Instant() + 333 * Second);
fork->LowerBound(Instant() + 667 * Second);
fork->LowerBound(Instant() + 833 * Second);
}
}

BENCHMARK(BM_DiscreteTrajectoryFront);
BENCHMARK(BM_DiscreteTrajectoryBack);
BENCHMARK(BM_DiscreteTrajectoryBegin);
BENCHMARK(BM_DiscreteTrajectoryEnd);
BENCHMARK(BM_DiscreteTrajectoryCreateDestroy)->Range(8, 1024);
BENCHMARK(BM_DiscreteTrajectoryIterate)->Range(8, 1024);
BENCHMARK(BM_DiscreteTrajectoryReverseIterate)->Range(8, 1024);
BENCHMARK(BM_DiscreteTrajectoryFind)->Range(8, 1024);
BENCHMARK(BM_DiscreteTrajectoryLowerBound)->Range(8, 1024);

} // namespace physics
} // namespace principia
10 changes: 6 additions & 4 deletions physics/forkable.hpp
Original file line number Diff line number Diff line change
@@ -1,12 +1,12 @@

#pragma once

#include <deque>
#include <optional>
#include <map>
#include <memory>
#include <optional>
#include <vector>

#include "absl/container/inlined_vector.h"
#include "base/not_null.hpp"
#include "geometry/named_quantities.hpp"
#include "serialization/physics.pb.h"
@@ -84,9 +84,11 @@ class ForkableIterator {
void CheckNormalizedIfEnd();

// |ancestry_| is never empty. |current_| is an iterator in the timeline
// for |ancestry_.front()|. |current_| may be at end.
// for |ancestry_.back()|. |current_| may be at end. The inline size of 3
// for |ancestry_| is intended to cover a vessel's history, psychohistory,
// and prediction.
TimelineConstIterator current_;
std::deque<not_null<Tr4jectory const*>> ancestry_; // Pointers not owned.
absl::InlinedVector<not_null<Tr4jectory const*>, 3> ancestry_;

template<typename, typename, typename>
friend class Forkable;
64 changes: 32 additions & 32 deletions physics/forkable_body.hpp
Original file line number Diff line number Diff line change
@@ -1,10 +1,10 @@

#pragma once

#include <deque>
#include <optional>
#include <vector>

#include "absl/container/inlined_vector.h"
#include "physics/forkable.hpp"

namespace principia {
@@ -15,14 +15,14 @@ template<typename Tr4jectory, typename It3rator, typename Traits>
not_null<Tr4jectory const*>
ForkableIterator<Tr4jectory, It3rator, Traits>::trajectory() const {
CHECK(!ancestry_.empty());
return ancestry_.back();
return ancestry_.front();
}

template<typename Tr4jectory, typename It3rator, typename Traits>
bool ForkableIterator<Tr4jectory, It3rator, Traits>::operator==(
It3rator const& right) const {
DCHECK_EQ(trajectory(), right.trajectory());
// The comparison of iterators is faster than the comparison of deques, so if
// The comparison of iterators is faster than the comparison of vectors, so if
// this function returns false (which it does repeatedly in loops), it might
// as well do so quickly. There is a complication, however, because the two
// iterators may not point to the same container, and we believe that
@@ -43,11 +43,11 @@ bool ForkableIterator<Tr4jectory, It3rator, Traits>::operator!=(
template<typename Tr4jectory, typename It3rator, typename Traits>
It3rator& ForkableIterator<Tr4jectory, It3rator, Traits>::operator++() {
CHECK(!ancestry_.empty());
CHECK(current_ != ancestry_.front()->timeline_end());
CHECK(current_ != ancestry_.back()->timeline_end());

// Check if there is a next child in the ancestry.
auto ancestry_it = ancestry_.begin();
if (++ancestry_it != ancestry_.end()) {
auto ancestry_it = ancestry_.rbegin();
if (++ancestry_it != ancestry_.rend()) {
// There is a next child. See if we reached its fork time.
Instant const& current_time = Traits::time(current_);
not_null<Tr4jectory const*> child = *ancestry_it;
@@ -58,8 +58,8 @@ It3rator& ForkableIterator<Tr4jectory, It3rator, Traits>::operator++() {
// a different time or the end of the children.
do {
current_ = child->timeline_begin(); // May be at end.
ancestry_.pop_front();
if (++ancestry_it == ancestry_.end()) {
ancestry_.pop_back();
if (++ancestry_it == ancestry_.rend()) {
break;
}
child = *ancestry_it;
@@ -81,7 +81,7 @@ template<typename Tr4jectory, typename It3rator, typename Traits>
It3rator& ForkableIterator<Tr4jectory, It3rator, Traits>::operator--() {
CHECK(!ancestry_.empty());

not_null<Tr4jectory const*> ancestor = ancestry_.front();
not_null<Tr4jectory const*> ancestor = ancestry_.back();
if (current_ == ancestor->timeline_begin()) {
CHECK_NOTNULL(ancestor->parent_);
// At the beginning of the first timeline. Push the parent in front of the
@@ -90,7 +90,7 @@ It3rator& ForkableIterator<Tr4jectory, It3rator, Traits>::operator--() {
do {
current_ = *ancestor->position_in_parent_timeline_;
ancestor = ancestor->parent_;
ancestry_.push_front(ancestor);
ancestry_.push_back(ancestor);
} while (current_ == ancestor->timeline_end() &&
ancestor->parent_ != nullptr);
return *that();
@@ -110,19 +110,17 @@ ForkableIterator<Tr4jectory, It3rator, Traits>::current() const {
template<typename Tr4jectory, typename It3rator, typename Traits>
void ForkableIterator<Tr4jectory, It3rator, Traits>::NormalizeIfEnd() {
CHECK(!ancestry_.empty());
if (current_ == ancestry_.front()->timeline_end() &&
ancestry_.size() > 1) {
ancestry_.erase(ancestry_.begin(), --ancestry_.end());
current_ = ancestry_.front()->timeline_end();
if (current_ == ancestry_.back()->timeline_end() && ancestry_.size() > 1) {
ancestry_.erase(ancestry_.begin() + 1, ancestry_.end());
current_ = ancestry_.back()->timeline_end();
}
}

template<typename Tr4jectory, typename It3rator, typename Traits>
void ForkableIterator<Tr4jectory, It3rator, Traits>::CheckNormalizedIfEnd() {
// Checking if the trajectory is a root is faster than obtaining the end of
// the front of the deque, so it should be done first.
CHECK(ancestry_.size() == 1 ||
current_ != ancestry_.front()->timeline_end());
// the back of the vector, so it should be done first.
CHECK(ancestry_.size() == 1 || current_ != ancestry_.back()->timeline_end());
}

template<typename Tr4jectory, typename It3rator, typename Traits>
@@ -187,7 +185,7 @@ template<typename Tr4jectory, typename It3rator, typename Traits>
It3rator Forkable<Tr4jectory, It3rator, Traits>::end() const {
not_null<Tr4jectory const*> const ancestor = that();
It3rator iterator;
iterator.ancestry_.push_front(ancestor);
iterator.ancestry_.push_back(ancestor);
iterator.current_ = ancestor->timeline_end();
iterator.CheckNormalizedIfEnd();
return iterator;
@@ -215,10 +213,10 @@ Find(Instant const& time) const {
// Go up the ancestry chain until we find a timeline that covers |time| (that
// is, |time| is after the first time of the timeline). Set |current_| to
// the location of |time|, which may be |end()|. The ancestry has |forkable|
// at the back, and the object containing |current_| at the front.
// at the front, and the object containing |current_| at the back.
Tr4jectory const* ancestor = that();
do {
iterator.ancestry_.push_front(ancestor);
iterator.ancestry_.push_back(ancestor);
if (!ancestor->timeline_empty() &&
Traits::time(ancestor->timeline_begin()) <= time) {
iterator.current_ = ancestor->timeline_find(time); // May be at end.
@@ -238,24 +236,24 @@ LowerBound(Instant const& time) const {
It3rator iterator;
Tr4jectory const* ancestor = that();

// This queue is parallel to |iterator.ancestry_|, and each entry is an
// This vector is parallel to |iterator.ancestry_|, and each entry is an
// iterator in the corresponding ancestry timeline. Note that we use a
// |nullopt| sentinel for the innermost timeline.
std::deque<std::optional<TimelineConstIterator>> fork_points;
fork_points.push_front(std::nullopt);
absl::InlinedVector<std::optional<TimelineConstIterator>, 3> fork_points;
fork_points.push_back(std::nullopt);

// Go up the ancestry chain until we find a (nonempty) timeline that covers
// |time| (that is, |time| is on or after the first time of the timeline).
do {
iterator.ancestry_.push_front(ancestor);
iterator.ancestry_.push_back(ancestor);
if (!ancestor->timeline_empty() &&
Traits::time(ancestor->timeline_begin()) <= time) {
// We have found a timeline that covers |time|. Find where |time| falls
// in that timeline (that may be after the end).
iterator.current_ = ancestor->timeline_lower_bound(time);

// Check if the returned iterator is directly usable.
auto const& fork_point = fork_points.front();
auto const& fork_point = fork_points.back();
if (iterator.current_ == ancestor->timeline_end() ||
(fork_point &&
*fork_point != ancestor->timeline_end() &&
@@ -268,15 +266,15 @@ LowerBound(Instant const& time) const {
// Check if we have a more nested fork with a point before |time|. Go
// down the ancestry looking for a timeline that is nonempty and not
// forked at the same point as its parent.
auto ancestry_it = iterator.ancestry_.begin();
auto fork_points_it = fork_points.begin();
auto ancestry_it = iterator.ancestry_.rbegin();
auto fork_points_it = fork_points.rbegin();
for (;;) {
++ancestry_it;
++fork_points_it;
if (ancestry_it == iterator.ancestry_.end()) {
if (ancestry_it == iterator.ancestry_.rend()) {
// We didn't find an interesting fork in the ancestry, so we stop
// here and |NormalizeIfEnd| will return a proper |End|.
CHECK(fork_points_it == fork_points.end());
CHECK(fork_points_it == fork_points.rend());
break;
}
if (!(*ancestry_it)->timeline_empty() &&
@@ -285,15 +283,17 @@ LowerBound(Instant const& time) const {
// We found an interesting timeline, i.e. one that is nonempty and
// not forked at the fork point of its parent. Cut the ancestry and
// return the beginning of that timeline.
iterator.ancestry_.erase(iterator.ancestry_.begin(), ancestry_it);
iterator.ancestry_.erase(ancestry_it.base(),
iterator.ancestry_.end());
ancestry_it = iterator.ancestry_.rbegin();
iterator.current_ = (*ancestry_it)->timeline_begin();
break;
}
}
}
break;
}
fork_points.push_front(ancestor->position_in_parent_timeline_);
fork_points.push_back(ancestor->position_in_parent_timeline_);
iterator.current_ = ancestor->timeline_begin();
ancestor = ancestor->parent_;
} while (ancestor != nullptr);
@@ -511,7 +511,7 @@ It3rator Forkable<Tr4jectory, It3rator, Traits>::Wrap(
// at the back, and the object containing |current_| at the front.
not_null<Tr4jectory const*> ancest0r = that();
do {
iterator.ancestry_.push_front(ancest0r);
iterator.ancestry_.push_back(ancest0r);
if (ancestor == ancest0r) {
iterator.current_ = position_in_ancestor_timeline; // May be at end.
iterator.CheckNormalizedIfEnd();
Loading