
近日 B 站看到概率问题:《连续抛 10000 次硬币,最多几连正的概率最大?》
使用擅长的 Java 模拟,共 10w 次实验,每次实验模拟投掷 1w 次,耗时 1080ms ;多次运行耗时相差不大。
同样的算法,用 Kimi 翻译成 Rust ,cargo build --release 生成可执行文件;但执行效率不如 Java ,且耗时 10x。
哪里有问题呢?
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; } } 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 } 1 wuruxu 2024-05-09 12:43:42 +08:00 按理应该差不多才是,rust 直接编译成机器码了,java 还有个 JIT 的虚拟机 |
2 fgwmlhdkkkw 2024-05-09 12:46:04 +08:00 via Android 会不会是随机设备不一样。 |
3 nagisaushio 2024-05-09 12:47:27 +08:00 via Android 盲猜 hasher 的问题。rust 默认 hasher 是比较慢的 |
4 KagurazakaNyaa 2024-05-09 12:55:27 +08:00 如果用统一的随机数生成方式,比如 java 和 rust 都改成读取/dev/urandom 耗时会不会有所变化 |
5 xiaopanzi 2024-05-09 12:58:59 +08:00 无法复现。我在 Linux 机器上,JDK 17 Execution time: 4273ms ; Rust 1.72 Execution time: 2310ms |
6 undeflife 2024-05-09 13:01:07 +08:00 之前碰到过类似的情况, 当时的分析结果是非常频繁的内存分配,rust 需要调用操作系统来分配会比有 gc 语言的开销要大, 使用 jemalloc 会有改善 |
7 undeflife 2024-05-09 13:02:40 +08:00 另外你确定你的 Rust 代码是跑的 release 来比较性能的吧? |
8 kneo 2024-05-09 13:03:55 +08:00 你这个测的基本是随机数库的性能。你把随机数代码单独拿出来测一下。 |
9 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(); |
10 rming 2024-05-09 13:12:40 +08:00 |
11 e3c78a97e0f8 2024-05-09 13:13:10 +08:00 1 两个标准库的随机数算法完全不一样 Rust 默认的是密码学安全的随机数,Java 不是。而且它们二者的密码学安全随机数生成器也是不同的算法。你要比,就得都用一个算法的随机数,比如 MT19937 。 |
12 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. |
13 lt0136 2024-05-09 13:17:05 +08:00 随机数算法的问题: Java 的随机数算法是 LCG:就是简单的 x(n+1) = (x(n) * a + c) % mod 计算 Rust 的 thread_rng 默认用的安全的随机数生成算法,好像是 chachaX ?会慢 |
14 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 是加密的 |
15 764664 2024-05-09 13:17:54 +08:00 Java 的随机数是线性同余方法生成的 https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadLocalRandom.html#next-int- rand crate 的 ThreadRng 是密码学安全的 ChaCha12 https://rust-random.github.io/rand/rand/rngs/struct.ThreadRng.html |
16 Akagi201 2024-05-09 13:19:27 +08:00 我用 rust 重写一个 js 算法(node.js 跟 bun), 结果耗时基本持平(rust 略差于 js), 最高内存消耗也持平. 所以带 gc 语言不一定就慢, 要看程序的瓶颈. 我算法的瓶颈主要在内存 io 上, 不在 cpu. |
17 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/ |
18 nullyouraise 2024-05-09 13:26:54 +08:00 你可以试试分别统计 for 循环和 sum 的耗时,然后二者相加,最后对比 Rust 和 Java 实现里这个耗时值,我猜不会差太多 |
19 acr0ss OP @nullyouraise 谢谢告知这个影响。不过我任务这点影响不大,print 也就 25 行左右。 |
20 realJamespond 2024-05-09 13:57:21 +08:00 随机算法设备这种基本环境得保证大致公平吧,不然这么比没意义了 |
21 lvlongxiang199 2024-05-09 14:07:00 +08:00 打个火焰图看看 ? |
22 Ericcccccccc 2024-05-09 14:22:19 +08:00 看不起 jit 吗... 很多时候性能比 c++ 都高 |
23 DAM 2024-05-09 14:23:42 +08:00 ![]() 有外网消息称 m4 替换了 AMX 为 Arm 的 SME ,排除这个因素的 IPC 提升为 0 ; 消息来源 https://twitter.com/negativeonehero/status/1788360191471431919 |
24 DAM 2024-05-09 14:35:55 +08:00 回复错了帖子 |
25 qzh993 2024-05-09 14:46:17 +08:00 |
26 UxwVI042kEc5pNx6 2024-05-09 14:54:48 +08:00 试了下 Go ,不用协程要 6130ms 左右,用了协程跟 Java 差不多,1110ms 左右: ```go package main import ( "fmt" "math/rand" "sync" "time" ) const ( tosses = 10_000 // 1e4 iteratiOns= 100_000 // 1e5 ) func main() { start := time.Now() // streakMap := make(map[int]int64) // 6130±20 streakMap := sync.Map{} // 1110±20 var wg sync.WaitGroup for i := 0; i < iterations; i++ { wg.Add(1) go func() { defer wg.Done() max := maxStreak() //streakMap[max] = streakMap[max] + 1 m, _ := streakMap.Load(max) if m == nil { m = int64(0) } streakMap.Store(max, m.(int64)+1) }() } wg.Wait() var total int64 //for _, value := range streakMap { // total += value //} streakMap.Range(func(key, value any) bool { if value == nil { value = int64(0) } total += value.(int64) return true }) //for key, value := range streakMap { // fmt.Printf("Max: %d, count: %d, percent: %.2f%%\n", key, value, (float64(value)*100)/float64(total)) //} streakMap.Range(func(key, value any) bool { fmt.Printf("Max: %d, count: %d, percent: %.2f%%\n", key, value, (float64(value.(int64))*100)/float64(total)) return true }) // print execute time in ms fmt.Printf("Execution time: %dms\n", time.Since(start).Milliseconds()) } func maxStreak() (max int) { var streak int var r = rand.New(rand.NewSource(time.Now().UnixNano())) for i := 0; i < tosses; i++ { current := r.Intn(2) == 1 if current { streak++ } else { streak = 0 } if streak > max { max = streak } } return max } ``` |
27 xgdgsc 2024-05-10 08:32:37 +08:00 via Android |
28 mmdsun 2024-05-10 12:03:51 +08:00 via iPhone Java 预热后也转成机器指令了,速度不一定比 rust 慢 |