# 2016q3 Homework 1 (phonebook)
###### tags: `sysprog21` `JongSyuGithub` `cache miss`

contributed by <`JonSyuGithub`>
github: https://gtihub.com/JonSyuGithub/phonebook

contributed by <`JonSyuGithub`>
>>請依照指定格式填寫標題和"contributed by" [name=課程助教]
>>已更正 [name=JonSyuGithub]

## Environment
* OS: Ubuntu 16.04 LTS
* CPU: [i5-457](http://ark.intel.com/products/75043/Intel-Core-i5-4570-Processor-6M-Cache-up-to-3_60-GHz)
* Cache ($ lscpu | grep cache)
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 6144K
* Memory 12GB ($ cat /proc/meminfo)

* Update & Install

$ sudo apt-get update
$ sudo apt-get install build-essential
$ sudo apt-get install linux-tools-common linux-tools-generic
$ sudo apt-get install astyle colordiff gnuplot

* Github

$ git clone https://github.com/JonSyuGithub/phonebook
			
# setting parameter
$ git config --global user.email "your e-mail"
$ git config --global user.name "your name"
$ git config --global push.default matching
$ git remote set-url origin https://github.com/github/phonebook.git
			
# update 
$ git add .
$ git commit -m "modify XXX"
$ git push

## Objective
* try reducing cache miss

## Original Version
* Compile & Run

$ make
$ make run
$ make plot
$ perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./phonebook_opt
$ perf record -F 12500 -e cache-misses ./phonebook_opt && perf report

## Optimal Version

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __DETAIL_ENTRY *detail;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

typedef struct __DETAIL_ENTRY {
    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];
} detailEntry;

## Result

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

120,6974 cache-misses # 84.776 % of all cache refs ( +- 0.36% )
142,3717 cache-references ( +- 0.22% )
2,6074,1438 instructions # 1.30 insns per cycle ( +- 0.02% )
2,0000,1906 cycles ( +- 0.17% )

0.057552514 seconds time elapsed ( +- 0.21% )

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

17,3636 cache-misses # 40.996 % of all cache refs ( +- 0.74% )
42,3539 cache-references ( +- 0.40% )
2,4388,0125 instructions # 1.93 insns per cycle ( +- 0.02% )
1,2660,9129 cycles ( +- 0.23% )

0.036543171 seconds time elapsed ( +- 0.28% )

* optimized
* 由於__PHONE_BOOK_ENTRY的detail改成由指標指向__DETAIL_ENTRY，因而cache Miss從84.776%減至40.996%
* append()並未將__DETAIL_ENTRY進行malloc，因此cache miss大幅降低極為合理
* append()若將__DETAIL_ENTRY進行malloc
* optimized的cache miss反而會高於original
* strcasecmp()所佔的cache miss之overhead會較高
* findName()所佔的cache miss之overhead會較低

## References
* [A01: phonebook](https://hackmd.io/s/S1RVdgza)
* [2016q3 Homework 1 (phonebook)](https://hackmd.io/CYJgZgHA7AnADAFgLQGMCmaCGSEGYCsyMARjPkgIwhS4gT4VwogJA===)
* [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github)