无等待是不够的

原文地址 ，译文链接，译者：许巧辉，校对：周可人

无等待是不够的

以目前针对演进条件(progress condition，注：参考[1])的算法和数据结构的分类来看，是不足以区分不同演进条件的能力和每一个演进条件的性能/延迟。

我们提出了一种新的“大O”记号来表示无等待的算法和数据结构。下面是它的工作原理：

一个算法或功能被称为“Wait-Free O(x)“，表示需要最多O(x)操作完成。

一些示例：

a)”Wait-Free O(NThreads)“表示：一个算法，扫描每个活动线程的状态 b)”Wait-Free O(ln NThreads)“表示：一个算法，需要自身插入到活动的线程（使用二分法）的排序列表 c)”Wait-Free O(NThreads^2)“表示：一个算法，扫描活动线程的每个状态平方次数 d)”Wait-Free O(1)“表示：一个算法，做3次操作，不论活动线程和其他变量数目 e)”Wait-Free O(N)“表示：一个算法，获取确定数值N，比如一个数列当前元素的数量N，并且做了O(N)操作 f)”Wait-Free O(N^2)“表示：一个算法，获取确定数值N，并且做了O(N^2)操作

根据当前表示法，示例a)、b)和c)都是”Wait-Free Bounded”，但示例b)显然比c)或a)更好。

根据当前表示法，示例d)、e)和f)都是”Wait-Free Population Oblivious”，崦示例d)显然比e)或f)更好

也许更有意思的是，示例b)可能比示例f)更好。特别地，如果N NThreads，即使b)是”Bounded”而f)是”Population Oblivious”，它只是用来显示”Wait-Free Population Oblivious”未必比”Wait-Free Bounded”更好。

无锁如何？

那么，在这个新的表示法中，无锁也可以写成”Wait-Free O(infinity)”形式，但要注意的是，尽管所有的无锁算法都有一个最坏情况O(infinity)，它们大多数都有一个预计的操作数O(1)或O(N)，并且不依赖于线程的数量。

再比方说：

一个链表，对于contains()方法是无等待（Wait-Free）的，但这永远不会比”Wait-Free O(N_elements)”更好（N_elements是在某个时刻contains()操作时，链表中元素的数量）

匹配新旧之间的分类：

ChatGPT 时代：阅读会不会被取代？ 在这AI 盛行的时代不禁会有人发出疑问，读书对我们来说还有价值吗？笔者对此进行了解答并对 2022 年读过的书籍进行了总结和分类，希望能对大家有一定的借鉴意义
慢SQL是如何拖垮数据库的 本文结合一个实际故障案例出发，从小白的视角分析慢SQL是如何打垮数据库并引发故障的。
【数据结构算法篇】链表面试必刷题1——反转链表 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
【MySQL笔记】数字类型、时间和日期类型、字符串类型 在数据库中，经常需要存储一些数字，适合用数字类型来保存。数字类型包括整数类型、浮点数类型、定点数类型、BIT（位）类型。
深入Spring配置项问题，全面解析 本文就Spring配置项解析问题展开分析，这其中涉及到bean定义注册表后置处理、bean工厂后置处理、工厂bean等Spring相关的概念。本文将以上述问题作为切入点，进行分析和展开介绍。
NestJS系列（1）：初识 NestJS 和 Hello,world 本文介绍了使用 @nest/cli 脚手架快速创建和启动一个 Nest 应用，随后又对“Hello, World”示例代码做了分析，简单介绍了一些 TypeSscript 语法，比如装饰器，和一些 Nest 的概念。相信看到这里，大家基本上了解了 Nest 应用接收到用户请求后，走了哪些流程，完成了响应。
对话框、模态框和弹出框看起来很相似，它们有何不同？ 由于一个新的 popover 属性正在被提出，所以这篇文章将探讨对话框(dialogs)、弹出窗口(popovers)、叠加层(overlays)和揭示小部件(disclosure widgets)之间的区别。
玩转AIGC，5分钟 Serverless 部署 Stable Diffustion 服务 双重奖品设置，完成体验场景可得社区1000 积分兑换奖品，还可参加 AI 生成图像比赛赢取 Airpods、500 元猫超卡及社区定制抱枕！