幹壞事是進步最大的原動力
前幾天的 Hacker News Daily 上看到的東西，是由 Bloomberg 開發出來的工具 Memray，這個工具是一個 Python 套件：
Memray is a memory profiler for Python. It can track memory allocations in Python code, in native extension modules, and in the Python interpreter itself.
套件有多種輸出，其中一種是可以產生出記憶體使用情況的 flamegraph，轉成圖檔後像是這樣：
官方支援 Python 3.7+：
Memray requires Python 3.7+ and can be easily installed using most common Python packaging tools.
用法看起來也很簡單，之後如果有需要看 memory footprint 的情況好像可以拿來用看看...
在 Hacker News 首頁上看到的消息，Golang 將會把 sort.Sort() 換成 pdqsort (Pattern-defeating Quicksort)：「Go will use pdqsort in next release (github.com/golang)」，對應的 commit 則是在「sort: use pdqsort」這邊可以看到。
然後另外是「Changing std:sort at Google’s scale and beyond (danlark.org)」這邊提到了，LLVM 將 libc++ 的 std::sort 從 Quicksort 換成 BlockQuicksort。另外在文章裡面有提到一段 Knuth 老大在 TAOCP 裡講 sorting algorithm 沒有霸主的情況：
It would be nice if only one or two of the sorting methods would dominate all of the others, regardless of application or the computer being used. But in fact, each method has its own peculiar virtues. […] Thus we find that nearly all of the algorithms deserve to be remembered, since there are some applications in which they turn out to be best.
先回到 pdqsort 的部份，pdqsort 作者的 GitHub 上 (orlp/pdqsort) 可以看到他對 pdqsort 的說明：
Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on inputs with certain patterns.
看名字也可以知道 pdqsort 是從 Quicksort 改良的版本，而依照 Golang 的 commit 上的測試，與 Quicksort 相比，少數情況下會慢一點點，大多數的情況下會快一些，而在特殊情境下會讓 worst case 下降。
Golang 選擇把 unstable 的 Quicksort 換成 pdqsort，LLVM 則是選擇把 Quicksort 換成 BlockQuicksort，這邊看起來有些分歧...
反倒是各個程式語言對於 stable 的 Mergesort 陸陸續續都換成了 Timsort，看起來比較像是有個共識...
一樣是今天的 Hacker News Daily 上看到的東西，透過 YouTube 的 Private API 操作 YouTube 的套件：「Youtube.js – full-featured wrapper around YouTube's private API (github.com/luanrt)」。
這些 Private API 就是 YouTube 自己在網站上用的：
A full-featured wrapper around the Innertube API, which is what YouTube itself uses.
也因為這不是 Public API，也就不需要申請 key：
Do I need an API key to use this?
No, YouTube.js does not use any official API so no API keys are required.
當然可以預期他會無預警壞掉，所以可以自己衡量一下要怎麼搞...
比較有趣的是 Hacker News 的討論裡面反而有人在問要怎麼偵測這種 library 或是 bot XDDD
If you’re YouTube or any site, and want to stop these sort of wrappers - what’s the easiest way to do so without breaking your own site?
I find this task to be an interesting engineering problem.
A related question is if there’s an unspoofable way to detect a client.
不過掃了一下好像還好...
前幾天在 Hacker News 上看到「Implementing Cosine in C from Scratch (2020) (austinhenley.com)」這篇 2020 的文章，原文是「Implementing cosine in C from scratch」，裡面內在講自己刻三角函數的 cosine 所遇到的一些嘗試。
cosine 是很基本的函數，所以可以使用的地方很多。另外一方面，也因為他不是那麼直覺就可以實做出來，在現代的實做裡面其實藏了超多細節...
不過真的有趣的是在翻 Hacker News 上的討論時陸陸續續翻其他的資料看到的知識。
第一個看到的是 Intel 對於 FPU-based 指令集內的 FSIN 因為 π 的精度不夠而導致誤差超大 (尤其是在 0 點附近的時候)：「Intel Underestimates Error Bounds by 1.3 quintillion」，然後 AMD 是「相容」到底，所以一樣慘：「Accuracy of FSIN and other x87 trigonometric instructions on AMD processors」。
這個就是有印象，但是太久沒有提到就會忘記...
第二個是 musl libc 裡的 cosine 實做 (看註解應該是從 FreeBSD 的 libc 移植過來的？)：「__cos.c\math\src」與「cos.c\math\src」(話說 cgit 在 html 內 title 的內容對路徑的表達方式頗有趣，居然是反過來放...)。
拆開的部份是先將範圍限制在 ![[-\pi/4, \pi/4]](https://s0.wp.com/latex.php?latex=%5B-%5Cpi%2F4%2C+%5Cpi%2F4%5D&bg=ffffff&fg=000&s=0&c=20201002)
另外帶出來第三個知識，查資料的時候翻到 binary64 (這也是 C 語言裡面的 double) 與 binary128 的差異：
而大家很常拿來惡搞的 double double 則是利用兩個 double 存放，形式是 
A common software technique to implement nearly quadruple precision using pairs of double-precision values is sometimes called double-double arithmetic.
不過這樣的精確度只能到 106 bits，雖然跟 binary128 能達到的 113 bits 相比低了一些，但在大多數的情況下也還算夠用：
Using pairs of IEEE double-precision values with 53-bit significands, double-double arithmetic provides operations on numbers with significands of at least[4] 2 × 53 = 106 bits (...), only slightly less precise than the 113-bit significand of IEEE binary128 quadruple precision.
在 Hacker News 上看到「Decrypting your own HTTPS traffic with Wireshark」這篇，就是用 SSLKEYLOGFILE 請 library 把 TLS 相關的 key 與 random number 寫到檔案裡面讓 Wireshark 可以解讀拿來用。對應的討論在「Decrypting your own HTTPS traffic with Wireshark (trickster.dev)」這邊。
看起 OpenSSL 系列的 library 都有支援這個變數，另外 NSS 也支援這個變數，所以常見的程式應該都包含在內了...
比起 MITMA 類的方式 (像是 mitmproxy)，這個方式會更接近真實的情境，不另外產生 CA 與 key，不過缺點就是使用的情境就再受限一些，算是除了 MITMA 類方式的另外一個方案...
Hacker News 上爬到的，是一篇 2019 的文章：「When Double Precision Is Not Enough (adambaskerville.github.io)」，原文在「T>T: When Double Precision is Not Enough」。
作者是拿矩陣 (matrix) 的運算當例子，遇到了 double precision 造成的計算誤差問題：
There is no error with the program; this discrepancy is caused by a loss of numerical accuracy in the eigenvalue calculation due to the limitation of hardware double precision (16-digit).
解法是用 mpmath 增加精度，算是一種暴力解，到要注意計算會慢很多：
Note that this library is incredibly slow for large matrices, so is best avoided for most applications.
另外在 Hacker News 的討論串裡面看到個有趣的東西：「Herbie: Automatically Improving Floating Point Accuracy」這個專案，你把公式丟進去，Herbie 會試著提供等價公式來維持精度，像是 
半自動化幫你改善...
Hacker News 首頁上看到的專案：「Libmill is a library that introduces Go-style concurrency to C.」。
使用上的設計可以看到就是用 Golang 裡面的設計，另外在網頁下方也有提到「libdill: Structured Concurrency for C」，就不是用 Golang 的設計，但是有同樣的功能性...
兩者都是 MIT/X11 license，大多數的專案用起來應該沒什麼問題，底層應該都是用 select() 或是 poll() 來實做就是了？
在 Hacker News Daily 上看到「Static torrent website with peer-to-peer queries over BitTorrent on 2M records (boredcaveman.xyz)」這個討論，作者試著在網頁上跑 SQLite + VFS + WebTorrent。
這好像是這陣子一連串的 combo 技累積出來的東西：
接下來就是文章作者把 HTTP Range 換掉，改用 BitTorrent 的 pieces 來處理，在網頁端的話就順勢拿 WebTorrent 來用，對於很熱門的網站來說還蠻有趣的設計，但也可以預期網頁的反應速度應該不會太快，偏 PoC...
先前在「修正 Curl 的 TLS handshake，避開 bot 偵測機制」這邊提到 curl-impersonate 這個專案，試著修改 curl 的 TLS handshake fingerprint 讓偽裝的更好，本來只支援 Firefox，現在則是支援 Google Chrome 的 fingerprint 了...
作者寫的兩篇說明文章也可以看看：「Making curl impersonate Firefox」、「Impersonating Chrome, too」。
看起來愈來愈完整了，連 LD_PRELOAD 的用法也出現了，然後在 Arch Linux 上也出現 AUR 可以用了...
在 Hacker News 上看到個有趣的 scalability 問題，在 Mac 上的 sprintf() 因為有 lock 造成的 scalability 問題：「Curious lack of sprintf scaling (aras-p.info)」。
作者注意到 Mac 在多 CPU 下 sprintf() 會有 scalability 的問題，要注意到這邊的 Y 軸是對數比例：
用了 std::stringstream << 反而更慢 (作者還酸了一句「Zero cost abstractions」)：
然後用了 Instruments 跑 profiling 找問題，可以看到看起來跟 locale 有關：
一般的情況下應該不會是問題，但如果是需要大量 sprintf() 組字串的人就會比較要注意了。
在「What else can we do?」這段有提到一些解法，包括了 stb_sprintf 當作替代品，以及 {fmt} 作為 iostreams 的替代品，然後另外是利用 to_chars 來解決，如果只是要把數字轉成字串。
算是蠻有趣的 bug hunting 過程，對於開發者來說，一般性的重點還是在 profiling，找到對的問題然後再往下提出解法...