2018q1 Homework1 (phonebook)

contributed by <ga639487>

Reviewed by 0922james0922

  • hash table的部份可以多加詳述過程讓大家裡解你的想法，都實作出來了少了說明有點可惜

Reviewed by f74034067

  • 可以解釋選擇何種 hash function，以及其動機為何。

系統環境

$ uname -a
Linux ga639487-GL552VW 4.13.0-36-generic #40~16.04.1-Ubuntu SMP Fri Feb 16 23:25:58 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 94
Model name:            Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz i7-7700HQ CPU @ 2.80GHz
Stepping:              3
CPU MHz:               2600.000
CPU max MHz:           3500.000
CPU min MHz:           800.0000
BogoMIPS:              5184.00
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              6144K
NUMA node0 CPU(s):     0-7
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti retpoline intel_pt rsb_ctxsw tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

$ free
              total        used        free      shared  buff/cache   available
Mem:        8061388     1161720     6150584      220760      749084     6397032
Swap:       4971516           0     4971516

優化方法1:縮小struct大小

根據題目要求，我們可以先忽略 email、phone number、address、zip 等詳細資訊，只專注在有沒有找到 last name ， 因此額外建立一個struct 如下





typedef struct __LAST_NAME_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __LAST_NAME_ENTRY *pNext;
} lentry;

新的struct大小為24byte，因此cache可以放進（32 * 1024)/(24 * 8)=170.66666個word，減少cache miss的機率。

初始版本

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

         4,455,629      cache-misses              #   90.072 % of all cache refs      ( +-  0.09% )
         4,946,762      cache-references                                              ( +-  0.06% )
       262,901,013      instructions              #    1.41  insn per cycle           ( +-  0.02% )
       187,035,077      cycles                                                        ( +-  0.07% )

       0.061372890 seconds time elapsed                                          ( +-  0.10% )

縮小struct後

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

           982,188      cache-misses              #   59.956 % of all cache refs      ( +-  0.81% )
         1,638,178      cache-references                                              ( +-  0.13% )
       241,176,737      instructions              #    2.11  insn per cycle           ( +-  0.02% )
       114,422,766      cycles                                                        ( +-  0.10% )

       0.038176904 seconds time elapsed                                          ( +-  0.99% )

可以看出cache miss 從90.072%下降至59.956%。

優化方法2:使用hash function

Select a repo