近日 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 196 天前
按理应该差不多才是,rust 直接编译成机器码了,java 还有个 JIT 的虚拟机
|
2
fgwmlhdkkkw 196 天前 via Android
会不会是随机设备不一样。
|
3
nagisaushio 196 天前 via Android 1
盲猜 hasher 的问题。rust 默认 hasher 是比较慢的
|
4
XiLingHost 196 天前
如果用统一的随机数生成方式,比如 java 和 rust 都改成读取/dev/urandom 耗时会不会有所变化
|
5
xiaopanzi 196 天前
无法复现。我在 Linux 机器上,JDK 17 Execution time: 4273ms ; Rust 1.72 Execution time: 2310ms
|
6
undeflife 196 天前
之前碰到过类似的情况, 当时的分析结果是非常频繁的内存分配,rust 需要调用操作系统来分配会比有 gc 语言的开销要大, 使用 jemalloc 会有改善
|
7
undeflife 196 天前
另外你确定你的 Rust 代码是跑的 release 来比较性能的吧?
|
8
kneo 196 天前 1
你这个测的基本是随机数库的性能。你把随机数代码单独拿出来测一下。
|
9
ns09005264 196 天前 1
是随机数生成器的性能吧。
rust 的 rand 包启用 smallRng 特性,然后 let mut rand = thread_rng(); 换成 let mut rand = rand::rngs::SmallRng::from_entropy(); |
10
rming 196 天前
|
11
e3c78a97e0f8 196 天前 1
两个标准库的随机数算法完全不一样
Rust 默认的是密码学安全的随机数,Java 不是。而且它们二者的密码学安全随机数生成器也是不同的算法。你要比,就得都用一个算法的随机数,比如 MT19937 。 |
12
rming 196 天前 1
@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 196 天前
随机数算法的问题:
Java 的随机数算法是 LCG:就是简单的 x(n+1) = (x(n) * a + c) % mod 计算 Rust 的 thread_rng 默认用的安全的随机数生成算法,好像是 chachaX ?会慢 |
14
ns09005264 196 天前 1
两个语言的随机数生成器的文档:
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 196 天前 1
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 196 天前
我用 rust 重写一个 js 算法(node.js 跟 bun), 结果耗时基本持平(rust 略差于 js), 最高内存消耗也持平.
所以带 gc 语言不一定就慢, 要看程序的瓶颈. 我算法的瓶颈主要在内存 io 上, 不在 cpu. |
17
nullyouraise 196 天前 1
除了 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 196 天前
你可以试试分别统计 for 循环和 sum 的耗时,然后二者相加,最后对比 Rust 和 Java 实现里这个耗时值,我猜不会差太多
|
19
acr0ss OP @nullyouraise 谢谢告知这个影响。不过我任务这点影响不大,print 也就 25 行左右。
|
20
realJamespond 196 天前
随机算法设备这种基本环境得保证大致公平吧,不然这么比没意义了
|
21
lvlongxiang199 196 天前
打个火焰图看看 ?
|
22
Ericcccccccc 196 天前
看不起 jit 吗...
很多时候性能比 c++ 都高 |
23
DAM 196 天前
有外网消息称 m4 替换了 AMX 为 Arm 的 SME ,排除这个因素的 IPC 提升为 0 ; 消息来源 https://twitter.com/negativeonehero/status/1788360191471431919 |
24
DAM 196 天前
回复错了帖子😨
|
25
qzh993 196 天前
|
26
UxwVI042kEc5pNx6 196 天前
试了下 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 195 天前 via Android
|
28
mmdsun 195 天前 via iPhone
Java 预热后也转成机器指令了,速度不一定比 rust 慢
|