contributed by <yanzijun
>
因為看到 @aweimeow 與 @louielu 共筆有使用lstopo套件,因此也決安裝一下,以便獲取更多詳細的cache資料,方便後面的分析。
非常順利的安裝完成了,沒有噴任何錯誤..
那就開啟lstopo吧!
因為我只要看 cache 資料,所以透過 –no-io 參數,使其不輸出I/O 裝置等資料
輸出
先看Kernel config 有沒有開啟 Perf , PC安裝一般 Linux distro ,預設應該有開。
如有開啟其值應該會是y
開始安裝perf
接著輸入perf top 查看系統目前各個函式再Event上的效能
應該會出現下面這種情形
透過sudo執行,即可看到perf top的分析
但可透過kernel.perf_event_paranoid 來決定你在沒有 root 權限下 (Normal User) 使用 perf 時,你可以取得哪些 event data。預設值是 1 ,可以輸入
來查看權限值。一共有四種權限值:
2
: 不允許任何量測。但部份用來查看或分析已存在的紀錄的指令仍可使用,如 perf ls、perf report、perf timechart、 perf trace。
1
: 不允許 CPU events data。但可以使用 perf stat、perf record 並取得 Kernel profiling data。
0
: 不允許 raw tracepoint access。但可以使用 perf stat、perf record 並取得 CPU events data。
-1
: 權限全開。
最後如果要檢測 cache miss event ,需要先取消 kernel pointer 的禁用。
安裝astyle
調整作業風格要求如下
安裝 Git pre-commit hook 可在每次 git commit 時,檢查 C/C++ 原始程式碼的風格是否一致:
先針對未優化過版本進行 cache-miss, cache-references, instructions, cycles 執行100次的分析
輸出結果
其cach-misses 高達 95.686%
查看執行效率
輸出
phonebook_orgi.h
中的code再找電話簿資料中,一般來說我們是以找姓名或住址等一項進行索引,找到符合後才去看相關資料如:電話、住址、Email、姓名等。這裡的程是以找lastName為主,但結構中卻有一大堆其他的資料,好比資料庫搜尋姓名卻把所有欄位都列入搜尋。
因此我們先把一些資料放在另一結構中,等有需要的時候再讀取
此處我要澄清一件事,就是我沒寫過C語言…
所以關於struct這邊的寫法是參照 aweimeow 的寫法,關於struct以前高中練演算法常見也知道是什麼,但畢竟對於C語言沒有開發經驗跟研讀,所以語法都是邊查邊問,如果有錯或不好之處請告知。
修改完畢後,cache-misses
已經下降至 73.224%
可以發現size of entry 僅剩下 32 bytes
與原先的 136bytes
差了100多 bytes, append
與 findName
的時間也都有下降。
L1 cache: 32K / Phonebook size: 136 Bytes => 約30筆 entry
L1 cache: 32K / Phonebook size: 32 Bytes => 約128筆 entry
能存放的筆數已經是原本約4倍,但35萬筆之料當中,其存放的量仍然相當的少,代表我們還有很大的進步空間。
新增main_hash.c
、 phonebook_hash.c
、 phonebook_hash.h
3個檔案
修改calculate.c
、 Makefile
2個檔案
phonebook_hash.h
複製 phonebook_opt.h
來修改此處使用pointer to pointer 使為了串接碰撞資料(這裡有點不懂,需再提問)
參考資料:TempoJiJi 學長共筆
修改函數 *findName
函數,第二個參數改用hashTable去做,而不再用pHead
串列去找,大幅下降findName
時間
append
函數,第二個參數也是用hashTable,但回傳型態修改為void,原本會再回傳entry
,這裡直接用HashTable,所以不用回傳。
重新宣告函數,並新增 createHashTable
與 hash
函數
phonebook_opt.c
為 phonebook_hash.c
進行修改新增 hash 函數,採用BKDR Hash
法
參考資料:各項Hash比對
有關為何要乘上一個seed係數
參考資料:Programming Small
新增 createHashTable
製作Hash Table
重新修改 findName 方式,採用HashTable能下降速度及減少cache-miss
修改 append 方式,改用無回傳值直接併入Hash Table
main.c
為 main_hash.c
來做修改建立Hash Table,呼叫 createHashTable
函數
修改 append
方式,原本為
因為改用Hash Table不用回傳,修改為
找到
將 findName
第二個參數改為Hash Table
Makefile
內相關設定新增一個共同編譯的main_hash.c
catch-test 部份再加 hash的測試
output.txt
,而calculate就是負責計算這部份添加
修改輸出至 outout.txt
資料
原本僅有兩個 %lf
放 org i
、opt
的數據,增加一個放hash的數據
使用 Hash 後,cahce-miss已經下降至59%,findName時間也減少很多
cache-miss rate
已經降低,findName
速度也下降很多,但 append
卻比原本還高許多,大概是opt版本的兩倍
append 時間變長,有些學長姐之前共筆有相關紀錄:
=目前進度=
9/28 教師節快樂