X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=a6e9a34d8859cdd22091d39954cf4cbd387d2c71;hb=31cbe17ff9d2be628495bb3806dfc4c3de028347;hp=b4f7cbb20220d655e002c4eac1aedcaacd232a74;hpb=adb69cdb99d0f38ad605cfbbd4898d0784ca09f9;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index b4f7cbb20..a6e9a34d8 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -997,12 +997,7 @@ impl cmp::PartialOrd for RouteGraphNode { // While RouteGraphNode can be laid out with fewer bytes, performance appears to be improved // substantially when it is laid out at exactly 64 bytes. -// -// Thus, we use `#[repr(C)]` on the struct to force a suboptimal layout and check that it stays 64 -// bytes here. -#[cfg(any(ldk_bench, not(any(test, fuzzing))))] const _GRAPH_NODE_SMALL: usize = 64 - core::mem::size_of::(); -#[cfg(any(ldk_bench, not(any(test, fuzzing))))] const _GRAPH_NODE_FIXED_SIZE: usize = core::mem::size_of::() - 64; /// A wrapper around the various hop representations. @@ -1179,7 +1174,7 @@ impl<'a> CandidateRouteHop<'a> { } } - #[inline] + #[inline(always)] fn src_node_counter(&self) -> u32 { match self { CandidateRouteHop::FirstHop { payer_node_counter, .. } => *payer_node_counter, @@ -1346,7 +1341,7 @@ fn iter_equal(mut iter_a: I1, mut iter_b: I2) /// Fee values should be updated only in the context of the whole path, see update_value_and_recompute_fees. /// These fee values are useful to choose hops as we traverse the graph "payee-to-payer". #[derive(Clone)] -#[repr(C)] // Force fields to appear in the order we define them. +#[repr(align(128))] struct PathBuildingHop<'a> { candidate: CandidateRouteHop<'a>, target_node_counter: Option, @@ -1370,11 +1365,6 @@ struct PathBuildingHop<'a> { /// channel scoring. path_penalty_msat: u64, - // The last 16 bytes are on the next cache line by default in glibc's malloc. Thus, we should - // only place fields which are not hot there. Luckily, the next three fields are only read if - // we end up on the selected path, and only in the final path layout phase, so we don't care - // too much if reading them is slow. - fee_msat: u64, /// All the fees paid *after* this channel on the way to the destination @@ -1391,17 +1381,8 @@ struct PathBuildingHop<'a> { value_contribution_msat: u64, } -// Checks that the entries in the `find_route` `dist` map fit in (exactly) two standard x86-64 -// cache lines. Sadly, they're not guaranteed to actually lie on a cache line (and in fact, -// generally won't, because at least glibc's malloc will align to a nice, big, round -// boundary...plus 16), but at least it will reduce the amount of data we'll need to load. -// -// Note that these assertions only pass on somewhat recent rustc, and thus are gated on the -// ldk_bench flag. -#[cfg(ldk_bench)] -const _NODE_MAP_SIZE_TWO_CACHE_LINES: usize = 128 - core::mem::size_of::<(NodeId, PathBuildingHop)>(); -#[cfg(ldk_bench)] -const _NODE_MAP_SIZE_EXACTLY_CACHE_LINES: usize = core::mem::size_of::<(NodeId, PathBuildingHop)>() - 128; +const _NODE_MAP_SIZE_TWO_CACHE_LINES: usize = 128 - core::mem::size_of::>(); +const _NODE_MAP_SIZE_EXACTLY_TWO_CACHE_LINES: usize = core::mem::size_of::>() - 128; impl<'a> core::fmt::Debug for PathBuildingHop<'a> { fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> { @@ -2007,6 +1988,8 @@ where L::Target: Logger { // if the amount being transferred over this path is lower. // We do this for now, but this is a subject for removal. if let Some(mut available_value_contribution_msat) = htlc_maximum_msat.checked_sub($next_hops_fee_msat) { + let cltv_expiry_delta = $candidate.cltv_expiry_delta(); + let htlc_minimum_msat = $candidate.htlc_minimum_msat(); let used_liquidity_msat = used_liquidities .get(&$candidate.id()) .map_or(0, |used_liquidity_msat| { @@ -2029,7 +2012,7 @@ where L::Target: Logger { .checked_sub(2*MEDIAN_HOP_CLTV_EXPIRY_DELTA) .unwrap_or(payment_params.max_total_cltv_expiry_delta - final_cltv_expiry_delta); let hop_total_cltv_delta = ($next_hops_cltv_delta as u32) - .saturating_add($candidate.cltv_expiry_delta()); + .saturating_add(cltv_expiry_delta); let exceeds_cltv_delta_limit = hop_total_cltv_delta > max_total_cltv_expiry_delta; let value_contribution_msat = cmp::min(available_value_contribution_msat, $next_hops_value_contribution); @@ -2040,13 +2023,13 @@ where L::Target: Logger { None => unreachable!(), }; #[allow(unused_comparisons)] // $next_hops_path_htlc_minimum_msat is 0 in some calls so rustc complains - let over_path_minimum_msat = amount_to_transfer_over_msat >= $candidate.htlc_minimum_msat() && + let over_path_minimum_msat = amount_to_transfer_over_msat >= htlc_minimum_msat && amount_to_transfer_over_msat >= $next_hops_path_htlc_minimum_msat; #[allow(unused_comparisons)] // $next_hops_path_htlc_minimum_msat is 0 in some calls so rustc complains let may_overpay_to_meet_path_minimum_msat = - ((amount_to_transfer_over_msat < $candidate.htlc_minimum_msat() && - recommended_value_msat >= $candidate.htlc_minimum_msat()) || + ((amount_to_transfer_over_msat < htlc_minimum_msat && + recommended_value_msat >= htlc_minimum_msat) || (amount_to_transfer_over_msat < $next_hops_path_htlc_minimum_msat && recommended_value_msat >= $next_hops_path_htlc_minimum_msat)); @@ -2121,12 +2104,14 @@ where L::Target: Logger { // payment path (upstream to the payee). To avoid that, we recompute // path fees knowing the final path contribution after constructing it. let curr_min = cmp::max( - $next_hops_path_htlc_minimum_msat, $candidate.htlc_minimum_msat() + $next_hops_path_htlc_minimum_msat, htlc_minimum_msat ); - let path_htlc_minimum_msat = compute_fees_saturating(curr_min, $candidate.fees()) + let candidate_fees = $candidate.fees(); + let src_node_counter = $candidate.src_node_counter(); + let path_htlc_minimum_msat = compute_fees_saturating(curr_min, candidate_fees) .saturating_add(curr_min); - let dist_entry = &mut dist[$candidate.src_node_counter() as usize]; + let dist_entry = &mut dist[src_node_counter as usize]; let old_entry = if let Some(hop) = dist_entry { hop } else { @@ -2170,7 +2155,7 @@ where L::Target: Logger { if src_node_id != our_node_id { // Note that `u64::max_value` means we'll always fail the // `old_entry.total_fee_msat > total_fee_msat` check below - hop_use_fee_msat = compute_fees_saturating(amount_to_transfer_over_msat, $candidate.fees()); + hop_use_fee_msat = compute_fees_saturating(amount_to_transfer_over_msat, candidate_fees); total_fee_msat = total_fee_msat.saturating_add(hop_use_fee_msat); } @@ -8592,14 +8577,23 @@ pub mod benches { score_params: &S::ScoreParams, features: Bolt11InvoiceFeatures, starting_amount: u64, bench_name: &'static str, ) { - let payer = bench_utils::payer_pubkey(); - let keys_manager = KeysManager::new(&[0u8; 32], 42, 42); - let random_seed_bytes = keys_manager.get_secure_random_bytes(); - // First, get 100 (source, destination) pairs for which route-getting actually succeeds... let route_endpoints = bench_utils::generate_test_routes(graph, &mut scorer, score_params, features, 0xdeadbeef, starting_amount, 50); // ...then benchmark finding paths between the nodes we learned. + do_route_bench(bench, graph, scorer, score_params, bench_name, route_endpoints); + } + + #[inline(never)] + fn do_route_bench( + bench: &mut Criterion, graph: &NetworkGraph<&TestLogger>, scorer: S, + score_params: &S::ScoreParams, bench_name: &'static str, + route_endpoints: Vec<(ChannelDetails, PaymentParameters, u64)>, + ) { + let payer = bench_utils::payer_pubkey(); + let keys_manager = KeysManager::new(&[0u8; 32], 42, 42); + let random_seed_bytes = keys_manager.get_secure_random_bytes(); + let mut idx = 0; bench.bench_function(bench_name, |b| b.iter(|| { let (first_hop, params, amt) = &route_endpoints[idx % route_endpoints.len()];