Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use polynomials to implement the continuous trajectories #1704

Merged
merged 25 commits into from
Feb 3, 2018

Conversation

pleroy
Copy link
Member

@pleroy pleroy commented Feb 1, 2018

The benchmarks are uniformly faster. Some (the ones that only exercise Prolong) marginally so (4-5%), probably because the Newhall construction got a wee bit faster. Others (the ones that exercise EvaluatePosition) by a factor that goes up to 1.4x-1.5x. The numbers are as follows:

Before:

----------------------------------------------------------------------------------------------------------------------
Benchmark                                                                               Time           CPU Iterations
----------------------------------------------------------------------------------------------------------------------
BM_EphemerisMultithreadingBenchmark/3/1                                         192160695 ns          0 ns        100 +9.98764787905515172e+06 m +1.99940980348012522e+07 m +2.99994767005555071e+07 m
BM_EphemerisMultithreadingBenchmark/3/2                                         135523789 ns          0 ns        100 +9.98764787905515172e+06 m +1.99940980348012522e+07 m +2.99994767005555071e+07 m
BM_EphemerisMultithreadingBenchmark/3/3                                          74235678 ns          0 ns        100 +9.98764787905515172e+06 m +1.99940980348012522e+07 m +2.99994767005555071e+07 m
BM_EphemerisMultithreadingBenchmark/3/4                                          74678913 ns     156001 ns        100 +9.98764787905515172e+06 m +1.99940980348012522e+07 m +2.99994767005555071e+07 m
BM_EphemerisMultithreadingBenchmark/3/5                                          72983813 ns          0 ns        100 +9.98764787905515172e+06 m +1.99940980348012522e+07 m +2.99994767005555071e+07 m
BM_EphemerisSolarSystemMajorBodiesOnly/-3                                      106779568246 ns 106517482800 ns          1 +1.00027593204189058e+00 ua
BM_EphemerisSolarSystemMinorAndMajorBodies/-3                                  243795453281 ns 243299159600 ns          1 +1.00027593305567897e+00 ua
BM_EphemerisSolarSystemAllBodiesAndOblateness/-3                               273971959636 ns 272580547300 ns          1 +1.00027577397770129e+00 ua
BM_EphemerisL4ProbeMajorBodiesOnly<&FlowEphemerisWithAdaptiveStep>/-3          1584319653 ns 1560010000 ns          1 154379 steps, +9.99375002345205599e-01 ua, +1.09612969423837914e+00 ua, degree 82.044495
BM_EphemerisL4ProbeMinorAndMajorBodies<&FlowEphemerisWithAdaptiveStep>/-3      4401848366 ns 4383628100 ns          1 154379 steps, +9.99375003101656612e-01 ua, +1.09612971674603221e+00 ua, degree 186.217687
BM_EphemerisL4ProbeAllBodiesAndOblateness<&FlowEphemerisWithAdaptiveStep>/-3   4588703193 ns 4570829300 ns          1 154379 steps, +9.99375002982151206e-01 ua, +1.09612960413464866e+00 ua, degree 187.141040
BM_EphemerisLEOProbeMajorBodiesOnly<&FlowEphemerisWithAdaptiveStep>/-3         4651553614 ns 4648829800 ns          1 750001 steps, +9.99957724690520910e-01 ua, +9.99472752321812266e+01 nmi
BM_EphemerisLEOProbeMajorBodiesOnly<&FlowEphemerisWithFixedStepSLMS>/-3        9523102888 ns 9500460900 ns          1 3155761 steps, +9.99973821713678102e-01 ua, +9.99960120359036466e+01 nmi
BM_EphemerisLEOProbeMajorBodiesOnly<&FlowEphemerisWithFixedStepSRKN>/-3        36672241275 ns 36504234000 ns          1 3155761 steps, +9.99973821496793924e-01 ua, +9.99960113933921377e+01 nmi
BM_EphemerisLEOProbeMinorAndMajorBodies<&FlowEphemerisWithAdaptiveStep>/-3     9147379773 ns 8985657600 ns          1 750001 steps, +9.99957730989526450e-01 ua, +9.99474104158218211e+01 nmi
BM_EphemerisLEOProbeMinorAndMajorBodies<&FlowEphemerisWithFixedStepSLMS>/-3    15741967171 ns 15693700600 ns          1 3155761 steps, +9.99973821135768492e-01 ua, +9.99960105026932382e+01 nmi
BM_EphemerisLEOProbeMinorAndMajorBodies<&FlowEphemerisWithFixedStepSRKN>/-3    73787516639 ns 73367270300 ns          1 3155761 steps, +9.99973820949692671e-01 ua, +9.99960102158594566e+01 nmi
BM_EphemerisLEOProbeAllBodiesAndOblateness<&FlowEphemerisWithAdaptiveStep>/-3  9437853206 ns 9438060500 ns          1 752025 steps, +9.99980462761811517e-01 ua, +8.93174822923318033e+01 nmi
BM_EphemerisLEOProbeAllBodiesAndOblateness<&FlowEphemerisWithFixedStepSLMS>/-3 16187778050 ns 16130503400 ns          1 3155761 steps, +9.99963448296896651e-01 ua, +8.91392599654803348e+01 nmi
BM_EphemerisLEOProbeAllBodiesAndOblateness<&FlowEphemerisWithFixedStepSRKN>/-3 76707756821 ns 76612091100 ns          1 3155761 steps, +9.99963448542561140e-01 ua, +8.91392570883830189e+01 nmi
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/-4                1726794119 ns 1684810800 ns          1 154379 steps, +9.99375002345205599e-01 ua, +1.09612969423837914e+00 ua, degree 84.413812
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/-3                1732307486 ns 1731611100 ns          1 154379 steps, +9.99375002345205599e-01 ua, +1.09612969423837914e+00 ua, degree 82.044495
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/-2                1706008415 ns 1684810800 ns          1 154379 steps, +9.99375002345206820e-01 ua, +1.09612969423829121e+00 ua, degree 76.283386
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/-1                1610964819 ns 1606810300 ns          1 154379 steps, +9.99375002345206820e-01 ua, +1.09612969423829121e+00 ua, degree 70.000000
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/0                 1718392617 ns 1622410400 ns          1 154379 steps, +9.99375002345204155e-01 ua, +1.09612969423844731e+00 ua, degree 63.205634
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/1                 1552869080 ns 1560010000 ns          1 154379 steps, +9.99375002345203822e-01 ua, +1.09612969423845263e+00 ua, degree 61.000000
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/2                 1515436257 ns 1513209700 ns          1 154379 steps, +9.99375002345203822e-01 ua, +1.09612969423842799e+00 ua, degree 57.000000
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/3                 1499061001 ns 1497609600 ns          1 154379 steps, +9.99375002345203600e-01 ua, +1.09612969423843998e+00 ua, degree 55.000000
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/4                 1476490398 ns 1466409400 ns          1 154379 steps, +9.99375002345203378e-01 ua, +1.09612969423847217e+00 ua, degree 54.000000
BM_EphemerisStartup<&FlowEphemerisWithFixedStepSLMS>/3                            1760124 ns    1793594 ns        374 11 steps, +9.99929985864532966e-01 ua, +9.99929985544194766e-01 ua, degree 55.000000
BM_EphemerisStartup<&FlowEphemerisWithFixedStepSRKN>/3                              68572 ns      74750 ns       8974 11 steps, +9.99929985864532966e-01 ua, +9.99929985544194766e-01 ua, degree 55.000000

After:

----------------------------------------------------------------------------------------------------------------------
Benchmark                                                                               Time           CPU Iterations
----------------------------------------------------------------------------------------------------------------------
BM_EphemerisMultithreadingBenchmark/3/1                                         172615405 ns          0 ns        100 +9.98764788888029195e+06 m +1.99940980346540436e+07 m +2.99994767007804625e+07 m
BM_EphemerisMultithreadingBenchmark/3/2                                         119318150 ns          0 ns        100 +9.98764788888029195e+06 m +1.99940980346540436e+07 m +2.99994767007804625e+07 m
BM_EphemerisMultithreadingBenchmark/3/3                                          67171344 ns          0 ns        100 +9.98764788888029195e+06 m +1.99940980346540436e+07 m +2.99994767007804625e+07 m
BM_EphemerisMultithreadingBenchmark/3/4                                          68544608 ns          0 ns        100 +9.98764788888029195e+06 m +1.99940980346540436e+07 m +2.99994767007804625e+07 m
BM_EphemerisMultithreadingBenchmark/3/5                                          66004206 ns          0 ns        100 +9.98764788888029195e+06 m +1.99940980346540436e+07 m +2.99994767007804625e+07 m
BM_EphemerisSolarSystemMajorBodiesOnly/-3                                      102641683616 ns 102555057400 ns          1 +1.00027593204189058e+00 ua
BM_EphemerisSolarSystemMinorAndMajorBodies/-3                                  230143093351 ns 229961074100 ns          1 +1.00027593305567897e+00 ua
BM_EphemerisSolarSystemAllBodiesAndOblateness/-3                               261569303409 ns 261426475800 ns          1 +1.00027577397770173e+00 ua
BM_EphemerisL4ProbeMajorBodiesOnly<&FlowEphemerisWithAdaptiveStep>/-3          1199530377 ns 1185607600 ns          1 154379 steps, +9.99375002345204155e-01 ua, +1.09612969423844309e+00 ua, degree 82.044495
BM_EphemerisL4ProbeMinorAndMajorBodies<&FlowEphemerisWithAdaptiveStep>/-3      3238862846 ns 3198020500 ns          1 154379 steps, +9.99375003101658388e-01 ua, +1.09612971674595627e+00 ua, degree 186.217687
BM_EphemerisL4ProbeAllBodiesAndOblateness<&FlowEphemerisWithAdaptiveStep>/-3   3259336479 ns 3260420900 ns          1 154379 steps, +9.99375002982150651e-01 ua, +1.09612960413471527e+00 ua, degree 187.141040
BM_EphemerisLEOProbeMajorBodiesOnly<&FlowEphemerisWithAdaptiveStep>/-3         3979957516 ns 3978025500 ns          1 750001 steps, +9.99957708942228352e-01 ua, +9.99472639320210021e+01 nmi
BM_EphemerisLEOProbeMajorBodiesOnly<&FlowEphemerisWithFixedStepSLMS>/-3        8431033716 ns 8424054000 ns          1 3155761 steps, +9.99973822025392423e-01 ua, +9.99960134579607995e+01 nmi
BM_EphemerisLEOProbeMajorBodiesOnly<&FlowEphemerisWithFixedStepSRKN>/-3        31613871197 ns 31512202000 ns          1 3155761 steps, +9.99973821849166056e-01 ua, +9.99960129884997997e+01 nmi
BM_EphemerisLEOProbeMinorAndMajorBodies<&FlowEphemerisWithAdaptiveStep>/-3     7814131494 ns 7722049500 ns          1 750001 steps, +9.99957751818578711e-01 ua, +9.99474216789493966e+01 nmi
BM_EphemerisLEOProbeMinorAndMajorBodies<&FlowEphemerisWithFixedStepSLMS>/-3    13806965291 ns 13556486900 ns          1 3155761 steps, +9.99973820518458734e-01 ua, +9.99960086472014638e+01 nmi
BM_EphemerisLEOProbeMinorAndMajorBodies<&FlowEphemerisWithFixedStepSRKN>/-3    60889881393 ns 60653188800 ns          1 3155761 steps, +9.99973820321925166e-01 ua, +9.99960084979087469e+01 nmi
BM_EphemerisLEOProbeAllBodiesAndOblateness<&FlowEphemerisWithAdaptiveStep>/-3  7892333431 ns 7878050500 ns          1 752025 steps, +9.99980466918425570e-01 ua, +8.93176027305386953e+01 nmi
BM_EphemerisLEOProbeAllBodiesAndOblateness<&FlowEphemerisWithFixedStepSLMS>/-3 14065352563 ns 14024489900 ns          1 3155761 steps, +9.99963448237548125e-01 ua, +8.91392610421626443e+01 nmi
BM_EphemerisLEOProbeAllBodiesAndOblateness<&FlowEphemerisWithFixedStepSRKN>/-3 66174206491 ns 65972822900 ns          1 3155761 steps, +9.99963448506915542e-01 ua, +8.91392576638347691e+01 nmi
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/-4                1197785375 ns 1185607600 ns          1 154379 steps, +9.99375002345204155e-01 ua, +1.09612969423844309e+00 ua, degree 84.413812
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/-3                1203694631 ns 1201207700 ns          1 154379 steps, +9.99375002345204155e-01 ua, +1.09612969423844309e+00 ua, degree 82.044495
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/-2                1166978430 ns 1170007500 ns          1 154379 steps, +9.99375002345204044e-01 ua, +1.09612969423843420e+00 ua, degree 76.283386
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/-1                1141520619 ns 1138807300 ns          1 154379 steps, +9.99375002345204044e-01 ua, +1.09612969423843420e+00 ua, degree 70.000000
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/0                 1185772626 ns 1185607600 ns          1 154379 steps, +9.99375002345204155e-01 ua, +1.09612969423844508e+00 ua, degree 63.205634
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/1                 1110106234 ns 1092007000 ns          1 154379 steps, +9.99375002345203156e-01 ua, +1.09612969423847573e+00 ua, degree 61.000000
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/2                 1120295729 ns 1076406900 ns          1 154379 steps, +9.99375002345204821e-01 ua, +1.09612969423839779e+00 ua, degree 57.000000
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/3                 1071555954 ns 1076406900 ns          1 154379 steps, +9.99375002345200714e-01 ua, +1.09612969423857276e+00 ua, degree 55.000000
BM_EphemerisFittingTolerance<&FlowEphemerisWithAdaptiveStep>/4                 1046421661 ns 1045206700 ns          1 154379 steps, +9.99375002345202934e-01 ua, +1.09612969423848794e+00 ua, degree 54.000000
BM_EphemerisStartup<&FlowEphemerisWithFixedStepSLMS>/3                            1519677 ns    1531874 ns        499 11 steps, +9.99929985864532966e-01 ua, +9.99929985544194766e-01 ua, degree 55.000000
BM_EphemerisStartup<&FlowEphemerisWithFixedStepSRKN>/3                              59264 ns      62578 ns      11218 11 steps, +9.99929985864532966e-01 ua, +9.99929985544194766e-01 ua, degree 55.000000

@pleroy
Copy link
Member Author

pleroy commented Feb 1, 2018

retest this please

@eggrobin
Copy link
Member

eggrobin commented Feb 1, 2018

This breaks mercury_perihelion_test, which is weird.

@eggrobin
Copy link
Member

eggrobin commented Feb 1, 2018

Ah nevermind, this is not a test that actually uses Prolong, so it is polynomial evaluation + Cartesian to Keplerian conversion; the error of the former went up as expected.

Sorry, something went wrong.

@@ -323,6 +323,7 @@ Derivative<Value, Argument>
HornerEvaluator<Value, Argument, degree>::EvaluateDerivative(
Coefficients const& coefficients,
Argument const& argument) {
// Starting at 1 prevents us from having polynomials of degree 0.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should we special-case this and return 0?

Sorry, something went wrong.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We could, although it's hard to be excited about degree 0. Maybe in a future PR...

// never need to extract their |t_min|. Logically, the |t_min| for a
// polynomial is the |t_max| of the previous one. The first polynomial has a
// |t_min| which is |*first_time_|.
struct InstantPolynomialPair {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So we end up having that pair after all... Is it still worth having the reference instant replicated in the polynomial itself, or would it make sense to use polynomials of Time?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Well, really we need a triple. Previously it was {t_min, t_max, series} now it's effectively {t_mid, t_max, polynomial}. I prefer the new code because there is less drudgery in ContinuousTrajectory.

struct InstantPolynomialPair {
InstantPolynomialPair(
Instant t_max,
not_null<std::unique_ptr<Polynomial<Displacement<Frame>, Instant>>>
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why are they not Position-valued?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Mostly because they were not in Chebyshev, and I wanted to be able to compare apples to apples. We could look into this in the future (it would probably be less clunky than with Chebyshev because the metaprogramming would just do the right thing). Nod to #770.

@eggrobin eggrobin added the LGTM label Feb 2, 2018
@@ -499,7 +499,7 @@ TEST_P(EphemerisTest, EarthProbe) {
// The solution is a line, so the rounding errors dominate. Different
// compilers result in different errors and thus different numbers of steps.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Change this to "different libms" as we now know the compilers are innocent (unless we get the flags wrong). The above involves std::pow to adapt the step size. I am unsure why earth_positions has variable errors, but there must be something similar somewhere...

@pleroy pleroy merged commit 4d8ffb9 into mockingbirdnest:master Feb 3, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants