实现了一套基于 lockfree 的并发安全的数据结构

[wencan]

https://github.com/wencan/freesync

https://pkg.go.dev/github.com/wencan/freesync

本项目包含两个部分，freesyn/lockfree 为一套无锁的基础数据结构。freesync 为一套基于无锁基础数据结构的简单复合结构。freesyn/lockfree 完全是 lockfree ，freesync 利用了 sync.Mutex 。

包	结构	说明	性能
freesync/lockfree	LimitedSlice	无锁的长度受限的 Slice
freesync/lockfree	SinglyLinkedList	无锁的单链表
freesync/lockfree	Slice	无锁的支持增长的 Slice
freesync	Slice	并发安全的 Slice	与官方 slice+mutex 相比，写性能提升一半，读性能提升百倍左右
freesync	Bag	并发安全的容器	与 sync.Map 相比，写性能提升一半左右

麻烦各路大佬指点。如果能发现 bug 更好。

[rekulas]

检测测了下单线程比 slice 快 50%左右，并没有达到说的百倍
通过原子性牺牲便捷性和锁机制来提升性能，我是有点疑虑的，比如我在“决定”访问一个 freesync.slice 的时候，访问到的可能是我决定之后推过来的新值，或者我在写一个 slice 的时候，可能也有其他协程在更新它，可能不是用户期望的
另外没有泛型支持要用于生产还不如直接原生方便

[wencan]

@rekulas
1. freesync 为并发场景设计。
性能列描述的是本机 benchmark 测试的结果，benchmark 代码见 XXX_benchmark_test.go 文件。希望诸位朋友能够提供在各自的机器上执行的 benchmark 的输出。
2. 任何解决方案，都只可能适用于特定场景。
““决定”访问一个 freesync.slice 的时候”，这个需要在“决定”时对整个 slice 做一次快照，或者在“决定”时阻塞其它写操作；
“写一个 slice 的时候，可能也有其他协程在更新它，可能不是用户期望的”，如果是并发 Append ，互不影响；如果是 UpdateAt 不同的索引，互不影响；如果是 UpdateAt 同一索引，后面的更新会覆盖前面的更新——除非 CompareAndSwap 。但目前的实现不支持在指定位置 CompareAndSwap 。
3. 我喜欢“较新”的产品，不喜欢“太新”的产品。后面应该会支持泛型。

[lesismal]

sync.Map 主要用途 go 源码注释里有写的：
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a separate Mutex or RWMutex.

所以 OP 跟它比 Write 没什么意义，换成 mutex+map 后，我只简单跑了下我笔记本的 windows 环境，没多测，但是估计也不会有太好的结果：
BenchmarkBagWrite-16 3418212 347.2 ns/op 87 B/op 3 allocs/op
BenchmarkSyncMapWrite-16 5754406 219.8 ns/op 0 B/op 0 allocs/op


slice 的场景，append 应该是非常少于读写的吧，如果多余那八成是做队列用 list 更好了。
而一个普通的[]T ，在单纯的 get/set 语义下，不加锁时才是与 OP 的无锁 slice 等价，因为都只是 get/set 并不是需要处理额外的其他一组操作，所以 OP 的 BenchmarkMutexSlice_Load 这里给[]T 加锁是不公平的，去掉则也是劣势得多了：
BenchmarkMutexSlice_Load-16 12368889 96.06 ns/op 0 B/op 0 allocs/op
BenchmarkRWMutexSlice_Load-16 1000000000 0.07468 ns/op 0 B/op 0 allocs/op


原子操作能解决的问题场景太少了，现实场景绝大多数需要的是“原子性”对一组操作的保障，尤其是 go 这种逻辑并发流非常多的场景，无锁数据结构能发挥的场景点就更少了

[lesismal]

上一楼 slice get 的贴错行了，更正下：
BenchmarkSlice_Load-16 115303052 10.37 ns/op 0 B/op 0 allocs/op
BenchmarkMutexSlice_Load-16 1000000000 0.07651 ns/op 0 B/op 0 allocs/op

如我上一楼所说，BenchmarkMutexSlice_Load 是把 Lock/Unlock 去掉了的，这样才是公平的

[wencan]

@lesismal
多谢

我为 Bag 和 Slice 增加了新的 benchmark 测试用例：
bag 增加了和 sync.Map 、sync.Mutex+map 比纯 Add/Store ，和比 Add/Store + Delete 。
slice 增加了 LoadAndUpdate 。

下面这个，烦劳提供改动后的代码：
BenchmarkBagWrite-16 3418212 347.2 ns/op 87 B/op 3 allocs/op
BenchmarkSyncMapWrite-16 5754406 219.8 ns/op 0 B/op 0 allocs/op

slice 的 Load 问题，如果是纯 Load ，Load 时没有 Append 和 Update ，确实不需要加锁。
但如我上面所说：任何解决方案，都只可能适用于特定场景。freesync.Slice 考虑的是并发安全读写。原生 slice 不加锁进行纯 Load ，和 freesync.Slice 纯 Load ，两者没有可比性，如果真要比，我反倒觉得对 freesync.Slice 不公平。好比让飞机和汽车比在地上跑道比谁跑得快。

至于无锁数据结构，能发挥的场景较少。这个我承认。
写这些，主要原因是最近几个月没工作，家里闲着。
欢迎提供能发挥场景多的无锁数据结构需求。

最后，我这边 benchmark 测试的条件为：
goos: linux
goarch: amd64
cpu: AMD Ryzen 7 1800X Eight-Core Processor

[wencan]

@lesismal
还有 freesync.Bag 和 sync.Map 比 Write 的问题，
开发 freesync.Bag 的出发点，就是 sync.Map 对读多友好，写多稍逊。Bag 为并发写多的场景设计。

[lesismal]

> 下面这个，烦劳提供改动后的代码：

sync.Map 源码里注释我的理解主要是优化多读、多读写（估计主要是读多）的场景，所以多写的场景，可能 Mutex+map 就好了，这个场景用 sync.Map 实际上是性能下降的。我改动的也只是换成 Mux+map:

func BenchmarkSyncMapWrite(b *testing.B) {
var mux sync.Mutex
var mapping = map[int]int{}

ch := make(chan int, 10000000)

b.ResetTimer()
b.RunParallel(func(p *testing.PB) {
var i int
for p.Next() {
mux.Lock()
mapping[i] = i
mux.Unlock()
ch <- i

i++

delI := <-ch
mux.Lock()
delete(mapping, delI)
mux.Unlock()
}
})
}

[lesismal]

> slice 的 Load 问题，如果是纯 Load ，Load 时没有 Append 和 Update ，确实不需要加锁。
> 欢迎提供能发挥场景多的无锁数据结构需求。

我以前接触过的、自己能想到的并发无锁优化性能的场景暂时只有一个，无锁队列做生产者消费者。比如多 IO 线程把事件丢到队列里，每个队列单线程 eventloop 消费。
但这种生产消费模型，也是与锁、同步（包括唤醒）机制比如信号量条件量。
通常的原子性（一组操作）场景都是不能简单到只使用无锁数据结构实现的，而 go 的 chan 里已经是自带了同步唤醒机制，入队出队也都是它自带流程里处理了的，所以多数时候，直接使用 chan 也就够用了。

我在自己网络框架中，对每个 connection 事件的有序执行设计用到了个执行队列，但是是直接用的[]T+Mutex ，因为对于单个 connection ，并发竞争的概率极低，Lock/Unlock 的开销就也只是简单的原子操作，所以也没必要引入无锁数据结构，而且是需要先判断是否队首再看要不要 pop 的多步骤，简单的无锁 get/set 并不能满足需求：
https://github.com/lesismal/nbio/blob/master/conn.go#L82

无竞争时 Mutex 的开销：
https://github.com/golang/go/blob/master/src/sync/mutex.go#L83

[wencan]

@lesismal
如果是 bag 和 sync.Mutex+内置 map 的 benchmark 的比较，
根据我这边的的 benchmark 测试结构
只 add 的话，bag 会有几倍的优势
add+delete ，两者结构差不多
benchmark 代码见最新的提交

freesync/lockfree 也实现了一个单链表，bag 也用到了这个单链表，但是还要继续优化。

你的 nbio ，我好好学习下，再请教。
额外问下，nbio 是不是牛逼 io 的意思？

[wencan]

@lesismal
纠正下错别字

如果是 bag 和 sync.Mutex+内置 map 的 benchmark 的比较，
根据我这边的的 benchmark 测试结构
只 add 的话，bag 会有几倍的优势
add+delete ，两者结果差不多
benchmark 代码见最新的提交

[lesismal]

> 只 add 的话，bag 会有几倍的优势

要不先试试弄个并发消息队列试试能不能比 chan 性能提升？我不太确定，因为还要有唤醒机制，用 cond 的话，意义还是不太大，可能优势主要是代码比 chan 的逻辑简单

因为数据存起来主要就是为了拿出来用，所以只 add 的场景，我暂时还想不出来

开始写 go 后我一直忽略了 go 的无锁相关，觉得没用，闲了我也学习研究下你的实现。

> 额外问下，nbio 是不是牛逼 io 的意思？

主要是 non-blocking 的意思，早期版本 readme 里还真加过牛逼的意思，后来删掉了：
https://github.com/lesismal/nbio/commit/c5122cc157bf098a4354eb75773c672233fb41de
性能应该是不输于其他 poller 框架的（ evio/easygo/gnet/gev ）:
https://github.com/lesismal/go-net-benchmark/issues/1

但是功能、可定制扩展空间，比他们丰富太多了，所以也对得起牛逼这俩字了。

我还想支持 HTTP2.0/3.0 ，但是工程量有点大、时间和体力吃不消，如果有兴趣，业余时间可以一起玩玩

[lysS]

你对 atomic.Value 的理解完全是错误的，应该从内存角度来看。像这个 ut 就过不了

```golang
func Test_Concurrent(t *testing.T) {
var slice Slice
slice.Append(0)
slice.Append(1)
slice.Append(2)
slice.Append(3)

go func() {
time.Sleep(time.Second * 2)
slice.UpdateAt(3, 0)
time.Sleep(time.Second * 5)
}()

slice.Range(func(index int, p interface{}) (stopIteration bool) {
time.Sleep(time.Second)
require.Equal(t, index, p)
return false
})
}
```

我们说原子变量比锁快，是因为原子变量相当于颗粒度更小的锁，如果锁和原子变量颗粒度相同，那么是没有性能差别的。

[wencan]

@lysS 没理解你的意思
你的意思是，Range 应该在调用时，给整个结构体的数据，取一次快照，然后 Range 遍历的是快照的内容？？
目前 freesync.Slice 的 Range ，是每次调用 f 时，Load 值。
我试着把你那段代码里的 Slice ，换成 sync.Map ，两边输出结果是一样的。

[lysS]

@wencan 这和 range 无关，只是 range 更好测出来，atomic.Value 的使用是完全错误的。

[wencan]

@lysS 还请直言，具体的错误是什么

[tsotsi]

@lysS 你这个代码感觉逻辑上就不对
这个跑的 index=3 要 4 秒。
slice.Range(func(index int, p interface{}) (stopIteration bool) {
time.Sleep(time.Second)
require.Equal(t, index, p)
return false
})
这里 2 秒后就更新了
go func() {
time.Sleep(time.Second * 2)
slice.UpdateAt(3, 0)
time.Sleep(time.Second * 5)
}()

[lysS]

@tsotsi 有啥问题，就是为了测并发操作啊

[lysS]

@wencan 起码你不应该用 atomic.Value 存指针。对于 slice 的操作，你应该对其细化，比如 read1 的时候 updata2 这种就可以不用串行化。其实都类似于无锁队列一样，只是 slice 更复杂

[wencan]

@lysS “不应该用 atomic.Value 存指针”的原因？
我看官方文档并无此要求。

[tsotsi]

@lysS https://go.dev/play/p/JJOLXeCwKVa
所以 sync.Map 也有问题 ？

[lysS]

@tsotsi range 的时候读取是更新前的还是后的，这取决于设计（是整体的并发安全还是对元素的并发安全）。从这个角度来说我那个 ut 不太准确。

但还是那个结论。如果把竞争检测开启，我那个 ut 会有竞争、而你那个 sync.Map 不会有

[tsotsi]

@lysS 你的代码去掉也不行。哈
建议用我的
https://go.dev/play/p/qyHVGs36Hkn
@wencan

[lysS]

@tsotsi 去掉也不行什么意思？ 我那个是 ut 是证明 op 的那个库是并发不安全的

[wencan]

@lysS @tsotsi
我重新跑了 freesync.Slice 和 freesync.Bag 的全部 unit test 和 branchmark test ，全部输出符合预期，没检测到 data race 。

[tsotsi]

@wencan 我的。🤡了

[lysS]

@wencan 数据竞争是有的，只不过不容易测出来吧。
比如函数 func (slice *Slice) Append(p interface{}) int 中，在互斥锁之前会读 limitSlicesNum ，互斥锁之后会写 limitSlicesNum 。而且这两个是可以同时发生的。

[lysS]

话说你都加了互斥锁了，那个 slice 的 value 完全没必要用 atomic.Value 了

[lysS]

还有，我看你里面有自旋，这显然是不太好的

[lysS]

@wencan L19 最好不存指针大概是这种情况：

func Benchmark_Race(b *testing.B) {

var i int
var at atomic.Value = atomic.Value{}
at.Store(&i)

b.RunParallel(func(p *testing.PB) {
for p.Next() {
*(at.Load().(*int))++
}
})
}

[wencan]

lockfree.Slice 创建之后，limitSlicesNum 是只读
查了下，slice 的用 value 的地方，都存在并发读写的可能。不知道你说的具体是哪里的 value ？
at.Store(&i)里 &i 不就是地址吗？
@lysS

[lysS]

@wencan limitSlicesNum 在 grow 会被写啊，就是

https://github.com/wencan/freesync/blob/9000626a5e8936710ce6b512051a940c46733f99/slice.go#L24

https://github.com/wencan/freesync/blob/9000626a5e8936710ce6b512051a940c46733f99/slice.go#L50

并发时，会有竞争