AlphaDev 將排序算法提速 70%，C 語言庫作者一文詳解 DeepMind 最新 AI

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

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

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

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

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

DeepMind 排序算法

DeepMind 的這一發(fā)現(xià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ù)，而是一個排序內核，旨在用作 sort3 () 函數(shù)的構建塊。

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

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

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

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

然而，這些技術往往不太容易理解。

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

這個想法是這個問題本質上歸結為 3 個比較和交換操作：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我希望有一天能找到時間做 DeepMind 做的事情，并在上游進行修改。Arm 公司的優(yōu)化程序庫也是多產(chǎ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)秀的內核函數(shù)如此有用的原因。

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

博客文章涵蓋了這個主題，但我認為分享一些實際上可移植和可執(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 正在做什么。它基本上是快速排序，除了在遞歸到更小的切片時切換到排序內核和插入排序。對于 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)絡內核真的能讓排序變得更快嗎？我會說是和不是。當你只想對升序長進行排序時，上面的代碼將比你的 C 庫提供的標準 qsort () 函數(shù)快 2 倍。只是你不需要內核來做到這一點。到目前為止，我已經(jīng)確定，在我的個人電腦上（它有一個英特爾酷睿 i9-12900KS），上面的函數(shù)以每秒 255 兆字節(jié)的速度排序。但是如果我注釋掉排序內核：

然后我的 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é)的二進制占用空間。因此，如果能看到這些內核做得更好就好了。

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

我認為值得注意的是，DeepMind 非?？犊ツ杲o了我們他們的矢量化快速排序庫（當時他們被稱為 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)絡。我認為這就是排序網(wǎng)絡技術真正閃耀的地方。

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

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

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

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

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

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

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

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

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

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

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

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

參考資料：

• https://justine.lol/sorting/

本文來自微信公眾號：新智元 （ID：AI_era）

廣告聲明：文內含有的對外跳轉鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時間，結果僅供參考，IT之家所有文章均包含本聲明。