Try   HackMD

2017q1 Homework1 (phonebook)

contributed by <ierosodin>

github

Reviewed by janetwei

  • 電話簿是否做到動態資料新增和刪除
  • 還有其他的方法可以實驗，如：字串壓縮法
  • 還未引進符合現實狀況的 data set實驗

開發環境

作業系統 : elementary OS loki

$ lscpu

Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 45
Model name: Genuine Intel® CPU @ 3.30GHz
Stepping: 5
CPU MHz: 2101.558
CPU max MHz: 3900.0000
CPU min MHz: 1200.0000
BogoMIPS: 6600.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 15360K
NUMA node0 CPU(s): 0-11

Astyle

To format your file you can execute below command:
$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none *.[ch]

未優化效能分析

$ perf stat --repeat 100 -e cache-misses,cache-references,instructions,cycles ./phonebook_orig

          199,0010      cache-misses              #   90.561 % of all cache refs      ( +-  0.07% )
          219,7433      cache-references                                              ( +-  0.07% )
       2,6118,9558      instructions              #    1.24  insns per cycle          ( +-  0.02% )
       2,1139,7062      cycles                                                        ( +-  0.38% )

$ ./phonebook_orig & perf top -p $!

  29.23%  libc-2.23.so    [.] __strcasecmp_l_avx
  17.38%  phonebook_orig  [.] findName
  10.93%  phonebook_orig  [.] main

優化

縮減 struct 大小

從 $ perf top 中可以發現，程式的熱點在 __strcasecmp_l_avx ，也就是花費許多的時間在比較字串，然而 findName() 中，字串的比較只使用到 entry 結構的 lastName，但程式每次在 cache data 時，卻要 cache 整個 136 bytes 的 entry，這也造成大量的 cache misses ，因此嘗試重寫 entry 的結構，將 append() 與 findName() 不會用到的資料獨立出來，增進程式 cache 時的效能。


















typedef struct __PHONE_BOOK_INFO {
    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];
} info;

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_INFO *info;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

           33,4150      cache-misses              #   50.126 % of all cache refs      ( +-  0.66% )
           66,6618      cache-references                                              ( +-  0.20% )
       2,4425,0894      instructions              #    1.65  insns per cycle          ( +-  0.02% )
       1,4798,1744      cycles                                                        ( +-  0.19% )

使用 hash function (BKDR)

從 $ perf top 中可以發現， findName() 花費了相當多的時間，嘗試在 append() 中使用 hash function ，加速 findName() 的效能。

參考 Hash function 中的 Hash Tables

有非常多不同的 hash function，請問是哪一個呢？
課程助教

這裡使用了 BKDR Hash Function ，有時間再來比較不同 function 的效能比較XDierosodin





int hash_number = 0;
for (int i = 0; i < s.length(); i++)
    hash_number = (seed * hash_number + s.charAt(i));
return hash_number %= SIZE;

perf stat:

           45,4762      cache-misses              #   31.637 % of all cache refs      ( +-  0.52% )
          143,7442      cache-references                                              ( +-  0.07% )
       3,5411,1494      instructions              #    1.51  insns per cycle          ( +-  0.15% )
       2,3525,5300      cycles                                                        ( +-  0.31% )

從效能分析圖中可以發現， findName() 的時間有大幅度的下降，不過相對的， append() 必須要額外花費時間。

比較不同 hash table size 對效能的影響

不同的 table 大小，會影響資料的分佈，越大的 size ，可以使每一個 hash number 的 linked-list 變短，加速 findName() 的速度。

這裡以 lastName = odontomous 為例，比較不同 size 對搜尋速度的影響：

table size search time
17 0.000267s
33 0.000151s
997 0.000004s
3571 0.000001s
9137 0.000001s

可以發現，當 table size 越大時，點的分佈會越均勻， slot 數下降，而搜尋速度也會更快。

比較使用不同的 hash function

  • ELF Hash Function

  • P. J. Weinberger Hash Function

  • AP Hash Function

  • SDBM Hash Function

  • RS Hash Function

  • JS Hash Function

  • BKDR Hash Function

只看 slot 數好像不容易比較不同方法間的效能差異，沒有找到一個比較適當的量測方式@@ierosodin

### OpenMP

在建立 linked-list 時，需要花費許多時間在 for 迴圈，可以利用 OpenMP 進行平行化的處裡，增進 append() 的效能。

append() 若沒有謹慎的使用平行化處理，會造成 race condition ，使 linked-list 的內容發生遺失。ierosodin

Memory pool

Wikipedia : 預先規劃一定數量的記憶體區塊，使得整個程式可以在執行期規劃 (allocate)、使用 (access)、歸還 (free) 記憶體區塊

在寫這段筆記前，必須要說… memory pool 太神啦！！！深深體會到，好的記憶體使用，可以大大提升效能ierosodin

比起原先在每次需要配置記憶體才使用 malloc() ， memory pool 主要的目的就是先配置好一大串連續的記憶體，之後要使用時再分配。不過在釋放記憶體的部分要非常小心，可以利用 valgrind 作為驗證的工具。


























m_pool *pool_allocate(int size)
{
    m_pool *pool = (m_pool *) malloc(sizeof(m_pool));
    pool->head = pool->next = (char *) calloc(1, size);
    pool->tail = pool->head + size;

    return pool;
}

void *pool_access(m_pool *pool, int size)
{
    if (pool->tail - pool->next < size)
        return NULL;

    void *tmp = pool->next;
    pool->next = pool->next + size;

    return tmp;
}

void pool_free(m_pool *pool)
{
    free(pool->head);
    free(pool);
}

這只是比較簡單的 memory pool 實作，如果一開始配置的記憶體大小不夠使用，將會造成 segmentation fault，在此實作中沒有做相對應的處裡。ierosodin

從下面的效能比教圖可以發現，使用 memory pool 後，append() 的時間下降許多：

而觀察優化後的 perf 分析可以發現，整體的 cache-misses 數量下降了！

           13,1139      cache-misses              #   29.716 % of all cache refs      ( +-  1.66% )
           44,1314      cache-references                                              ( +-  0.27% )
       2,4768,6310      instructions              #    1.78  insns per cycle          ( +-  0.21% )
       1,3943,8197      cycles                                                        ( +-  0.52% )

       0.090425028 seconds time elapsed                                          ( +-  1.58% )

GCC optimization

對原程式碼做 compilier 的 -Ofast 最佳化，結果可以發現，我們做的優化已經超越 compiler 啦～

再對所有方法做一次 -Ofast 的最佳化：

Memory leak

為了確認使用完的 Linked-list 的記憶體空間是否被釋放，利用 valgrind 工具來檢測使用 memory 的狀況。

檢查 phonebook_orig：
$ valgrind --leak-check=full ./phonebook_orig

結果：

==21434== HEAP SUMMARY:
==21434==     in use at exit: 47,586,264 bytes in 349,899 blocks
==21434==   total heap usage: 349,906 allocs, 7 frees, 47,596,856 bytes allocated

可以明顯看到，程式執行過程中，總共 alloc 了 349,906 次，卻只有釋放 7 次記憶體！

修改 main.c 中釋放記憶體的部份：






    entry *tmp;
    while ((tmp = pHead) != NULL) {
        pHead = pHead->pNext;
        free(tmp);
    }

重新檢查：

==22359== HEAP SUMMARY:
==22359==     in use at exit: 0 bytes in 0 blocks
==22359==   total heap usage: 353,476 allocs, 353,476 frees, 11,321,392 bytes allocated
==22359== 
==22359== All heap blocks were freed -- no leaks are possible
Last changed by 
 
許耕福
0
1173
Published on HackMD