关于在协程框架中加入有界队列的讨论

[chloro-pn]

有界队列是一个比较常用的基础组件，有必要在协程框架中提供支持，目前有三种选择：

1. 依靠基础组件condition_variable和mutex / spinlock + stl容器实现，这种实现的特点：读写共同竞争一把锁，实现简洁、对元素类型的限制小（允许构造过程中抛出异常）、但是性能不是很高，不适合性能敏感场景。
2. 依靠基础组件Semaphore + 无锁队列，这种实现由于无锁队列本身支持线程安全的读写，Semaphore的作用主要是必要时避免轮询，而是将协程挂在Semaphore上，实现特点：采用两个Semaphore分别用于同步读和写，因此相当于读竞争一把锁、写竞争一把锁，性能可能会比第一种高，但是对元素类型有限制（基本上无锁队列都会要求元素类型的构造是noexcept的），而且由于Semaphore本身的同步开销相比于无锁队列的cas开销要大（纯猜测，欢迎纠正。比如folly的实现，即使同步操作不导致挂起协程，也要创建一个新的Lazy并且有一些额外的原子操作），我的疑问是Semaphore本身的同步开销是否导致无锁队列的性能优势被抹平了，即这种实现相比于第一种是否有必要。
3. 直接使用无锁队列，出现轮询意味着性能or资源到达瓶颈，应该由应用层处理。

我个人的建议是使用1+3分别应对性能敏感和性能不敏感场景。我想知道本库将会考虑哪种实现策略。

[ChuanqiXu9]

我对有界队列的使用场景不太熟悉。但看上去使用协程 condition_variable 等组件看上去并不太好。所谓协程性能好的假设是我们可以将等IO/等阻塞所浪费的计算资源充分利用起来，但调度本身还是要消耗资源的，同时对队列做更改的操作成本应该没那么高。所以很难想象使用协程 condition_variable 等组件会什么场景下比直接的无锁队列实现要好。

不过把有界队列这样的数据结构和协程结合起来的价值应该还是有的，例如可以将有界队列封装为 AsyncGenerator，这样在取值和添加值时都可以避免阻塞，易用性也高不少。可惜目前 async_simple 还不支持 AsyncGenerator。

[chloro-pn]

所以很难想象使用协程 condition_variable 等组件会什么场景下比直接的无锁队列实现要好。

直接的无锁队列实现指的是上述第二种实现还是第三种实现呢。
如果是第二种实现，其实协程版本的Semaphore的开销不比 condition_variable小，async_simple的Semaphore就是基于condition_variable实现的，folly的我没细看，但是类似于condition_variable（因为从语义上需要线程安全的挂起、回复协程的操作，实现都是原子操作+wait_list）。而相比于直接的无锁队列读写的开销应该要大不少（因为直接的无锁队列读写只需要读线程or写线程对某个原子变量进行CAS（在非轮询的情况下），而condition_variable和Semaphore涉及的操作就多多了）。
如果是第三种实现，基于锁的有界队列与无锁队列的应用场景不完全重合，即无锁队列并不总是可以替代基于锁的有界队列，因为很多场景下写比读快，而用户只是想挂起协程/线程，而不是轮询。

[ChuanqiXu9]

我指的是第三种。我想的是在有界队列未满/未到临界值时，使用无锁队列的实现写入/读出，在到底临界值时，使用协程框架进行调度。

甚至在无锁队列轮询时间过长时还可以主动 yield。

[ChuanqiXu9]

有可能我说的和你说的第二种是一回事；

关于性能，使用协程框架进行调度毫无疑问是有成本的，导致这种方案单纯的读写性能肯定是不如无锁队列的。它的优势是可以把计算资源及时尽早分配出去吧，例如某些任务执行时间过长对于整个系统来说就不是好事。提高某些热点任务 latenccy 换取整个系统 qps 的增加应该是很常见的思路。

当然对我来说有些纸上谈兵了，我遇到使用协程异步化提高性能的场景主要还是 IO 密集场景中通过快速切换提高并发度来提高所谓的性能。而上面描述的这种多核竞争计算资源的场景能不能用协程框架来解决我到没实际经验。我感觉希望协程调度框架能解决这种问题的理想假设是 “我们可以通过将短时间内对热点资源密集的访问分摊到长时间内对这些资源稀疏的访问从而减少竞争带来的效率损耗”。但我不确定满足这种假设的场景有多少。

当然了，如果想贡献这种 patch，肯定也是欢迎的。

[chloro-pn]

emmm，感觉这种思路和其他方案相比是有独特的优势的，等有需求场景再来实现吧，虚空打靶不太好。

[RainMark]

感觉队列和协程是正交的。用户基于协程cv + 现有的各种非block队列即可实现协程阻塞式的队列。如果咱们直接实现了某一种感觉用户不一定会选择

[chloro-pn]

emmm概念上确实是正交的，但是就像go的channel在goroutine中的地位一样 ，不同协程间需要通信的场景其实很多，并且侧重点不一样的话对Queue的要求也不一样。
这要看async_simple是要做小而精的库还是大而全的库了。我感觉各种c++20协程库最后还是要拼生态，毕竟不同的协程库的协程组织模型不一样，executor目前也还没统一，很难无缝相互调用的，小而精的协程库可能会比较尴尬。
当然，这只是讨论，我会先自己实现一个Queue用的。

[ChuanqiXu9]

是的，有现成的 Helper 的话，其实对用户来说会比较方便。抽象层设计得好的话也不会对现有代码和用户造成影响。

[RainMark]

嗯，你可以先按你需求实现queue来用着，如果后续比较合适的话咱们可以搞一个专门放这些组件的目录？然后逐步实现合入各种组件

[RainMark]

最简单的话，自己实现可以直接bounded-mpmc-queue + enqueue/dequeue 失败重试策略 + cv
重试策略或许可以缓解高负载情况下cv频繁挂起恢复带来的开销