跳轉至

記憶體與快取 *

在本章的前兩節中,我們探討了陣列和鏈結串列這兩種基礎且重要的資料結構,它們分別代表了“連續儲存”和“分散儲存”兩種物理結構。

實際上,物理結構在很大程度上決定了程式對記憶體和快取的使用效率,進而影響演算法程式的整體效能。

計算機儲存裝置

計算機中包括三種類型的儲存裝置:硬碟(hard disk)記憶體(random-access memory, RAM)快取(cache memory)。下表展示了它們在計算機系統中的不同角色和效能特點。

  計算機的儲存裝置

硬碟 記憶體 快取
用途 長期儲存資料,包括作業系統、程式、檔案等 臨時儲存當前執行的程式和正在處理的資料 儲存經常訪問的資料和指令,減少 CPU 訪問記憶體的次數
易失性 斷電後資料不會丟失 斷電後資料會丟失 斷電後資料會丟失
容量 較大,TB 級別 較小,GB 級別 非常小,MB 級別
速度 較慢,幾百到幾千 MB/s 較快,幾十 GB/s 非常快,幾十到幾百 GB/s
價格 較便宜,幾毛到幾元 / GB 較貴,幾十到幾百元 / GB 非常貴,隨 CPU 打包計價

我們可以將計算機儲存系統想象為下圖所示的金字塔結構。越靠近金字塔頂端的儲存裝置的速度越快、容量越小、成本越高。這種多層級的設計並非偶然,而是計算機科學家和工程師們經過深思熟慮的結果。

  • 硬碟難以被記憶體取代。首先,記憶體中的資料在斷電後會丟失,因此它不適合長期儲存資料;其次,記憶體的成本是硬碟的幾十倍,這使得它難以在消費者市場普及。
  • 快取的大容量和高速度難以兼得。隨著 L1、L2、L3 快取的容量逐步增大,其物理尺寸會變大,與 CPU 核心之間的物理距離會變遠,從而導致資料傳輸時間增加,元素訪問延遲變高。在當前技術下,多層級的快取結構是容量、速度和成本之間的最佳平衡點。

計算機儲存系統

Tip

計算機的儲存層次結構體現了速度、容量和成本三者之間的精妙平衡。實際上,這種權衡普遍存在於所有工業領域,它要求我們在不同的優勢和限制之間找到最佳平衡點。

總的來說,硬碟用於長期儲存大量資料,記憶體用於臨時儲存程式執行中正在處理的資料,而快取則用於儲存經常訪問的資料和指令,以提高程式執行效率。三者共同協作,確保計算機系統高效執行。

如下圖所示,在程式執行時,資料會從硬碟中被讀取到記憶體中,供 CPU 計算使用。快取可以看作 CPU 的一部分,它透過智慧地從記憶體載入資料,給 CPU 提供高速的資料讀取,從而顯著提升程式的執行效率,減少對較慢的記憶體的依賴。

硬碟、記憶體和快取之間的資料流通

資料結構的記憶體效率

在記憶體空間利用方面,陣列和鏈結串列各自具有優勢和侷限性。

一方面,記憶體是有限的,且同一塊記憶體不能被多個程式共享,因此我們希望資料結構能夠儘可能高效地利用空間。陣列的元素緊密排列,不需要額外的空間來儲存鏈結串列節點間的引用(指標),因此空間效率更高。然而,陣列需要一次性分配足夠的連續記憶體空間,這可能導致記憶體浪費,陣列擴容也需要額外的時間和空間成本。相比之下,鏈結串列以“節點”為單位進行動態記憶體分配和回收,提供了更大的靈活性。

另一方面,在程式執行時,隨著反覆申請與釋放記憶體,空閒記憶體的碎片化程度會越來越高,從而導致記憶體的利用效率降低。陣列由於其連續的儲存方式,相對不容易導致記憶體碎片化。相反,鏈結串列的元素是分散儲存的,在頻繁的插入與刪除操作中,更容易導致記憶體碎片化。

資料結構的快取效率

快取雖然在空間容量上遠小於記憶體,但它比記憶體快得多,在程式執行速度上起著至關重要的作用。由於快取的容量有限,只能儲存一小部分頻繁訪問的資料,因此當 CPU 嘗試訪問的資料不在快取中時,就會發生快取未命中(cache miss),此時 CPU 不得不從速度較慢的記憶體中載入所需資料。

顯然,“快取未命中”越少,CPU 讀寫資料的效率就越高,程式效能也就越好。我們將 CPU 從快取中成功獲取資料的比例稱為快取命中率(cache hit rate),這個指標通常用來衡量快取效率。

為了儘可能達到更高的效率,快取會採取以下資料載入機制。

  • 快取行:快取不是單個位元組地儲存與載入資料,而是以快取行為單位。相比於單個位元組的傳輸,快取行的傳輸形式更加高效。
  • 預取機制:處理器會嘗試預測資料訪問模式(例如順序訪問、固定步長跳躍訪問等),並根據特定模式將資料載入至快取之中,從而提升命中率。
  • 空間區域性:如果一個數據被訪問,那麼它附近的資料可能近期也會被訪問。因此,快取在載入某一資料時,也會載入其附近的資料,以提高命中率。
  • 時間區域性:如果一個數據被訪問,那麼它在不久的將來很可能再次被訪問。快取利用這一原理,透過保留最近訪問過的資料來提高命中率。

實際上,陣列和鏈結串列對快取的利用效率是不同的,主要體現在以下幾個方面。

  • 佔用空間:鏈結串列元素比陣列元素佔用空間更多,導致快取中容納的有效資料量更少。
  • 快取行:鏈結串列資料分散在記憶體各處,而快取是“按行載入”的,因此載入到無效資料的比例更高。
  • 預取機制:陣列比鏈結串列的資料訪問模式更具“可預測性”,即系統更容易猜出即將被載入的資料。
  • 空間區域性:陣列被儲存在集中的記憶體空間中,因此被載入資料附近的資料更有可能即將被訪問。

總體而言,陣列具有更高的快取命中率,因此它在操作效率上通常優於鏈結串列。這使得在解決演算法問題時,基於陣列實現的資料結構往往更受歡迎。

需要注意的是,高快取效率並不意味著陣列在所有情況下都優於鏈結串列。實際應用中選擇哪種資料結構,應根據具體需求來決定。例如,陣列和鏈結串列都可以實現“堆疊”資料結構(下一章會詳細介紹),但它們適用於不同場景。

  • 在做演算法題時,我們會傾向於選擇基於陣列實現的堆疊,因為它提供了更高的操作效率和隨機訪問的能力,代價僅是需要預先為陣列分配一定的記憶體空間。
  • 如果資料量非常大、動態性很高、堆疊的預期大小難以估計,那麼基於鏈結串列實現的堆疊更加合適。鏈結串列能夠將大量資料分散儲存於記憶體的不同部分,並且避免了陣列擴容產生的額外開銷。