[PATCH 4/4] pressure interpolation: incrementally update interpolation data

[Linus Torvalds]

From: Linus Torvalds <torvalds at linux-foundation.org>
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 <torvalds at linux-foundation.org>
---

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