From 8904073a15d87b789ebf36993ed1b06fee591a1e Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sat, 9 Dec 2023 04:18:46 +0000 Subject: [PATCH] Cache the total points tracked in our historical liquidity data When we go to score a channel using the historical liquidity data, the first thing we do is step through all the valid bucket combinations, multiply the min and max bucket, and then add them together to calculate the total number of points tracked. This isn't a free operation, and for scorers without much data it represents a large part of the total time spent scoring during routefinding. Thus, here we cache this value, updating it every time the buckets are updated. --- lightning/src/routing/scoring.rs | 32 ++++++++++++++++++++++++++------ 1 file changed, 26 insertions(+), 6 deletions(-) diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 6c49c635e..d64f11639 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -1634,6 +1634,7 @@ mod bucketed_history { pub(super) struct HistoricalLiquidityTracker { min_liquidity_offset_history: HistoricalBucketRangeTracker, max_liquidity_offset_history: HistoricalBucketRangeTracker, + total_valid_points_tracked: u64, } impl HistoricalLiquidityTracker { @@ -1641,6 +1642,7 @@ mod bucketed_history { HistoricalLiquidityTracker { min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + total_valid_points_tracked: 0, } } @@ -1648,10 +1650,13 @@ mod bucketed_history { min_liquidity_offset_history: HistoricalBucketRangeTracker, max_liquidity_offset_history: HistoricalBucketRangeTracker, ) -> HistoricalLiquidityTracker { - HistoricalLiquidityTracker { + let mut res = HistoricalLiquidityTracker { min_liquidity_offset_history, max_liquidity_offset_history, - } + total_valid_points_tracked: 0, + }; + res.recalculate_valid_point_count(); + res } pub(super) fn has_datapoints(&self) -> bool { @@ -1667,6 +1672,16 @@ mod bucketed_history { for bucket in self.max_liquidity_offset_history.buckets.iter_mut() { *bucket = ((*bucket as u64) * 1024 / divisor) as u16; } + self.recalculate_valid_point_count(); + } + + fn recalculate_valid_point_count(&mut self) { + self.total_valid_points_tracked = 0; + for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() { + for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(32 - min_idx) { + self.total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); + } + } } pub(super) fn writeable_min_offset_history(&self) -> &HistoricalBucketRangeTracker { @@ -1706,6 +1721,7 @@ mod bucketed_history { self.tracker.max_liquidity_offset_history.track_datapoint(min_offset_msat, capacity_msat); self.tracker.min_liquidity_offset_history.track_datapoint(max_offset_msat, capacity_msat); } + self.tracker.recalculate_valid_point_count(); } } @@ -1746,11 +1762,15 @@ mod bucketed_history { let max_liquidity_offset_history_buckets = self.max_liquidity_offset_history_buckets(); - let mut total_valid_points_tracked = 0; - for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate() { - for max_bucket in max_liquidity_offset_history_buckets.iter().take(32 - min_idx) { - total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); + let total_valid_points_tracked = self.tracker.total_valid_points_tracked; + #[cfg(debug_assertions)] { + let mut actual_valid_points_tracked = 0; + for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate() { + for max_bucket in max_liquidity_offset_history_buckets.iter().take(32 - min_idx) { + actual_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); + } } + assert_eq!(total_valid_points_tracked, actual_valid_points_tracked); } // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme), -- 2.39.5