一個有趣的面試問題

Hacker News Daily 上看到「Performance comparison: counting words in Python, Go, C++, C, AWK, Forth, and Rust」這個有趣的面試問題,在 Hacker News 上的討論也可以看看:「Performance comparison: counting words in Python, Go, C++, C, Awk, Forth, Rust (benhoyt.com)」。

問題是這樣:

Write a program to count the frequencies of unique words from standard input, then print them out with their frequencies, ordered most frequent first. For example, given this input:

The foo the foo the
defenestration the

The program should print the following:

the 4
foo 2
defenestration 1

在面試時,重點不在於用哪個程式語言,而是在面試時一路往下問,像是 profiling 的部份,內部資料結構的部份,可以問得很深。

撇開面試,這個問題其實是個經典問題,當年 Donald KnuthDoug McIlroy 兩位大師都有玩過:

Incidentally, this problem set the scene for a wizard duel between two computer scientists several decades ago. In 1986, Jon Bentley asked Donald Knuth to show off “literate programming” with a solution to this problem, and he came up with an exquisite, ten-page Knuthian masterpiece. Then Doug McIlroy (the inventor of Unix pipelines) replied with a one-liner Unix shell version using tr, sort, and uniq.

不過當年玩的問題有點變形:

Given a text file and an integer k, print the k most common words in the file (and the number of their occurrences) in decreasing frequency.

他們當時其實一個是在示範 Literate programming,而另外一個在展現 pipe 的威力,都是借題發揮而已,跟上面的那些東西倒是沒什麼太大關係。

GTA Online 釋出官方修正,大幅改善啟動效能

看到「GTA Online load time fix released, shaves off actual minutes of waiting for some」這邊的消息,先前在「GTA 的啟動讀取效能問題」這邊提到 GTA Online 啟動速度很慢的問題,官方正式推出修正版本了:「GTAV Title Update 1.53 Notes (PS4 / Xbox One / PC)」。

抓了一些在 Reddit 的討論「Loading Times Have FINALLY been patched - Discussion Thread」。

這則降的比率與當時 workaround 的修正差不多:

Insane. GTA menu -> GTA: Online.

Dropped from 7 minutes to 1:57

i7-2600k,GTX1070,16GB RAM and the game is on HDD.

這個就有點誇張了,這是 90% 吧?

Dropped from 5-8 minutes to 35 seconds

這個差不多 70%~80%:

Loading time 2m 20s for online directly from steam. Before it was like 8-10 minutes for me. Damn

Edit: 50s for story mode. 35s from story mode to online. So it seems it's still faster to load into online from story mode.

這個也差不多 70%:

From 4-5 minutes to 1 a minute and 22 seconds. Y e s p l e a s e

然後 PS4 的版本原來也受到一樣的影響?

Currently tested on PS4 , from main menu to online : 3min 45 sec From story mode to online: 1min 20sec (😩 i can't tell for sure )

整體看起來是正面的,畢竟大家等這個問題等超久了... 另外也可以看出來當初的 workaround patch 其實相當精準的把問題都解掉了,官方的修正並沒有快更多。

來繼續關注 libc 那邊的問題...

GTA 的啟動讀取效能問題

這件事情也已經過了一個禮拜,來整理一下發生什麼事情...

起因是 GTA Online 的遊戲開啟速度很慢,而有人一路 reverse engineering 找出問題並且解決:「How I cut GTA Online loading times by 70%」,對應的 Hacker News 討論有提到其他有趣的事情也可以看看:「How I cut GTA Online loading times by 70% (nee.lv)」。

作者的電腦不算太差,但光開啟 GTA Online 就需要六分鐘,網路上甚至有辦投票蒐集大家的等待時間,發現也有很多人反應類似的問題:

接下來就開始 reverse engineering 了,先觀察各種狀態後發現是卡在 CPU,而不是網路或 Disk I/O,然後就拿出 Luke Stackwalker 這個工具 profiling,不過因為沒有 debug symbol 幫忙 group,所以只能人工判斷後,可以看到兩個問題:

第一個問題發現效能是卡在 strlen(),而 call stack 可以看出來是從 sscanf() 一路打進去的:

反追發現是在處理 10MB 的 JSON 檔造成的,裡面 sscanf() 因為拉出 strlen(),於是就造成把整個 10MB 的 JSON 掃過很多次 (一開始是 10MB,掃到後面會愈來愈少,平均下來應該是 5MB):

第二個問題產生的時間會在第一個問題跑完後,另外看問題的性質,應該跟第一個 JSON 處理有關,他會把 JSON 處理過的資料丟進 array,每個 entry 長這樣:

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

丟進 array 是 OK 的,但問題在於他需要判斷 entry 是否重複,卻沒有用 hash 或是 tree 的結構,而這邊大約有 63k 筆資料,用 array 實做就產生了 O(n^2) 的演算法:

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

作者在 PoC 的章節裡面描述他怎麼解這兩個問題。

第一個問題比較好的解法是修正 JSON Parser,但這太複雜,所以他用 workaround 解:把 strlen() 包起來,針對長字串加上一層 cache:

  • hook strlen
  • wait for a long string
  • “cache” the start and length of it
  • if it’s called again within the string’s range, return cached value

而第二個問題他直接把檢查是否有重複的跳過,因為資料本身不重複:

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

整個開啟的速度從六分鐘降到一分五十秒,還是偏慢,但算是大幅緩解的 GTA Online 啟動速度的問題了。

不過故事到這邊還沒結束,有人一路去挖,發現其實 sscanf() 的效能地雷已經不是第一次了:YAML 的 Parser 也中過一樣的問題:「Parsing can become accidentally quadratic because of sscanf」,這篇也一樣上了 Hacker News:「Parsing can become accidentally quadratic because of sscanf (github.com/biojppm)」。

然後這又帶出了六年前在 StackOverflow 上就有人問過這個問題:「Why is glibc's sscanf vastly slower than fscanf on Linux?」。

另外也有人整理出來,應該是大家把同樣的演算法拿來實做:

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.

後續的更新動作可以再追一下進度 (包括 GTA Online 與各家的 libc)。

PostgreSQL 的 Fuzzy Matching

在「Fuzzy Name Matching in Postgres」這邊看到 PostgreSQL 下怎麼設計 Fuzzy Matching 的方式,文章裡用的方法主要是出自 PostgreSQL 的文件:「F.15. fuzzystrmatch」。

文章最後的解法是 Soundex + Levenshtein

翻了一下資料,這個領域另外有 NYSIIS (New York State Identification and Intelligence System):

The New York State Identification and Intelligence System Phonetic Code, commonly known as NYSIIS, is a phonetic algorithm devised in 1970 as part of the New York State Identification and Intelligence System (now a part of the New York State Division of Criminal Justice Services). It features an accuracy increase of 2.7% over the traditional Soundex algorithm.

以及 Metaphone

Metaphone is a phonetic algorithm, published by Lawrence Philips in 1990, for indexing words by their English pronunciation. It fundamentally improves on the Soundex algorithm by using information about variations and inconsistencies in English spelling and pronunciation to produce a more accurate encoding, which does a better job of matching words and names which sound similar. As with Soundex, similar-sounding words should share the same keys. Metaphone is available as a built-in operator in a number of systems.

不過這些都是以英文為主,中文的沒特別翻到...

Dehydrated 取得憑證的預設演算法改成 secp384r1

這兩天弄 dehydrated,結果發現 v0.7.0 取得憑證的預設演算法改成 ECCsecp384r1 了:

Using EC secp384r1 as default certificate type

這會導致很多「稍微舊一點」的 client 失效 (瀏覽器與 library),不知道為什麼要預設... 目前避開的方法是強制在 /etc/dehydrated/config 內設定使用 rsa

KEY_ALGO=rsa

剛剛把公司一堆機器改上去,然後把自己的 server 也加一加...

OpenSSH 8.4 預設停用 ssh-rsa

前幾天 OpenSSH 8.4 釋出了:「Announce: OpenSSH 8.4 released」。

比較重要的改變是 ssh-rsa 預設變成停用,因為是使用 SHA-1 演算法的關係:

It is now possible[1] to perform chosen-prefix attacks against the SHA-1 algorithm for less than USD$50K. For this reason, we will be disabling the "ssh-rsa" public key signature algorithm by default in a near-future release.

官方給了三個方案:

  • The RFC8332 RSA SHA-2 signature algorithms rsa-sha2-256/512. These algorithms have the advantage of using the same key type as "ssh-rsa" but use the safe SHA-2 hash algorithms. These have been supported since OpenSSH 7.2 and are already used by default if the client and server support them.
  • The ssh-ed25519 signature algorithm. It has been supported in OpenSSH since release 6.5.
  • The RFC5656 ECDSA algorithms: ecdsa-sha2-nistp256/384/521. These have been supported by OpenSSH since release 5.7.

掃了一下 ~/.ssh/known_hosts,看起來目前大多都是 ssh-ed25519 了,還有少數還是 ssh-rsa

翻了一下 Ubuntu 這邊的版本,16.04 是 7.2p2,看起來目前有支援的版本都可以用這三個。

官方有提到可以在 command 上強制關閉 ssh-rsa 測試的方法:

ssh -oHostKeyAlgorithms=-ssh-rsa user@host

現在看起來比較麻煩的是 Dropbear 的部份,我自己之前是有包 PPA 來用 (2019.78),但看起來還是不夠新支援 ssh-ed25519 (要今年六月的 2020.79 才支援),所以也許要找時間來把 PPA 更新到 2020.80...

另外一種方法是走 ecdsa-sha2-nistp{256,384,521} 這些演算法,不過從名字就可以知道裡面演算法的由來,卡個 NIST 在那邊看起來就不太舒服,但還是寫一下方法好了:

先用 dropbearkey 產生對應的 ecdsa host key:

sudo dropbearkey -t ecdsa -f /etc/dropbear/dropbear_ecdsa_host_key -s 256

再來在 /etc/default/dropbear 裡面把 DROPBEAR_EXTRA_ARGS 加上對應的 ecdsa host key 資訊,這邊直接用 -r 是因為他可以重複指定,不會影響到其他的 host key 設定:

# any additional arguments for Dropbear
DROPBEAR_EXTRA_ARGS="-r /etc/dropbear/dropbear_ecdsa_host_key"

然後重跑 dropbear 就可以了。

另外有興趣的人可以用 ssh -Q key 看 openssh client 支援的演算法。

NIST 對密碼學演算法建議的長度 (2020 版)

在「Comparing SSH Encryption Algorithms - RSA, DSA, ECDSA, or EdDSA?」這邊一路翻到「Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2020)」這篇,裡面引用的是 NIST 的「NIST Special Publication 800-57 Part 1 Revision 5」。

在 NIST 的文件裡面,不同的演算法散落在不同地方,Keylength 整理起來後比較方便看。

想要特別拉出來講是因為看到 RSA 2048 bits 被放到 112 這個等級 (Security Strength),我一直以為是 128,不過查了一下發現好像以前是就 112 了...

AWS Site-to-Site VPN 支援 AES-GCM 了

AWS 更新了 Site-to-Site VPN:「AWS Site-to-Site VPN now supports additional encryption, integrity and key exchange algorithms」。

這次更新支援了一些新的演算法,其中 AES-GCM 的部份看起來是這次這波最重要的:

Encryption: AES128-GCM-16, AES256-GCM-16.
Integrity: SHA2-384, SHA2-512.
Diffie-Hellman groups: 19, 20, 21.

傳統的方式是 encryption algorithm + hash algorithm 搭配,所以就會出現各種排列組合,而不同的方式在實做上很容易出現安全問題,也就是這篇在討論的:「Should we MAC-then-encrypt or encrypt-then-MAC?」。

AEAD 試著用一包解決,對於實做的安全性好不少...

避開人臉辨識系統的演算法

Hacker News Daily 上看到的專案,針對現在很多演算法可以抓出照片上的人臉進行防禦:「Image "Cloaking" for Personal Privacy」。

這算是 Evasion 的應用,這個專案想要提供演算法,可以在照片上「隱形」,使得演算法偵測不到「人臉」,程式碼可以在 Shawn-Shan/fawkes 這邊翻到,可以看到是在 Python 上用 TensorFlowKeras 實做出來的。

不過會覺得比較有趣的反而不是裡面的方法,而是這篇論文的六個作者:

Shawn Shan†, PhD Student
Emily Wenger†, PhD Student
Jiayun Zhang, Visiting Student
Huiying Li, PhD Student
Haitao Zheng, Professor
Ben Y. Zhao, Professor

† Project co-leaders and co-first authors

從名字上來看五個是華人,而且一路搜下來會發現掛在最後一位的 Ben Y. Zhao 教授在 Quora 上常常回答問題,而且這些問題 (與回答) 還蠻有趣的,可以自己搜看看...

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

應該是直接在 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 上的情況...