Function decide_sharing

crates/ixon/src/sharing.rs:578–627

Decide which subterms to share based on profitability. Sharing is profitable when: `(N - 1) * term_size > N * share_ref_size` where N is usage count, term_size is effective size, and share_ref_size is the size of a Share(idx) reference at the current index. Optimized from O(k×n) to O(n log n) by pre-sorting candidates.

(
  info_map: &HashMap<blake3::Hash, SubtermInfo>,
  topo_order: &[blake3::Hash],
)

/// Optimized from O(k×n) to O(n log n) by pre-sorting candidates.
pub fn decide_sharing(
  info_map: &FxHashMap<blake3::Hash, SubtermInfo>,
  topo_order: &[blake3::Hash],
) -> IndexSet<blake3::Hash> {
  let effective_sizes = compute_effective_sizes(info_map, topo_order);

  // Pre-filter and sort candidates by potential savings (assuming minimal ref_size=1)
  // This gives us a stable ordering since relative savings don't change as ref_size grows
  let mut candidates: Vec<_> = info_map
    .iter()
    .filter(|(_, info)| info.usage_count >= 2)
    .filter_map(|(hash, info)| {
      let term_size = *effective_sizes.get(hash)?;
      let n = info.usage_count;
      // Potential savings assuming ref_size = 1 (minimum)
      let potential = (n as isize - 1) * (term_size as isize) - (n as isize);
      if potential > 0 { Some((*hash, term_size, n)) } else { None }
    })
    .collect();

  // Sort by decreasing gross benefit, with hash bytes as tie-breaker for determinism
  candidates.sort_unstable_by(|a, b| {
    let gross_a = (a.2 as isize - 1) * (a.1 as isize);
    let gross_b = (b.2 as isize - 1) * (b.1 as isize);
    match gross_b.cmp(&gross_a) {
      std::cmp::Ordering::Equal => a.0.as_bytes().cmp(b.0.as_bytes()),
      other => other,
    }
  });

  let mut shared: IndexSet<blake3::Hash> = IndexSet::new();

  // Process ALL candidates - don't break early!
  // The early-break was incorrect: ref_size growth affects candidates differently
  // based on their usage count. A high-usage small term may become unprofitable
  // while a low-usage large term remains profitable.
  for (hash, term_size, usage_count) in candidates {
    let next_idx = shared.len();
    let next_ref_size =
      Tag4::new(Expr::FLAG_SHARE, next_idx as u64).encoded_size();
    let n = usage_count as isize;
    let savings = (n - 1) * (term_size as isize) - n * (next_ref_size as isize);

    if savings > 0 {
      shared.insert(hash);
    }
  }

  shared
}

/// Rewrite expressions to use Share(idx) references for shared subterms.
///
/// Returns the rewritten expressions and the sharing vector.