Category: Library

Intel 用 AVX-512 加速 NumPy 的排序演算法被整合進主線了

Intel 用 AVX-512 加速 NumPy 排序的實做被整合進主線了：「「Intel Publishes Blazing Fast AVX-512 Sorting Library, Numpy Switching To It For 10~17x Faster Sorts」」。

GitHub 的 PR 在「ENH: Vectorize quicksort for 16-bit and 64-bit dtype using AVX512 #22315」這邊，可以看到相關的留言：

This patch adds AVX512 based 64-bit on AVX512-SKX and 16-bit sorting on AVX512-ICL. All the AVX512 sorting code has been reformatted as a separate header files and put in a separate folder. The AVX512 64-bit sorting is nearly 10x faster and AVX512 16-bit sorting is nearly 16x faster when compared to std::sort. Still working on running NumPy benchmarks to get exact benchmark numbers

16-bit int sped up by 17x and float64 by nearly 10x for random arrays. Benchmarked on a 11th Gen Tigerlake i7-1165G7.

有點「有趣」的情況是，AVX-512 在新的 Intel 消費級 CPU 被拔掉了，只有伺服器工作站的 CPU 有保留。而 AMD 的 Zen 4 則是跳下去支援 AVX-512...

另外在「Intel Publishes Fast AVX-512 Sorting Library, 10~17x Faster Sorts in NumPy (phoronix.com)」這邊當然也有人提到，如果用更廣泛的 AVX2 (寬度是 256bits) 加速的話應該也會有很大的進步才對？幾乎這十年的 CPU 都有 AVX2 了... 不過看起來沒有什麼深入的討論？

jQuery 3.6.2

看到 jQuery 出新版的消息：「jQuery 3.6.2 Released!」。

這個版本的說明裡面針對了 :has() 這個功能著墨，主要還是因為這功能 jQuery 支援很久了，而 Chromium 與 Safai 在最近都開始支援了：「Issue 669058: CSS selectors Level 4: support :has()」、「Using :has() as a CSS Parent Selector and much more」。

不過看起來 jQuery 要整合原生的 :has() 還是有技術困難，因為裡面可能會包括 jQuery 自己定義的 selector extension：

That was problematic in cases where :has() contained another jQuery selector extension (e.g. :has(:contains("Item"))) or contained itself (:has(div:has(a))).

總之，難得又看到 jQuery 的消息... 前一版的 3.6.1 是 2022/08/26，而 3.6.0 則是再一年多前的 2021/03/02，再往前面是 3.5.1 的 2020/05/04 與 3.5.0 的 2020/04/10。

是個歷史...

calloc() 與 malloc() 的差異

前陣子在 Hacker News Daily 上看到的，原文是 2016 的文章：「Why does calloc exist?」，裡面講的東西包括了 implementation dependent 的項目，所以要注意一下他的結論未必適用於所有的平台與情境。

malloc() 與 calloc() 的用法是這樣，其中 calloc() 會申請 count 個 size 的空間：

void* buffer1 = malloc(size);
void* buffer2 = calloc(count, size);

第一個差異是，count * size 可能會 overflow (而 integer overflow 在 C 裡面是 undefined behavior)，這點除非你在乘法時有檢查，不然大多數的行為都還是會生一個值出來。

而 calloc() 則是會幫你檢查，如果會發生 overflow 的時候就不會真的去要一塊記憶體用。

第二個差異是 calloc() 保證會將內容都設定為 0，這點在 POSIX 的標準裡面是這樣寫的：

The calloc() function shall allocate unused space for an array of nelem elements each of whose size in bytes is elsize. The space shall be initialized to all bits 0.

但作者就發現 malloc() + memset() + free() 還是比 calloc() + free() 慢很多：

~$ gcc calloc-1GiB-demo.c -o calloc-1GiB-demo
~$ ./calloc-1GiB-demo
calloc+free 1 GiB: 3.44 ms
malloc+memset+free 1 GiB: 365.00 ms

研究發現是 calloc() 用了 copy-on-write 的技巧，先把所有的 page 都指到同一塊完全被塞 0 的記憶體，只有在真的寫到該段記憶體時，系統才會要一塊空間來用：

Instead, it fakes it, using virtual memory: it takes a single 4 KiB page of memory that is already full of zeros (which it keeps around for just this purpose), and maps 1 GiB / 4 KiB = 262144 copy-on-write copies of it into our process's address space. So the first time we actually write to each of those 262144 pages, then at that point the kernel has to go and find a real page of RAM, write zeros to it, and then quickly swap it in place of the "virtual" page that was there before. But this happens lazily, on a page-by-page basis.

但畢竟這是 implementation dependent，看看有個印象就好。

AOM-AV1 v3.5.0 的效能改善

在翻資料的時候翻到「Google Releases AOM-AV1 3.5 With More Speedups & Memory Optimizations」這篇，講 AOM-AV1 v3.5.0 的效能改善，看了 v3.4.0 的 changelog 可以看到最主要的大幫助是有 multithreading 的支援，但不確定跟其他的 AV1 library 相比可以有多快...

印象中 (好幾個月前的印象) 目前最快的應該是 SVT-AV1？記得 dav1d 有宣稱很快但不是 apple-to-apple 比較，比較像是 marketing 上的宣稱。

先前測試 AV1 在 Android 上的支援度與效能，記得在老一點的手機上軟解還是很辛苦啊，最後還是先選了 VP9 用，硬體解碼支援度比較廣，加上軟解需要的 CPU resource 也低不少。

OpenSSL 3.0 RCE

OpenSSL 居然出了一包 RCE：「CVE-2022-3786 and CVE-2022-3602: X.509 Email Address Buffer Overflows」，security advisory 在「OpenSSL Security Advisory [01 November 2022]」這邊。

看第一個 CVE-2022-3602，本來看到這個 CVE 號碼為覺得應該是年初的號碼 (現在已經三萬多了？)，但依照官方的說法是十月的事情，看起來是用假名回報 (Polar Bear)：

This issue was reported to OpenSSL on 17th October 2022 by Polar Bear.
The fixes were developed by Dr Paul Dale.

在 CVE 的頁面上也可以看到「Date Record Created」這邊標的是 20221019，不知道是什麼情況。

另外一組 CVE-2022-3786 也是類似的情況，官方收到也是十月的事情：

This issue was discovered on 18th October 2022 by Viktor Dukhovni while
researching CVE-2022-3602. The fixes were developed by Dr Paul Dale.

在 CVE 頁面上則是標 20221101 建立，昨天的事情。

這次出事的範圍是 3.0.0 系列的 OpenSSL，前面的 1.1 與 1.0 系列是沒中的：

[T]he bugs were introduced as part of punycode decoding functionality (currently only used for processing email address name constraints in X.509 certificates). This code was first introduced in OpenSSL 3.0.0. OpenSSL 1.0.2, 1.1.1 and other earlier versions are not affected.

Ubuntu 上中的是 22.04 的 jammy 以及之後的版本，包括了 22.10 的 kinetic。還在用 20.04 的基本上都還是 1.1 系列的 OpenSSL 在跑，這次沒被貓到。

Python 上的 reals 套件 (需要 3.10+ 以上才能裝)

看到「A lightweight python3 library for arithmetic with real numbers.」這個有趣的 Python 延伸套件，可以用他進行高精度的實數運算...

一開始在 Python 3.9 環境裝，結果就跳出需要 3.10+ 的環境，想了一下，開了一個 Docker container 裝 pyenv 來測，測過以後覺得還蠻有趣的，看起來之後把預設環境變成 3.10+ 應該會裝起來用...

這個 reals 的重點在於保證顯示數字的正確性：

It allows you to compute approximations to an arbitrary degree of precision, and, contrary to most other libraries, guarantees that all digits it displays are correct.

目前支援的常數與操作有這些：

Constants: pi, e, phi
Functions related to powers: sqrt, exp, log
Operators: negation, addition, subtraction, multiplication, division, powers
Trigonometric functions: sin, sinh, csc, csch, cos, cosh, sec, sech, tan, tanh, cot, coth

用法的部份，先把 reals 拉進來：

>>> from reals import sqrt

然後用法算直覺：

>>> sqrt2 = sqrt(2)
>>> sqrt2
<reals._real.Real object at 0x10d182560 (approximate value: 1.41421)>
>>> sqrt2.evaluate(10)
'1.4142135624'
>>> '{:.10f}'.format(sqrt2)
'1.4142135624'
>>> sqrt2.to_decimal(10)
Decimal('1.4142135624')

不過作者有提到效能沒有處理到很好，所以應該是拿來快速做一些運算得到結果而已。

JavaScript 上的 fuzzy search library

在 Hacker News Daily 上看到 Show HN (作者自己或是主要的 contributor 上來發表的作品) 給了一個號稱速度很快，吃資源很少的 fuzzy search library：「Show HN: uFuzzy.js – A tiny, efficient fuzzy search that doesn't suck (github.com/leeoniya)」。

這種已經發展許久，但突然有一天有人說他的東西超好超棒棒的，除非是有新的基礎演算法突破，不然馬上就會想到很經典的「Three circles model」，中間的那些區塊就懶的畫上去了：

依照他的「測試」，可以看到他宣稱完全領先的狀態：

但回過頭來看評論：

Thank you for this!

I am also quite frustrated with the current state of full text search in the javascript world. All libs I've tried miss the most basic examples and their community seems to ignore it. Will give yours a try but it already looks much better from the comparison page.

Edit: Nope, your lib doesn't seem to handle substitution well (THE most common type of typo), so yep, we are back to square one ...

From fuzzy search I expected that entering "super meet boy" or "super maet boy" will return "Super Meat Boy" but unfortunately currently it doesn't work this way and it's quite disappointing.

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

看起來這個 library 沒有辦法解決 fuzzy search 最常見的 case (小 typo)，依照範例描述的更像是 substring 搜尋加上一些額外的的功能，反而比較像是 auto completion library，或是講的比較廣一點，可以算是 auto suggestion library。

不過我覺得真正的重點 (對我來說的重點) 是下面的比較表格，因為列出了目前市場上的方案，這份清單之後可以拿來參考...

cURL 的 TLS fingerprint

看到「curl's TLS fingerprint」這篇，cURL 的作者 Daniel Stenberg 提到 TLS fingerprint。

先前在「修正 Curl 的 TLS handshake，避開 bot 偵測機制」與「curl 的 TLS fingerprint 偽裝專案 curl-impersonate 支援 Chrome 了」這邊有提到 curl-impersonate 這個專案，試著在 cURL 裡模擬市面上常見的瀏覽器的 TLS fingerprint。

在 Daniel Stenberg 的文章裡面也有提到這件事情，另外也提到了對 curl-impersonate 的態度：

I cannot say right now if any of the changes done for curl-impersonate will get merged into the upstream curl project, but it will also depend on what users want and how the use of TLS fingerprinting spread or changes going forward.

看起來短期內他是沒打算整，跟當初 curl-impersonate 的預期差不多...

這次 OpenSSL 的兩個 CVE

難得在 Hacker News 首頁上看到 OpenSSL 的 CVE：「OpenSSL Security Advisory [5 July 2022]」，相關的討論在「OpenSSL Security Advisory (openssl.org)」。

第一個 CVE 是 RCE 等級，但觸發條件有點多：

首先是 RSA 2048bits，這個條件應該算容易發生的。

第二個是，因為這個安全問題是因為 OpenSSL 3.0.4 才引入的程式碼，而 OpenSSL 3.0.4 是 2022/06/21 發表的，未必有很多人有升級。

第三個是，因為這次出包的段落是用到了 AVX-512 指令集，一定要 Intel 或是 Centaur 的 CPU，後面這家公司前身就是威盛 (VIA) 的一員，去年賣給了 Intel (然後發現連官網用的 domain 都沒續約...)。

而 AMD 雖然在 Zen 4 架構上支援 AVX-512，但還沒推出產品，所以直接閃避 XD

另外第三個還有額外的限制，因為這次用到的是 IFMA 指令集，所以也不是所有有支援 AVX-512 的 CPU 都會中獎：

只看 Intel 的部份，第一個支援 IFMA 的是 2018 年推出的 Cannon Lake，這個架構只有一顆行動版的 Intel® Core™ i3-8121U Processor。

真正大量支援 IFMA 的是 2019 後的 Intel CPU 了，但到了去年推出的 Alder Lake 因為 E-core 不支援 AVX-512 的關係 (但 P-core 支援)，預設又關掉了。

所以如果問這個 bug 嚴不嚴重，當然是很嚴重，但影響範圍就有點微妙了。

接下來講第二個 CVE，是 AES OCB 的實做問題，比較有趣的地方是 Hacker News 上的討論引出了 Mosh 的作者跳出來說明，他居然提到他們在二月的時候試著換到 OpenSSL 的 AES OCB 時有測出這個 bug，被 test case 擋下來了：

Mosh uses AES-OCB (and has since 2011), and we found this bug when we tried to switch over to the OpenSSL implementation (away from our own ocb.cc taken from the original authors) and Launchpad ran it through our CI testsuite as part of the Mosh dev PPA build for i686 Ubuntu. (It wasn't caught by GitHub Actions because it only happens on 32-bit x86.) https://github.com/mobile-shell/mosh/issues/1174 for more.

So I would say (a) OCB is widely used, at least by the ~million Mosh users on various platforms, and (b) this episode somewhat reinforces my (perhaps overweight already) paranoia about depending on other people's code or the blast radius of even well-meaning pull requests. (We really wanted to switch over to the OpenSSL implementation rather than shipping our own, in part because ours was depending on some OpenSSL AES primitives that OpenSSL recently deprecated for external users.)

Maybe one lesson here is that many people believe in the benefits of unit tests for their own code, but we're not as thorough or experienced in writing acceptance tests for our dependencies.

Mosh got lucky this time that we had pretty good tests that exercised the library enough to find this bug, and we run them as part of the package build, but it's not that farfetched to imagine that we might have users on a platform that we don't build a package for (and therefore don't run our testsuite on).

這有點有趣 XDDD

Perl 的 Regular Expression 的強度：NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目，就像是維基百科上的條列：

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇，裡面試著用 Perl 的 regular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。

Recursive descent parser 可以當作是 CFG 的子集合，而 CFG 對應到的語言是 CFL，另外他對應到的自動機是 PDA。

我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern)，所以他能接受的 language 已經超過 RL，但我很好奇他能夠做到什麼程度。

用搜尋引擎翻了翻，查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library)：「Which languages do Perl-compatible regular expressions recognize?」。

在裡面有人提到「The true power of regular expressions」這篇文章，裡面給了一個在 PTIME 演算法，將 3SAT 轉換到 PCRE 裡解，這證明了 PCRE 是 NP-hard；另外也很容易確認 PCRE 是 NP，所以就達成了 NP-complete 的條件了...

本來一直以為 PCRE 只是 CFG/CFL/PDA 而已，沒想到這麼強，NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD