限时15秒！精彩的酒店宣传广告！

<随心_句子c><随心_句子c><随心_句子c><随心_句子c><随心_句子c>AlphaDev將(jiang)排(pai)序(xu)算(suan)法(fa)提(ti)速(su)70%！C語(yu)言(yan)庫(ku)作(zuo)者(zhe)壹(yi)文(wen)詳(xiang)解(jie)DeepMind最(zui)新(xin)AI

新智(zhi)元(yuan)報(bao)道(dao)

編(bian)輯(ji)：桃(tao)子(zi)

【新智元導(dao)讀(du)】阿(e)爾(er)法家(jia)族(zu)新成(cheng)員(yuan)AlphaDev近(jin)來(lai)引(yin)發(fa)不(bu)少(shao)關(guan)註(zhu)與(yu)討(tao)論(lun)。一位(wei)曾(zeng)在(zai)谷(gu)歌(ge)工(gong)作的(de)研(yan)究(jiu)人(ren)员對(dui)這(zhe)項(xiang)最新研究進(jin)行(xing)了(le)详解。

幾(ji)天(tian)前(qian)，DeepMind推(tui)出(chu)了AlphaDev，直(zhi)接(jie)把(ba)排序算法提速70%。

这一全(quan)新AI系(xi)統(tong)，便(bian)是(shi)基(ji)於(yu)下(xia)棋(qi)高(gao)手(shou)AlphaGo打(da)造(zao)。

而(er)这项研究恰(qia)恰激(ji)起(qi)了前谷歌研究人员Justine Tunney的興(xing)趣(qu)。

她(ta)表(biao)示(shi)，作為(wei)一名(ming)C语言库的作者，我(wo)一直在尋(xun)找(zhao)機(ji)會(hui)来策(ce)劃(hua)最好(hao)的東(dong)西(xi)。

一起看(kan)看Justine如(ru)何(he)详解DeepMind排序算法。

DeepMind排序算法

DeepMind的这一发現(xian)贏(ying)得(de)了當(dang)之(zhi)無(wu)愧(kui)的关注，但(dan)不幸(xing)的是，他(ta)們(men)本(ben)可(ke)以(yi)更(geng)好地(di)解釋(shi)AlphaDev。

接下来，從(cong)DeepMind发布(bu)的匯(hui)编代(dai)碼(ma)開(kai)始(shi)，該(gai)代码将一個(ge)有(you)三(san)个项目(mu)的數(shu)組(zu)进行排序，从偽(wei)汇编翻(fan)譯(yi)成汇编：

我将这个函(han)数命(ming)名为 move37 ，是因(yin)为DeepMind的博(bo)客(ke)文章(zhang)，将其(qi)与AlphaGo下的令(ling)人震(zhen)驚(jing)的「第(di)37步(bu)」进行了比(bi)較(jiao)。

在2016那(na)場(chang)人机大(da)戰(zhan)中(zhong)，AlphaGo下了一顆(ke)違(wei)反(fan)人類(lei)直覺(jiao)的棋，一个簡(jian)單(dan)的肩(jian)沖(chong)，擊(ji)敗(bai)了傳(chuan)奇(qi)圍(wei)棋選(xuan)手李(li)世(shi)石(shi)。

所(suo)以如果(guo)運(yun)行DeepMind代码：

但是，在我看来这是一个錯(cuo)誤(wu)。

我们給(gei)它(ta)的数组是{3,1,2}，但 move37 将其排序为{2,1,3}。

DeepMind一定(ding)在欺(qi)騙(pian)我们，因为我不相(xiang)信(xin)2在1之前。再(zai)来看看他们对LLVM libcxx所做(zuo)的开源(yuan)貢(gong)獻(xian)，这有望(wang)澄(cheng)清(qing)一些(xie)事(shi)情(qing)：

所以 move37 實(shi)際(ji)上(shang)不是一个排序函数，而是一个排序內(nei)核(he)，旨(zhi)在用(yong)作 sort3 函数的構(gou)建(jian)塊(kuai)。

如果论文和(he)博客文章能(neng)提到(dao)这一點(dian)就(jiu)好了，因为它讓(rang)我在最短(duan)的時(shi)間(jian)内感(gan)到非(fei)常(chang)困(kun)惑(huo)。下面(mian)是更好的代码版(ban)本，其中包(bao)括(kuo)缺(que)失(shi)的交(jiao)換(huan)（swap）操(cao)作。

为了解释为什(shen)麽(me)他们的代码很(hen)重(zhong)要(yao)，让我们考(kao)慮(lv)一下这个算法在高層(ceng)次(ci)上是如何工作的。当我第一次嘗(chang)試(shi)自(zi)己(ji)解決(jue) sort3 問(wen)題(ti)时，我想(xiang)到了这个：

然(ran)後(hou)我查(zha)看了libcxx，发现它们也(ye)在做同(tong)樣(yang)的事情。上述(shu)代码的问题是，编译器(qi)並(bing)不善(shan)于優(you)化(hua)它。

如果妳(ni)尝试编译上面的代码，就会注意(yi)到你的编译器插(cha)入(ru)了大量(liang)的分(fen)支(zhi)指(zhi)令。这就是DeepMind试圖(tu)通(tong)過(guo)LLVM贡献来改(gai)进的地方(fang)。

然而，这些技(ji)術(shu)往(wang)往不太(tai)容(rong)易(yi)理(li)解。

我实际上喜(xi)歡(huan)天真(zhen)无邪(xie)的代码，因为如果我们瞇(mi)起眼(yan)睛(jing)，可以看到一種(zhong)模(mo)式(shi)，与DeepMind最先(xian)进的汇编代码有相同的基本想法。

这个想法是这个问题本質(zhi)上歸(gui)結(jie)为3个比较和交换操作：

上面的代码是之前排序網(wang)絡(luo)的最先进技术。现在，这就是DeepMind的新发现发揮(hui)作用的地方。他们发现有时上面的 mov 指令是不必(bi)要的。

如果你试著(zhe)运行上面的代码，你会发现不管(guan)有沒(mei)有被(bei)刪(shan)除(chu)的行，它都(dou)是100%正(zheng)確(que)的。

这行代码看起来像(xiang)是在做什么，但实际上什么也没做。所以我并不惊訝(ya)这样的事情会被計(ji)算机科(ke)學(xue)忽(hu)視(shi)几十(shi)年(nian)。

现在也應(ying)该更清楚(chu)AlphaDev是如何工作的。

DeepMind基本上构建了一个人工智能，它可以擺(bai)弄(nong)汇编代码，隨(sui)机删除一些东西，看看它是否(fou)損(sun)壞(huai)。

我这么說(shuo)并不是要否定AlphaDev的智能，因为如果我说我没有做同样的事情，那就是在撒(sa)謊(huang)。

上面的代码中還(hai)有兩(liang)个 mov 指令，我们有可能将其删除。通过使(shi)用ARM64指令集(ji)来做到这一点，它可以为类似(si)的问题提供(gong)更小(xiao)的代码。

在这裏(li)，我们不需(xu)要任(ren)何指令来創(chuang)建臨(lin)时變(bian)量：

Arm公(gong)司(si)最近風(feng)頭(tou)正勁(jin)，我想上面的例(li)子可以作为他们赢得名聲(sheng)的證(zheng)據(ju)。

Arm也是目前开源領(ling)域(yu)最好的公司之一。比如，他们的MbedTLS库是我迄(qi)今(jin)为止(zhi)見(jian)过的最被低(di)估(gu)的瑰(gui)寶(bao)之一。

当我开始使用它时，我原(yuan)本有这样的计划，即(ji)修(xiu)改Arm的代码，使之在x86硬(ying)件(jian)上更好地工作。

我编寫(xie)了所有这些精(jing)心(xin)設(she)计的汇编优化，使其与x86上的OpenSSL達(da)到相同的性(xing)能。

MbedTLS是简单、可移(yi)植(zhi)、可破(po)解的C代码，因此(ci)对于任何想要一个不是Perl生(sheng)成的汇编的加(jia)密(mi)库的人来说，是个好消(xiao)息(xi)。

我告(gao)訴(su)了Arm公司的人我在做什么，他们并没有觉得这是顛(dian)覆(fu)性的。

我希(xi)望有一天能找到时间做DeepMind做的事情，并在上遊(you)进行修改。Arm公司的优化程(cheng)序库也是多(duo)產(chan)的，它在质量上与雙(shuang)轉(zhuan)换无懈(xie)可击。

它对C库对此特(te)別(bie)感兴趣，因为几十年来，开源社(she)區(qu)一直依(yi)靠(kao)Sun Microsystems在90年代初(chu)编写的数学函数来維(wei)持(chi)生计。

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

比如，如果你在純(chun)軟(ruan)件中使用Arm的解决方案(an)在x86机器上实现 pow(x,y) ，那么它将比英(ying)特尔的原生x87指令快(kuai)5倍(bei)。

很幸运，DeepMind也加入了这个游戲(xi)，所以我冒(mao)昧(mei)地把他们的libcxx diff翻译成可读的C代码。

这是我希望在论文和博客文章中看到的另(ling)一件事，因为在这段(duan)代码中，你会发现專(zhuan)家们用来让编译器生成无分支 MOVcc 指令的規(gui)範(fan)技巧(qiao)。

当我看到 Sort5 函数，我觉得自己对DeepMind研究的動(dong)机有了更好的理解。

如果你在ARM64上编译 Sort5 函数，那么编译器将产生一个處(chu)理11个寄(ji)存(cun)器的函数。如果你在推理一个数学方程，那么你能一次在你的工作記(ji)憶(yi)中保(bao)存11个变量嗎(ma)？

可能不会。这就是为什么有一个像 PartialSort3 这样优秀(xiu)的内核函数如此有用的原因。

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

博客文章涵(han)蓋(gai)了这个主(zhu)题，但我認(ren)为分享(xiang)一些实际上可移植和可執(zhi)行的东西会很有用。

The above algorithm shows what the new and improved libcxx is doing. It's basically quicksort except it switches to the sorting kernels and insertion sort when recursing into smaller slices. With libcxx I think they even took the added step of schlepping in heapsort, which is kind of slow, but prevents adversaries from smashing your stack. 上面的算法顯(xian)示了新的和改进的libcxx正在做什么。它基本上是快速排序，除了在遞(di)归到更小的切(qie)片(pian)时切换到排序内核和插入排序。对于libcxx，我认为他们甚(shen)至(zhi)采(cai)取(qu)了在堆(dui)排序中移动的額(e)外(wai)步驟(zhou)，这有点慢(man)，但可以防(fang)止对手破坏您(nin)的堆棧(zhan)。

The main thing you may be wondering at this point is, can I use this? Do these sorting network kernels actually make sorting go faster? I would say yes and no. When all you want is to sort ascending longs, the code above will go 2x faster than the standard qsort function provided by your C library. Except you don't need the kernels to do that. What I've determined so far is that, on my personal computer (which has an Intel Core i9-12900KS) the above function sorts longs at 255 megabytes per second. However if I comment out the sorting kernels: 在这一点上，你可能想知(zhi)道的主要事情是，我可以使用这个吗？这些排序网络内核真的能让排序变得更快吗？我会说是和不是。当你只(zhi)想对升(sheng)序長(chang)进行排序时，上面的代码将比你的C库提供的標(biao)準(zhun) qsort 函数快2倍。只是你不需要内核来做到这一点。到目前为止，我已(yi)經(jing)确定，在我的个人電(dian)腦(nao)上（它有一个英特尔酷(ku)睿(rui)i9-12900KS），上面的函数以每(mei)秒(miao)255兆(zhao)字(zi)節(jie)的速度(du)排序。但是如果我注释掉(diao)排序内核：

然后我的 longsort 函数以每秒275兆字节的速度运行，通过简化算法实现了7%的性能提升。

long 的好处是它足(zu)夠(gou)长，可以存儲(chu) int 鍵(jian)值对，能够快速对地图條(tiao)目进行排序是一个有用的技巧。

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

由(you)于DeepMind的 sort3 只有42字节，我希望可以交换一些大小以獲(huo)得性能优勢(shi)。

因为到目前为止，我发现的下一个最佳(jia)算法是改用基数排序，速度为400 MB/s，但除了依賴(lai)于 malloc 之外，还需要高达763字节的二(er)进制(zhi)占(zhan)用空(kong)间。因此，如果能看到这些内核做得更好就好了。

这并不是说DeepMind的想法没有價(jia)值。

我认为值得注意的是，DeepMind非常慷(kang)慨(kai)，去(qu)年给了我们他们的矢(shi)量化快速排序库（当时他们被稱(cheng)为Google Brain），并通过这样做实现了永(yong)遠(yuan)无法挑(tiao)战的排序优势。

Vqsor在我的电脑上以1155 MB/s的速度对长时间进行排序。

它甚至略(lve)微(wei)优于djbsor，后者是开源社区中最受(shou)欢迎(ying)的库之一，盡(jin)管它从未(wei)推廣(guang)到比 int 更多的数据类型(xing)。

这两种实现实现的方式都是通过矢量化排序网络。我认为这就是排序网络技术真正閃(shan)耀(yao)的地方。

我想，如果就智能实體(ti)而言，AlphaDev不是一个蹣(pan)跚(shan)学步的孩(hai)子，它就会这样做。

当你从基本原則(ze)开始时，僅(jin)基線(xian)指令集就非常難(nan)以支持。如果我们等(deng)待(dai)，那么我认为我们可以期(qi)待在未来看到AlphaDev的偉(wei)大成就，因为它正在努(nu)力应对更強(qiang)大的挑战。

我也很喜欢DeepMind让算法变得更小的事实，因为这是我不常看到的。

大小编码是我最喜欢的愛(ai)好之一。在这个博客上，我发布了一个383字节的lambda演(yan)算虛(xu)擬(ni)机和一个436字节的帶(dai)有垃(la)圾(ji)回(hui)收(shou)机制的lisp机。

我还在博客上介(jie)紹(shao)了我在cosmpolitan c库中使用的大小优化技巧。

我也喜欢DeepMind的母(mu)公司，因为几周(zhou)前Google给我頒(ban)发了开源同行獎(jiang)金(jin)，很高兴看到他们分享我使软件变小的熱(re)情。

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

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

作为一个建设者，我发现这比OpenAI正在创造的未来要少得多。

他们已经建立(li)了一个巨(ju)大的家长式机器，在零(ling)和经濟(ji)中与地球(qiu)上的每个建设者競(jing)爭(zheng)，然后誘(you)使世界(jie)上的寻租(zu)者通过政(zheng)府(fu)監(jian)管来控(kong)制这臺(tai)机器。

我不认为OpenAI承(cheng)諾(nuo)将所有我最喜欢做的任務(wu)（如编码）自动化是一种进步。我想要的是能够控制一台机器，这台机器能够完(wan)成我自己无法完成的事情，比如发现排序内核。这才(cai)是真正的进步。

我认为，我们能够砍(kan)掉的每一条裝(zhuang)配(pei)线都是朝(chao)着这个夢(meng)想的積(ji)極(ji)方向(xiang)邁(mai)出的一步。

參(can)考資(zi)料(liao)：

https://justine.lol/sorting/返(fan)回搜(sou)狐(hu)，查看更多

責(ze)任编辑：