golang 随机数演化

news/2024/10/21 3:05:56/

在Go1.22版本中引入了math/rand/v2包，为原math/rand带来了必要提升

随机数特性

假随机

无论是原版本还是v2版本都不存在真正的随机数，其本质依然是根据初始种子生成的数字序列

全局随机数并发安全

对于原math/rand，全局随机数生成器rngSource在每次获取随机数后，会重新设置rng.vec的值，所以会出现并发冲突。因此通过sync.Mutex来进行并发竞争处理

type lockedSource struct {lk sync.Mutexs  *rngSource
}func (r *lockedSource) Int63() (n int64) {r.lk.Lock()n = r.s.Int63()r.lk.Unlock()return
}

对于v2，全局随机数则是通过在绑定的系统线程获取chacha8随机数生成器，这个锁显然粒度更低，仅在系统线程绑定的协程中加锁

// rand returns a random uint64 from the per-m chacha8 state.
// Do not change signature: used via linkname from other packages.
//go:nosplit
//go:linkname rand
func rand() uint64 {// Note: We avoid acquirem here so that in the fast path// there is just a getg, an inlined c.Next, and a return.// The performance difference on a 16-core AMD is// 3.7ns/call this way versus 4.3ns/call with acquirem (+16%).mp := getg().mc := &mp.chacha8for {// Note: c.Next is marked nosplit,// so we don't need to use mp.locks// on the fast path, which is that the// first attempt succeeds.x, ok := c.Next()if ok {return x}mp.locks++ // hold m even though c.Refill may do stack split checksc.Refill()mp.locks--}
}

原math/rand问题

生成器并不是最优的

可重复性要求意味着无法在不破坏兼容性的情况下替换生成器

Source定义为缩短的63位

Source接口定义为缩短的63位，这并不是现代生成器的uint64

全局生成器的初始化种子责任不明

大多数用户直接使用全局生成器，而全局生成器默认Seed(1)，这意味着随机数生成的都是一致的

全局生成器不易拓展

全局生成器为了保护共享的生成器状态，分布到各goroutine会造成锁竞争加剧，此外由于用的同一初始种子，破坏了随机数生成器的可重复性

分裂

在原实现中，先求得小于等于1<<63 - 1且模n为0的最大的int64值，这样确保生成的随机数在取模n后能够均匀分布在[0,n)范围内，但也由此带来了性能问题。

Lemire算法可以使得rand.Intn(1000)快20～30%，可是由于破坏了可重复性，所以无法在原实现直接引入

func (r *Rand) Int63n(n int64) int64 {if n <= 0 {panic("invalid argument to Int63n")}max := int64((1<<63 - 1)  - (1<<63)%uint64(n))v := r.src.Int63()for v > max {v = r.Int63()}return v % n
}