Java 性能竟然优于 Rust,哪里有问题呢?

2024-05-09 12:39:33 +08:00
 acr0ss

近日 B 站看到概率问题:《连续抛 10000 次硬币,最多几连正的概率最大?》

使用擅长的 Java 模拟,共 10w 次实验,每次实验模拟投掷 1w 次,耗时 1080ms ;多次运行耗时相差不大。
同样的算法,用 Kimi 翻译成 Rust ,cargo build --release 生成可执行文件;但执行效率不如 Java ,且耗时 10x
哪里有问题呢?

Java

public class TossStreakProbability {
    public static final int tosses = 10_000; // 10^4
    public static final int iterations = 100_000; // 10^5

    public static void main(String[] args) {
        Instant start = Instant.now();
        Map<Integer, Long> streakMap = new HashMap<>();

        for (int i = 0; i < iterations; i++) {
            int maxStreak = maxStreak();
            streakMap.put(maxStreak, streakMap.getOrDefault(maxStreak, 0L) + 1);
        }

        long total = streakMap.values().stream().mapToLong(Long::intValue).sum();
        streakMap.forEach((key, value) -> System.out.printf(
                "Max: %d, count: %d, percent:%.2f%%\n",
                key, value, (value * 100.0) / total));

        // print execute time in ms
        System.out.println("Execution time: " + (Instant.now().toEpochMilli() - start.toEpochMilli()) + "ms");
    }

    public static int maxStreak() {
        int streak = 0, maxStreak = 0;
        var random = ThreadLocalRandom.current();
        for (int i = 0; i < tosses; i++) {
            boolean current = random.nextBoolean();
            if (current) {
                streak++;
            } else {
                streak = 0;
            }
            maxStreak = Math.max(maxStreak, streak);
        }
        return maxStreak;
    }
}

Rust

use std::collections::HashMap;
use std::time::Instant;

use rand::prelude::*;


const TOSSES: i32 = 10_000; // 10^4
const ITERATIONS: i32 = 100_000; // 10^5

fn main() {
    let start = Instant::now();
    let mut streak_map: HashMap<i32, i64> = HashMap::new();

    for _ in 0..ITERATIONS {
        let max_streak = max_streak();
        *streak_map.entry(max_streak).or_insert(0) += 1;
    }

    let total: i64 = streak_map.values().sum();
    for (key, value) in &streak_map {
        println!("Max: {}, count: {}, percent: {:.2}%", key, value, (*value as f64 / total as f64) * 100.0);
    }

    // print execute time in ms
    let duration = start.elapsed();
    println!("Execution time: {}ms", duration.as_millis());
}

fn max_streak() -> i32 {
    let mut streak = 0;
    let mut max_streak = 0;
    let mut rand = thread_rng();

    for _ in 0..TOSSES {
        let current = rand.gen_bool(0.5);
        if current {
            streak += 1;
        } else {
            streak = 0;
        }
        max_streak = std::cmp::max(max_streak, streak);
    }
    max_streak
}
6129 次点击
所在节点    程序员
28 条回复
wuruxu
2024-05-09 12:43:42 +08:00
按理应该差不多才是,rust 直接编译成机器码了,java 还有个 JIT 的虚拟机
fgwmlhdkkkw
2024-05-09 12:46:04 +08:00
会不会是随机设备不一样。
nagisaushio
2024-05-09 12:47:27 +08:00
盲猜 hasher 的问题。rust 默认 hasher 是比较慢的
XiLingHost
2024-05-09 12:55:27 +08:00
如果用统一的随机数生成方式,比如 java 和 rust 都改成读取/dev/urandom 耗时会不会有所变化
xiaopanzi
2024-05-09 12:58:59 +08:00
无法复现。我在 Linux 机器上,JDK 17 Execution time: 4273ms ; Rust 1.72 Execution time: 2310ms
undeflife
2024-05-09 13:01:07 +08:00
之前碰到过类似的情况, 当时的分析结果是非常频繁的内存分配,rust 需要调用操作系统来分配会比有 gc 语言的开销要大, 使用 jemalloc 会有改善
undeflife
2024-05-09 13:02:40 +08:00
另外你确定你的 Rust 代码是跑的 release 来比较性能的吧?
kneo
2024-05-09 13:03:55 +08:00
你这个测的基本是随机数库的性能。你把随机数代码单独拿出来测一下。
ns09005264
2024-05-09 13:12:29 +08:00
是随机数生成器的性能吧。
rust 的 rand 包启用 smallRng 特性,然后
let mut rand = thread_rng();
换成
let mut rand = rand::rngs::SmallRng::from_entropy();
rming
2024-05-09 13:12:40 +08:00
搜了下,参考这个 issue ,https://github.com/rust-lang/rust/issues/43120

rand crate 并不是标准库
e3c78a97e0f8
2024-05-09 13:13:10 +08:00
两个标准库的随机数算法完全不一样
Rust 默认的是密码学安全的随机数,Java 不是。而且它们二者的密码学安全随机数生成器也是不同的算法。你要比,就得都用一个算法的随机数,比如 MT19937 。
rming
2024-05-09 13:13:29 +08:00
@rming Also note that Java's ThreadLocalRandom is an extremely simple linear congruential PRNG, while Rust's rand's thread_rng() is based on the ISAAC (claimed-to-be) cryptographically secure PRNG which is more expensive, so this benchmark is not an exactly apple-to-apple comparison.
lt0136
2024-05-09 13:17:05 +08:00
随机数算法的问题:
Java 的随机数算法是 LCG:就是简单的 x(n+1) = (x(n) * a + c) % mod 计算
Rust 的 thread_rng 默认用的安全的随机数生成算法,好像是 chachaX ?会慢
ns09005264
2024-05-09 13:17:48 +08:00
两个语言的随机数生成器的文档:
java:https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadLocalRandom.html
Instances of ThreadLocalRandom are not cryptographically secure
ThreadLocalRandom 没有加密

rust:https://docs.rs/rand/latest/rand/rngs/index.html
meaning a cryptographically secure PRNG
ThreadRng 所使用的 StdRng 是加密的
764664
2024-05-09 13:17:54 +08:00
Akagi201
2024-05-09 13:19:27 +08:00
我用 rust 重写一个 js 算法(node.js 跟 bun), 结果耗时基本持平(rust 略差于 js), 最高内存消耗也持平.
所以带 gc 语言不一定就慢, 要看程序的瓶颈. 我算法的瓶颈主要在内存 io 上, 不在 cpu.
nullyouraise
2024-05-09 13:25:27 +08:00
除了 rand 这个库可能是导致耗时增高的因素以外,你的 profile scope 内包含了 println ,向 stdout 输出时会 flush ,可能会导致耗时增高,在其他 Java vs Rust 的对比中也存在这样的可能性 https://www.reddit.com/r/rust/comments/1677ar8/why_is_rust_println_slower_than_java_println/
nullyouraise
2024-05-09 13:26:54 +08:00
你可以试试分别统计 for 循环和 sum 的耗时,然后二者相加,最后对比 Rust 和 Java 实现里这个耗时值,我猜不会差太多
acr0ss
2024-05-09 13:36:22 +08:00
@nullyouraise 谢谢告知这个影响。不过我任务这点影响不大,print 也就 25 行左右。
realJamespond
2024-05-09 13:57:21 +08:00
随机算法设备这种基本环境得保证大致公平吧,不然这么比没意义了

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/1039069

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX