Month: June 2022

搜尋引擎的替代方案清單

看到「A look at search engines with their own indexes」這篇在介紹各個搜尋引擎，作者設計了一套方法測試，另外在文章裡面也給了很多主觀的意見，算是很有參考價值的，可以試看看裡面提出來的建議。

另外在 Hacker News 上也有討論可以參考：「A look at search engines with their own indexes (2021) (seirdy.one)」。

在文章開頭的「General indexing search-engines」這個章節，先列出三大搜尋引擎 GBY (Google、Bing、Yandex)，以及使用這三家當作後端資料庫的搜尋引擎，可以看到到處都是 Bing 的影子。

接著作者推薦 Mojeek 這個作為 GBY 的替代方案：

Mojeek: Seems privacy-oriented with a large index containing billions of pages. Quality isn’t at GBY’s level, but it’s not bad either. If I had to use Mojeek as my default general search engine, I’d live. Partially powers eTools.ch. At this moment, I think that Mojeek is the best alternative to GBY for general search.

在「Smaller indexes or less relevant results」這邊也有一些方案，像是這個章節第一個提到的 Right Dao，作者就給他了不錯的評價：

Right Dao: very fast, good results. Passes the tests fairly well. It plans on including query-based ads if/when its user base grows.

接下來的「Smaller indexes, hit-and-miss」與「Unusable engines, irrelevant results」也可以翻一下，看看作者怎麼批評 XD

然後是後面的「Semi-independent indexes」就出現了最近幾個比較有名的，像是 Brave Search 與目前我在用的 Kagi。

整理的相當不錯...

在 Shell 下一行用 SQLite 查詢 CSV 內的資料

從 Simon Willison 這邊看到 command line 下用 SQLite 的技巧：「One-liner for running queries against CSV files with SQLite」。

範例指令是這樣 (整理了一下排版)：

sqlite3 :memory: \
    -cmd '.import -csv taxi.csv taxi' \
    'SELECT passenger_count, COUNT(*), AVG(total_amount) FROM taxi GROUP BY passenger_count'

可以看出來這個方式是將 csv 檔先讀到 in-memory database (:memory:)，再用 SQLite 下指令處理，另外也可以自己變化，應該可以透過 /dev/stdin 這樣的方式讀 pipe 的東西。

拿來簡單跑一些東西應該還不賴？

GitHub Copilot 宣佈 GA

GitHub Copilot 宣佈 GA：「GitHub Copilot is generally available to all developers」，Hacker News 上的討論可以看一下：「GitHub Copilot is generally available (github.blog)」。

價錢也出來了，US$10/mo 或是 US$100/year：

We’re making GitHub Copilot, an AI pair programmer that suggests code in your editor, generally available to all developers for $10 USD/month or $100 USD/year. It will also be free to use for verified students and maintainers of popular open source projects.

不過重點不是價錢，而是還沒有被挑戰過的 license 問題，像是在 Hacker News 上有人提到有些程式碼的授權是有感染性的 GPL 類的，這些在法院上還沒有被戰過。

不過還是很看好這個服務，畢竟可以處理掉很多無聊的 coding 時間... 查了一下發現 Neovim 已經有支援了，似乎可以來看看要怎麼玩 :o

可以在 Cat5 上面跑 1km 的 Ethernet 標準 10BASE-T1L

在 Hacker News 上看到「SPEBlox-Long (10BASE-T1L) - 10Mbps, 1km range」這個產品，看到 10BASE-T1L 這個標準還有蠻有趣的，對應的討論在「10mbps over 1km on a single pair of wires (botblox.io)」這邊。

在維基百科的「Ethernet over twisted pair」這個頁面上面有提到 10BASE-T1S 與 10BASE-T1L 這兩個在 2019 推出的新標準：

Two new variants of 10 megabit per second Ethernet over a single twisted pair, known as 10BASE-T1S and 10BASE-T1L, were standardized in IEEE Std 802.3cg-2019. 10BASE-T1S has its origins in the automotive industry and may be useful in other short-distance applications where substantial electrical noise is present. 10BASE-T1L is a long-distance Ethernet, supporting connections up to 1 km in length. Both of these standards are finding applications implementing the Internet of things.

從標準的名字就可以知道是 10Mbps 的速度，但只用一對線路就可以跑 1km 還蠻有趣的，主打在 IoT 場景...

Telegram 推出 Premium 方案

Telegram 宣佈推出 Premium 了：「700 Million Users and Telegram Premium」。看了一下有點長度，就直接放 iThome 的報導：「Telegram正式推出付費訂閱服務Telegram Premium」。

更新 Telegram 後就會在 Settings 裡面看到 Premium 的設定可以選，然後看起來走 IAP，我自己是在台灣的 iOS 上面買，NT$160/mo，裡面提到的功能基本上都用不到 (大概只有 no ads)，但還是買起來...

在 Hacker News 上看到幾個 Key-Value Store 軟體

在 Hacker News 上看到「Redis vs. KeyDB vs. Dragonfly vs. Skytable」這篇，裡面介紹了四套 key-value store 軟體：

  • Redis：這個應該不太需要介紹...
  • KeyDB：Snapchat 搞出來的 Redis clone，主要的賣點是 multi-threading。
  • Dragonfly：宣稱地球上最快，但作者跑不出來，下面的討論有人提到 Dragonfly 在更多的 CPU 資源效能就會更好。
  • Skytable：作者測出來最快的。

裡面看起來都蠻有趣的，可以追起來看看發展的情況，但如果真的要的用的話，應該還是先以 Redis 為主，穩定度以及功能還是重點...

ARC (Authenticated Received Chain)

標題的 ARC 是指 Authenticated Received Chain，是前陣子在 Hacker News 上看到「Gmail accepts forged YouTube emails (john-millikin.com)」這篇才發現的東西，原文在「Gmail accepts forged YouTube emails」這邊。

作者發現 Gmail 收了從不是直接從 YouTube 發出來的信件：

主要的原因是，Gmail 除了使用標準的 SPF 與 DKIM 判斷外，還吃上面提到的 ARC。

查了一下 ARC，標準是 RFC 8617，目前還是被標成 experimental，主打是解決 forwarding 的問題，看了一下作者群是 LinkedIn (Microsoft)、Google 與 Valimail。

ARC 這東西與之前 Google 在強推的 AMP (然後被罰) 以及現在在推的 Signed HTTP Exchanges 都有相同的味道，無視 security & privacy concern 的東西...

從簡單的 C 語言函式來看現代 Compiler 使用 SIMD 的威力

兩個禮拜前在 Hacker News Daily 上看到這篇很精彩的問題與分析，裡面展現出了現代 compiler 最佳化的能力，大量使用了 SIMD 來衝效能：「Why does this code execute more slowly after strength-reducing multiplications? (stackoverflow.com)」，原文在 Stack Overflow 上：「Why does this code execute more slowly after strength-reducing multiplications to loop-carried additions?」。

這篇會很長，除了本來 Stack Overflow 上的討論以外，我另外自己測 GCC 9.4.0 不加上 -O、加上 -O 與 -O3，發現這次 Stack Overflow 給的範例剛剛好把這幾個常見的最佳化等級都練出不同結果，算是蠻厲害的題目。

作者一開始是寫了一個很簡單的版本 A，會透過 loop (對 i 進行) 計算 A*i^2 + B*i + C 的值，把結果放到 array 裡面：

double data[LEN];

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] = A*i*i + B*i + C;
    }
}

透過一些紙本公式計算可以知道，每次遞增的值雖然不是固定值，但也是有規律的：

所以可以改寫成一堆加號的版本 B：

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;
    const double A2 = A+A;
    double Z = A+B;
    double Y = C;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] = Y;
        Y += Z;
        Z += A2;
    }
}

理想上版本 A 在 loop 內用到三個乘法與兩個加法，而版本 B 只用到了三個加法，預期版本 B 應該會快不少，但實際上跑出來的結果剛好反過來：版本 B 慢了許多。

作者實際用 objdump 拉出來看，粗粗看下來也會發現版本 A 的指令多很多：

而版本 B 的指令簡單很多：

在討論下面已經有人給出解釋，主要的原因包括了兩個。

首先是現代 CPU 靠著暴力電路解決，乘法速度跟加法其實不像以前差那麼多，可以從 Instruction tables 這邊看到 MUL 類的指令速度雖然不能跟加法相比，但其實不算慢了，反倒是 DIV 整數除法類的指令比較痛。

另外一個原因，如果仔細看作者貼的 screenshot 分析會發現，在版本 A 裡面，一個 loop 其實做了四次 i 的運算 (add rax, 0x20)，而版本 B 只做了一個 i 的運算 (add rax, 0x8)，這邊 compiler 幫你 unroll 最佳化改用 SIMD 處理掉了。

在 Stack Overflow 的回答裡面，有人給了一段不錯的 code 示意，提到版本 A 其實先被展成像是這樣的程式碼：

int i;
for (i = 0; i < LEN; i += 4) {
    data[i+0] = A*(i+0)*(i+0) + B*(i+0) + C;
    data[i+1] = A*(i+1)*(i+1) + B*(i+1) + C;
    data[i+2] = A*(i+2)*(i+2) + B*(i+2) + C;
    data[i+3] = A*(i+3)*(i+3) + B*(i+3) + C;
}

然後被 SIMD 包起來處理掉了。

我把作者的 code (他有貼在 GitHub Gist 上) 拿下來編，用不同的 -O 與 -O3 測試，然後去讀 assmebly 的部份也可以看到很多有趣的東西...

首先是在 -O3 的情況下 (也就是作者使用的參數)，可以看到類似的結果：(我桌機的 CPU 是定速，沒有跑動態調整)

$ repeat 10 ./a
[-] Took: 248830 ns.
[-] Took: 249150 ns.
[-] Took: 248760 ns.
[-] Took: 248730 ns.
[-] Took: 248770 ns.
[-] Took: 248861 ns.
[-] Took: 248760 ns.
[-] Took: 253050 ns.
[-] Took: 248640 ns.
[-] Took: 249211 ns.
$ repeat 10 ./b
[-] Took: 686660 ns.
[-] Took: 696090 ns.
[-] Took: 696310 ns.
[-] Took: 694431 ns.
[-] Took: 691971 ns.
[-] Took: 697690 ns.
[-] Took: 693241 ns.
[-] Took: 692900 ns.
[-] Took: 654751 ns.
[-] Took: 679101 ns.

從版本 A 的 objdump -d -S -M intel a 可以看到作者 screenshot 內也有看的 unroll 與 SSE2 指令集：

13a0:       66 0f 6f c2             movdqa xmm0,xmm2
13a4:       48 83 c0 20             add    rax,0x20
13a8:       66 0f fe d6             paddd  xmm2,xmm6
13ac:       f3 0f e6 f8             cvtdq2pd xmm7,xmm0
13b0:       66 0f 28 cf             movapd xmm1,xmm7
13b4:       66 0f 70 c0 ee          pshufd xmm0,xmm0,0xee
13b9:       66 0f 59 cd             mulpd  xmm1,xmm5
13bd:       f3 0f e6 c0             cvtdq2pd xmm0,xmm0
13c1:       66 0f 59 cf             mulpd  xmm1,xmm7
13c5:       66 0f 59 fc             mulpd  xmm7,xmm4
13c9:       66 0f 58 cf             addpd  xmm1,xmm7
13cd:       66 0f 58 cb             addpd  xmm1,xmm3
13d1:       0f 29 48 e0             movaps XMMWORD PTR [rax-0x20],xmm1
13d5:       66 0f 28 c8             movapd xmm1,xmm0
13d9:       66 0f 59 cd             mulpd  xmm1,xmm5
13dd:       66 0f 59 c8             mulpd  xmm1,xmm0
13e1:       66 0f 59 c4             mulpd  xmm0,xmm4
13e5:       66 0f 58 c1             addpd  xmm0,xmm1
13e9:       66 0f 58 c3             addpd  xmm0,xmm3
13ed:       0f 29 40 f0             movaps XMMWORD PTR [rax-0x10],xmm0
13f1:       48 39 c2                cmp    rdx,rax
13f4:       75 aa                   jne    13a0 <compute+0x40>

而版本 B 的 objdump -d -S -M intel b 也符合作者提到的現象：

1340:       f2 0f 11 08             movsd  QWORD PTR [rax],xmm1
1344:       48 83 c0 08             add    rax,0x8
1348:       f2 0f 58 c8             addsd  xmm1,xmm0
134c:       f2 0f 58 c2             addsd  xmm0,xmm2
1350:       48 39 d0                cmp    rax,rdx
1353:       75 eb                   jne    1340 <compute+0x30>

但把 gcc 改成 -O 後，可以看到版本 A 的速度慢很多，但還是稍微比版本 B 快一些：

$ repeat 10 ./a
[-] Took: 571140 ns.
[-] Took: 570280 ns.
[-] Took: 571271 ns.
[-] Took: 573971 ns.
[-] Took: 571981 ns.
[-] Took: 569650 ns.
[-] Took: 566361 ns.
[-] Took: 571600 ns.
[-] Took: 571330 ns.
[-] Took: 571030 ns.
$ repeat 10 ./b
[-] Took: 697521 ns.
[-] Took: 696961 ns.
[-] Took: 696201 ns.
[-] Took: 694921 ns.
[-] Took: 696930 ns.
[-] Took: 695001 ns.
[-] Took: 701661 ns.
[-] Took: 698100 ns.
[-] Took: 702430 ns.
[-] Took: 702641 ns.

從 objdump 可以看到版本 A 的變化，退化成一次只處理一個，但把所有的數字都用 xmmN 存放計算：

11b1:       66 0f ef c9             pxor   xmm1,xmm1
11b5:       f2 0f 2a c8             cvtsi2sd xmm1,eax
11b9:       66 0f 28 c1             movapd xmm0,xmm1
11bd:       f2 0f 59 c4             mulsd  xmm0,xmm4
11c1:       f2 0f 59 c1             mulsd  xmm0,xmm1
11c5:       f2 0f 59 cb             mulsd  xmm1,xmm3
11c9:       f2 0f 58 c1             addsd  xmm0,xmm1
11cd:       f2 0f 58 c2             addsd  xmm0,xmm2
11d1:       f2 0f 11 04 c2          movsd  QWORD PTR [rdx+rax*8],xmm0
11d6:       48 83 c0 01             add    rax,0x1
11da:       48 3d 40 42 0f 00       cmp    rax,0xf4240
11e0:       75 cf                   jne    11b1 <compute+0x28>

而版本 B 在 -O 的情況下基本上是一樣的東西 (所以速度上差不多)：

11b3:       f2 0f 11 08             movsd  QWORD PTR [rax],xmm1
11b7:       f2 0f 58 c8             addsd  xmm1,xmm0
11bb:       f2 0f 58 c2             addsd  xmm0,xmm2
11bf:       48 83 c0 08             add    rax,0x8
11c3:       48 39 d0                cmp    rax,rdx
11c6:       75 eb                   jne    11b3 <compute+0x2a>

再來是拔掉 -O，都不加就會超慢：

$ repeat 10 ./a
[-] Took: 1097091 ns.
[-] Took: 1092941 ns.
[-] Took: 1092501 ns.
[-] Took: 1091991 ns.
[-] Took: 1092441 ns.
[-] Took: 1093970 ns.
[-] Took: 1091341 ns.
[-] Took: 1093931 ns.
[-] Took: 1094111 ns.
[-] Took: 1092231 ns.
$ repeat 10 ./b
[-] Took: 2703282 ns.
[-] Took: 2705933 ns.
[-] Took: 2703582 ns.
[-] Took: 2702622 ns.
[-] Took: 2703043 ns.
[-] Took: 2702262 ns.
[-] Took: 2703352 ns.
[-] Took: 2703532 ns.
[-] Took: 2703112 ns.
[-] Took: 2702533 ns.

看 objdump 就可以發現幾乎都是對記憶體操作，沒有放到 register 裡面，這是版本 A：

11c1:       f2 0f 2a 45 e4          cvtsi2sd xmm0,DWORD PTR [rbp-0x1c]
11c6:       66 0f 28 c8             movapd xmm1,xmm0
11ca:       f2 0f 59 4d e8          mulsd  xmm1,QWORD PTR [rbp-0x18]
11cf:       f2 0f 2a 45 e4          cvtsi2sd xmm0,DWORD PTR [rbp-0x1c]
11d4:       f2 0f 59 c8             mulsd  xmm1,xmm0
11d8:       f2 0f 2a 45 e4          cvtsi2sd xmm0,DWORD PTR [rbp-0x1c]
11dd:       f2 0f 59 45 f0          mulsd  xmm0,QWORD PTR [rbp-0x10]
11e2:       f2 0f 58 c1             addsd  xmm0,xmm1
11e6:       f2 0f 58 45 f8          addsd  xmm0,QWORD PTR [rbp-0x8]
11eb:       8b 45 e4                mov    eax,DWORD PTR [rbp-0x1c]
11ee:       48 98                   cdqe   
11f0:       48 8d 14 c5 00 00 00    lea    rdx,[rax*8+0x0]
11f7:       00 
11f8:       48 8d 05 41 2e 00 00    lea    rax,[rip+0x2e41]
11ff:       f2 0f 11 04 02          movsd  QWORD PTR [rdx+rax*1],xmm0
1204:       83 45 e4 01             add    DWORD PTR [rbp-0x1c],0x1
1208:       81 7d e4 3f 42 0f 00    cmp    DWORD PTR [rbp-0x1c],0xf423f
120f:       7e b0                   jle    11c1 <compute+0x38>

這是版本 B：

11e8:       8b 45 cc                mov    eax,DWORD PTR [rbp-0x34]
11eb:       48 98                   cdqe   
11ed:       48 8d 14 c5 00 00 00    lea    rdx,[rax*8+0x0]
11f4:       00 
11f5:       48 8d 05 44 2e 00 00    lea    rax,[rip+0x2e44]
11fc:       f2 0f 10 45 d8          movsd  xmm0,QWORD PTR [rbp-0x28]
1201:       f2 0f 11 04 02          movsd  QWORD PTR [rdx+rax*1],xmm0
1206:       f2 0f 10 45 d8          movsd  xmm0,QWORD PTR [rbp-0x28]
120b:       f2 0f 58 45 d0          addsd  xmm0,QWORD PTR [rbp-0x30]
1210:       f2 0f 11 45 d8          movsd  QWORD PTR [rbp-0x28],xmm0
1215:       f2 0f 10 45 d0          movsd  xmm0,QWORD PTR [rbp-0x30]
121a:       f2 0f 58 45 f8          addsd  xmm0,QWORD PTR [rbp-0x8]
121f:       f2 0f 11 45 d0          movsd  QWORD PTR [rbp-0x30],xmm0
1224:       83 45 cc 01             add    DWORD PTR [rbp-0x34],0x1
1228:       81 7d cc 3f 42 0f 00    cmp    DWORD PTR [rbp-0x34],0xf423f
122f:       7e b7                   jle    11e8 <compute+0x5f>

寫到這邊差不多了，作者拿的這個範例算是很有趣的例子，尤其是現代 compiler 幫我們做了超多事情後，很多自己以為的 optimization 其實未必比較好，還是要有個 profiling review 才準...

圖片無損壓縮下的演算法比較

Hacker News 上看到「What’s the best lossless image format? Comparing PNG, WebP, AVIF, and JPEG XL」這篇，在講圖片的無損壓縮演算法。在 Hacker News 上的討論也可以看看：「What’s the best lossless image format? (siipo.la)」。

文章有點舊 (2021 年七月)，但應該還行... 另外作者看起來是以 service bandwidth 考量為主，在這種情境下，自然圖片一般都會以非無損的方式提供 (像是 JPEG)，而人造圖片則是以無損的方式提供 (像是 PNG)，所以在這邊討論無損的時候會以人造圖片的 dataset 來挑選，於是作者是跑去 Dribbble 上翻圖片當 dataset：

What I ended up with was downloading a set of images from Dribbble, a portfolio site for designers.

最後的結果就是：

考慮到目前各家瀏覽器的支援性，可以看到 Lossless WebP 其實是個很好的選擇，檔案算蠻小的，而且 Apple ecosystem 的支援性也已經出來了：

如果不用考慮到瀏覽器的話，JPEG XL 也可以考慮，不過本來宣稱 royalty-free 的部份蒙上了陰影：「Alarm raised after Microsoft wins data-encoding patent」，用的人反而要注意到 patent 問題...