From 897350e1acf71e93dd9406632d399504c51ef0d8 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sat, 16 Dec 2023 01:52:44 +0000 Subject: [PATCH] Pull the `linear_scoring` if out of the hot bucket iteration loop Our loops iterating the scoring buckets are incredibly performance-sensitive. Currently, inside them, we branch on whether we're doing a linear or non-linear scoring, selecting a different probability model depending on our parameters. While the branching itself isnt' necessarily all that problematic, by pulling the branching out of the loop we open up the possibility of future optimizations on a per-model basis. --- lightning/src/routing/scoring.rs | 237 ++++++++++++++++++------------- 1 file changed, 142 insertions(+), 95 deletions(-) diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index e64c9826d..393945f71 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -1076,55 +1076,63 @@ fn three_f64_pow_3(a: f64, b: f64, c: f64) -> (f64, f64, f64) { (a * a * a, b * b * b, c * c * c) } -/// Given liquidity bounds, calculates the success probability (in the form of a numerator and -/// denominator) of an HTLC. This is a key assumption in our scoring models. -/// -/// Must not return a numerator or denominator greater than 2^31 for arguments less than 2^31. -/// -/// min_zero_implies_no_successes signals that a `min_liquidity_msat` of 0 means we've not -/// (recently) seen an HTLC successfully complete over this channel. #[inline(always)] -fn success_probability( +fn linear_success_probability( + amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64, _capacity_msat: u64, + min_zero_implies_no_successes: bool, +) -> (u64, u64) { + let (numerator, mut denominator) = + (max_liquidity_msat - amount_msat, + (max_liquidity_msat - min_liquidity_msat).saturating_add(1)); + + if min_zero_implies_no_successes && min_liquidity_msat == 0 && + denominator < u64::max_value() / 21 + { + // If we have no knowledge of the channel, scale probability down by ~75% + // Note that we prefer to increase the denominator rather than decrease the numerator as + // the denominator is more likely to be larger and thus provide greater precision. This is + // mostly an overoptimization but makes a large difference in tests. + denominator = denominator * 21 / 16 + } + + (numerator, denominator) +} + +#[inline(always)] +fn nonlinear_success_probability( amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64, capacity_msat: u64, - params: &ProbabilisticScoringFeeParameters, min_zero_implies_no_successes: bool, + min_zero_implies_no_successes: bool, ) -> (u64, u64) { debug_assert!(min_liquidity_msat <= amount_msat); debug_assert!(amount_msat < max_liquidity_msat); debug_assert!(max_liquidity_msat <= capacity_msat); - let (numerator, mut denominator) = - if params.linear_success_probability { - (max_liquidity_msat - amount_msat, - (max_liquidity_msat - min_liquidity_msat).saturating_add(1)) - } else { - let capacity = capacity_msat as f64; - let min = (min_liquidity_msat as f64) / capacity; - let max = (max_liquidity_msat as f64) / capacity; - let amount = (amount_msat as f64) / capacity; - - // Assume the channel has a probability density function of (x - 0.5)^2 for values from - // 0 to 1 (where 1 is the channel's full capacity). The success probability given some - // liquidity bounds is thus the integral under the curve from the amount to maximum - // estimated liquidity, divided by the same integral from the minimum to the maximum - // estimated liquidity bounds. - // - // Because the integral from x to y is simply (y - 0.5)^3 - (x - 0.5)^3, we can - // calculate the cumulative density function between the min/max bounds trivially. Note - // that we don't bother to normalize the CDF to total to 1, as it will come out in the - // division of num / den. - let (max_pow, amt_pow, min_pow) = three_f64_pow_3(max - 0.5, amount - 0.5, min - 0.5); - let num = max_pow - amt_pow; - let den = max_pow - min_pow; - - // Because our numerator and denominator max out at 0.5^3 we need to multiply them by - // quite a large factor to get something useful (ideally in the 2^30 range). - const BILLIONISH: f64 = 1024.0 * 1024.0 * 1024.0; - let numerator = (num * BILLIONISH) as u64 + 1; - let denominator = (den * BILLIONISH) as u64 + 1; - debug_assert!(numerator <= 1 << 30, "Got large numerator ({}) from float {}.", numerator, num); - debug_assert!(denominator <= 1 << 30, "Got large denominator ({}) from float {}.", denominator, den); - (numerator, denominator) - }; + let capacity = capacity_msat as f64; + let min = (min_liquidity_msat as f64) / capacity; + let max = (max_liquidity_msat as f64) / capacity; + let amount = (amount_msat as f64) / capacity; + + // Assume the channel has a probability density function of (x - 0.5)^2 for values from + // 0 to 1 (where 1 is the channel's full capacity). The success probability given some + // liquidity bounds is thus the integral under the curve from the amount to maximum + // estimated liquidity, divided by the same integral from the minimum to the maximum + // estimated liquidity bounds. + // + // Because the integral from x to y is simply (y - 0.5)^3 - (x - 0.5)^3, we can + // calculate the cumulative density function between the min/max bounds trivially. Note + // that we don't bother to normalize the CDF to total to 1, as it will come out in the + // division of num / den. + let (max_pow, amt_pow, min_pow) = three_f64_pow_3(max - 0.5, amount - 0.5, min - 0.5); + let mut num = max_pow - amt_pow; + let mut den = max_pow - min_pow; + + // Because our numerator and denominator max out at 0.5^3 we need to multiply them by + // quite a large factor to get something useful (ideally in the 2^30 range). + const BILLIONISH: f64 = 1024.0 * 1024.0 * 1024.0; + let numerator = (num * BILLIONISH) as u64 + 1; + let mut denominator = (den * BILLIONISH) as u64 + 1; + debug_assert!(numerator <= 1 << 30, "Got large numerator ({}) from float {}.", numerator, num); + debug_assert!(denominator <= 1 << 30, "Got large denominator ({}) from float {}.", denominator, den); if min_zero_implies_no_successes && min_liquidity_msat == 0 && denominator < u64::max_value() / 21 @@ -1139,6 +1147,34 @@ fn success_probability( (numerator, denominator) } + +/// Given liquidity bounds, calculates the success probability (in the form of a numerator and +/// denominator) of an HTLC. This is a key assumption in our scoring models. +/// +/// min_zero_implies_no_successes signals that a `min_liquidity_msat` of 0 means we've not +/// (recently) seen an HTLC successfully complete over this channel. +#[inline(always)] +fn success_probability( + amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64, capacity_msat: u64, + params: &ProbabilisticScoringFeeParameters, min_zero_implies_no_successes: bool, +) -> (u64, u64) { + debug_assert!(min_liquidity_msat <= amount_msat); + debug_assert!(amount_msat < max_liquidity_msat); + debug_assert!(max_liquidity_msat <= capacity_msat); + + if params.linear_success_probability { + linear_success_probability( + amount_msat, min_liquidity_msat, max_liquidity_msat, capacity_msat, + min_zero_implies_no_successes, + ) + } else { + nonlinear_success_probability( + amount_msat, min_liquidity_msat, max_liquidity_msat, capacity_msat, + min_zero_implies_no_successes, + ) + } +} + impl, HT: Deref, T: Deref> DirectedChannelLiquidity< L, HT, T> { /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in @@ -1808,63 +1844,74 @@ mod bucketed_history { let mut cumulative_success_prob_times_billion = 0; let mut cumulative_success_points = 0; - // Special-case the 0th min bucket - it generally means we failed a payment, so only - // consider the highest (i.e. largest-offset-from-max-capacity) max bucket for all - // points against the 0th min bucket. This avoids the case where we fail to route - // increasingly lower values over a channel, but treat each failure as a separate - // datapoint, many of which may have relatively high maximum-available-liquidity - // values, which will result in us thinking we have some nontrivial probability of - // routing up to that amount. - if min_liquidity_offset_history_buckets[0] != 0 { - let mut highest_max_bucket_with_points = 0; // The highest max-bucket with any data - let mut total_max_points = 0; // Total points in max-buckets to consider - for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate() { - if *max_bucket >= BUCKET_FIXED_POINT_ONE { - highest_max_bucket_with_points = cmp::max(highest_max_bucket_with_points, max_idx); - } - total_max_points += *max_bucket as u64; - } - let max_bucket_end_pos = BUCKET_START_POS[32 - highest_max_bucket_with_points] - 1; - if payment_pos < max_bucket_end_pos { - let (numerator, denominator) = success_probability(payment_pos as u64, 0, - max_bucket_end_pos as u64, POSITION_TICKS as u64 - 1, params, true); - let bucket_prob_times_billion = - (min_liquidity_offset_history_buckets[0] as u64) * total_max_points - * 1024 * 1024 * 1024 / total_valid_points_tracked; - cumulative_success_prob_times_billion += bucket_prob_times_billion * - numerator / denominator; - } - } - - for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate().skip(1) { - let min_bucket_start_pos = BUCKET_START_POS[min_idx]; - if payment_pos < min_bucket_start_pos { - for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate().take(32 - min_idx) { - let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1; - if payment_pos >= max_bucket_end_pos { - // Success probability 0, the payment amount may be above the max liquidity - break; + macro_rules! calculate_probability { + ($success_probability: ident) => { { + // Special-case the 0th min bucket - it generally means we failed a payment, so only + // consider the highest (i.e. largest-offset-from-max-capacity) max bucket for all + // points against the 0th min bucket. This avoids the case where we fail to route + // increasingly lower values over a channel, but treat each failure as a separate + // datapoint, many of which may have relatively high maximum-available-liquidity + // values, which will result in us thinking we have some nontrivial probability of + // routing up to that amount. + if min_liquidity_offset_history_buckets[0] != 0 { + let mut highest_max_bucket_with_points = 0; // The highest max-bucket with any data + let mut total_max_points = 0; // Total points in max-buckets to consider + for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate() { + if *max_bucket >= BUCKET_FIXED_POINT_ONE { + highest_max_bucket_with_points = cmp::max(highest_max_bucket_with_points, max_idx); + } + total_max_points += *max_bucket as u64; + } + let max_bucket_end_pos = BUCKET_START_POS[32 - highest_max_bucket_with_points] - 1; + if payment_pos < max_bucket_end_pos { + let (numerator, denominator) = $success_probability(payment_pos as u64, 0, + max_bucket_end_pos as u64, POSITION_TICKS as u64 - 1, true); + let bucket_prob_times_billion = + (min_liquidity_offset_history_buckets[0] as u64) * total_max_points + * 1024 * 1024 * 1024 / total_valid_points_tracked; + cumulative_success_prob_times_billion += bucket_prob_times_billion * + numerator / denominator; } - cumulative_success_points += ((*min_bucket as u32) * (*max_bucket as u32)) as u64; } - } else { - for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate().take(32 - min_idx) { - let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1; - // Note that this multiply can only barely not overflow - two 16 bit ints plus - // 30 bits is 62 bits. - let bucket_prob_times_billion = (*min_bucket as u64) * (*max_bucket as u64) - * 1024 * 1024 * 1024 / total_valid_points_tracked; - if payment_pos >= max_bucket_end_pos { - // Success probability 0, the payment amount may be above the max liquidity - break; + + for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate().skip(1) { + let min_bucket_start_pos = BUCKET_START_POS[min_idx]; + if payment_pos < min_bucket_start_pos { + for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate().take(32 - min_idx) { + let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1; + if payment_pos >= max_bucket_end_pos { + // Success probability 0, the payment amount may be above the max liquidity + break; + } + cumulative_success_points += ((*min_bucket as u32) * (*max_bucket as u32)) as u64; + } + } else { + for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate().take(32 - min_idx) { + let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1; + if payment_pos >= max_bucket_end_pos { + // Success probability 0, the payment amount may be above the max liquidity + break; + } + let (numerator, denominator) = $success_probability(payment_pos as u64, + min_bucket_start_pos as u64, max_bucket_end_pos as u64, + POSITION_TICKS as u64 - 1, true); + // Note that this multiply can only barely not overflow - two 16 bit ints plus + // 30 bits is 62 bits. + let bucket_prob_times_billion = ((*min_bucket as u32) * (*max_bucket as u32)) as u64 + * 1024 * 1024 * 1024 / total_valid_points_tracked; + debug_assert!(bucket_prob_times_billion < u32::max_value() as u64); + cumulative_success_prob_times_billion += bucket_prob_times_billion * + numerator / denominator; + } } - let (numerator, denominator) = success_probability(payment_pos as u64, - min_bucket_start_pos as u64, max_bucket_end_pos as u64, - POSITION_TICKS as u64 - 1, params, true); - cumulative_success_prob_times_billion += bucket_prob_times_billion * - numerator / denominator; } - } + } } + } + + if params.linear_success_probability { + calculate_probability!(linear_success_probability); + } else { + calculate_probability!(nonlinear_success_probability); } // Once we've added all 32*32/2 32-bit success points together, we may have up to 42 -- 2.39.5