進階電腦系統理論與實作 (Fall 2017)
contributed by < jcyztw
, davidshih0908
>
使用 lscpu
指令查詢 cache size。
可看到我的電腦 CPU 使用 32 KB 的 L1 data cache,32 KB 的 L1 instruction cache,以及 2 MB 的 L2 cache。
在開始進行作業最主要的要求(降低 cache miss)前,先看看未優化程式的效能檢測數據。
首先先編譯程式,在本機存放 phonebook 原始碼的目錄下輸入以下指令:
$ make
$ make plot
得到結果如下:
__PHONE_BOOK_ENTRY
的 structure size__PHONE_BOOK_ENTRY
的 structure size未優化
優化
由上面的數據可看出,縮減 structure 的 size 讓 miss rate 由 40.955% 降到了 4.534%,幾乎是變成原先 miss rate 的一成。
接續方案 1 繼續改進,用 hash table 取代原先 linked list,將 hashing 實作到 append()
和 findName()
中。
而 hash function 如下:
此 hash function 採用一個比資料筆數大的一個質數(42737)作為 hash table size,以減少碰撞(collision)。
檢測結果如下:
由圖中可看到 findName()
在改用 hash function 的實作方式後,花費的時間遠遠少於方案 1。
hash function 優化後 miss rate 上升,可能是因為改 main.c 時,我把__builtin___clear_cache
這東西拿掉導致。此現象的原因有待釐清。
可看出大多不是真實英文姓名,與實際上的應用有落差,因此個人判斷比較不具有代表性。
參考 ierosodin 實作 memory pool 的程式碼,依樣畫葫蘆實作,測試看看使用 memory pool 可以將 miss rate 降到多低。
我在實作 memory pool 時,是基於 hash table 方案來加以改善,兩者差別只是在建立電話簿中的資料時 ( append()
),每筆 entry 配置記憶體的方式不同。hash table 的作法是使用 malloc()
配置記憶體,而 memory pool 是用一開始配置好的 pool 直接指定可使用的記憶體位址。
上面的程式碼為 memory pool 優化方案透過 pool_alloc()
直接指定可使用的記憶體位址。
以下是 memory pool 相關操作 (create, allocate, free) 的程式碼片段:
比較 miss rate:
original | resized structure | hash table | memory pool |
---|---|---|---|
87.693% | 51.938% | 43.080% | 37.338% |
由下圖可看出 memory pool 方案是所有情況中 append()
以及 findName()
中執行時間花費最短的。
search engine
,ex: google search 中,當你輸入 mississipp
, google search 會建議你要不要搜尋 mississippi
。Levenshtein distance
是將一字串轉換成另一個字串所需之編輯次數,能使用的編輯方式有 insertions , deletions or substitutions,而且視這3個 operation 的 cost 是一樣的,所以總 cost 就是 總編輯次數 x 每編輯一次的 cost
。
其數學式是
以字串 kitten
與 sitting
來做示範
我想將 kitten
轉變成 sitting
1.kitten -> sitten (s取代k)
2.sitten -> sittin (i取代e)
3.sittin -> sitting (字串尾加上g)
所以總編輯次數為 3
。
在實作上可以採用 recursive
或者 iterative
recursive
是個不有效率的做法,會有大量的重複計算,所以我這裡就不介紹了。
iterative
的話可以採用 Wagner–Fischer algorithm
來實作。
Wagner–Fischer algorithm:
利用 dynamic programming
的方式算兩字串的編輯距離。
其演算法為:
很直接的就是設初值,然後開始建 table
上述以 GARVEY
和 AVERY
為例,算出 edit distance
為 3
是建立在 Levenshtein distance
的基礎上的樹狀資料結構。
一開始假如有一棵樹
其中邊的數值,以 BOOK
與 BOOKS
相連的邊為例,數值為1
,是因為 BOOK
與 BOOKS
的 Levenshtein distance
為1
BK-trees
插入的規則:
root
的 Levenshtein distance
, 這裡我另為 n
,接著看 root
的子結點有哪個與 root
的 Levenshtein distance
為 n
,沒有的話直接把新增的字串插在 root
底下,有的話接著那個與 root
Levenshtein distance
相距為 n
DFS
的方式做下去,最終可以找到插入的點。假如我今天想插入一個為字串 BOO
,首先先與 root 也就是 BOOK
算出之間的 Levenshtein distance
為 1
然後再繼續跟 BOOKS
比較 Levenshtein distance
為 2
然後無從比較了,就將點插在 BOOKS
後面。
BK-trees
找相似字串的規則:
先決定你可以允許多大的容錯程度,這裡我另容錯程度為 : n
,所以也就是在兩字串的 Levenshtein distance
加減 n 的範圍內的字串皆是我可以搜尋的目標,並且假如搜尋目標與 search partern
的 Levenshtein distance
n
,便可以將它加入可能是想要的搜尋的字串中。
以搜尋 CAQE
為例 :(另: n = 1)
(1) CAQE
先與 BOOK
算出 Levenshtein distance
為 4
,4
並未小於 n = 1
,所以 BOOK
並未加入可能想要搜尋的字串內,又因為 n = 1
,所以搜尋字串的 range
為 (4-1,4+1) = (3,5)
。
(2) 接著看有無與 BOOK(root)
Levenshtein distance
介於 (3,5)
的字串,看到 CAKE
是個選擇,於是再拿 CAQE
與 CAKE
算 Levenshtein distance
結果為 1
,1
小於等於 n = 1
,所以可以將 CAKE
納入可能想要搜尋的字串中,並且算出接下來搜尋字串的範圍為 (1-1,1+1) = (0,2)
。
(3) 接著繼續依上述範圍找與 CAKE
Levenshtein distance
在上述範圍的字串,發現 CAPE
是個選擇,於是拿 CAQE
與 CAPE
算 Levenshtein distance
結果為 1
,1
小於等於 n = 1
,所以可以將 CAPE
納入可能想要搜尋的字串中。
(4) 因為此搜尋是採 DFS
所以退回 CAKE
看有無符合搜尋範圍為 (0,2)
,發現 CART
也符合,,於是拿 CAQE
與 CAPE
算 Levenshtein distance
結果為 2
,2
並未小於等於 n = 1
,所以CART
並未納入可能想要搜尋的字串中。
所以最後在容錯為 1
的情況下,可能是想要搜尋的字串有 CAKE
,CAPE
。