Prefix search - HackMD

# Prefix search contributed by <`vulxj0j8j8`> ## 系統環境 ``` Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 142 Model name: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz Stepping: 9 CPU MHz: 477.740 CPU max MHz: 3100.0000 CPU min MHz: 400.0000 BogoMIPS: 5424.00 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 3072K NUMA node0 CPU(s): 0-3 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 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 tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch epb intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp ``` ## Makefile 閱讀https://yodalee.blogspot.tw/2017/04/makefile-header.html wildcard match: 通用符匹配 ## Ternary search tree `rex662624` 同學的共筆 https://hackmd.io/K4v3wF-8SFudCT2-ckK9Hg TST的視覺化 https://www.cs.usfca.edu/~galles/visualization/TST.html Ternary search tree http://blog.csdn.net/lionel_fengj/article/details/74147618 TST 的每一個node 儲存了 * 一個char (紀錄那個node儲存的字) * 3 個子節點 (在英文的分類方法可以為英文字母的順序) * low kid * equal kid * high kid 老師的程式每個node 還多了一個 refcnt, 這個變數是拿來紀錄這個key （前綴）出現的次數另外若是要delete node必須判斷refcnt是否 == 0 ### 與 hash map的比較 ## 嘗試閱讀程式 ```Clike static void rmcrlf(char *s) { size_t len = strlen(s); if (len && s[len - 1] == '\n') s[--len] = 0; //question } ``` :::info 註解question 的地方為何不是s[--len] = '\0'; 尚需測試 ::: > 因為 '\0' == 0 > [name=ryanpatiency][color=green] >> 瞭解感謝！ >> 剛剛查了資料後發現, 因為一個字元若是char ch = '\0' >> 則ch 以位元表示會變成 0000 0000 (char is 1 byte) >> 此狀況代表 ch == 0 (非 '0', 僅單純代表ch 的數值 == 0) >> [name=vulxj0j8j8][color=pink] ```Clike void *tst\_ins\_del(tst_node **root, char *const *s, const int del, const int cpy) ``` del: * 0 ==> insert 's' at node->eqkid * 1 ==> delete 's' from tree cpy: * 0 ==> save pointer to 's' * 1 ==> allocate storage for 's' line 234 ```Clike if (*p++ == 0) { /\* check if word is duplicate */ ``` 應該是判斷下一位是不是 '\0'(結尾), 如果是的話, 代表現在這個詞完全沒有新增新的node, 都是跟之前的node 重複再參考 [`tina0405`](https://hackmd.io/s/SkEFpwh2-#) 之後發現一個地方很有趣 ```Clike while ((rtn = fscanf(fp, "%s", word)) != EOF) { char *p = word; printf("%p\\n", p); \* 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++; } ``` 這段程式碼的 ``` char *p = word; ``` 竟然再不同次的迴圈的時候還是使用同一個地址往上拉發現原來word 是上面宣告的陣列所以難怪每次都指到相同的地址那麼我只要複製相同的文字到 *p 裏面就可以再每次迴圈的時候宣告新的字串 *p 這樣就可以避免之前每次都指到相同的地址, 造成ref沒辦法加新的字上去的問題將程式改為 ```Clike while ((rtn = fscanf(fp, "%s", word)) != EOF) { char *p = (char *)malloc(sizeof(word)); strcpy(p, word); printf("%p\n", p); /* 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++; } ``` 付帶一提，一開始忘記 malloc 空間給 *p 就產生 Segmentation fault Q 口Q 不過malloc 完之後目前看起來一切順利 ### 加上--bench 遇到perf 出狀況了 ``` Error: You may not have permission to collect stats. Consider tweaking /proc/sys/kernel/perf_event_paranoid, which controls use of the performance events system by unprivileged users (without CAP_SYS_ADMIN). The current value is 3: -1: Allow use of (almost) all events by all users >= 0: Disallow raw tracepoint access by users without CAP_IOC_LOCK >= 1: Disallow CPU event access by users without CAP_SYS_ADMIN >= 2: Disallow kernel profiling by users without CAP_SYS_ADMIN To make this setting permanent, edit /etc/sysctl.conf too, e.g.: kernel.perf_event_paranoid = -1 ``` 原來是權限問題呢搜尋後透過下列指令可以改權限 ``` $sudo sh -c 'echo 1 >/proc/sys/kernel/perf_event_paranoid' ``` 成功之後得到目前的結果 ``` Performance counter stats for './test_ref --bench s Tai' (100 runs): 613,7279 cache-misses # 58.207 % of all cache refs ( +- 1.14% ) 1054,3867 cache-references ( +- 0.89% ) 5,2809,3154 instructions # 0.98 insn per cycle ( +- 0.01% ) 5,3628,0088 cycles ( +- 0.90% ) 0.175280586 seconds time elapsed ( +- 0.96% ) ``` ``` Performance counter stats for './test_cpy --bench s Tai' (100 runs): 374,2553 cache-misses # 49.356 % of all cache refs ( +- 1.63% ) 758,2812 cache-references ( +- 0.92% ) 4,5124,6229 instructions # 1.09 insn per cycle ( +- 0.02% ) 4,1238,1551 cycles ( +- 0.89% ) 0.135232047 seconds time elapsed ( +- 0.95% ) ``` ## 加入 memory pool 參考 [`rex662624`](https://hackmd.io/K4v3wF-8SFudCT2-ckK9Hg?view)試試看上次我自己實作失敗的memory pool memory pool 的部份是參考[`ierosodin`](https://hackmd.io/s/SJ4uqs9Yx) https://hackmd.io/s/BJl6pFyzf 實作之後遇到 ```Clike void *pool_access(mPool *pool, size_t size) { printf("size = %zu\n", size); printf("1. pool->next = %p\n", pool->next); printf("pool->end = %p\n", pool->end); printf("next + size = %p\n", pool->next+size); if (pool->end - pool->next < size) { return NULL; } void *thisPtr = pool->next; pool->next = pool->next + size; printf("2. pool->next = %p\n", pool->next); return thisPtr; } ``` pool->next + size得到的數值遠超於計算值可能是因為我搞錯byte的計算方式後來發現是因為 ```Clike mPool *mPool_allocate(size_t size) { mPool *pool = (mPool *) malloc(sizeof(mPool)); pool->head = pool->next = (mPool *) calloc(1, size); pool->end = pool->head + size; return pool; } ``` 使得pool->head, pool->next, pool->end 這些指標的單位 mPool(24 bytes) 找到問題, 正常狀況下 ```Clike char *p = (char *) pool_access(POOL, sizeof(char) * strlen(word)); ``` 這個時候的 p ``` (gdb) p p $16 = 0x7ffff780c3f8 "" ``` 但似乎在出現 ``` (gdb) p p $6 = 0x7ffff7a0d050 "@" ``` 的時候程式就會在 ```Clike strcpy(p, word); ``` 產生 ``` Program received signal SIGSEGV, Segmentation fault. __strcpy_sse2_unaligned () at ../sysdeps/x86_64/multiarch/strcpy-sse2-unaligned.S:650 650 ../sysdeps/x86_64/multiarch/strcpy-sse2-unaligned.S: No such file or directory. ``` 的問題再引入valgrind 後判斷應該是初始時allocate 的空間不夠調整空間後，就沒有問題了。但是需要再詳細計算空間，減少空間浪費成果 ``` Performance counter stats for './testMpool --bench s Tai' (100 runs): 512,0940 cache-misses # 51.925 % of all cache refs ( +- 1.22% ) 986,2184 cache-references ( +- 1.52% ) 4,8658,4318 instructions # 1.00 insn per cycle ( +- 0.01% ) 4,8660,4955 cycles ( +- 0.99% ) 0.160609575 seconds time elapsed ( +- 1.79% ) ``` 最後詢問其他同學發現其實是我計算錯誤 ```Clike pool->next = pool->next + size ``` 這樣指標位置的移動數量其實是 sizeof(pool->next) * size 個 bytes 而不是 size 個 bytes 因此造成存取超過memory pool的範圍並且中間有很多個空缺 swo swp檔應該不需要被儲存透過vi .gitignore修改gitignore 忽略掉這兩個檔案 ## 參考資料 [`kevin550029`](https://hackmd.io/s/S1UlwCTnZ#) 的共筆 ### GDB https://henrybear327.gitbooks.io/gitbook_tutorial/content/Linux/GDB/index.html http://gitqwerty777.github.io/gdb-introduction/ gdb prints NULL ('\\0') as \\000. ## NOTICE hidden Markov Model CS:APP p159 推估hash function 所耗時間

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.