JavaScript 的 sort 變成 stable

看到「Stable Array.prototype.sort」這篇在講 JavaScript 規格書裡的 sort...

本來 JavaScript 的規格書裡,各種 sort 都沒有保證 stable,而在「[Normative] Make Array.prototype.sort stable #1340」與「[Normative] Make %TypedArray%.prototype.sort stable #1433」這兩個地方則有了變化,提案在規格裡加入 stable 的要求,可以減少開發者因為不知道 unstable 而造成的問題...

Firefox 則是很久前就決定使用 Merge sort 了 (看了一下,當時還在從 Firebird 轉換名稱到 Firefox 的時期):「Array.sort isn't a stable sort (switch to MergeSort)」。

另外這篇也剛好提到了 V8 使用 Timsort 當作 stable sorting algorithm,之前就有看到但發現沒在 blog 上提過...

Timsort 是 1993 年發明出來的演算法,與 Merge sort 的情況類似,除了 stable 外,還可以保證最差的情境下的時間複雜度是 O(n*log(n))

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

這個演算法的重點是善用已經排好的子序列,藉此降低記憶體操作次數而提昇效能,符合真實環境裡常見到的資料:

The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

除了 V8 採用這個演算法以外,其他常見的包括了 PythonAndroid 上的 Java SE:

Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, and Google Chrome.

V8 version 6.5 (Chrome 65) 的改變

V8 version 6.5 將會有不少改變:「V8 release v6.5」。

其中因為 Spectre 的關係,新的 V8 設計了 Untrusted code mode,拿來跑不信任的程式,裡面會設計反制措施。而且這在新版的 Chrome 將會預設開啟:

In response to the latest speculative side-channel attack called Spectre, V8 introduced an untrusted code mode. If you embed V8, consider leveraging this mode in case your application processes user-generated, not-trustworthy code. Please note that the mode is enabled by default, including in Chrome.

另外是針對 WebAssembly 提供邊下載邊 compile 的能力,這讓速度大幅提昇。在原文是拿一個比較大包的 WebAssembly 來測試:

For the graph below we measure the time it takes to download and compile a WebAssembly module with 67 MB and about 190,000 functions. We do the measurements with 25 Mbit/sec, 50 Mbit/sec, and 100 Mbit/sec download speed.

可以看到網路不夠快的使用者就會直接被 compile 速度跟上,讓瀏覽器在下載時就做一些事情。

另外在某些情況下對 Array 的操作會有大幅改善:

這些新功能與改善都會在 Chrome 65 推出。依照「Chrome Platform Status」這邊的資料,stable 版預定在三月初,beta 版應該是要出了... (雖然上面寫著 2/1,但目前好像還沒更新)

Cloudflare 也能在各端點跑 JavaScript 了

類似於 AWS 先前推出的 Using CloudFront with Lambda@Edge (參考「在 CloudFront 的 edge 上跑 Lambda」以及「Lambda@Edge 的 GA」),Cloudflare 也推出了類似的功能:「Introducing Cloudflare Workers: Run Javascript Service Workers at the Edge」、「Code Everywhere: Why We Built Cloudflare Workers」。

整個系統是架構在 Chrome V8 上,尤其是安全性的部分是 Cloudflare 的人頗讚賞的重點:

Security: The V8 JavaScript engine is arguably the most scrutinized code sandbox in the history of computing, and the Chrome security team is one of the best in the world. Moreover, Google pays massive bug bounties to anyone who can find a vulnerability. (That said, we have added additional layers of our own sandboxing on top of V8.)

比較不一樣的地方在於 Cloudflare 拿 Service Worker API 來設計他們的架構,AWS 則是自己幹了一套出來...

然後現在還沒給出價錢,也還沒完全開放使用... 想要玩的人需要申請 beta。

V8 對 Hash Flooding 的防禦措施

Hash Flooding 問題是指 Hash 這個資料結構是可以被預測 collision 所造成的問題,在隨機的情況下會是 O(1) 的操作,在特定挑選故意讓他 collision 而變成 O(n),當有 n 個元素時,乘起來就會變成 O(n^2)。這算是一種阻斷攻擊 (DoS attack)。

在「About that hash flooding vulnerability in Node.js...」這邊提到了 V8 之前為了避免 Hash Flooding 的問題,關掉了 Startup snapshot 而造成的效能問題,以及後續的很多故事,最後找了長期的解法。

這個解法已經併入 Node.js 裡,預定下個包括的版本是 8.3.0:

The patch to re-enable startup snapshot has been merged into Node.js. It is part of the recent Node.js v8.3.0 release.

不過這表示現有的 LTS (4.8.4 以及 6.11.2) 還是... XD

V8 對 for-in 的最佳化

V8 引擎的人對 for-in 的最佳化寫了一篇解釋「Fast For-In in V8」,比較直接的結果就是維基百科Facebook 都變快了:

For example, in early 2016 Facebook spent roughly 7% of its total JavaScript time during startup in the implementation of for-in itself. On Wikipedia this number was even higher at around 8%.

可以看得出來是挑比較大的來改,而下一版的 Google Chrome (57) 將會對 for-in 會到另外一個極致:

The most important for-in helpers are at position 5 and 17, accounting for an average of 0.7% percent of the total time spent in scripting on a website. In Chrome 57 ForInEnumerate has dropped to 0.2% of the total time and ForInFilter is below the measuring threshold due to a fast path written in assembler.

主要是因為 spec 對 for-in 的定義寫得很模糊,所以就有很多實作的空間可以調整:

When we look at the spec-text of for-in, it’s written in an unexpectedly fuzzy way,which is observable across different implementations.

Google Chrome 55 的記憶體改善

前陣子 Google Chrome 55 出了,其中最讓人期待的是對記憶體的改善,有人整理了數據:「Chrome 55 uses ~30% less memory than Chrome 54」。

依照作者拿 weather.comreddit.com 測試,前者的記憶體省了 26%,後者省了 30%,都相當明顯。我自己在升到 55 後有明顯感覺到改善,尤其是重開 Chrome 時重新讀取頁面的速度也快了不少...

這些改善主要是出自於「Fall cleaning: Optimizing V8 memory consumption」這邊提到對 V8 engine 的改寫,我感覺到速度變快應該是記憶體用量降低使得 CPU cache rate 提高的關係吧...

V8 JavaScript 引擎將支援 WebAssembly

V8 JavaScript 引擎宣佈支援 WebAssembly:「Experimental support for WebAssembly in V8」。

依照說明,看起來在 Google Chrome 51 之後的版本 (目前是在 Chrome Canary) 可以打開 chrome://flags#enable-webassembly 啟用 WebAssembly 測試。

目前還是只有想到電玩遊戲之類的用途...

V8 Engine 的 Math.random() 在新版被重寫了...

先前在「V8 的 Math.random() 亂度不足的問題」提到 Math.random() 因為使用 MWC1616 (Fast random number generation using 128 bit multimedia extension registers on Pentium class machines) 而不夠亂的問題。

這個問題在新版 V8 Engine 提出改善了:「There's Math.random(), and then there's Math.random()」。

Untitled drawing

新實作的方法是 xorshift128+,擁有極長的 period length:

This has been pointed out to us, and having understood the problem and after some research, we decided to reimplement Math.random based on an algorithm called xorshift128+. It uses 128 bits of internal state, has a period length of 2128 - 1, and passes all tests from the TestU01 suite.

將會在 Google Chrome 49 (目前是 47) 引入:

The new implementation landed in V8 4.9.41.0 within a few days of us becoming aware of the issue. It will become available with Chrome 49. Both Firefox and Safari switched to xorshift128+ as well.

同時還是再次提醒,這不是 CSPRNG,要用在密碼學相關應用還是要用專門的 library 來產生 pseudo random number:

Make no mistake however: even though xorshift128+ is a huge improvement over MWC1616, it still is not cryptographically secure.

V8 的 Math.random() 亂度不足的問題

在「TIFU by using Math.random()」這篇看到作者踩到地雷,於是在討論 V8 EngineMath.random() 的亂度不足。

其實這個問提早在 2012 年就有人在 StackOverflow 上詢問:「Why is Google Chrome's Math.random number generator not *that* random?」,而且也回答得很清楚。

而 Mozilla 這邊在 2006 年也被提出了類似的問題:「Bug 322529 - Upgrade Math.random() to a better algorithm, such as Mersenne Twister」。

文章中間花了許多篇幅講 PRNG 的介紹,以及 cycle length 的說明,重點其實在結論的部份。

主要是因為 V8 Engine 的 Math.random() 實作的是 MWC1616 演算法 (Fast random number generation using 128 bit multimedia extension registers on Pentium class machines),而這個演算法用起來也綁手綁腳:

If you’re only using the most significant 16 bits it has a very short effective cycle length (less than 2³⁰).

有兩個方向可以改善 (不衝突的方向),一個是使用 CSPRNG (保證有極長的 cycle length),另外一個請求 V8 Engine 把 Math.random() 的演算法換掉,像是 MT19937 這類 cycle length 超級長的演算法。

不知道後續有沒有機會改善...