使用二分法解決擴充套件問題

2021年2月16日 作者：Johannes Rieken, @johannesrieken

“就像 git-bisect 一樣，但是是針對 VS Code 擴充套件的。”

Visual Studio Code 的真正強大之處在於它的擴充套件：主題擴充套件增加顏色和圖示，語言擴充套件支援智慧程式碼補全 (IntelliSense) 和導航，偵錯程式擴充套件讓你能夠執行程式碼並輕鬆找到 bug。還有播放音樂的擴充套件，顯示股票行情的擴充套件，以及支援跨地點和時區協同工作的擴充套件。VS Code Marketplace 託管著超過28,000個擴充套件，使用者安裝50個或更多擴充套件的情況並不少見。有如此多的擴充套件，bug 在所難免。我們不想否認它的存在，而是希望讓故障排除變得容易。

“不良”擴充套件

我們熱愛擴充套件，並不認為真的存在什麼“不良”擴充套件。然而，像所有軟體一樣，擴充套件也有 bug 和功能缺失。因此，為了方便閱讀和製造一點人為的戲劇性，我們姑且使用“不良擴充套件”這個詞，它指的是可能會崩潰或簡單地顯示不需要行為的擴充套件。幸運的是，我們在設計 VS Code 時考慮到了“不良”擴充套件，因此它們執行在獨立的程序中。這種隔離保證了 VS Code 能夠持續執行，游標始終閃爍，並且你始終可以儲存你的工作。

為了好玩，也為了更容易演示擴充套件二分法，我們建立併發布了Extension Bisect Demo 擴充套件。安裝後，每當你輸入到“bisect”這個詞時，它就會煩人地重置你的游標。你可以使用這個擴充套件來跟著這篇博文一起操作。

用困難的方式尋找“不良”擴充套件

如今，找到一個“不良”擴充套件可能容易也可能困難。開啟“擴充套件”檢視（⇧⌘X（Windows、Linux Ctrl+Shift+X）），停用一個擴充套件，重新載入視窗（Developer: Reload Window），然後檢查問題是否仍然存在。如果問題消失了，那麼那個擴充套件就是“不良”的，你就可以收工了。否則，重新啟用該擴充套件，並對下一個擴充套件重複此過程。

如果你幸運，第一個擴充套件就是“不良”的；如果你不幸，則是最後一個。用計算機科學的語言來說，這意味著對於 N 個擴充套件，最壞情況下你需要重複該過程 O(N)（N 階），平均情況下是 O(N/2)。因為這個演算法是由人（你）操作的，即使 N 的值很小，也仍然很費力。這就是擴充套件二分法工具派上用場的地方。它在最壞和平均情況下要好得多，因為它透過減半的方式停用擴充套件。

歡迎使用擴充套件二分法

VS Code 中的擴充套件二分法工具的靈感來源於 git bisect 命令。對於熟悉 Git 的人來說，這個命令對於找出倉庫中哪個提交引入了問題非常有幫助。

讓我們舉個例子：我安裝了24個擴充套件，其中第8個擴充套件是“不良”的。我們知道迭代方法需要8個步驟。那麼二分法呢？

下面的影片展示瞭如何透過 Help: Start Extension Bisect 命令啟動擴充套件二分法，然後選擇 Good now 或 This is bad，直到識別出“不良”擴充套件。一旦識別出來，你就可以選擇為該擴充套件報告問題。

以下是發現“不良”擴充套件的逐步過程

1. 二分法將24個擴充套件分成兩半，每半12個擴充套件，並停用第二半的所有12個擴充套件。
2. 在這個例子中，第8個擴充套件是“不良”擴充套件，所以它在前半部分，沒有被停用。情況仍然不盡如人意。由於問題依然存在，擴充套件二分法重複該過程，將前12個擴充套件分成兩部分：6個啟用，6個停用。所有其他擴充套件也被重新啟用。
3. 現在，第8個擴充套件被停用了。現在情況很好。這意味著二分法可以繼續處理後半部分（擴充套件6-11），並將其分為3個啟用和3個停用的擴充套件。
4. 現在，第8個擴充套件被重新啟用，問題再次出現。這意味著二分法繼續處理前半部分。它將其分為1個啟用和2個停用的擴充套件。
5. 第8個擴充套件現在被停用了，情況又好起來了，二分法繼續處理後半部分，將其分成1個啟用和1個停用的擴充套件。
6. 第8個擴充套件是唯一被停用的擴充套件，問題也消失了。這意味著我們找到了“不良”擴充套件，並且我們完成了。

更快地排除故障

我們看到，在每一步中，二分法都將搜尋空間減少了一半。現在它以對數時間執行，導致平均和最壞情況下的效能為 O(log N)。這非常好，因為它具有良好的可擴充套件性。對於24個擴充套件，你需要4到5步才能找到一個“不良”擴充套件；對於38個擴充套件，只需要多1步。然而，最佳情況會更糟，因為使用迭代方法，你可能運氣好在第一輪就找到“不良”擴充套件。

請記住，擴充套件二分法依賴於你提供正確的反饋。你可以很容易地騙過它，也騙過你自己，方法是總是回答 Good now（會歸咎於最後一個擴充套件）或 This is bad（將找不到任何擴充套件）。

另一個有用的見解是，擴充套件二分法一開始會考慮所有已啟用的擴充套件。這意味著你可以透過在開始前停用一個已知“良好”的擴充套件，並在之後重新啟用它來將其排除在二分法之外。但是，只有在你確定該擴充套件不是“不良”擴充套件時才這樣做。

最後，你可能會注意到二分法多花了一個步驟（log2(N) + 1）。那是因為它在第一輪中停用了所有擴充套件。執行這第一步是因為你可能遇到的問題是由 VS Code 本身而非擴充套件引起的，我們不想不必要地將你引入歧途。

就這樣。我們希望你永遠不需要使用擴充套件二分法。然而，如果你確實遇到了可能與擴充套件相關的問題，那麼我們希望我們能讓故障排除變得更簡單、更快、更愉快。

程式設計愉快，

Johannes Rieken, VS Code 首席軟體工程師 @johannesrieken