From: Linus Torvalds <[email protected]> Date: Sun, 21 Feb 2016 15:34:04 -0800 Subject: [PATCH 4/4] pressure interpolation: incrementally update interpolation data
Instead of re-calculating all the interpolation data for each plot entry (which means that we have a quadratic algorithm that walks over all the plot-info points for each plot-info point), we can just update it incrementally within any particular interpolation segment. The previous cleanups made the code sane enough to understand, and makes it trivial to see how you don't have to recalculate the full thing. This gets rid of the O(n**2) algorithm, and it instead becomes O(n*m) where 'n' is the number of plot entries, and 'm' is the number of gas segments (which is usually a much smaller numer, typically "1"). Signed-off-by: Linus Torvalds <[email protected]> --- This is the patch that actually speeds things up by avoiding the O(n**2) behavior. The other patches migth have helped a bit by just making the code generation better, but this one should make the cylinder pressure interpolation just be a non-issue from a performance standpoint. subsurface-core/gaspressures.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) diff --git a/subsurface-core/gaspressures.c b/subsurface-core/gaspressures.c index 5e7cd72ea785..a8bb808128fb 100644 --- a/subsurface-core/gaspressures.c +++ b/subsurface-core/gaspressures.c @@ -200,6 +200,8 @@ static void fill_missing_tank_pressures(struct dive *dive, struct plot_info *pi, { int cyl, i; struct plot_data *entry; + pr_interpolate_t interpolate = { 0 }; + pr_track_t *last_segment = NULL; int cur_pr[MAX_CYLINDERS]; // cur_pr[MAX_CYLINDERS] is the CCR diluent cylinder for (cyl = 0; cyl < MAX_CYLINDERS; cyl++) { @@ -235,7 +237,6 @@ static void fill_missing_tank_pressures(struct dive *dive, struct plot_info *pi, for (i = 1; i < pi->nr; i++) { // For each point on the profile: double magic; pr_track_t *segment; - pr_interpolate_t interpolate; int pressure; int *save_pressure, *save_interpolated; @@ -257,6 +258,7 @@ static void fill_missing_tank_pressures(struct dive *dive, struct plot_info *pi, } if (pressure) { // If there is a valid pressure value, + last_segment = NULL; // get rid of interpolation data, cur_pr[cyl] = pressure; // set current pressure continue; // and skip to next point. } @@ -272,7 +274,14 @@ static void fill_missing_tank_pressures(struct dive *dive, struct plot_info *pi, } // If there is a valid segment but no tank pressure .. - interpolate = get_pr_interpolate_data(segment, pi, i); // Set up an interpolation structure + if (segment == last_segment) { + interpolate.acc_pressure_time += entry->pressure_time; + } else { + // Set up an interpolation structure + interpolate = get_pr_interpolate_data(segment, pi, i); + last_segment = segment; + } + if(dive->cylinder[cyl].cylinder_use == OC_GAS) { /* if this segment has pressure_time, then calculate a new interpolated pressure */ -- 2.7.0.170.ge572fef _______________________________________________ subsurface mailing list [email protected] http://lists.subsurface-divelog.org/cgi-bin/mailman/listinfo/subsurface
