使用Rayon的Rust多线程BigUint进制转换性能不及单线程求解

我正在开发一个将BigUint转换为1048576进制的函数。单线程版本处理大数值时会导致程序卡顿、CPU占用100%且耗时极长，因此尝试用Rayon实现多线程版本，但性能并未得到提升，特此求助。

单线程实现代码：

fn deci_convert(number: &mut BigUint, map: &HashMap<u32, char>) -> String {
    println!("Decimal conversion start");
    let base = BigUint::from_u32(1048575).unwrap(); // Create BigUint once for base
    let mut temp_string = String::new();

    // Precompute powers of base up to the needed value
    let mut base_powers = vec![BigUint::one()];
    let mut current_power = BigUint::one();

    while &current_power <= number {
        current_power *= &base;
        base_powers.push(current_power.clone());
    }
    base_powers.pop(); // Remove the last power as it exceeds the number

    while *number != BigUint::zero() {
        for i in (0..base_powers.len()).rev() {
            if &base_powers[i] <= number {
                let digit = (&*number / &base_powers[i]).to_u32().unwrap();
                *number %= &base_powers[i];
                if let Some(&c) = map.get(&digit) {
                    temp_string.push(c);
                } else {
                    panic!("Digit not on the map. The digit that caused the issue is {}", digit);
                }
                break;
            }
        }
    }

    temp_string
}

多线程实现代码：

fn _par_deci_convert(number: &mut BigUint, map: &HashMap<u32, char>) -> String {
    println!("Parallel decimal conversion begins");

    let base = 1048575u32;
    let base_biguint = BigUint::from_u32(base).unwrap();
    
    // Compute the maximum exponent
    let max_exponent = (0..)
        .take_while(|&i| *number >= base_biguint.pow(i as u32))
        .last()
        .unwrap_or(0);

    // Precompute base powers
    let base_powers: Vec<BigUint> = (0..=max_exponent)
        .map(|i| base_biguint.pow(i as u32))
        .collect();

    println!("Deci convert started");

    // This mutex will be used to safely modify the string in parallel
    let result = Arc::new(Mutex::new(String::new()));

    // Parallel processing of base powers
    base_powers.into_par_iter().rev().for_each(|base_power| {
        let mut local_number = Arc::new(Mutex::new(number.clone()));

        let digit = {
            let mut num = local_number.lock().unwrap();
            let digit = (&*num / &base_power).to_u32().unwrap();
            *num %= base_power;
            digit
        };

        if let Some(&c) = map.get(&digit) {
            let mut result = result.lock().unwrap();
            result.push(c);
        } else {
            panic!("Digit not on the map, you messed up somewhere. Digit: {}", digit);
        }
    });

    // Collect the final result
    let final_result = Arc::try_unwrap(result).unwrap().into_inner().unwrap();

    println!("Deci convert finished");

    final_result
} 

多线程版本失效的核心原因 #

你的多线程实现存在几个致命问题，直接导致性能不升反降，甚至结果错误：

1. 无意义的克隆与锁开销：每个线程都克隆了完整的BigUint，对于超大数值来说，这个克隆操作的开销远大于并行计算的收益；同时给每个克隆的数值加Mutex完全多余，徒增同步开销。
2. 逻辑错误导致重复计算：所有线程都基于原始number的副本计算，而非逐步取余后的数值，这会导致每个线程计算出相同的高位数字，结果完全错误，还做了大量重复工作。
3. 结果写入串行化：用Mutex保护结果字符串，每个线程写入都要加锁，把并行操作强行变成串行，彻底抵消了并行优势。

此外，原始单线程版本也存在效率浪费：每次循环都逆序遍历base_powers找当前最大幂次，完全可以直接从最高次幂依次处理，避免重复遍历。

优化方案 #

第一步：优化单线程版本 #

先修复单线程的冗余遍历问题，提升基础性能：

use num_bigint::BigUint;
use std::collections::HashMap;

fn optimized_deci_convert(number: &mut BigUint, map: &HashMap<u32, char>) -> String {
    let base = BigUint::from_u32(1048575).unwrap();
    let mut temp_string = String::new();

    // 预计算所有需要的base幂次
    let mut base_powers = vec![BigUint::one()];
    let mut current_power = BigUint::one();
    while &current_power <= number {
        current_power *= &base;
        base_powers.push(current_power.clone());
    }
    base_powers.pop(); // 移除超出数值的最后一个幂次

    // 从最高次幂开始依次处理，无需每次遍历
    for power in base_powers.iter().rev() {
        if power <= number {
            let digit = (&*number / power).to_u32().unwrap();
            *number %= power;
            if let Some(&c) = map.get(&digit) {
                temp_string.push(c);
            } else {
                panic!("Digit not on the map. The digit that caused the issue is {}", digit);
            }
        }
        // 数值为0时提前退出，避免无用循环
        if *number == BigUint::zero() {
            break;
        }
    }

    temp_string
}

第二步：正确的多线程实现 #

BigUint的进制转换无法直接并行处理完整取余流程（每一步依赖上一步结果），但可以通过并行计算每个幂次对应的数字（独立无依赖），最后排序拼接结果来实现并行加速：

use num_bigint::BigUint;
use std::collections::HashMap;
use std::sync::Arc;
use rayon::prelude::*;

fn par_deci_convert(number: &BigUint, map: &Arc<HashMap<u32, char>>) -> String {
    let base = 1048575u32;
    let base_big = BigUint::from_u32(base).unwrap();

    // 预计算所有需要的base幂次
    let mut base_powers = vec![BigUint::one()];
    let mut current_power = BigUint::one();
    while &current_power <= number {
        current_power *= &base_big;
        base_powers.push(current_power.clone());
    }
    base_powers.pop();

    // 绑定幂次与索引，用于后续排序
    let power_with_index: Vec<(usize, &BigUint)> = base_powers.iter().enumerate().collect();

    // 并行计算每个幂次对应的数字，记录索引
    let digits: Vec<(usize, char)> = power_with_index
        .par_iter()
        .filter_map(|&(idx, power)| {
            if power <= number {
                let digit = (number / power).to_u32().unwrap();
                map.get(&digit).map(|&c| (idx, c))
            } else {
                None
            }
        })
        .collect();

    // 按索引排序，恢复正确的进制位顺序（高位到低位）
    let mut digits_sorted = digits;
    digits_sorted.sort_by_key(|&(idx, _)| idx);
    digits_sorted.reverse();

    // 拼接结果字符串
    digits_sorted.into_iter().map(|(_, c)| c).collect()
}

这个实现的关键改进：

1. 不再克隆原始BigUint，所有线程共享只读引用，无同步开销。
2. 并行计算每个幂次对应的数字，避免重复工作。
3. 通过索引排序拼接结果，避免写入时的锁竞争。
4. 用Arc共享HashMap，避免多线程克隆哈希表。

额外优化建议 #

• 移除转换函数中的日志打印，I/O操作会严重拖慢性能。
• 将HashMap替换为固定长度数组（因为digit范围是0~1048575），数组访问速度远快于哈希表：

  // 提前构建数组代替HashMap
  let mut char_map = ['\0'; 1048576];
  // 填充char_map，例如 char_map[digit] = 对应字符
  

• 对于超大BigUint，可使用to_bytes_le/to_bytes_be转换为字节数组，按进制字节长度拆分块并行处理，进一步提升效率。

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