Rust优化Vec查找性能：避免重复创建迭代器的方案

问题背景 #

处理Cargo dump数据构建crate关联图，需将每个包版本与符合semver规则的最新依赖版本关联（数据库返回的版本数据已按ID降序排列，首个匹配版本即为目标）。当前代码因每次查找都遍历数百万元素的Vec导致耗时过长（本地约3小时），核心瓶颈在于重复创建迭代器并全量遍历查找。

相关定义与原代码 #

结构体定义 #

#[derive(Debug, Clone, sqlx::FromRow)]
pub struct CargoCrateVersionRow {
    pub id: i32,
    pub crate_id: i32,
    pub version_num: String,
    pub created_at: sqlx::types::chrono::NaiveDateTime,
    pub updated_at: sqlx::types::chrono::NaiveDateTime,
    pub downloads: i32,
    pub features: sqlx::types::Json<HashMap<String, Vec<String>>>,
    pub yanked: bool,
    pub license: Option<String>,
    pub crate_size: Option<i32>,
    pub published_by: Option<i32>,
}

#[derive(Debug, sqlx::FromRow)]
pub struct CargoDependenciesRow {
    pub version_id: i32,
    pub crate_id: i32,
    pub req: String,
    pub optional: bool,
    pub features: Vec<String>,
    pub kind: i32,
}

#[derive(Debug)]
pub struct CargoCrateVersionDependencyEdge {
    pub version_id_from: i32,
    pub version_id_to: i32,
    pub optional: bool,
    pub with_features: Vec<String>,
    pub kind: i32,
}

数据查询SQL #

获取依赖数据：

select version_id, crate_id, req, optional, features, kind 
from dependencies;

获取版本数据（已按ID降序）：

select 
    id, crate_id, num "version_num", created_at, updated_at, 
    downloads, features, yanked, license, crate_size, published_by 
from 
    versions
order by 
    id desc;

原核心逻辑（性能瓶颈） #

let mut cargo_crate_dependency_edges: Vec<CargoCrateVersionDependencyEdge> = vec![];
let mut i = 0;
for dep in crate_dependencies {
    if i % 10_000 == 0 {
        println!("done 10k");
    }

    let req = skip_fail!(VersionReq::parse(dep.req.as_str()));
    
    // 每次遍历数百万元素的Vec，耗时极高
    let possible_crate_version = crate_versions.iter().find(|s| {
        if s.crate_id != dep.crate_id {
            return false;
        }
        if let Ok(parsed_version) = Version::parse(&s.version_num) {
            req.matches(&parsed_version)
        } else {
            false
        }
    });

    if let Some(found_crate_version) = possible_crate_version {
        cargo_crate_dependency_edges.push(
            CargoCrateVersionDependencyEdge {
                    version_id_from: dep.version_id,
                    version_id_to: found_crate_version.id,
                    optional: dep.optional,
                    with_features: dep.features.clone(),
                    kind: dep.kind,
                }
        );
    }

    i += 1;
}
println!("{}", cargo_crate_dependency_edges.len());

优化方案 #

1. 预处理版本数据：按crate_id分组+提前解析版本号 #

原代码每次查找都要遍历全量版本并重复解析版本号，将版本数据按crate_id分组存入哈希表，同时提前解析版本号（仅解析一次），将时间复杂度从O(NM)降至O(M + NK)（K为单crate平均版本数，远小于M）。

use std::collections::HashMap;
use semver::{Version, VersionReq};

// 封装提前解析好版本的结构体，避免重复解析开销
#[derive(Debug)]
struct ParsedCrateVersion<'a> {
    row: &'a CargoCrateVersionRow,
    parsed_version: Option<Version>,
}

// 预处理：按crate_id分组存储版本数据，同时预解析版本号
let mut crate_versions_by_id: HashMap<i32, Vec<ParsedCrateVersion>> = HashMap::new();
for version in &crate_versions {
    let parsed_version = Version::parse(&version.version_num).ok();
    crate_versions_by_id
        .entry(version.crate_id)
        .or_default()
        .push(ParsedCrateVersion {
            row: version,
            parsed_version,
        });
}

2. 优化依赖查找逻辑 #

直接从哈希表中获取对应crate的版本列表，无需遍历全量数据：

// 预分配结果Vec容量，减少扩容开销
let mut cargo_crate_dependency_edges = Vec::with_capacity(crate_dependencies.len());
let mut i = 0;

for dep in crate_dependencies {
    if i % 10_000 == 0 {
        println!("done 10k");
    }

    // 跳过解析失败的semver规则
    let Ok(req) = VersionReq::parse(&dep.req) else {
        i += 1;
        continue;
    };

    // 仅遍历目标crate的版本列表
    if let Some(versions) = crate_versions_by_id.get(&dep.crate_id) {
        let possible_crate_version = versions.iter().find(|pv| {
            pv.parsed_version.as_ref().map_or(false, |v| req.matches(v))
        });

        if let Some(found) = possible_crate_version {
            cargo_crate_dependency_edges.push(CargoCrateVersionDependencyEdge {
                version_id_from: dep.version_id,
                version_id_to: found.row.id,
                optional: dep.optional,
                with_features: dep.features.clone(),
                kind: dep.kind,
            });
        }
    }

    i += 1;
}

println!("{}", cargo_crate_dependency_edges.len());

3. 额外性能提升点 #

• 使用高效哈希表：替换标准库HashMap为rustc_hash::FxHashMap，大幅提升哈希查找性能。
• 并行处理：依赖查找是无状态操作，可通过rayon实现并行迭代，进一步缩短耗时：

  use rayon::prelude::*;
  
  let cargo_crate_dependency_edges: Vec<_> = crate_dependencies
      .par_iter()
      .filter_map(|dep| {
          let Ok(req) = VersionReq::parse(&dep.req) else {
              return None;
          };
  
          crate_versions_by_id.get(&dep.crate_id).and_then(|versions| {
              versions.iter().find(|pv| {
                  pv.parsed_version.as_ref().map_or(false, |v| req.matches(v))
              }).map(|found| {
                  CargoCrateVersionDependencyEdge {
                      version_id_from: dep.version_id,
                      version_id_to: found.row.id,
                      optional: dep.optional,
                      with_features: dep.features.clone(),
                      kind: dep.kind,
                  }
              })
          })
      })
      .collect();
  

• 避免不必要的克隆：若无需保留原dep.features数据，可直接移动所有权（with_features: dep.features）代替clone()。

内容的提问来源于stack exchange，提问作者TDiblik