關于JavaScript的的高速緩存未命中分析
在本文中，我們將討論創建和訪問數據的方式可能對應用程序性能的影響。
介紹
JavaScript是一種非常高級的語言，在使用JavaScript開發的時候不必對存儲器中的數據存儲方式作過多的考慮。在本文中，我們將探討數據如何存儲在內存中，以及JavaScript中分發和訪問數據的方式將如何影響CPU和內存的性能。
浪漫三角
當計算機需要進行一些計算任務時，計算機處理單元(CPU)需要數據進行處理，因此，根據手中的任務，它將發送請求到內存以通過總線獲取待處理的數據，就像下面這樣：
這就是我們的浪漫三角
CPU->總線->內存
浪漫三角需要第四個元素來保持穩定
由于CPU比內存快得多，因此從CPU->總線->內存->總線->CPU這樣的處理方式就浪費了很多計算時間，因為查找內存時，CPU處于空閑狀態而無法執行其他操作。
緩存的出現有效的緩解了這個問題。在本文中我們不會詳細討論緩存的技術細節和類型，我們只需要知道緩存可以作為CPU的一個內部存儲空間。
當CPU接收到要運行的命令時，它將首先在高速緩存中搜索目標數據，如果沒有搜索到目標數據，它再通過總線發起請求。
然后，總線將請求的數據加上一部分內存，將其存儲在高速緩存中以供CPU快速調用。
這樣一來，CPU就能夠有效的處理數據，而不會浪費時間等待內存返回。
高速緩存的引用也可能導致新的問題
基于上面的架構，我們在處理大量數據時可能會出現一種名為”高速緩存未命中”的錯誤。
高速緩存未命中意味著在計算期間，CPU發現高速緩存中沒有必要的數據，因此需要通過常規通道(即已知的慢速存儲器)來請求此數據。
上圖是一個很好的實例，在處理組中數據是，由于計算的數據超出了緩存限制的數據，就導致了緩存未命中。
可是這跟我作為JavaScript程序員有什么關系呢?
好問題，大多數情況下，我們JavaScript開發人員不必關心這個問題。但是隨著越來越多的數據涌入Node.js服務器甚至富客戶端，所以當使用JavaScript遍歷大型數據集時就容易遇見緩存未命中的問題。
一個經典的例子
接下來讓我們以一個例子作為說明。
這是一個叫做Boom的類：
- class Boom {
- constructor(id) {
- this.id = id;
- }
- setPosition(x, y) {
- this.x = x;
- this.y = y;
- }
- }
此類(Boom)僅具有3個屬性：id，x和y。
現在，讓我們創建一個填充x和y的方法。
讓我們構建設置：
- const ROWS = 1000;
- const COLS = 1000;
- const repeats = 100;
- const arr = new Array(ROWS * COLS).fill(0).map((a, i) => new Boom(i));
現在，我們將在一種方法中使用此設置：
- function localAccess() {
- for (let i = 0; i < ROWS; i++) {
- for (let j = 0; j < COLS; j++) {
- arr[i * ROWS + j].x = 0;
- }
- }
- }
本地訪問的作用是線性遍歷數組并將x設置為0。
如果我們重復執行此功能100次(請查看設置中的重復常數)，則可以測量運行時間：
- function repeat(cb, type) {
- console.log(`%c Started data ${type}`, 'color: red');
- const start = performance.now();
- for (let i = 0; i < repeats; i++) {
- cb();
- }
- const end = performance.now();
- console.log('Finished data locality test run in ', ((end - start) / 1000).toFixed(4), ' seconds');
- return end - start;
- }
- repeat(localAccess, 'Local');
日志輸出是這樣的：
丟失緩存要付出的代價
現在，根據上面的了解，如果我們處理迭代過程中距離較遠的數據，則會導致緩存丟失。遠處的數據是不在相鄰索引中的數據，如下所示：
- function farAccess() {
- for (let i = 0; i < COLS; i++) {
- for (let j = 0; j < ROWS; j++) {
- arr[j * ROWS + i].x = 0;
- }
- }
- }
在這里發生的是，在每次迭代中，我們都處理上次迭代距ROWS的索引。因此，如果ROWS為1000(在我們的例子中)，我們將得到以下迭代：[0，1000，2000，…，1，1001，2001，…]。
讓我們將其添加到速度測試中：
- repeat(localAccess, 'Local');
- setTimeout(() => {
- repeat(farAccess, 'Non Local');
- }, 2000);
這是最終結果：
非本地迭代速度幾乎慢了4倍。隨著數據量的增加，這種差異將越來越大。發生這種情況的原因是由于高速緩存未命中，CPU處于空閑狀態。
那么您要付出的代價是什么?這完全取決于您的數據大小。
好吧，我發誓我永遠不會那樣做!
您通常可能不這么認為，但在某些情況下，您可能會希望使用非線性(例如1,2,3,4,5)或非偶然性。比如( for (let i = 0; i < n; i+=1000))
例如，您從服務或數據庫中獲取數據，并需要通過某種復雜的邏輯對數據進行排序或過濾。這可能導致訪問數據的方式與farAccess函數中顯示的方式類似。
如下所示：
查看上圖，我們看到了存儲在內存中的數據(頂部灰色條)。在下面，我們看到了當數據從服務器到達時創建的數組。最后，我們看到排序后的數組，其中包含對存儲在內存中各個位置的對象的引用。
這樣，對排序后的數組進行迭代可能會導致在上面的示例中看到的多個緩存未命中。
請注意，此示例適用于小型陣列。高速緩存未命中與更大的數據有關。
在當今世界中，您需要在前端使用精美的動畫，并且可以在后端(無服務器或其他服務器)中為CPU的每毫秒時間計費(這很關鍵)。
不好了!都沒了!!!
并不是，有多種解決方案可以解決此問題，現在您已經知道造成性能下降的原因，您可以自己考慮解決方案。比如只需要將處理在一起的數據更緊密地存儲在內存中。
這種技術稱為數據局部性設計模式。
讓我們繼續我們的例子。假設在我們的應用程序中，最常見的過程是使用farAccess函數中顯示的邏輯來遍歷數據。我們希望對數據進行優化，以使其在最常見的for循環中快速運行。我們將像這樣排列相同的數據：
- const diffArr = new Array(ROWS * COLS).fill(0);
- for (let col = 0; col < COLS; col++) {
- for (let row = 0; row < ROWS; row++) {
- diffArr[row * ROWS + col] = arr[col * COLS + row];
- }
- }
所以現在在diffArr中，原始數組中索引為[0,1,2，…]的對象現在被設置為[0,1000,2000，…，1，1001，2001，…，2， 1002，2002，…]。數字表示對象的索引。這模擬了對數組進行排序的方法，這是實現數據局部性設計模式的一種方法。
為了方便測試，我們將稍微更改farAccess函數以獲得一個自定義數組：
- function farAccess(array) {
- let data = arr;
- if (array) {
- data = array;
- }
- for (let i = 0; i < COLS; i++) {
- for (let j = 0; j < ROWS; j++) {
- data[j * ROWS + i].x = 0;
- }
- }
- }
現在將場景添加到我們的測試中：
- repeat(localAccess, 'Local');
- setTimeout(() => {
- repeat(farAccess, 'Non Local')
- setTimeout(() => {
- repeat(() => farAccess(diffArr), 'Non Local Sorted')
- }, 2000);
- }, 2000);
我們運行它，我們得到：
我們已經優化了數據，以適應需要查看的更常見的方式。
完整示例參見
https://yonatankra.com/performance/memory/liveExamples/objectPool2/index.html
