# 2018q3 Homework3(dict)
## 探討實作上 CPY vs REF 的差異
* REF 版本
在進入 test_ref 程式進入點 main 之後，預設是讀取 cities.txt 並進行必要的初始化
* bloom filter
* [bloom_filter structure](https://github.com/posutsai/dict/blob/master/bloom.h#L15) and [bloom_hash structure](https://github.com/posutsai/dict/blob/master/bloom.h#L10)

        typedef unsigned int (*hash_function)(const void *data);
        typedef struct bloom_filter *bloom_t;
        
        // 從 bloom_hash 可以知道實作中是以 single linked list
        // 串連各個 hash function，而在實作中我們使用了兩種 hash
        // function，分別是 jenkins and djb2
        struct bloom_hash {
            hash_function func;
            struct bloom_hash *next;
        };
        
        struct bloom_filter {
            struct bloom_hash *func; // function list
            void *bits; // where we store our 1s and 0s
            size_t size;
        };
        

* [bloom_create constructor](https://github.com/posutsai/dict/blob/master/bloom.c#L32)

        bloom_t bloom_create(size_t size) {
            bloom_t res = calloc(1, sizeof(struct bloom_filter));
            res->size = size;
            res->bits = malloc(size);
            bloom_add_hash(res, djb2);
            bloom_add_hash(res, jenkins);
            return res;
        }

* memory pool
在開檔成功後，如果 tst_ins_del 沒有發生錯誤，便會一路讀到 EOF

      // memory pool 透過一開始宣告所需要的記憶體空間，省去需要時每次 
      // malloc and free 所帶來的成本 memory pool 實作中，固定會有
      // 一個 pool 指標指向 pool 的起始位址，另一個 Top 指標指向下一
      // 個可插入的單位
      char *pool = (char *) malloc(poolsize * sizeof(char));
      char *Top = pool;
      
      // 實際把字串塞入 memory pool 使用的是 fscanf，並在每次 while
      // loop iteration 之後，把 Top 向後移上個 iteration 已經輸入
      // 的那個字串長度
      while ((rtn = fscanf(fp, "%s", Top)) != EOF) {
          char *p = Top;
          /* insert reference to each string */
          if (!tst_ins_del(&root, &p, INS, REF)) { /* fail to insert */
              fprintf(stderr, "error: memory exhausted, tst_insert.\n");
              fclose(fp);
              return 1;
          } else { /* update bloom filter */
              bloom_add(bloom, Top);
          }
          idx++;
          Top += (strlen(Top) + 1);
      }
      
      void bloom_add(bloom_t filter, const void *item) {
          struct bloom_hash *h = filter->func;
          uint8_t *bits = filter->bits;
          while (h) {
              unsigned int hash = h->func(item);
              hash %= filter->size;
              bits[hash] = 1;
              h = h->next;
          }
      }

* CPY 版本
* [main function](https://github.com/posutsai/dict/blob/master/test_cpy.c#L25) 內讀取資料的機制明顯與 REF 版本不同

    // 從以下這段程式碼可以清楚看到，word 一開始先被設定了最長的長度
    // 沒有先經過一層外在的記憶體管理就進到 TST 裡
    char word[WRDMAX] = "";
    while ((rtn = fscanf(fp, "%s", word)) != EOF) {
        char *p = word;
        if (!tst_ins_del(&root, &p, INS, CPY)) {
            fprintf(stderr, "error: memory exhausted, tst_insert.\n");
            fclose(fp);
            return 1;
        }
        idx++;
    }

## 分析效能表現
1. 在以 gnuplot 畫圖之前，勢必要先獲取資料，但在獲取資料上卡了很久，始終不懂單純從 command line 介面，怎麼分析 instruction per cycle，最後查到用 <linux/perf_event.h>，不過時間似乎已經太晚了。
2. 我的分析方法是隨機從 cities.txt 找非 "," 的字串，我在想作業教學上的圖表受到 "," 的影響是很大的，實際上 "," 是會進去 TST 的，且相較於其他可能字串，出現頻率過高，導致分析上的失真。
3. 實驗中，我每次需要查詢一個字串就會 fork 一個 child process 並測量這個 process 的執行時間。
4. 我實作了一個 [cpu_cycles](https://github.com/posutsai/dict/blob/master/measure_ipc.c#L30) 函式，在給的時間區間內計算 child process cpu_cycle
5. 以下為部分紀錄

Okha, 0.001148, 7487000
Uruguay, 0.001085, 43227000
Saint-Florent-des-Bois, 0.001074, 54829000
....