幾天前，DeepMind推出了AlphaDev，直接把排序算法提速70%。

這一全新AI系統(tǒng)，便是基于下棋高手AlphaGo打造。

而這項研究恰恰激起了前谷歌研究人員Justine Tunney的興趣。

她表示，作為一名C語言庫的作者，我一直在尋找機會來策劃最好的東西。

一起看看Justine如何詳解DeepMind排序算法。

DeepMind排序算法

DeepMind的這一發(fā)現(xiàn)贏得了當之無愧的關(guān)注，但不幸的是，他們本可以更好地解釋AlphaDev。

接下來，從DeepMind發(fā)布的匯編代碼開始，該代碼將一個有三個項目的數(shù)組進行排序，從偽匯編翻譯成匯編：

我將這個函數(shù)命名為 move37() ，是因為DeepMind的博客文章，將其與AlphaGo下的令人震驚的「第37步」進行了比較。

在2016那場人機大戰(zhàn)中，AlphaGo下了一顆違反人類直覺的棋，一個簡單的肩沖，擊敗了傳奇圍棋選手李世石。

所以如果運行DeepMind代碼：

但是，在我看來這是一個錯誤。

我們給它的數(shù)組是{3,1,2}，但 move37() 將其排序為{2,1,3}。

DeepMind一定在欺騙我們，因為我不相信2在1之前。再來看看他們對LLVM libcxx所做的開源貢獻，這有望澄清一些事情：

所以 move37() 實際上不是一個排序函數(shù)，而是一個排序內(nèi)核，旨在用作 sort3() 函數(shù)的構(gòu)建塊。

如果論文和博客文章能提到這一點就好了，因為它讓我在最短的時間內(nèi)感到非常困惑。下面是更好的代碼版本，其中包括缺失的交換（swap）操作。

為了解釋為什么他們的代碼很重要，讓我們考慮一下這個算法在高層次上是如何工作的。當我第一次嘗試自己解決 sort3() 問題時，我想到了這個：

然后我查看了libcxx，發(fā)現(xiàn)它們也在做同樣的事情。上述代碼的問題是，編譯器并不善于優(yōu)化它。

如果你嘗試編譯上面的代碼，就會注意到你的編譯器插入了大量的分支指令。這就是DeepMind試圖通過LLVM貢獻來改進的地方。

然而，這些技術(shù)往往不太容易理解。

我實際上喜歡天真無邪的代碼，因為如果我們瞇起眼睛，可以看到一種模式，與DeepMind最先進的匯編代碼有相同的基本想法。

這個想法是這個問題本質(zhì)上歸結(jié)為3個比較和交換操作：

上面的代碼是之前排序網(wǎng)絡(luò)的最先進技術(shù)。現(xiàn)在，這就是DeepMind的新發(fā)現(xiàn)發(fā)揮作用的地方。他們發(fā)現(xiàn)有時上面的 mov 指令是不必要的。

如果你試著運行上面的代碼，你會發(fā)現(xiàn)不管有沒有被刪除的行，它都是100%正確的。

這行代碼看起來像是在做什么，但實際上什么也沒做。所以我并不驚訝這樣的事情會被計算機科學忽視幾十年。

現(xiàn)在也應(yīng)該更清楚AlphaDev是如何工作的。

DeepMind基本上構(gòu)建了一個人工智能，它可以擺弄匯編代碼，隨機刪除一些東西，看看它是否損壞。

我這么說并不是要否定AlphaDev的智能，因為如果我說我沒有做同樣的事情，那就是在撒謊。

上面的代碼中還有兩個 mov 指令，我們有可能將其刪除。通過使用ARM64指令集來做到這一點，它可以為類似的問題提供更小的代碼。

在這里，我們不需要任何指令來創(chuàng)建臨時變量：

Arm公司最近風頭正勁，我想上面的例子可以作為他們贏得名聲的證據(jù)。

Arm也是目前開源領(lǐng)域最好的公司之一。比如，他們的MbedTLS庫是我迄今為止見過的最被低估的瑰寶之一。

當我開始使用它時，我原本有這樣的計劃，即修改Arm的代碼，使之在x86硬件上更好地工作。

我編寫了所有這些精心設(shè)計的匯編優(yōu)化，使其與x86上的OpenSSL達到相同的性能。

MbedTLS是簡單、可移植、可破除的C代碼，因此對于任何想要一個不是Perl生成的匯編的加密庫的人來說，是個好消息。

我告訴了Arm公司的人我在做什么，他們并沒有覺得這是顛覆性的。

我希望有一天能找到時間做DeepMind做的事情，并在上游進行修改。Arm公司的優(yōu)化程序庫也是多產(chǎn)的，它在質(zhì)量上與雙轉(zhuǎn)換無懈可擊。

它對C庫對此特別感興趣，因為幾十年來，開源社區(qū)一直依靠Sun Microsystems在90年代初編寫的數(shù)學函數(shù)來維持生計。

Arm找到了一種改進其中幾個函數(shù)的方法，例如 pow(x,y) 。考慮到這是數(shù)學中最基本的運算之一，這是一件非常有影響力的事情。

比如，如果你在純軟件中使用Arm的解決方案在x86機器上實現(xiàn) pow(x,y) ，那么它將比英特爾的原生x87指令快5倍。

很幸運，DeepMind也加入了這個游戲，所以我冒昧地把他們的libcxx diff翻譯成可讀的C代碼。

這是我希望在論文和博客文章中看到的另一件事，因為在這段代碼中，你會發(fā)現(xiàn)專家們用來讓編譯器生成無分支 MOVcc 指令的規(guī)范技巧。

當我看到 Sort5() 函數(shù)，我覺得自己對DeepMind研究的動機有了更好的理解。

如果你在ARM64上編譯 Sort5() 函數(shù)，那么編譯器將產(chǎn)生一個處理11個寄存器的函數(shù)。如果你在推理一個數(shù)學方程，那么你能一次在你的工作記憶中保存11個變量嗎？

可能不會。這就是為什么有一個像 PartialSort3 這樣優(yōu)秀的內(nèi)核函數(shù)如此有用的原因。

值得一提的是， Sort3() 和 Sort5() 本身就是內(nèi)核，因為它們旨在成為傳統(tǒng)排序功能的構(gòu)建塊。

博客文章涵蓋了這個主題，但我認為分享一些實際上可移植和可執(zhí)行的東西會很有用。

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. 上面的算法顯示了新的和改進的libcxx正在做什么。它基本上是快速排序，除了在遞歸到更小的切片時切換到排序內(nèi)核和插入排序。對于libcxx，我認為他們甚至采取了在堆排序中移動的額外步驟，這有點慢，但可以防止對手破壞您的堆棧。

• 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: 在這一點上，你可能想知道的主要事情是，我可以使用這個嗎？這些排序網(wǎng)絡(luò)內(nèi)核真的能讓排序變得更快嗎？我會說是和不是。當你只想對升序長進行排序時，上面的代碼將比你的C庫提供的標準 qsort() 函數(shù)快2倍。只是你不需要內(nèi)核來做到這一點。到目前為止，我已經(jīng)確定，在我的個人電腦上（它有一個英特爾酷睿i9-12900KS），上面的函數(shù)以每秒255兆字節(jié)的速度排序。但是如果我注釋掉排序內(nèi)核：

• 

然后我的 longsort() 函數(shù)以每秒275兆字節(jié)的速度運行，通過簡化算法實現(xiàn)了7%的性能提升。

long 的好處是它足夠長，可以存儲 int 鍵值對，能夠快速對地圖條目進行排序是一個有用的技巧。

上面的函數(shù)編譯后只有181字節(jié)的x86-64機器代碼。

由于DeepMind的 sort3() 只有42字節(jié)，我希望可以交換一些大小以獲得性能優(yōu)勢。

因為到目前為止，我發(fā)現(xiàn)的下一個最佳算法是改用基數(shù)排序，速度為400 MB/s，但除了依賴于 malloc() 之外，還需要高達763字節(jié)的二進制占用空間。因此，如果能看到這些內(nèi)核做得更好就好了。

這并不是說DeepMind的想法沒有價值。

我認為值得注意的是，DeepMind非常慷慨，去年給了我們他們的矢量化快速排序庫（當時他們被稱為Google Brain），并通過這樣做實現(xiàn)了永遠無法挑戰(zhàn)的排序優(yōu)勢。

Vqsor在我的電腦上以1155 MB/s的速度對長時間進行排序。

它甚至略微優(yōu)于djbsor，后者是開源社區(qū)中最受歡迎的庫之一，盡管它從未推廣到比 int 更多的數(shù)據(jù)類型。

這兩種實現(xiàn)實現(xiàn)的方式都是通過矢量化排序網(wǎng)絡(luò)。我認為這就是排序網(wǎng)絡(luò)技術(shù)真正閃耀的地方。

我想，如果就智能實體而言，AlphaDev不是一個蹣跚學步的孩子，它就會這樣做。

當你從基本原則開始時，僅基線指令集就非常難以支持。如果我們等待，那么我認為我們可以期待在未來看到AlphaDev的偉大成就，因為它正在努力應(yīng)對更強大的挑戰(zhàn)。

我也很喜歡DeepMind讓算法變得更小的事實，因為這是我不常看到的。

大小編碼是我最喜歡的愛好之一。在這個博客上，我發(fā)布了一個383字節(jié)的lambda演算虛擬機和一個436字節(jié)的帶有垃圾回收機制的lisp機。

我還在博客上介紹了我在cosmpolitan c庫中使用的大小優(yōu)化技巧。

我也喜歡DeepMind的母公司，因為幾周前Google給我頒發(fā)了開源同行獎金，很高興看到他們分享我使軟件變小的熱情。

很高興看到他們用它來改進矢量化快速排序。

最后，我喜歡人工智能公司用機器語言編寫代碼的機器的想法。他們?yōu)槭裁床荒兀繖C器的本質(zhì)就是機器。

作為一個建設(shè)者，我發(fā)現(xiàn)這比OpenAI正在創(chuàng)造的未來要少得多。

他們已經(jīng)建立了一個巨大的家長式機器，在零和經(jīng)濟中與地球上的每個建設(shè)者競爭，然后誘使世界上的尋租者通過政府監(jiān)管來控制這臺機器。

我不認為OpenAI承諾將所有我最喜歡做的任務(wù)（如編碼）自動化是一種進步。我想要的是能夠控制一臺機器，這臺機器能夠完成我自己無法完成的事情，比如發(fā)現(xiàn)排序內(nèi)核。這才是真正的進步。

我認為，我們能夠砍掉的每一條裝配線都是朝著這個夢想的積極方向邁出的一步。