Try   HackMD

2016q3 Homework 1 (phonebook)

contributed by <louis222220>

前置作業

  • 灌好雙系統(Ubuntu 16.04)
  • markdown的使用
  • 了解github的基礎使用
  • 了解Perf的基礎使用
  • 在看完幾份資料之後，又重新看了老師的講解影片

開發環境

  • Operating System: Ubuntu 16.04 LTS (64bit)
  • CPU: 8-core, Intel i7-2630QM 2.00GHz
  • Memory: 16GB
  • Cache:
    • L1d cache: 32K
    • L1i cache: 32K
    • L2 cache: 256K
    • L3 cache: 6144K
      使用 lscpu(總覽) 和 sudo lshw(詳細) 可看到硬體資訊
      (參考鄧安哲同學共筆)

優化方案

  • 使用體積較小的 struct
  • 使用 hash function
  • Binary Tree

開發紀錄

  • 一開始發現opt跟orig畫了一樣的圖，後來參考上學期王紹華的共筆解決了問題，開始著手思考程式碼

1. 縮小struct

把目前搜尋時不會用到的欄位放到額外的struct(稱detail)
減少了alloc記憶體跟cache miss的時間成本
(不過前題是，我們還不需要用到那些detail資訊，所以根本沒有分配記憶體)

  • FindName()的搜尋時間幾乎降為原本的一半

  • struct縮小 -> 記憶體alloc減少 -> cache miss大幅下降

ori的72%:

opt下降至29%

2.hash function

未了解

  • Perf的三種事件種類
  • clock_gettime

略過沒看

  • Perf的==>補充資料
  • Programming small - Swapping in C, C++, and Java

參考資料

瑣碎

Last changed by 
 
Louis Su
0
388
Published on HackMD