Try   HackMD

2017q3 Homework2 (prefix-search)

tags: 進階電腦系統理論與實作 (Fall 2017)

contributed by < jcyztw >

開發環境

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                2
On-line CPU(s) list:   0,1
每核心執行緒數：1
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              15
Model name:            Intel(R) Core(TM)2 Duo CPU     T5750  @ 2.00GHz
製程：              13
CPU MHz：             1000.000
CPU max MHz:           2000.0000
CPU min MHz:           1000.0000
BogoMIPS:              3990.25
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           2048K
NUMA node0 CPU(s):     0,1
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 lm constant_tsc arch_perfmon pebs bts rep_good nopl aperfmperf pni dtes64 monitor ds_cpl est tm2 ssse3 cx16 xtpr pdcm lahf_lm dtherm

修改 test_ref.c

在修改程式碼之前，首先我從閱讀作業附帶的資料開始。在此作業的 GitHub repository 看到關於 Ternary Search Tree (以下簡稱 TST)的簡介，再加上 trace 程式碼(如下)，得知兩個執行檔 test_cpy 和 test_ref，在插入節點到 TST 時，test_cpy 利用 strdup() 來配置額外的記憶體空間，以用來存放字串；而 test_ref 則是將欲插入的字串，放到 programmer 提供的字串指標所指的位址。

main() 中建立 TST 的地方 (in test_ref.c)












    while ((rtn = fscanf(fp, "%s", word)) != EOF) {
        char *p = strdup(word);
        /* FIXME: insert reference to each string */
        if (!tst_ins_del(&root, &p, INS, REF)) {
            fprintf(stderr, "error: memory exhausted, tst_insert.\n");
            fclose(fp);
            return 1;
        }
        idx++;
    }

tst_ins_del() (in tst.c)














        if (*p++ == 0) {
            if (cpy) { /* allocate storage for 's' */
                const char *eqdata = strdup(*s);
                if (!eqdata)
                    return NULL;
                curr->eqkid = (tst_node *) eqdata;
                return (void *) eqdata;
            } else { /* save pointer to 's' (allocated elsewhere) */
                curr->eqkid = (tst_node *) *s;
                return (void *) *s;
            }
        }

根據作業的提示，修改所有 FIXME 的部份：將 tst_ins_del() 中的第四個參數由 CPY 改為 REF。但是這邊要小心，前面提過 test_ref 是根據 programmer 給的字串指標所指位址來存取字串，而 test_ref 在建立 TST 和 新增城市名稱時，tst_ins_del()中的第二個參數若不配置另外的記憶體空間給欲插入 TST 的字串，程式的執行結果會有問題。參考 st9007a 同學的作法，使用 strdup() 解決此問題。

老師在 st9007a 同學的共筆中有提到用 strdup() 的代價較大，目前我還沒有想到其他比較好的方法，待改進。

以新增城市名稱 的 FIXME 處為例 (in test_ref.c)






            p = strdup(word);
            t1 = tvgetf();
            /* FIXME: insert reference to each string */
            res = tst_ins_del(&root, &p, INS, REF);
            t2 = tvgetf();

對 TST 的實作做效能評比(包含建立 TST 及 prefix search 的時間)

以下分為兩個部份進行：

  • TST 的優點以及引入 TST 到電話簿或戶政管理系統的適用性
  • TST 實作(test_cpy 和 test_ref)的效能評比

TST 的優點以及引入 TST 到電話簿或戶政管理系統的適用性

TST 簡介

TST 為一種 trie (prefix tree)，其中一個節點最多有三個子節點，此三個子節點分別稱為 low kid，equal kid 以及 high kid (也可稱為 left，middle，right)。

每個節點主要包含以下資料：

  • key
  • 三個節點指標(指向子節點)

其中 key 為一字元，而 low kid 子節點的 key 值比其父節點的 key 來的小，high kid 子節點的 key 會比父節點的 key 值大。

當我們要在 TST 中搜尋想找的字串時，字元若與目前的節點 key 值相同，則往 equal kid 子節點繼續往下尋找。

優點和引入 TST 到電話簿或戶政管理系統的適用性

  • (pending)

TST 實作(test_cpy 和 test_ref)的效能評比

分析 test_cpy 和 test_ref 兩種方式的效能，並針對現代處理器架構，提出效能改善機制

  • (pending)

目前實作中，針對各國城市的 prefix search 有無缺陷呢？並提出具體程式碼的修正

  • (pending)

延續 phonebook 的基礎工作，引入 TST 讓電話簿程式得以更符合人性

  • (pending)

為什麼 tst.h 和 tst.c 要 forward declaration 呢？

  • (pending)

如何運用 tst_traverse_fn 函式？

  • (pending)

參考資料

Last changed by 
 
Jason Chu
0
330
Published on HackMD