最近討論到的二分搜尋法...

應該是直接在 Hacker News 上看到的東西,有人丟出一個二分搜尋法實做,宣稱比標準實做快不少:「Binary Search: A new implementation that is up to 25% faster (github.com)」。

實做的程式碼放在 GitHub 的「scandum/binary_search」這邊,讀了 source code 後可以看到一臉就要利用現代 CPU 預測平行化的能力加速 XDDD

另外看了 Hacker News 上的討論,這種寫法會透過 CPU 預測平行化的能力善用記憶體頻寬,這應該是測起來比較快的主因。

不過這只算是個開頭,丟出一些方向讓社群可以研究,實際上還是得看看負面影響的部份,像是比較舊的 CPU 會不會有很重的 penalty (overhead),以及其他類型 CPU 上的情況...

用 Raspberry Pi 4 與 HDMI-to-USB 組出 KVM over IP 裝置

一樣是在 Hacker News Daily 上看到的專案,弄出便宜的 KVM over IP 裝置:「TinyPilot: Build a KVM Over IP for Under $100」。

主要是他在 Twitter 看到了這則,裡面提到了「Video Capture Cards, HDMI to USB 2.0, High Definition 1080p 30fps, Video Record via DSLR,Camcorder, Action Cam for Live Broadcasting, Live Streaming, Gaming, Teaching, Video Conference」這個產品:

而作者在 eBay 上面也找到了一樣的裝置,但是更便宜 (所以是「親,$11 包郵」?XDDD):

接下來是在接觸 pikvm 的時候發現了 µStreamer 這個專案:

µStreamer is a lightweight and very quick server to stream MJPG video from any V4L2 device to the net.

最後則是發現他使用的 HDMI-to-USB 裝置直接就是輸出 MJPG 格式,連 transcoding 都不用做了,大幅把 latency 降到 200ms:

其實從作者的文章可以知道,你想做的事情說不定在地球上已經有其他人做差不多了,重點是要找出來,而不需要自己硬幹 XD

Mass Effect 的 3D 場景黑塊問題一路追到 Intel/AMD 的 SSE2 指令集...

Mass Effect 是個 2007 在 Xbox 上推出的遊戲,並且在 2008 推出 Windows 版,這個遊戲在 2011 年 AMD 推出的 CPU 上 (Bulldozer),某些場景會產生人物黑塊的 bug,社群有些猜測但一直都沒被證實,作者一路追出不少問題,並且給了一個還算乾淨的 workaround:「Fixing Mass Effect black blobs on modern AMD CPUs」,另外在 Hacker News 上有很精彩的討論:「Fixing Mass Effect black blobs on modern AMD CPUs (cookieplmonster.github.io)」。

這篇主要是看趣味的,裡面的狀況有點複雜。

社群有一些 workaround 可以避開這個問題,作者後來是從關閉 PSGP (Processor Specific Graphics Pipeline) 的方法找問題,然後發現在計算時會產生出 NaN 的問題,所以導致貼出來的圖就變成黑塊了...

一路追下去,發現遊戲本身好像沒什麼大問題,但跟 Direct3D 裡面的 D3DXMatrixInverse 有關,會依照 CPU 的支援度決定怎麼跑:

  • Disabling PSGP makes both Intel and AMD take a regular x86 code path.
  • Intel CPUs always take an intelsse2 code path.
  • AMD CPUs supporting 3DNow! take a amd_mmx_3dnow or amd3dnow_amdmmx code path, while CPUs without 3DNow take an intelsse2 code path.

會有這些邏輯是因為 AMD 在 2010 後決定放生 3DNow!,所以會需要這樣判斷。

接著寫了一隻小程式測試,用 memcmp() 判斷是不是一樣,結果發現 AMD 的 SSE2 跑出來的程式不被遊戲接受:(不一樣是正常的,因為這些指令本來就沒有要求完全正確,是可以接受誤差的)

接著就是翻資料,可以知道 XMMatrixInverse 算是接班人:

I figured that since we were to replace that matrix function anyway, I could try replacing it with XMMatrixInverse being a “modern” replacement for D3DXMatrixInverse. XMMatrixInverse also uses SSE2 instructions so it should be equally optimal to the D3DX function, but I was nearly sure it would break the same way.

所以就弄個一個 DLL,把本來呼叫 D3DXMatrixInverse 的部份用 XMMatrixInverse 改寫換掉:「SilentPatchME/source/D3DXMatrix.cpp」,這個方式算是乾淨的 workaround 掉,保持 API 相容性,以及該有的加速能力 (由 XMMatrixInverse 提供)。

Hacker News 上有討論到 Intel 與 AMD 這些指令在 SSE2 上的誤差值,都是在規格要求的範圍內:

Const-me 14 hours ago [–]

Here’s Intel versus AMD relative error of RCPPS instruction: http://const.me/tmp/vrcpps-errors-chart.png AMD is Ryzen 5 3600, Intel is Core i3 6157U.
Over the complete range of floats, AMD is more precise on average, 0.000078 versus 0.000095 relative error. However, Intel has 0.000300 maximum relative error, AMD 0.000315.

Both are well within the spec. The documentation says “maximum relative error for this approximation is less than 1.5*2^-12”, in human language that would be 3.6621E-4.

Source code that compares them by creating 16GB binary files with the complete range of floats: https://gist.github.com/Const-me/a6d36f70a3a77de00c61cf4f6c17c7ac

至於為什麼會生出 NaN 的原因,沒找出來還是有點可惜,不過這個解法還行,就是「新版的 library 既然沒問題,就大家也不要太計較舊版的問題」的概念...

Linus 狂幹 Intel 的 AVX-512

這幾天蠻熱鬧的消息,Linus 幹翻 Intel 丟出來的 AVX-512:「Alder Lake and AVX-512」。

在維基百科的「Advanced Vector Extensions」這邊有提到,因為 AVX-512 執行時會消耗產生更多的熱量,所以得壓低 Turbo Boost 執行:

Since AVX instructions are wider and generate more heat, Intel processors have provisions to reduce the Turbo Boost frequency limit when such instructions are being executed. The throttling is divided into three levels:

  • L0 (100%): The normal turbo boost limit.
  • L1 (~85%): The "AVX boost" limit. Soft-triggered by 256-bit "heavy" (floating-point unit: FP math and integer multiplication) instructions. Hard-triggered by "light" (all other) 512-bit instructions.
  • L2 (~60%): The "AVX-512 boost" limit. Soft-triggered by 512-bit heavy instructions.

本來 AVX 與 AVX-2 只會在某些重量級的指令時會壓 15%,現在在 AVX-512 則是變成常態,而且有些會降到 40%,對於同時在跑的應用會受到很大的影響,所以 Linus 也直接放話要用他的權限擋這件事情 (我把動詞讀錯了):

I want my power limits to be reached with regular integer code, not with some AVX512 power virus that takes away top frequency (because people ended up using it for memcpy!) and takes away cores (because those useless garbage units take up space).

在後面的討論串「Alder Lake and AVX-512」這邊 Linus 有提到更細,像是他對於 MMX/SSE/AVX/AVX2 的想法,以及為什麼他這麼厭惡 AVX-512。

AMD 的繼續看戲 XDDD

把 SSH Key 放進 Secure Enclave 裡保護

看到 Secretive 這個專案,是利用蘋果的 Secure Enclave 機制,把 SSH private key 放進去在裡面進行運算,避免 private key 檔案被惡意程式讀取就洩漏出去了。

從 Secure Enclave 的介紹頁面可以看到這個需要有 T1 或是 T2 晶片才有 Secure Enclave 功能:

Mac computers that contain the T1 chip or the Apple T2 Security Chip

而從 Apple Silicon 這邊可以看到 Apple T1 chip 是 2016 年後的機種引入的:

The Apple T1 chip is an ARMv7 SoC (derived from the processor in S2 SiP) from Apple driving the System Management Controller (SMC) and Touch ID sensor of the 2016 and 2017 MacBook Pro with Touch Bar.

然後對於沒有 Secure Enclave 的古董機,可以透過有支援 smart card 的硬體掛上去,像是 YubiKey

For Macs without Secure Enclaves, you can configure a Smart Card (such as a YubiKey) and use it for signing as well.

照著他講的建議去翻了「YubiKey Smart Card Deployment Guide」這邊的資料,看起來 YubiKey 在 4 系列之後就有產品支援 Smart Card 了,不過要注意純 U2F 的版本沒支援。

Intel 的 RDRAND 爆炸...

在正妹 wens 的 Facebook 上看到的,IntelRDRAND 因為有安全漏洞 (CrossTalk/SRBDS),新推出的修正使得 RDRAND 只有原來的 3% 效能:

從危機百科上看,大概是因為這個指令集有 compliance 的要求,所以這個安全性漏洞必須在安全性上修到乾淨,所以使用了暴力鎖硬解,造成效能掉這麼多:

The random number generator is compliant with security and cryptographic standards such as NIST SP 800-90A, FIPS 140-2, and ANSI X9.82.

不過畢竟這個指令不是常常被使用,一般使用者的影響應該是還好:

As explained in the earlier article, mitigating CrossTalk involves locking the entire memory bus before updating the staging buffer and unlocking it after the contents have been cleared. This locking and serialization now involved for those instructions is very brutal on the performance, but thankfully most real-world workloads shouldn't be making too much use of these instructions.

另外這個漏洞早在 2018 九月的時候就通報 Intel 提了,但最後花了超過一年半時間才更新,這算是當初在提 Bug Bounty 制度時可能的缺點,在這次算是比較明顯:

We disclosed an initial PoC (Proof-Of-Concept) showing the leakage of staging buffer content in September 2018, followed by a PoC implementing cross-core RDRAND/RDSEED leakage in July 2019. Following our reports, Intel acknowledged the vulnerabilities, rewarded CrossTalk with the Intel Bug Bounty (Side Channel) Program, and attributed the disclosure to our team with no other independent finders. Intel also requested an embargo until May 2020 (later extended), due to the difficulty of implementing a fix for the cross-core vulnerabilities identified in this paper.

回到原來的 bug,主要還是 Intel 架構上的問題造成大家打得很愉快,現在 Intel 這邊的架構對於資安研究員仍然是個大家熱愛的地方... (因為用的使用者太多)

Linux Kernel 5.7 釋出...

在「The New Features Of The Linux 5.7 Kernel: Tiger Lake Graphics Stable, New exFAT, Zstd F2FS, Performance」這邊有列出重點來。

其中把過熱保護機制也一起考慮進來,這樣可以避免過熱被強制降速而反而變非常慢:

Thermal pressure tracking for systems that are thermally overloaded for better task placement on CPU cores running hot.

另外一個是把 exFAT 驅動換成由 Samsung 維護的版本,照其他文章的說明,這個版本比較穩定...

The new exFAT file-system driver that replaces the exFAT driver in the staging area that had been around for a few releases. This new exFAT driver is in much better shape and actively maintained by Samsung.

主要還是過熱保護那段還蠻值得期待,不然就是要硬上水冷壓,避免遇到溫度牆...

Amazon EC2 推出 AMD 版本的 C5a 主機

前幾天 AWS 宣佈了使用 AMD CPU 的 c5a 主機:「New – Amazon EC2 C5a Instances Powered By 2nd Gen AMD EPYC™ Processors」。

定價上與其他 AWS 上 AMD 的機器都類似 (m5ar5a 以及 t3a),大約都低 10% 左右:

Today, I am excited to announce the general availability of compute-optimized C5a instances featuring 2nd Gen AMD EPYC™ processors, running at frequencies up to 3.3 GHz. C5a instances are variants of Amazon EC2’s compute-optimized (C5) instance family and provide high performance processing at 10% lower cost over comparable instances.

以這兩年 AMD 在 CPU 這塊碾壓 Intel 的情況來說 (AMD YES!),目前 AMD CPU 上唯一的缺點應該是單核的時脈比較低,這在捉機上的領域裡面來說,遇到一些沒有做好多核最佳化的遊戲時 Intel 的表現會比較好,其他的情況其實都可以看出 AMD 幹爆 Intel。

如果你在 AWS 上跑的應用程式也有類似需要吃單核效能,無法充分使用多核環境時,還是可以回頭看一下 c5 系列,頻率會高一些:

C5 and C5d instances feature either the 1st or 2nd generation Intel Xeon Platinum 8000 series processor (Skylake-SP or Cascade Lake) with a sustained all core Turbo CPU clock speed of up to 3.6 GHz. The new C5 and C5d 12xlarge, 24xlarge, and metal instance sizes feature the 2nd generation Intel Xeon Scalable Processors (Cascade Lake) with a sustained all-core Turbo CPU frequency of 3.6GHz.

說到這個,Linus 前陣子在發表 5.7-rc7 的時候也說換了 AMD 的 3970x,整個處理 kernel 編譯的速度是用倍數在改善:「Linux 5.7-rc7」:

In fact, the biggest excitement this week for me was just that I upgraded my main machine, and for the first time in about 15 years, my desktop isn't Intel-based. No, I didn't switch to ARM yet, but I'm now rocking an AMD Threadripper 3970x. My 'allmodconfig' test builds are now three times faster than they used to be, which doesn't matter so much right now during the calming down period, but I will most definitely notice the upgrade during the next merge window.

回到 AWS 這邊... 目前有提供的區域來說,歐美比較大的區域都在首發清單,台灣這邊比較常用的東京還沒有看到,不過公司在用的新加坡上了:

You can launch C5a instances today in eight sizes in the US East (N. Virginia), US East (Ohio), US West (Oregon), Europe (Ireland), Europe (Frankfurt), Asia Pacific (Sydney), and Asia Pacific (Singapore) Regions in On-Demand, Spot, and Reserved Instance or as part of a Savings Plan.

如果沒有什麼特別成本壓力的人,可以等一陣子看看有沒有其他人丟效能測試出來,看看 CPU 的計算能力是不是可以無痛換過去... (這邊是相較於 ARM 那邊)

Raspberry Pi 4 推出 8GB 版本

Raspberry Pi 宣佈了 8GB 版本:「8GB Raspberry Pi 4 on sale now at $75」。

除了記憶體變成 8GB 以外,也因為記憶體加大而需要更多電力,所以電供元件的部份也跟著改動,然後也提到 COVID-19 造成的延遲:

To supply the slightly higher peak currents required by the new memory package, James has shuffled the power supply components on the board, removing a switch-mode power supply from the right-hand side of the board next to the USB 2.0 sockets and adding a new switcher next to the USB-C power connnector. While this was a necessary change, it ended up costing us a three-month slip, as COVID-19 disrupted the supply of inductors from the Far East.

超過 4GB 的時候一定會檢視 32-bit 與 64-bit 環境的差異,所以就會發現,在預設的 kernel 因為使用 32-bit LPAE (ARM 上的 PAE),所以雖然是有機會可以使用到 8GB,但單一程式會有 3GB 限制:

Our default operating system image uses a 32-bit LPAE kernel and a 32-bit userland. This allows multiple processes to share all 8GB of memory, subject to the restriction that no single process can use more than 3GB.

目前如果想要原生支援 64-bit 環境的話,需要使用其他作業系統:

But power users, who want to be able to map all 8GB into the address space of a single process, need a 64-bit userland. There are plenty of options already out there, including Ubuntu and Gentoo.

不過另外官方也在測自家的 64-bit 版本,已經有 early beta 版本可以測試看看了 (話說 early beta 這個詞,可以解釋成 alpha 的品質...):

Not to be left out, today we’ve released an early beta of our own 64-bit operating system image. This contains the same set of applications and the same desktop environment that you’ll find in our regular 32-bit image, but built against the Debian arm64 port.

不過上面的 ChromiumFirefox 不完整支援硬體解壓影片的部份還是痛,四代的 CPU 在 YouTube 上是可以硬撐 1080p30 解碼,但畫面順暢度就不太行了,客廳還是用老 Mac Mini (2011 的版本) 來撐場...

Amazon EC2 的 M6g 系列正式推出了

先前提到 AWS 要在 EC2 上推出新的 ARM 架構主機 (參考「Amazon EC2 推出了新一代的 ARM 系統」這篇),最近正式推出了:「New – EC2 M6g Instances, powered by AWS Graviton2」。

當時的定價還沒出來,現在正式開賣後可以拉出來看了。

us-east-1 上 2 vCPU + 8GB RAM 這個級距的價錢出來,m5.large 是 USD$0.096/hour,m6g.large 是 USD$0.077/hour,低大約 20%,不過這是兩個不同的平台,只是抓一下感覺知道差距。

不過這個價差其實蠻有吸引力的,對於有支援 ARM 的應用程式,或是手上有 source code 的大型應用,可以測試看看效能有差多少,或是先等一下,這陣子應該就會有人初步測一些數字出來可以參考。

另外 AWS 有打算要出 C6gR6g 的計畫,算是在雲上面補齊 ARM 的戰線:

We are not going to stop at general purposes M6g instances, compute optimized C6g instances and memory optimized R6g instances are coming soon, stay tuned.

目前支援的區域不算多,不過幾個老區域都先上了:

Now it’s your turn to give it a try in one the following AWS Regions : US East (N. Virginia), US East (Ohio), US West (Oregon), Europe (Ireland), Europe (Frankfurt), and Asia Pacific (Tokyo).