排序算法提速70%，C语言库作者详解最新AI

2023/6/21 14:07:08 主编：孟泽

Alpha家族的新成员最近引起了广泛的关注和讨论。 一位曾在谷歌工作的研究员解释了最新研究。

日前，上线，直接将排序算法提速70%。

这个新的人工智能系统是基于国际象棋大师的。

这项研究激起了前谷歌研究人员的兴趣。

“作为一名 C 库作者，我一直在寻找机会来策划最好的东西，”她说。

我们来看看如何详细解释排序算法。

排序算法

研究人员的发现引起了当之无愧的关注，但不幸的是，它们本可以得到更好的解释。

接下来，从发布的汇编代码开始，该代码对包含三个项目的数组进行排序，从伪汇编转换为汇编：

我将这个函数命名为 () 是因为我的博客文章将它与下面令人震惊的“步骤 37”进行了比较。

在2016年的人机大战中，他下了一局违背人类直觉的棋局，一个简单的肩拳，打败了围棋传奇高手李世石。

所以如果你运行代码：

然而，在我看来，这是一个错误。

我们给它的数组是{3,1,2}，但是()将它排序为{2,1,3}。

一定是在欺骗我们，因为我不相信 2 在 1 之前出现。让我们再看看他们对 LLVM 的开源贡献，希望能澄清一些事情：

so() 实际上并不是一个排序函数，而是一个排序内核，旨在用作 sort3() 函数的构建块。

如果论文和博客文章能提到这一点那就太好了，因为它在最短的时间内让我震惊了。 下面是代码的更好版本，其中包括缺少的交换操作。

为了解释为什么他们的代码很重要，让我们考虑一下该算法如何在高层次上工作。 当我第一次尝试自己解决 sort3() 问题时，我想到了这个：

然后我查了一下，发现他们也在做同样的事情。 上面代码的问题是编译器不太擅长优化它。

如果您尝试编译上面的代码，您会注意到编译器插入了很多分支指令。 这是尝试通过 LLVM 贡献进行改进的地方。

然而，这些技术往往没有被很好地理解。

我实际上喜欢无辜的代码，因为如果我们眯起眼睛，我们可以看到一个与最先进的汇编代码具有相同基本思想的模式。

这个问题本质上可以归结为 3 个比较和交换操作：

上面的代码是以前最先进的排序网络。 现在，这就是新发现发挥作用的地方。 他们发现有时上面的 mov 指令是不必要的。

如果您尝试运行上面的代码，您会发现无论是否删除行，它都是 100% 正确的。

这行代码看起来像是在做某事，实际上什么也没做。 因此，几十年来计算机科学都忽略了这样的事情，我并不感到惊讶。

现在也应该更清楚这是如何运作的。

基本上构建了一个人工智能，可以摆弄汇编代码，随机删除某些内容，并查看它是否损坏。

我这么说并不是为了否定智力，因为如果我说我没有这样做，那我就是在撒谎。

上面的代码中还有两条 mov 指令，我们可以将其删除。 它通过使用 ARM64 指令集来实现这一点，该指令集允许使用更小的代码来解决类似的问题。

在这里，我们不需要任何指令来创建临时变量：

Arm 最近备受瞩目，我认为上面的例子足以证明他们是名副其实的。

Arm 也是目前开源领域最好的公司之一。 就像，他们的图书馆是我迄今为止见过的最被低估的瑰宝之一。

当我开始使用它时，我原本打算修改Arm代码，以便更好地在x86硬件上工作。

我编写了所有这些精心设计的汇编优化，以实现与 x86 上相同的性能。

是简单、可移植、可破解的 C 代码，对于任何想要一个不是 Perl 生成的程序集的加密库的人来说是个好消息。

我告诉 Arm 的人百思特网我在做什么，他们并不认为这具有破坏性。

我希望有一天能找到时间做我所做的事情并在上游做出改变。 Arm的优化库也很丰富，而且双转换的质量无可挑剔。

它对 C 库特别感兴趣，因为几十年来开源社区一直依赖 Sun 在 90 年代初编写的数学函数为生。

Arm 找到了一种改进其中几个函数的方法，例如 pow(x,y) 。 考虑到这是数学中最基本的运算之一，这是一件非常有影响力的事情。

例如，如果使用Arm的纯软件解决方案在x86机器上实现pow(x,y)，它将比Intel原生x87指令快5倍。

幸运的是，我也参与其中，所以我冒昧地将他们的差异翻译成可读的 C 代码。

这是我希望在论文和博客文章中看到的另一件事，因为在这段代码中，您将找到专家用来让编译器生成无分支 MOVcc 指令的规范技巧。

当我看到 Sort5() 函数时，我觉得我对研究的动机有了更好的理解。

如果在 ARM64 上编译 Sort5() 函数，编译器将生成一个处理 11 个寄存器的函数。 如果您正在推理一个数学方程，您的工作记忆中可以同时保存 11百思特网 个变量吗？

可能不会。 这就是为什么拥有像这样的优秀内核函数如此有用。

值得一提的是，Sort3() 和 Sort5() 本身就是内核，因为它们旨在成为传统排序功能的构建块。

这篇博客文章涵盖了这个主题，但我认为分享一些实际上可移植和可执行的东西会很有用。

上面显示了 new 正在做什么。 这是它到 并排序时进入 。 我认为他们甚至采取了 in 的附加步骤，这有点慢，但来自你的堆栈。 上面的算法显示了新的算法和正在进行的改进。 它基本上是快速排序，只是在递归到更小的切片时切换到排序内核和插入排序。 因为，我认为他们甚至采取了移动堆排序的额外步骤，这有点慢但可以防止对手破坏你的堆栈。

此时你可能最关心的是，我可以使用这个吗？ 这些行吗？ 我会说是和否。 当您只想对 long 进行排序时，上面的代码将比您的 C 的 qsort () 快 2 倍。 你不需要这样做。 我到目前为止的情况是，在我的（它有一个 Intel Core i9-）上，上面的多头排序为 255 per。 如果我退出 : 在这一点上，您可能想知道的主要问题是，我可以使用它吗？ 这些排序网络内核真的能让排序更快吗？ 我会说是和不是。 当您只想按升序长序排序时，上面的代码将比 C 库提供的标准 qsort() 函数快 2 倍。 只是您不需要内核即可执行此操作。 到目前为止，我已经确定在我的 PC（具有 Intel Core i9-）上，上述函数以每秒 255 兆字节的速度排序。 但是如果我注释掉排序内核：

然后 my() 函数以每秒 275 兆字节的速度运行，与简化算法相比，性能提高了 7%。

long 的好处是它的长度足以存储 int 键值对，能够快速对 map 条目进行排序是一个有用的技巧。

上面的函数编译成只有 181 字节的 x86-64 机器代码。

由于 sort3() 只有 42 字节，我希望用一些大小来换取性能优势。

因为到目前为止我发现的下一个最佳算法是使用基数排序，它的速度要快 400 MB/s，但除了依赖 () 之外，还需要高达 763 字节的二进制占用空间。 因此，很高兴看到这些核心做得更好。

这并不是说想法没有价值。

我认为值得注意的是，去年非常慷慨地给了我们他们的矢量化快速排序库（当时他们被称为 Br百思特网ain），并通过这样做实现了永远无法挑战的排序优势。

Vqsor 在我的计算机上以 1155 MB/s 的速度对长期运行进行排序。

它甚至稍微优于开源社区中最受欢迎的库之一，尽管它从未推广到比 int 更多的数据类型。

这两种实现都是通过矢量化排序网络来实现的。 我认为这就是网络排序技术真正的亮点。

我认为，如果它不是一个具有智能实体的幼儿，它就会做到这一点。

当你从基础开始时，仅靠基线指令集是很难支持的。 如果我们等待，那么我认为我们可以期待在未来看到更大的成就，因为它会应对更严峻的挑战。

我还喜欢算法变得更小，因为这是我不经常看到的。

尺寸编码是我最喜欢的爱好之一。 在这个博客上，我发布了一个 383 字节的微积分虚拟机和一个带有垃圾收集功能的 436 字节的 lisp 机器。

我还在博客中介绍了我在 c 库中使用的大小优化技巧。

我也喜欢母公司，因为几周前授予了我开源同行资助，很高兴看到他们分享我对缩小软件规模的热情。

很高兴看到他们使用它来改进矢量化快速排序。

最后，我喜欢人工智能公司用机器语言编写机器的想法。 他们为什么不呢？ 机器的本质就是机器。

作为一名建设者，我发现这远远小于正在创造的未来。

他们建造了一个巨大的家长式机器，在零和经济中与地球上的每一个建筑商竞争，然后引诱世界各地的寻租者通过政府监管来控制这台机器。

我不认为自动化所有我最喜欢的任务（例如编码）的承诺是进步。 我想要的是能够控制一台机器，它可以做我自己做不到的事情，比如发现排序内核。 这是真正的进步。

我认为我们能够削减的每一条装配线都是朝着这个梦想的积极方向迈出的一步。

参考：