owned this note   changed 7 years ago  
Linked with GitHub

2018q1 Homework1 (phonebook)

contributed by <YuanHaoHO>

Reviewed by <mrwenwei>

  • github commit 只有標題，以及沒有太大意義的內容。
  • hackmd 編輯方式可參考功能介紹，讓你的程式碼更具有可讀性。

Reviewed by catpig1630

  • 可以試著嘗試使用hash table，看看效能會不會提升。

開發環境

hoyuanhao@hoyuanhao-X550VB:~$ lscpu 
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              58
Model name:            Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
製程：              9
CPU MHz：             1203.109
CPU max MHz:           3200.0000
CPU min MHz:           1200.0000
BogoMIPS:              5188.13
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

處理目標

1.降低cache-miss的比率
2.降低 findName()時間
3.降低append()時間

程式碼回顧

這次功課主要處理的目標在於有關優化後時間與cache-miss上的差異，所以主要是爭對phonebook_opt與main.c上著手更改，先從main.c開始看：

  • <time.h>和clock_gettime()
    在main.c中是使用CLOCK_REALTIME這種計時方式，並且將其運用在diff_in_second這個static double的function中，
    用以計算每次跑搜尋的時間差。
  • malloc()函式的運用
    使用malloc()動態配置去即時抓取資料指標，並同時計算資料抓取索花費之時間。妥善運用動態配置可以省去多數不常被使用的變數，防止其佔取空間。
    參考：molloc()動態配置

main.c上主要是在進行動態讀取txt檔與計算時間，並沒有進一步去進行更改讀取效果或著套用資料結構，而運用OPT這個變數來分化是origin還是optimal，如此再從phonebook_opt.[hc]上看其程式碼內容：

  • 同樣運用malloc（）去取得動態配置並往下分配記憶體給新的值
/\* allocate memory for the new entry and put lastName */

e = e->pNext   = (entry *) malloc(sizeof(entry));

e = e->pNext;

 strcpy(e->lastName, lastName);

e->pNext   =   NULL;
  • 在phonebook_opt.h可以觀察到，在__PHONE_BOOK_ENTRY被分為許多組字元陣列來儲存資料，並將其指標儲存於pNext中，以待動態配置運用。
typedef   struct   \_\_PHONE\_BOOK_ENTRY {
    
    char lastName\[MAX\_LAST\_NAME_SIZE\];//只有這裡再搜索時會運用到
    char firstName\[16\];
    char email\[16\];
    char phone\[10\];
    char cell\[10\];
    char addr1\[16\];
    char addr2\[16\];        
    char city\[16\];
    char state\[2\];
    char zip\[5\];

    struct   __PHONE_BOOK_ENTRY* pNext;

} entry;

解決方向

當CPU在快速的搬運資料時會使用到cache，然而因為cache空間及為有限，所以如果沒有在搬運資料時，妥善運用搬運空間，cache-miss rate 上升，而整體效能下降。目前主要解決方向式讓搬運內容比例上升還有減少搜索時間，如此可以向鎖定精確區域搜索，和增加一次可搬運的量。

解決方法

  • 在搜索區域上只留下結構指標和lastName
    參考ryanwang的做法，先用註解的方式拿掉其他資料，看看執行結果如何。

資料比較

chche-test

origin

execution time of findName() : 0.005664 sec

 Performance counter stats for './phonebook_orig' (100 runs):

         2,269,002      cache-misses              #   83.264 % of all cache refs      ( +-  0.19% )
         2,725,054      cache-references                                              ( +-  0.24% )
       322,678,743      instructions              #    1.06  insns per cycle          ( +-  0.02% )
       303,609,265      cycles                                                        ( +-  1.27% )

       0.102145149 seconds time elapsed                                          ( +-  1.33% )

perf stat --repeat 100 \
        -e cache-misses,cache-references,instructions,cycles \
        ./phonebook_opt

opt

Performance counter stats for './phonebook_opt' (100 runs):

           283,392      cache-misses              #   58.172 % of all cache refs      ( +-  0.33% )
           487,162      cache-references                                              ( +-  1.08% )
       279,804,090      instructions              #    1.52  insns per cycle          ( +-  0.02% )
       184,513,078      cycles                                                        ( +-  0.72% )

       0.062222535 seconds time elapsed                                          ( +-  0.77% )

./calculate
gnuplot scripts/runtime.gp

執行時間比較

問題討論

在這次實驗上，我同我同學一起研究，發現再硬體設備上的差異，對於cache-miss上的比率有很大的關係，我使用的筆電在cache上的大小不大，為：

L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K

如此同樣使用拿掉其他無用的資料的方法我的cache-miss從83%降至58%，而我的同學硬體設備更好，一開始的cache-miss就比我低很多，在attend()上所花的時間也比我更少，如此因硬體設備而影響數據，造就大家在coding上的結果也會受到快取的大小而改變。

Select a repo