Golang Go语言中实现了一套基于lockfree的并发安全的数据结构
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 更好。
Golang Go语言中实现了一套基于lockfree的并发安全的数据结构
更多关于Golang Go语言中实现了一套基于lockfree的并发安全的数据结构的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html
检测测了下单线程比 slice 快 50%左右，并没有达到说的百倍
通过原子性牺牲便捷性和锁机制来提升性能，我是有点疑虑的，比如我在“决定”访问一个 freesync.slice 的时候，访问到的可能是我决定之后推过来的新值，或者我在写一个 slice 的时候，可能也有其他协程在更新它，可能不是用户期望的
另外没有泛型支持要用于生产还不如直接原生方便
更多关于Golang Go语言中实现了一套基于lockfree的并发安全的数据结构的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html
1. freesync 为并发场景设计。
性能列描述的是本机 benchmark 测试的结果，benchmark 代码见 XXX_benchmark_test.go 文件。希望诸位朋友能够提供在各自的机器上执行的 benchmark 的输出。
2. 任何解决方案，都只可能适用于特定场景。
““决定”访问一个 freesync.slice 的时候”，这个需要在“决定”时对整个 slice 做一次快照，或者在“决定”时阻塞其它写操作；
“写一个 slice 的时候，可能也有其他协程在更新它，可能不是用户期望的”，如果是并发 Append ，互不影响；如果是 UpdateAt 不同的索引，互不影响；如果是 UpdateAt 同一索引，后面的更新会覆盖前面的更新——除非 CompareAndSwap 。但目前的实现不支持在指定位置 CompareAndSwap 。
3. 我喜欢“较新”的产品，不喜欢“太新”的产品。后面应该会支持泛型。
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 这种逻辑并发流非常多的场景，无锁数据结构能发挥的场景点就更少了
上一楼 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 去掉了的，这样才是公平的
多谢
我为 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
还有 freesync.Bag 和 sync.Map 比 Write 的问题，
开发 freesync.Bag 的出发点，就是 sync.Map 对读多友好，写多稍逊。Bag 为并发写多的场景设计。
> 下面这个，烦劳提供改动后的代码：
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()
}
})
}
> 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
如果是 bag 和 sync.Mutex+内置 map 的 benchmark 的比较，
根据我这边的的 benchmark 测试结构
只 add 的话，bag 会有几倍的优势
add+delete ，两者结构差不多
benchmark 代码见最新的提交
freesync/lockfree 也实现了一个单链表，bag 也用到了这个单链表，但是还要继续优化。
你的 nbio ，我好好学习下，再请教。
额外问下，nbio 是不是牛逼 io 的意思？
纠正下错别字
如果是 bag 和 sync.Mutex+内置 map 的 benchmark 的比较，
根据我这边的的 benchmark 测试结构
只 add 的话，bag 会有几倍的优势
add+delete ，两者结果差不多
benchmark 代码见最新的提交
> 只 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 ，但是工程量有点大、时间和体力吃不消，如果有兴趣，业余时间可以一起玩玩
你对 atomic.Value 的理解完全是错误的，应该从内存角度来看。像这个 ut 就过不了golang<br>func Test_Concurrent(t *testing.T) {<br> var slice Slice<br> slice.Append(0)<br> slice.Append(1)<br> slice.Append(2)<br> slice.Append(3)<br><br> go func() {<br> time.Sleep(time.Second * 2)<br> slice.UpdateAt(3, 0)<br> time.Sleep(time.Second * 5)<br> }()<br><br> slice.Range(func(index int, p interface{}) (stopIteration bool) {<br> time.Sleep(time.Second)<br> require.Equal(t, index, p)<br> return false<br> })<br>}<br>
我们说原子变量比锁快，是因为原子变量相当于颗粒度更小的锁，如果锁和原子变量颗粒度相同，那么是没有性能差别的。
没理解你的意思
你的意思是，Range 应该在调用时，给整个结构体的数据，取一次快照，然后 Range 遍历的是快照的内容？？
目前 freesync.Slice 的 Range ，是每次调用 f 时，Load 值。
我试着把你那段代码里的 Slice ，换成 sync.Map ，两边输出结果是一样的。
你这个代码感觉逻辑上就不对
这个跑的 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)
}()
我重新跑了 freesync.Slice 和 freesync.Bag 的全部 unit test 和 branchmark test ，全部输出符合预期，没检测到 data race 。
数据竞争是有的，只不过不容易测出来吧。
比如函数 func (slice *Slice) Append(p interface{}) int 中，在互斥锁之前会读 limitSlicesNum ，互斥锁之后会写 limitSlicesNum 。而且这两个是可以同时发生的。
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))++
}
})
}
lockfree.Slice 创建之后，limitSlicesNum 是只读
查了下，slice 的用 value 的地方，都存在并发读写的可能。不知道你说的具体是哪里的 value ？
at.Store(&i)里 &i 不就是地址吗？
在Go语言中，实现基于lock-free（无锁）的并发安全数据结构是一项挑战但极具价值的工作。Lock-free算法能够减少传统锁机制带来的开销，提升系统的吞吐量和响应速度，尤其在多核处理器环境下效果显著。
Go语言本身提供了强大的并发编程支持，通过goroutine和channel机制，可以轻松实现并发任务。但要实现lock-free数据结构，通常需要使用到原子操作（atomic operations）来确保数据一致性和线程安全。
Go语言的sync/atomic包提供了一系列底层的原子操作，比如原子加载（Load）、原子存储（Store）、原子交换（Swap）、原子比较并交换（CompareAndSwap）以及原子加减（Add、Sub）等。这些操作是lock-free数据结构实现的基础。
常见的lock-free数据结构包括无锁队列（Lock-Free Queue）、无锁链表（Lock-Free Linked List）等。这些数据结构的设计和实现需要深入理解并发编程的原理和算法，以及Go语言的特性。
值得注意的是，虽然lock-free数据结构在性能上有显著优势，但它们的实现往往更加复杂，且在某些情况下可能引发更难调试的并发错误。因此，在选择是否使用lock-free数据结构时，需要权衡其带来的性能提升和实现的复杂性。
总之，Go语言提供了实现lock-free并发安全数据结构所需的工具和机制，但实现这些数据结构需要深入的专业知识和丰富的实践经验。
