進階電腦系統理論與實作

# 進階電腦系統理論與實作 ###### tags: `sysprog2020` `lesson` --- [TOC] --- # Lesson_1 P19 把每個位元反過來 bit order 用於網際網路傳輸時將每個位元順序反轉 P20 把負有號整數最小值取絕對值會得到負值一補數有在用用在網際網路 ```c void remove_list_node(List *list, Node *target) { Node *prev = NULL; Node *current = list->head; // Walk the list while (current != target) { prev = current; current = current->next; } // Remove the target by updating the head or the previous node. if (!prev) list->head = target->next;//可能是開頭 else prev->next = target->next; } ``` ```c void remove_list_node(List *list, Node *target) { // The "indirect" pointer points to the *address* // of the thing we'll update. Node **indirect = &list->head; // Walk the list, looking for the thing that // points to the node we want to remove. while (*indirect != target) indirect = &(*indirect)->next; *indirect = target->next; } ``` 指標的指標不是成對的不是double 有從屬關係排程用linked list的空間效率很好下次測驗題會考加前面的addentry 指標的指標不用return就能更新頭如何用指標的指標改寫swap_pair 讓使用時不用head=swap_pair(head) 變成swap_pair(&head) 9/20作業deadline O(1)指的不是都是固定執行時間，而是隨著資料量input增加而不會影響執行時間的分布 --- # Lesson_2 Xor Filter integer overflow ``` copy_from_kernel(void *user_dent,int maxlen) ``` maxlen傳入負數就可以拿到一大塊kernel資料 bitwise 1000 & 0111 =0 ->power of 2 'A'與'a'剛好差32 bitmask '\0'叫編號0 16進位的0x80很重要，因為位於0x00~0xFF中央一口氣處理4byte 裡面是不是有編號0 XOR在加密學很重要用於圖片可使肉眼看不出 cloc main.c 用來看有幾行 sizeof使用size_t 定義在typedef'd 為無號 XOR 32相當於大小寫轉換 jitblit半透明字下下週亞馬遜工程師上課 SIMD (Single Instruction, Multiple Data) MMM=dd MASK=cc AAA=aa BBB=db XXX=bf YYY=ac VV1=e VV2=b VV3=a VV4=e KKK=dc JJJ=cd in=100 0110 1000110+shift=00001111 shift=1000001 110 0001 100 0001 000 0001 MASK找ＡＡＡＢＢＢ共同點 AB剛好差2^5 MASK不能大於a跟A 但又不能小於16 3跟6是湊出來的延伸： MASK=0x20會不會shift不了 single number III 260: 有兩個只出現一次其他明確只出現兩次要constant space linear runtime complexity leetcode 137: 2次可以只用XOR 3次會需要狀態這題有三個變形 lower跟1次有關 higher跟2次有關 eg:[9,3,3,3,7,7,7] i=0 lower=1001(bitwise XOR) 1001(bitwise AND) higher=1001(bitwise XOR) 1001(bitwise AND) 第3題快速除法 128事為了考慮乘的範圍處理掉jemalloc內的magic 把str[]改成str* 會有string litera問題因為會是read only 實作會有修改 --- # Lesson_3 \*void與\*char行為相同從void轉成其他型態行為會相同但從其他型態轉回void行為就可能不同 sizeof()指標一定是bus寬度 Word 早期:有36位元的電腦，出現的比32位元還早 (36->16->32) 因為長度剛好適合浮點數他的word就是36bit 若要取1~4 要先取0~3再取4~8 取兩次如果硬體支援unaligned access 則可以只取1次 ```cpp=0 void func(int *x) { return *x; } int n = 0; printf("%d %d %d\n", n++, n++, n++); printf("%d %d %d\n", func(&n), func(&n), func(&n)); ``` 第2行，不知道是哪個n會先被++ 地區不同: 123456.789 美制 123,456.789 歐制 123.456,789 --- 5=0...0101 -5=1...1011 -3=1...1101 4=00000100 8=00001000 16=00010000 32=00100000 64=01000000 ``` (num & (num - 1))==0 && !(__builtin_ctzl(num) OPQ); ``` __builtin_ctzl(num) OPQ=FALSE 2=0x10 10&01=0 10^01=0 4=0x100 100&001=0 100^001=1 ->expect 0 6=0x110 8=0x1000 3=0x11 11&01=1 11^01=10 ->expect 1 5=0x101 101&001=1 101^001=100 bfg ctz = count tail 0 4位元clz = count leading 0 001=2 010=1 Expo Gol coding跟資料壓縮有關 3. 某數值除幾次2會變0 pop clz 延伸:最多1分支 KKK:因為每次改是要1->0 0->1所以XOR OP1bb OP2ac m=0 OPQff AAAaa BBBbb XXXdb v YYYbe u <\<shift KKKde bitset & -bitset 5.bitarray 輸入是bitmap size=64 作用是把bitmap的如果bitmap全0 回傳的pos=0 如果最低位元是1 回傳的pos=64 第1個被set t = bitset & -bitset bitset=1111 t=0001 (1111-1110) 再利用XOR把該bit反向 KKK要找的是最低位在哪處理指定區塊(block) 4.GCD 原: 取餘數直到v==0 改成沒有使用取餘數與乘法的方式第一個for (u|v)&1 其中一個是不是奇數 !((u|v)&1) 檢查兩個是不是都是偶數可以先把2提出來 while(!(u&1)) u/=2 確認u一定是奇數一偶一奇奇數那邊一定沒有二 BMI=Bit Manipulation Instruction https://en.wikipedia.org/wiki/Bit_manipulation_instruction_set 以CPU優化很常會造成漏洞 --- # Lesson_4 OP=cc ^ AAA=ab int **parent BBB=db-1 CCC=bf1 << i KK1=aa div5 KK2=ad div3 KK3=dc 2 CASES= (bcf) 第三題fizzbuzz C-style string 做reverse+可讀性要寫會不會回傳新head 如果不回傳要解釋做完後head就會動(pointer to pointer版) sort也會如果size=2也不用用到遞迴&merge sort >linked list多大才需要用到merge sort? 寫程式前就要考慮範圍 git commit --amend insert & delete 有修改size卻不在同一次commit -> 不好不好追溯散落在好幾個commit commit message 寫出限制,TODO... ### 浮點數 bfloat16 長度 16bytes長 --- # Lesson_5 (10/6) render 修正牆壁透視錯誤修正鋸齒畫面左邊(鋸齒化)用fixed point 實作右邊(牆壁透視)用floating point實作程式碼內有其他錯要找出來下周開始講自駕車 Software Define Everything 資料量(傳輸&處理)每秒1.8G ICS NCKU 拿物普通價廉的商業處理器作工業控制偶爾會當機，但這不是工業控制要的自駕車難的是軟體驗證(模擬器模擬情景要夠多，但又不能太延遲) #### 浮點數符合交換律:屬於阿貝爾群不用FPU浮點數運算單元，只用ALU對浮點數\*2 出現場景:懷疑FPU有設計錯、需要製作硬體電路實驗不能只用快跟慢，還要分析能跟不能 10進位的7轉二進制會是111，但轉成浮點數不會是111 --- 隨堂考 1.遞迴&除法有前提是浮點數除"整數" 可搭配上課的浮點數\*2 想法:若能先除二就先除(右移) https://hackmd.io/@billsun/B1gii716N 2.實作根號2 3.Leetcode 829 想法:從N到1 i要用減的 D1=cc 2 D2=dd 1 QQ0=aa 0x01000000 QQ1=dd 0x3f000000 QQ2=gg 23 ZZZ=dd 1-i 2. 牛頓法比較快逼近的原因 QQ0後目的：逼近（牛頓法） leetcode 69 fail原因：逼近速度太慢 3. 改進點:除法可以改進 --- 美國FAANG FB討論區 ##### Dict 用bloom filter預測是不是在dict裡時間複雜度缺陷:都市很多會產生hash碰撞，會有false positive 因為有幾個hash func是固定的所以要分析裡面兩個hash func分散夠不夠平均原本的bloom，受到資料刪除時會不知道有被刪如果刪除不用bit set check(?)，bloom會花更多搜尋tst時間 XOR filter 有4次hash >fingerprinthash: >作用: >把元素變成hash >與bit set做XOR比對 > >同學實驗的是64-bit，空間浪費很多，但hash很平均優點:建立的過程 Algorithm 3會做隨機，連seed一起包進去把set做XOR 補充:deletable bloom filter perf refcnt: ReferenceCounted 下周可能用線上上課 --- # Lesson_6(10/13) Create Read Update Delete compiler 也有分frontend與backend Mars Pathfinder priority inversion gcc只是compiler driver 真的編譯器是cc1 render翻為算繪不翻為渲染用在牆壁叫粉刷 database render展現特定搜尋結果技巧篇 BB1=f(c) 0xff800000 BB2=e(e) 0xffff0000 RB1=a(a) 1 RB2=a(a) 1 A=a(d) 7 B=b(c) 4 C=c(b) 5 D=d(a) 9 SS1=d(d) `node->next = *head` SS2=b(b) `*head = node` CCC=b(b) c1 < c2 (struct llist[]){ccc,D} 525 k num[k] bit=1 ,2 ,3 ,4 0000 0101 0 1 0 0 0 1 0 0 0001 0010 1 1 0 1 0 1 0 0 0010 0101 1 2 1 1 0 2 0 0 1010 ### 3 先拉node->next = head 在換head =node ## 討論 ### 1 `*pr &= BB1;` 作用:取出sign+exp 所以選==0xff800000== 目標:把23位元砍到變7位元，且不能動到sign&exp 因為bitwise是對整數所以要強制轉型(`int *pr = (int *) &r;`) 23到7是右位移16 所以除以256(`r /= 256;`) 如果不能表示到10萬或1萬等高位數會有更嚴重的誤差把最低的16bit去掉選==0xffff0000== ### 2 問題:沒有malloc 放在哪? 答:`static T static_ringbuf_mem[S + 1];` 問:如果把static拿掉會怎樣答:init兩個以上會出事，此處舉例因為沒有重新進入同一塊所以沒事 c static ``` static int x; int main(){ static int y; y++; } ``` x只能在此檔看的到(visibillity:private(only visible in the file)) y在此function外的也是用同一塊，例如遞迴，沒static會一直用新的，有static會用同一塊，所以會一直++ 大括號好處:會是獨立scope ``` { int i=9; i++ } { int i=99; i++ } ``` 這樣寫會合法，不會有重複宣告問題 gcc -E | less 停在preprocessor觀察展開後結果 ### 3 先把A串到null 再串B到list 再串C到list (struct llist[]){{y, x}} :compound literal compound:由兩個或多個東西組合而來的東西描述時型態使用指標將數值跟指標結合，即能實作list 所以要倒過來插入依序為 7 4 5 9 ``` if (!*head || (*head)->val >= node->val) { SS1; SS2; return; } ``` 把新節點插入已經排序好的list insertion sort: avg:$O(n^2)$ worse:$O(n^2)$ best:$O(n)$ tile:確定剩下的很少時換成insertion sort等較快的 ## 作業 ### render 因為圖檔是用cpp寫的所以用cpp RayCaster: floatCaster fixedCaster main loop: ``` while(!isExiting){ floatRenderer.TraceFrame(...) ... } ``` 兩邊能同步的原因: 處理好後都丟到一段buffer fix放一邊float放一邊更新螢幕時使用這段buffer做更新因此能同步更新延伸:手機/電腦更新螢幕原理:ping pong buffer 一邊拿來顯示另一邊拿來放處理完的新資料，然後交換顯示跟新資料作業:理解複雜程式執行 ### kcalc 計算機必須使用bfloat16，原程式碼是用32bit float 執行在linux kernel，因為kernel不建議(不允許)使用float --- # Lesson_7 (10/20) ## linker linker分兩種:動態/靜態 dynamic linker是OS的一部份 mazu rocket simulator ``` static int x; ``` >Visibility ``` int func(){ static int y; } ``` >靜態配置空間，不會隨func離開而釋放降低symbol(控制visibility)可以改善50%的速度 ## 靜態Linker init script 常用於安裝檔都內嵌在執行檔內建立一個session做前處理 ## Linker 在最佳化的角色 firefox底層(引擎):libxul 黑線:讀取執行檔的哪個區 ## CRT ### C語言特色相對低階、關鍵字少且與I/O無關 #### libgcc 硬體沒有/不能用fpu，只能用libgcc Linux kernel是不能直接做浮點數運算的，會造成context switch成本上升浮點數參數傳遞 GPR 通用暫存器 FPR 浮點數暫存器 GPR->FPR若FPR不能用則直接接到libgcc --- T=c(c) funcB 是 Tail recursion，但 funcA 不是 Tail recursion Q=a(c) 只要函式 g 沒有對 global_var 指標作 dereference，那麼 TCO 就有機會 P=a(b) 不影響，依然可產生符合預期的輸出 MASK=d(a) ~((1U << count) - 1) RRR=b(b) i + j - 1 ### 1 funcA回來要再乘5 TCO是為了變成for迴圈，因此留在stack上的不必要留 funcB會有五層0 funcA回傳非遞減值因此每層都必須保留因此必須留在stack 因此不能TCO優化 ### 2 c語言的func是stateful的 rand()可能會有一樣的結果，也可能不一樣不給/使用固定seed就會一樣上面: 因為x的lifetime到了(只在該層有效) 回上一層時deference會抓不到目的地 unspecify behevior 下面: g還是在範圍內 ### 3 ### 4 2^31 5&6&7=4 ### 5 有沒有可能把byte array改成bit array 能不能用clz之類的? dp: >查表，用來存下之前狀態，減少運算 >經典題:KMP (Knuth-Morris-Pratt) >給字串找子字串此題dp用法一開始預設0原因:假設兩個輸入的是空字串即成立後面的迴圈 j>0段:兩個字串交錯，但順序一定相同，因此做比較 --- ## 最佳化 micro(謬)arch 基因(gene)演算法 >基因演算法元素: >>crossover >>fitness function >Branch Prediction(BP) --- # Lesson_8(10/27) INIT=b(a) 0x5F COND=e(b) !(i & (1 << j)) HHH=d(d) h = ++(d->height) III=b(a) iterator = iterator->next[0]; callback(iterator) ## 1 因為會涉及到儲存表格 BFS/DFS 圖論:directed graph 一個有加不用考慮的condition 1什麼都不慮 OR跟AND沒過濾掉太多 e跟b是反效果 b的作用: 把比對結果存在bit array i跟j需要32位元長紀錄 16門課有C16取4種組合如果用二進制就可以用bitwise處理排列組合 DP不是萬靈丹要看狀態能不能存 INIT還可以取更大的值必須要大於n的上界不然初始化時可能會小於minimal day ## 2 效能問題:cache line夠不夠放資料若不夠大可能會有大量cache miss mm256 (intrinsic function) 有256/8=32個bytes 透過SIMD一次讀好幾個元素(SIMD Friendly) >AVX可以處理mm512,512/8=64bytes ## ROS SLAM ## 現代處理器 prefetch 要求先載入到cache cache有時候會簡寫成$ software pipeline ## code review ### Week 4 #### 第二題找兩節點的祖先跟子孫關係如何解? 要先找到限制與條件先找階層數表格空間範圍就是深度，深度$n$的完全二元樹有$2^n-1$個節點表格只要記祖先，要回推自己是第幾代找不找的到 max_level作用: 以2為底的對數，用clz數這邊的+1是不需要的改進方式可以把這邊的+1拿掉目前優點:沒遞迴有沒有機會用更少的空間實作? obj->parent[i] a pointer to a pointer to integer 存在parent的值都知道範圍，範圍小於輸入節點數的最大值如果對空間很在意，連malloc都要考慮 ### quiz2 #### 第三題 >洗牌程序 >要注意分布，不能有偏頗(bias) 此題要避免除法為什麼能把除法換成乘法? 數學推導 128位元存在的原因? 因為在intel處理器上可以做64位元乘法有128才不會overflow 問題:整數運算導致每次計算可能有不整除誤差要做補償 (5+3)/2 =5/2+3/2 =2+1 =3 但實際是4 想要改進除法與取餘數，因此改用處理器有優化的乘法 side effect --- # Lesson_9 (11/3) 計算機組織軟硬體介面計算機結構 pipeline、super scalor multi-core 翻譯為"核" kernel 翻譯為"核心" AVX-512 SIMD Phase-Locked Loop(PLL) overclock:把PLL拉高時脈增加->熱超頻性能增加13% 但耗能增加73% 降頻性能降為87% 耗能為原本的50% 把處理器降頻+多個處理器合作耗能相同而效能提升 big.LITTLE --- ## quiz ### 1 關鍵在輸入 8組輸入 8組輸出 multiplexer 用random做random search ### 2:數獨 WWW=b(b) hidden + 1 RRR=b(c) ANN_RAND() - 0.5 MOVE=d(b) posmoves - 1 MMM=b(e) mask - 1 ### 1 激勵函數有給-15~+15的範圍這之間可微 adaptive適應性 RRR:調權重 double sum = *w++ * (-1.0); ctx->weight[i] = ANN_RAND() - 0.5; /* weights from -0.5 to 0.5 */ weight-0.5對收斂有幫助 WWW:推到下個layer ### 2 MOVE: posmoves &= posmove -1 -> clear LSB 原本:DFS實作 boardSize、*boardColSize完全沒用到故意湊出連續的記憶體 --- Code Review ## render 在2D畫面呈現3D效果要克服的點: 定點數可表示範圍沒浮點數那麼廣，要如何讓兩者接近 ray casting texture 牆壁只是範圍，哪邊開始哪邊結束，最後在貼材質改彩色:改RGB值，原程式碼將RGB用相近值，所以會像黑白怎麼畫到螢幕上的? 兩個buffer一起更新位置在main loop 94行&97行 115&116更新buffer 再利用SDL API呼叫，畫在螢幕上 SDL為什麼不讓人直接更新pixel/畫布? 讓寫程式的人決定什麼時候要更新更新到畫面是慢的，更新到主MEM是快的 CPU是最快的 ->double/triple buffering 螢幕為什麼速度沒那麼快: - 人眼看不出 - 耗電 (video RAM是用DRAM) DRAM不能頻繁充放電，會燙 >VSync >電視牆 >需要9條線，不可能在完全一樣的時間更新 >要看起來順暢 >在不同timing時調整，像對時那樣 >AR >同時要攝影+繪圖/特效 >Triple buffer >A跟B buffer能不能同步VSync 122行才真正更新到video上怎麼修正錯誤? #### 右邊牆壁不連續 ->範圍不一樣的問題座標(0,0)正常會在左上角 screenY是從中心點往上跟往下延伸多少要畫東西原因:投影效果 screenY的意義是真正有效的範圍，不用更新所有的範圍 screenY是uint8 INV_FACTOR / distance 在distance接近0時會overflow 所以先用uint16接，最後再轉成uint8 pixel-art scaling algorithm 反鋸齒會變平順，但是有點假 hq2x 彩色反鋸齒 ->用來讓畫面變好看 #### 角落的牆壁看很遠的地方少了else #### 消失的牆壁人靠近牆壁到某個特定角度牆會消失邏輯判斷時少判斷了近的判斷點 tan(1)在浮點數沒問題，在定點數會有問題因為不能表示正/負無窮大解法:運算時避開這種範圍，可能需要改寫數學式要考慮可能的範圍把1改成0 合併成一個式子 #### 其中兩面的牆比例異常邏輯判斷多寫了等號定點數如何處理三角函數? table Ray casting會用到 tan cot sin cos 裡面把360切成了1024個等分只要算90度就好，等於256等分表格該設計多大? 有機會用內插法減少表格大小 deltaAngle 從人的視角對物體要看的範圍 table大小是動態的，隨螢幕大小不同 --- # Lesson_10 (11/10) 記憶體階層(Hierarchy) 傳統硬碟讀取: 變異量(variance)過大(20ms~16sec) Locality temporal locality在意的是時間，現在用的到下個時間也用的到，(昨天讀今天出)。 Spatial locality想要找一筆資料，旁邊的資料剛好有用一起拿 Locality Example >for是德語fur(介係詞) / ALGO 對陣列取值剛好在附近:空間要讀寫的地方總是固定為sum:時間指令觀點(branch,counter...) row major: ```c=1 int sum_array_rows(int a[M][N]) { int sum = 0; for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) sum += a[i][j]; return sum; } ``` 這樣的locality好嗎? >a[M][N]:subscripting，實作依然是線性 column major: ```c=1 int sum_array_cols(int a[M][N]) { int sum = 0; for (int j = 0; j < N; j++) for (int i = 0; i < M; i++) sum += a[i][j]; return sum; } ``` 效能較差 |SRAM|DRAM| |-|-| |靜態(static)|動態(dynamic)| |不須隨時充電|需時刻反覆充電| |速度快|速度慢| |良率低|良率高| cache miss 為什麼只討論miss不討論hit? 因為miss的成本(penalty)較嚴重 1999吞吐量不到1GB/s 2008吞吐量達到20GB/s 2013吞吐量達到35GB/s 2016樹梅派吞吐量5GB/s 處理器->微架構microarchitecture CS:APP 第9章你看到的記憶體不是真的記憶體 MMU記憶體管理單元創造假象:記憶體看起來是線性的，總是可以用指標，總是可以存取...等都是因為MMU才能辦到代價:page,TLB(cache for page) k-level page table 現代電腦很多都4-level ## quiz ### 1 紅綠藍RGBA轉灰階 /256 = >>8 NEON:ARM SIMD 實作:一次載入多筆資料做乘加Vector Multiply Accumulate ### 2 狀態壓縮:什麼都用0,1，要有明確區分 OFFSET1=d(d) 0 OFFSET2=g(g) 4 COND1=b(a) conn_nxt == ctmp COND2=a(c) ~ctmp & S ITER=e(b) --ret COND1我猜是代表不能連下去conn找不到下個 COND2也是出來時如果是0出來的就不處理 ### 1 SIMD寬度視處理器架構而定:64b/128b R2Y是無號整數，使用GPR v開頭都跟向量/浮點數有關 vdup:從GPR搬到SIMD/浮點數暫存器(FPR)使用 vst1q_f32:作用:store 本來是126bit 也就是32bit*4 看手冊重點:寬度所以寬度是4 ### 2 ```c=1 #include <stdint.h> #include <stdlib.h> #include <string.h> #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define ITERATE(i, begin, end) \ for (int i = (begin), i##_end_ = (end); i < i##_end_; i++) int *countSubgraphsForEachDiameter(int n, int **edges, int edgesSz, int *edges0sz, int *rsz) { uint8_t d[n][n]; /* distance */ memset(d, 0xFF, sizeof(d)); uint16_t conn[n]; ITERATE (i, 0, n) conn[i] = 1 << i; for (int z = 0; z < edgesSz; z++) { int *e = edges[z]; int u = e[0] - 1, v = e[1] - 1; d[u][v] = d[v][u] = 1; conn[u] |= 1 << v, conn[v] |= 1 << u; } ITERATE (k, 0, n) ITERATE (i, 0, n) ITERATE (j, 0, n) d[i][j] = MIN(d[i][j], d[i][k] + d[k][j]); int *rv = calloc(n - 1, sizeof(int)); ITERATE (S, 1, (1 << n)) { int ctmp = 1 << __builtin_ctz(S); while (1) { int conn_nxt = ctmp; ITERATE (d, 0, n) if ((ctmp >> d) & 1) conn_nxt |= conn[d]; conn_nxt &= S; if (COND1) break; ctmp = conn_nxt; } if (COND2) continue; uint8_t ret = 0; ITERATE (i, 0, n) if ((S >> i) & 1) ITERATE (j, 0, i) if (((S >> j) & 1) && (ret < d[i][j])) ret = d[i][j]; if (!ret) continue; rv[ITER]++; } *rsz = n - 1; return rv; } ``` conn[]那些點之間有連結 20行ITER後初始化不管其他節點，先標記自己就是節點 >另一種寫法:用OR做bitset COND1 第35行開始做的是狀態壓縮 41行是精隨如果不壓縮，可能要極大空間 41行在算出下個連接點題目只要總數若要印出所有subtree則要BFS/DFS 只要不是唯一路徑就是無效的所以能連就跳出(COND1) ## 舊題目寫好 ### dict [範例](https://hackmd.io/@eecheng/HJd1sde8v) 建一個特別的dict 自動補完能用的資料結構 - TST - Trie TST空間效率高，但搜尋時間長 CPY REF CPY: 利用strdup複製字串 REF: 會從mem poll拉效能差異結論:跟cache有關不管走到哪裡，都會用指標指到正確資料位置再存取 XOR filter 找字串有沒有在樹中最怕走到底發現不存在解決:bloom filter TST:一個字一個字找 XOR:拿到3個hash值，再對值做XOR就能找到 >gnuplot:boxplot >可用來圖表化分布情況 bloom要一個一個做hash*3次 XOR是分開做3次hash XOR建表比較久，有時候還會失敗有找到跟沒找到的差異都沒找到的情況: - 第一個字就錯 - 最後一個字才錯 bloom filter hash完會作取餘數，是程式瓶頸(hotspot) 改成快速module ->bit distributed 看得出要多複雜的dataset，哪個結構比較適合? --- # Lesson_11 (11/17) CS:APP 第9章 VM兩個簡稱都行 Virtual Machine Virtual Memory VM Management -> VMM 也都能用 Addressing定址過去的電腦定址有限制，所以不能亂指/指太遠 near pointer: 指標所指的範圍窄 far pointer: 指標範圍寬 huge pointer: 指標範圍更大來自硬體限制會造成程式開發困擾突破點:virtual memory 這邊的虛擬是跟實體physical相比的，實際上跟存在的，跟虛擬寶物等用在不存在的東西的用法不同 ## Virtual Memory 把MEM描述成線性來存取存在意義:可以把整個mem用c指標做存取，不用考慮定址範圍的問題具有兩個address - physical memory - virtual memory 利用MMU進行轉換與管理 MMU: swap mem資料到disk A槽B槽以前都是軟碟 C槽開始才是硬碟 -> 磁碟編號從C開始原因 ### Page Fault 當kernely在用Virtual address時，分為兩種space:user/kernel permission對等的==選擇==(男/女廁)(讀取/寫入) privileged==與生俱來的==等級就有高低(天才/凡人)(user/kernel) 在user space使用privileged instruction會送警告/報錯 ARM64跟x86_64切 user/kernel 的位置不同 0x8000000000000000 – ARM64 0xffff880000000000 – x86_64 P.27 針對32位元x86架構 kernel:user = 1:3 user的空間是kernel的3倍沒有caching的話檔案系統效率會變低 >GPU:圖形處理單元，可能==沒有圖形顯示能力== >GPU: 有特製的記憶體管理器- Graphics Execution Manager(GEM) >Direct Rendering Memory: DRM 連續的physical memory是很珍貴的資源 user space中的mmap mmap:memory map記憶體映射 mmap回傳的是個指標 page fault有三種: - Minor: 不影響正確，只影響讀取時間 - Major: (騎驢找馬:mem不夠借disk來用) - Invalid: 用到invalid的位置程式執行到某個程度後，OS透過MMU把位置0的位置設為無效(invalid) ==malloc不是syscall== anonymous mapping ## Transalting MMU是數學上的virtual->physical 2^64 -> 160 TB+... VPO PPO VPN Copy-on-write (COW) ## Linux記憶體管理 Overcommit: 要的資源超過能給的，造成資源衝突(承諾太多，但全都要) linux賭你要了記憶體後不會立刻用 ->OOM killer buddy system 配置空間時確認空間有效 slab 向 buddy system 去「批發」一些記憶體，加工切塊以後「零售」出去零售賣不掉可以賣回批發 overcommit相當於借貸，相信未來能拿到 ### slub/slab/slob 記憶體管理器左最新又最舊 First-Fit Best-Fit (很難達到) 參考歷史行為 Worse-Fit slob: First-Fit多半表現不錯 slab: 針對cache做調整(cache-friendly) slub: 因應多核處理器，不是為了benchmark，是為了execution time overcommit: 過度使用系統可用記憶體在web server / 高頻率存取資料庫 > 夢之大地BBS ## Functional Programming pure function 在哪個core運算結果都相同 >ex: sqrt(4) C語言的function函式隱含著狀態跟數學上的function函數不同函數只要管定義域與值域 C中的function的y可能是變數甚至是未定義 >twitter:scala語言 >scala >function OO programming language >需要大量的filter/access database >用於社交網路 isLower(int) 特別為了例外處理，不用char直接傳入 ## Stream I/O, EOF, 例外處理 River:不會斷流 stream:涓涓細流，有可能會停 ## signal C語言標準函式庫的一部份不在UNIX中在POSIX下也會有 C語言中的比較少 windows等的signal列表比較完整是由C語言的列表進行擴充的 ## exception CS:APP第8章 kill: list/send signal 不是為了殺掉process 一開始只是為了傳signal到process ## 高效能 Web 伺服器開發平行運算不一定高效率有可能會有人沒事做要搞懂瓶頸 TCP/IP是通訊協定的組合在低層級的IP上加一層高層級的TCP 瓶頸:減少等待時間 Blocking I/O Model 等待事件跟處理事件都要花時間改成一次等待好幾個事件 epoll用來新增想監視的file descriptor priority queue 用來解決timer問題單工程式情況下執行多工:維護timer ex:什麼時候播音樂、什麼時候接收移動指令、什麼時候更新畫面 --- # Lesson_12 (11/24) linux VMA process活的 program死的/未活共享機制有很多種 SysV (SysFive) 共享記憶體機制 >linux常會有被取代的東西的遺跡被POSIX(share memory)取代 mmap 可把兩塊虛擬記憶體對應到同一塊實體記憶體 ![](https://i.imgur.com/TBoSwNa.png) 以前:查表(1980) 現在:開發框架 free可以看mem資訊共享mem沒有人在使用才能釋放掉 ``` $ file /dev/shm /dev/shm: sticky, directory $ mount | grep shm tmpfs on /dev/shm type tmpfs (rw,nosuid,nodev) ``` 把檔案映射到記憶體把記憶體映射到記憶體 memfd 什麼都可以用file descriptor描述 smartphone殺手應用:camera 手機架構中有個CamIF (camera interface) 先做ISP(image signal processing) 做疊合之類的前處理目前資料都在kernel 若在kernel處理，kernel會太擠若搬到user處理，搬動成本太大 ->使用zero copy #### Chrome: ![](https://i.imgur.com/8rGW2jY.png) GPU加速compositor 前景/背景能不能用硬體加速影像疊合，且要處理透明度 >z-order 不是1+1疊合，要變0.7+0.3，要做透明度處理、聲音降低處理真正做疊合的是Render中的compositor 疊完結果放到compositor context 最後再用OpenGL等繪製到OS的螢幕 ### 檔案系統 VFS可對應到許多實作例如:網路 ![](https://i.imgur.com/d0B55x1.png) ![](https://i.imgur.com/qtsbKqn.png) >無碟工作站 >利用NFS處理 pseudo看起來是真的但是是假的 virtual跟現實有一對一對應 /tmp是pseudo file system 可以接收但是實際上存到哪不知道 coda檔案系統改本地端的cache 連上網路後再比較更改的cache 因為網路可能暫時失連 cephFS 容錯系統分散式物件儲存 RADOS ### quiz Q1&2 buddy Q3 需持續接受連線 telnet 0 <port>相當於連本地端 Q1=c(a) 在一個 buddy system 中，最高可達 50% 的空間可因內部碎片化 (fragmentation) 而被浪費 Q2=a(d) 安照 block size 遞增排序的 free list 上，使用 first-fit 和 best-fit 演算法等價 MASK1=a(a) EPOLLIN MASK2=b(b) EPOLLOUT COUNT=g(g) 86 COUNT我覺得是寫入多少字元 ## 1 bubby system用2的次方做區隔 32位元架構定址空間2^32 64位元架構定址空間只用2^48 48次方夠大且不過大，64次方過大 IA32是intel發明的 IA64是intel發明的 x86-32是intel發明的 x86-64是AMD發明的，跟過去相容，原本叫AMD64 IA64跟IA32等等不相容 AArch64使用多層translation table 若page size訂為4KB，使用3或4層table，定址使用39-bits(512G) / 48-bits(256T) 若page size訂為64KB，使用2層table，定址使用42-bits(4T) ## 1 (b) 要看情境 (c) 如果是按照高低排列，每次都要線性 (d) 不一定，還是有可能有 ## 2 關鍵在freelist跟block有沒有合併 (a) 不能避免 ## 3 nmap <網址> 可觀察port port num < 1024 superuser才能註冊 epoch還是有blocking IO 但有IO multiplexer，可以一次等好幾個人 91行才開始建立epoch epoch是由一堆系統呼叫組成 read是blockingIO 要等到收完資料，把資料copy進userspace才回傳玄機:回傳時為什麼要回傳size? >因signal打斷可能讀不完/EOF NFS網路檔案系統 read會有更新週期為了UNIX sematics(風格):關掉了cache，不然要多次read 2038問題(Y2K) UNIX有epoch，從1970開始算所以是1970+32位元，到2038年就會爆要兼顧相容的情況下解決此問題 ->關鍵字linaro 引入新的API https://www.slideshare.net/linaroorg/hkg15206-solving-the-year-2038-problem-in-linux errno:EAGAIN read變形:readv(vector) lib要夠新，要維護更複雜的狀態機，可讀寫多buffer >使用thread能優化前提->瓶頸在userspace且可切割改進: IO multiplex reactor pattern 只檢查完成了沒，需維護非同步事件，是單執行緒程式可避免context switch 36~47是input 48~59是output COUNT需有足夠長度，不然字串會被截掉 ```c=1 #include <errno.h> #include <fcntl.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/epoll.h> #include <unistd.h> #define MAX_EVENTS 4096 #define BACKLOG 1024 #define PORT 55688 #define CRLF "\r\n" #define DOUBLE_CRLF CRLF CRLF #define SOCKET_NON_BLOCKING(fd) \ int flags = fcntl(fd, F_GETFL, 0); \ if (flags == -1) \ abort(); \ flags |= O_NONBLOCK; \ if (fcntl(fd, F_SETFL, flags) == -1) \ abort(); #define EPOLL_CTL(efd, a, cfd, evs) \ if (epoll_ctl( \ efd, a, cfd, \ &(struct epoll_event){.events = evs, .data = {.fd = cfd}}) == -1) \ exit(EXIT_FAILURE); static const char *content = "HTTP/1.1 200 OK" CRLF "Content-Length: 18" CRLF "Content-Type: text/html" DOUBLE_CRLF "Users Static Files" DOUBLE_CRLF; static void do_use_fd(int epollfd, struct epoll_event *d) { if (d->events & MASK1) { char buf[512] = {0}; int n = read(d->data.fd, buf, 512); if (n > 0) { EPOLL_CTL(epollfd, EPOLL_CTL_MOD, d->data.fd, EPOLLOUT); } else { if (n == 0) { EPOLL_CTL(epollfd, EPOLL_CTL_DEL, d->data.fd, 0); close(d->data.fd); return; } } } else if (d->events & MASK2) { int n = write(d->data.fd, content, COUNT); if (n > 0) { EPOLL_CTL(epollfd, EPOLL_CTL_MOD, d->data.fd, EPOLLIN); } else { if (n == 0) { EPOLL_CTL(epollfd, EPOLL_CTL_DEL, d->data.fd, 0); close(d->data.fd); } if (errno != EAGAIN && errno != EWOULDBLOCK) close(d->data.fd); } } else { EPOLL_CTL(epollfd, EPOLL_CTL_DEL, d->data.fd, 0); close(d->data.fd); } } int main(void) { int listen_sock = socket(AF_INET, SOCK_STREAM | SOCK_NONBLOCK, IPPROTO_TCP); if (listen_sock == -1) exit(EXIT_FAILURE); struct sockaddr_in server_addr = {.sin_family = AF_INET, .sin_addr.s_addr = htonl(INADDR_ANY), .sin_port = htons(PORT)}; if ((bind(listen_sock, (struct sockaddr *) &server_addr, sizeof(server_addr))) != 0) exit(EXIT_FAILURE); if ((listen(listen_sock, BACKLOG)) != 0) exit(EXIT_FAILURE); struct linger linger = {.l_onoff = 1, .l_linger = 0}; if (setsockopt(listen_sock, SOL_SOCKET, SO_REUSEADDR, (const char *) &linger.l_onoff, sizeof(linger.l_onoff)) == -1) exit(EXIT_FAILURE); if (setsockopt(listen_sock, SOL_SOCKET, SO_LINGER, (const void *) &linger, sizeof(struct linger)) == -1) exit(EXIT_FAILURE); int epollfd = epoll_create1(0); if (epollfd == -1) exit(EXIT_FAILURE); struct epoll_event ev = {.events = EPOLLIN, .data.fd = listen_sock}; if (epoll_ctl(epollfd, EPOLL_CTL_ADD, listen_sock, &ev) == -1) exit(EXIT_FAILURE); struct epoll_event events[MAX_EVENTS]; for (;;) { int nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1); if (nfds == -1) exit(EXIT_FAILURE); for (int n = 0; n < nfds; ++n) { if (events[n].data.fd == listen_sock) { ev.data.fd = accept(listen_sock, NULL, NULL); if (ev.data.fd == -1) exit(EXIT_FAILURE); SOCKET_NON_BLOCKING(ev.data.fd); ev.events = EPOLLIN; if (epoll_ctl(epollfd, EPOLL_CTL_ADD, ev.data.fd, &ev) == -1) exit(EXIT_FAILURE); } else do_use_fd(epollfd, &events[n]); } } return 0; } ``` bilabs blapay 用flutter-dart語言 dart: 跨平台框架 JS/TS: 瀏覽器原生語言 Python: 開發方便 Go: C++有效能問題，改用GO OpenCL: 涉及GPU數學運算、hash --- # Lesson_13 (12/1) 拖到論文結束才找工作表現不好沒有理由會塞車主管來不及看會跟大學部畢業生競爭 ## linux發展 2800萬行需要有工具才能檢查驗證產品成本遠大於開發 live migration 為了省電，本來有50台主機的伺服器，改成只開10台其他的，其他的以VM方式存放，要用時再migrate到實體機快照 zero-copy 用於DDoS 虛擬化隔離程度較高容器化把OS切成更小部分同台機器有資料庫有伺服器 eBPF 把一小段程式放到kernel中可以快速做某些工作(e.x.處理封包) >NIC: network interface controler >IRQ: interupt WIN NT64 windows font 在字型檔動手腳 LINUX歪路哪裡效能不好就搬 Windows NT = Windows New Technology linux SMP kernel:核心 core:核及時=in time 即時=real time Linux逐漸朝向多核 CTSS 第一個多人多工作業系統 Compatible Time-Sharing System MS-DOS 單人單工不是作業系統 (不能排程) 在相對廉價的環境能運作 Big Kernel Lock 把所有CPU鎖住才能確保正確執行 ARM server 目標:高強度concurent ### 虛擬化 KVM(Kernel-based Virtual Machine) 只需幾萬行 ### quiz 1. 字元轉bitwise 2. mmap:快速檔案複製兩次mmap 一次讀一次寫 ACT1=b(b) if (__builtin_popcount(k) != len) continue ACT2=f(f) *maxm = MAX(__builtin_popcount(c), *maxm) ASSIGN=c(a) c |= arr[i] PROP=a(a) PROT_READ | PROT_WRITE #### 2 先把檔案映射到記憶體 lseek先確認檔案有效 src==NULL表示映射失敗把新建立的檔案映設到記憶體把檔案-檔案變成記憶體-記憶體所以跳過檔案系統那層只要做memcpy就好也可以適用於SIMD --- # Lesson 14 (12/8) ## quiz PPP=b(a) -1 QQQ=b(e) queries_size - i AAA=a(a) ++vm->object_num BBB=b(b) --vm->object_num CCC=c(f) 7 DDD=c(c) 4 K111=d(d) if (content && len) return gapbuf_insert(*gb, content, len) K222=c(a) gb->size - gb->rb - 1 K333=a(c) gap->lb + new_siz K444=b(d) (gap->rb + 1) ### 1 leetcode 1409 暴力解可解陷阱: 計算index方式如果n太大會不能暴力 O(q*m) 關鍵字:線段樹、prefix sum 不是考演算法，是考程式設計 map指的是hash map 記錄目前{queries[i]=2}整個()不是只存2 更新prefixep 根據index進行搬移 ->可用AVX2加速 AVX2提供256bits寬度 SIMD ### 2 CSAPP 第9張 garbage collector mark&sweep 物件的生命週期lifetime ex: malloc/free 保存在heap中 heap只要是有共享記憶體空間的都看的到 lifetime是從呼叫malloc開始到呼叫free結束為止 #### lab0 如何偵測記憶體的沒有free ->Valgrind Valgrind是虛擬機器 > SQLite 是資料庫也是虛擬機器經常需要查詢，但沒辦法建太大的DBMS(DataBase Management System) 可以把過去的查詢記錄保存起來(編譯起來) ->stored procedure 針對常常查詢特定條件的路徑進行加速 Google F1 分散式資料庫 DBA(Dynamic Binary Analysis) 在程式間插入程式碼，使其在執行時顯示程式狀態 ### 2 比Valgrind成本低的garbage collector -> mark & sweep sObject 生命週期管理、找鄰近路徑 Tri-colored AAA reference counter > Dict 也有用到reference counting 完全沒人用時才能釋放多工關鍵:協調、分配、共享 test4雙向指 a指向b，b指向a 要刪掉a跟b ### 3 要有陣列成本低跟linked list可插入刪除的特性 -> gap buffer 難處:size、如何切割 ## 專題 ### 針對 Arm 架構的多工處理實作 ARMMultiTasking 條件:先創造執行單元thread、描述thread的描述元為TCB 單一處理器多工:切換執行緒/分時多工使用者看起來 ![](https://i.imgur.com/LUw32BA.png) 在處理器上實際行為 ![](https://i.imgur.com/1DZHxnW.png) AMT message: thread間的溝通好處:thread間記憶體有共享(tls、stack) 傳訊息:sender->receiver應有順序 recv應創造blocking sender應接收ack exit ### Game Boy 模擬器改成更易維護debug 全部的實作都放在.h 應該要改成.h宣告.c實作重構方向 CPU模組內有instruction 改成static編譯->能夠逐行編譯如何debug模擬器追蹤關鍵記憶體內容(LCD等等) 如何檢驗狀態機->GBIT Game Boy Instruction Tester --- # Lesson_15 (12/15) ITER1=c(c) for (int k = n - j - 1; k >= 0; k--) res[k + j] = res[k] ITER2=d(b) for (int k = j; k < n; k++) res[k - j] = res[k] DECL=c(c) int cache[N + 1][N] 或(d)int (*cache)[N + 1] INT=e(a) comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD P1=a(d) i - prev_start + 1 P2=b(b) i + 1 j為正表示下移再班的時候得從最下 2猜b/d ### 1 ```c=1 #include <string.h> #define max(a, b) (((a) > (b)) ? (a) : (b)) static inline int overlap_count(unsigned int *AA, unsigned int *BB, int size) { int res = 0; for (int i = 0; i < size; ++i) res += __builtin_popcount(AA[i] & BB[i]); return res; } static void translate(unsigned int *v, int vsize, int i, int j, unsigned int *res) { memcpy(res, v, sizeof(unsigned int) * vsize); int mask[32]; for (int k = 0; k < 32; k++) mask[k] = (1U << k) - 1; int n = vsize; if (i >= 0) { for (int k = 0; k < n; k++) res[k] >>= i; } else { i = -i; for (int k = 0; k < n; k++) res[k] = ((res[k] << i) & mask[n]); } if (j >= 0) { ITER1; for (int k = 0; k < j; k++) res[k] = 0; } else { j = -j; ITER2; for (int k = n - j; k < n; k++) res[k] = 0; } } int largestOverlap(int **img1, int img1Size, int *img1ColSize, int **img2, int img2Size, int *img2ColSize) { int n = img1Size; unsigned int A[n], B[n]; memset(A, 0, sizeof(unsigned int) * n); memset(B, 0, sizeof(unsigned int) * n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (img1[i][j] == 1) A[i] |= 1 << j; if (img2[i][j] == 1) B[i] |= 1 << j; } } int res = 0; for (int i = -(n - 1); i <= (n - 1); ++i) { for (int j = -(n - 1); j <= (n - 1); ++j) { unsigned int AA[n]; translate(A, n, i, j, AA); res = max(res, overlap_count(AA, B, n)); } } return res; } ``` ### 2 ```c=1 #include <string.h> static const int MOD = 1e9 + 7; /* prime */ static int recursive(int *nums, int nums_size, int N, DECL) { if (nums_size <= 2) return 1; int left[N + 1], left_size = 0, right[N + 1], right_size = 0; for (int i = 1; i < nums_size; i++) nums[i] > nums[0] ? (right[right_size++] = nums[i]) : (left[left_size++] = nums[i]); int l = recursive(left, left_size, N, cache), r = recursive(right, right_size, N, cache); return (((long) cache[nums_size - 1][left_size] * l % MOD) * r) % MOD; } int numOfWays(int *nums, int N) { int comb[N + 1][N + 1]; /* combination table */ memset(comb, 0, sizeof(comb)); comb[0][0] = 1; for (int i = 1; i <= N; i++) { comb[i][0] = 1; for (int j = 1; j <= N; j++) INIT; } return recursive(nums, N, N, comb) - 1; } ``` ### 3 ```c=1 /* * Hash table is represented as `htable` array of size N (N = number of lines in * dict), where each element either points to the end of a singly-linked list or * is equal to zero. Lists are stored in pre-allocated array `clist` of size N. * * This implementation is memory-efficient and cache-friendly, requiring only * 12N + O(1) bytes of "real" memory which can be smaller than the size of * dict, sacrificing however for request processing speed, which is * O(req_size) in most cases, but may be up to O(dict_size) due to hash collision. */ #include <fcntl.h> #include <stdbool.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/mman.h> #include <sys/stat.h> #include <unistd.h> /* 2 additional bytes for '\n' and '\0' */ #define MAX_REQUEST_SIZE (128 * 1024 * 1024 + 2) struct htable_entry { uint32_t ptr; }; struct collision_list { uint32_t fpos; uint32_t len; uint32_t prev; }; struct compr_collision_list { uint32_t fpos; uint32_t len; }; typedef struct htable_entry htable_entry_t; typedef struct collision_list collision_list_t; typedef struct compr_collision_list compr_collision_list_t; static char *dict; static htable_entry_t *htable; static collision_list_t *clist; static compr_collision_list_t *cclist; static size_t num_of_bytes, num_of_lines; static size_t num_of_buckets; static int clist_size = 1; static uint32_t hash(char *s, size_t len) { uint32_t hash = 5381; for (size_t i = 0; i < len; i++) hash = ((hash << 5) + hash) + (s[i] - 32); return hash % num_of_buckets; } static void htable_insert(size_t fpos, size_t len) { uint32_t h = hash(dict + fpos, len); clist[clist_size].fpos = fpos; clist[clist_size].len = len; clist[clist_size].prev = htable[h].ptr; htable[h].ptr = clist_size; ++clist_size; } static bool htable_lookup(char *s, size_t len) { uint32_t h = hash(s, len); uint32_t ptr = htable[h].ptr; uint32_t nextptr = htable[h + 1].ptr; for (; ptr < nextptr; ptr++) { if ((len == cclist[ptr].len) && !memcmp(s, dict + cclist[ptr].fpos, len)) return true; } return false; } int main(int argc, char **argv) { if (argc != 2) { printf("usage: %s dictionary_file\n", argv[0]); return 2; } /* Map dictionary file directly to memory for easier access from program */ int dictfd; if ((dictfd = open(argv[1], O_RDONLY)) < 0) return 1; struct stat st; fstat(dictfd, &st); num_of_bytes = st.st_size; if ((dict = mmap(0, num_of_bytes, PROT_READ, MAP_PRIVATE, dictfd, 0)) == MAP_FAILED) return 1; /* Count number of lines in file */ for (size_t i = 0; i < num_of_bytes; i++) { if (dict[i] == '\n') num_of_lines++; } num_of_lines++; num_of_buckets = num_of_lines; htable = calloc(num_of_buckets + 1, sizeof(htable_entry_t)); clist = malloc((num_of_lines + 1) * sizeof(collision_list_t)); size_t prev_start = 0; for (size_t i = 0; i < num_of_bytes; i++) { if (dict[i] == '\n') { htable_insert(prev_start, P1); prev_start = P2; } } /* Compress collision list and update ptrs in htable accordingly */ htable[num_of_buckets].ptr = num_of_lines; cclist = malloc((num_of_lines + 1) * sizeof(compr_collision_list_t)); size_t clines = 0; for (size_t i = 0; i < num_of_buckets; i++) { uint32_t ptr = htable[i].ptr; htable[i].ptr = clines; while (ptr) { cclist[clines].fpos = clist[ptr].fpos; cclist[clines].len = clist[ptr].len; ptr = clist[ptr].prev; clines++; } } free(clist); /* Ready to accept requests */ char *req_buf = malloc(MAX_REQUEST_SIZE); while (!feof(stdin)) { fgets(req_buf, MAX_REQUEST_SIZE, stdin); size_t len = strlen(req_buf); /* Exit on "exit" command */ if (!strncmp(req_buf, "exit\n", len)) break; printf("%s: %s\n", req_buf, htable_lookup(req_buf, len) ? "YES" : "NO"); } free(req_buf); free(htable); free(cclist); munmap(dict, num_of_bytes); close(dictfd); return 0; } ``` --- ## 電腦網路 CS:APP 第11章 transaction 請助教去拿信件翻成交易不太好原意:做一件事有往返，會有派送端-回應端一來一往可能被撤銷也可能失敗更多資源是在遠端如何描述資源? >URL:Uniform Resource Locator >URI:Uniform Resource Identify arpanet: internet前身 BBN 怎麼訂架構 network global IP internet sockets interface socket簡潔 IP較完整 HTTP/3 下一代網路通訊協定可以捨棄TCP 提升效率與安全電腦特性透過network adapter或NIC(controller) 不是寫成network card IPv6 目的:連結所有裝置(包括藍芽) BLE 屬於藍芽連線每台裝置都會有IPv6 都可以互相連線 #### 電腦網路電腦網路串接方式/層次 SAN 一台電腦 LAN 系館同樓層 WAN 對外服務 internet是不同層次的通稱最小單元:ethernet segment >burst:累積一定量再把frame傳出去，不會一個一個bit傳下一層次:bridged ethernet segment 同個節點下面集結越多的裝置，速度需越快下一層次:internet Routing 要建網路還需要協定protocol 兩邊要互動且互信 internet protocol提供 >描述資源 >傳送機制(包括檢驗) 為什麼叫TCP/IP ==stack== ? >TCP/IP checksum使用1補數系統 #### Global IP scheme 計畫、一系列動作、大概樣貌 naming scheme 命名規範、命名準則光有IP只能解決命名需要解決更精準地傳遞 IP->UDP->TCP 可靠建立在大量handshake TCP像掛號信 >P2P: 用UDP就行 #### IPv4 & IPv6 Domain Naming System(DNS) 可以視為server的資料庫跟區塊鍊機制很像連線存取: >port:港口、端口、埠 >>接口:interface 如何看現在電腦有開那些port? ``` netstat -l ``` #### Socket RIO throughput - latency 拉鋸 >CSAPP第10章 Buffer/Unbuffer Echo buffer >LiFi光照上網先搞懂來自什麼socket(addr/IP) 什麼port 系統呼叫包括socket、bind、connect...等 SA:address系列的集合 #### Web server >HTTP/1.1 keep alive >把完整內容傳完層次: ![](https://i.imgur.com/DwFR8pA.png) 動態與靜態內容靜態: 由文字圖片內容組成動態: 跳出視窗、畫面互動 >CDN:Content Delivery Network >讓常見的靜態內容在比較近的地方存放 >方向是server端推送而不是client要求 >Common Gateway Interface(CGI) >用於動態網頁 >cgi-bin:可執行，以C語言撰寫 >是獨立程式 >舉例:eserv 網址列傳參數>會有隱私問題(帳號密碼看網址就能看出) 要注意換行符號在不同OS可能是一個字元/兩個字元 proxies --- # Lesson_16 ## 多處理器架構 seL4 作業系統以往有未知缺陷目標:bug-free seL4可用數學方法證明其執行結果符合預期 ->形式化驗證 Operating System==s== ->指的是不同種類不是數量有些OS不是for通用有些是for特定應用 ->Android內有Trusty作業系統 Scalability 給5000塊零用錢能考上成大給30000快能考上台大嗎? ->未知 - Uniprocessor OS 單處理器架構作業系統(OS執行環境) 多處理器但只有單個(硬體)有效不是單核(封裝) - Multiprocessor OS Correctness of Shared Data涉及共享資料如何確保結果正確 Scalability問題 Correctness of Shared Data Concurrency control - Locks - Semaphores - Transactions - Lock-free data structures Lockfree關鍵:競爭 ex:ring buffer Scalability ![](https://i.imgur.com/1JhJVPb.png) ![](https://i.imgur.com/PGJ5z1f.png) Scalability and Serialisation Parallel 同質的執行單元有可能會有競爭問題競爭多會反效果 Serial / sequential 現今的瓶頸不在CPU 在記憶體(cache不是MEM) ex: linux spin lock: ```c=1 while (0 != atomic_dec(&lock->counter)) { do { // Pause the CPU until some coherence // traffic : 考慮到 cache line 的效應!! } while (lock->counter <= 0); } ``` lock->counter不同CPU頻繁存取此段記憶體會一直進出cache ->可能會競爭/出錯 >真八核-假八核: >硬體是8核，軟體只能控4核 cache miss 指的是多核情況下的不是以往那個 Multi-what? >封裝 package >晶圓 die CMP 一個晶圓內超過1 core 且core間可互相連接 SMP processor間彼此同質且有連線 SMT 硬體只有一個但軟體開兩個(兩個硬體執行緒) >hyper threading cache line在多核特別重要 micro archtechture ARM 異質多核心虛擬化技術 big.LITTLE 兼顧續航力與效能 ->分析程式規律/效能/行為能不能把CPU分兩類型:高能耗電/低能省電 ->提升70%效率問題:比較強的CPU用到一半會被關掉需做CPU熱插拔(hotplug) 如何確保程式正確?原本在上面跑的OS怎辦 ARM DynamiQ 關鍵:不均衡的 ARM A9 SCU讓cache同步透過合理的CCI可以控制超過4核 ## 多核處理器與spinlock CSAPP 第12章 Concurrent並行(交錯) Parallel平行 Kernel 名詞 Semphore mutex ### quiz F1=d(d) socket F2=d(d) socket F3=g F4=e F5=f F6= (i) send F7=h(i) send htons 因為TCPIP是big endian 所以要轉換byte order fseek 改變檔案cursor 相關:rewind, fgetpos, ... 上面是讀取網路資料下面是寫入檔案 peer socket 用來處理當下有沒有新封包進來 server socket 用來傳送檔案 --- NUMA Non-uniform memory access Linux贏在整體行為、綜合表現異質性 IPC Library OS Unikernel Library OS延伸直接執行在硬體/hypervisor之上通常特殊的OS會搭配特殊的硬體/硬體機制 Intel SGX 硬體保護確保在安全的環境下執行 (資源隔離) KVM Kernel-based Virtual Machine 虛擬化三階級 CPU虛擬化 MEM虛擬化周邊虛擬化 KVM統治了雲端的作業系統同時達到了虛擬化的三個階級 VirtIO libVirt 提供一系列函式庫、介面 SPICE protocol 通訊協定，可存取桌面 --- # Lesson_17 12/29 Scalability ![](https://i.imgur.com/QRyB8Q9.png) Amdahl’s Law 整個系統有多少單元可以並行parallel 看起來並行沒有提升很多但效能提升很多 Gunther’s Law 真實世界的情形並行到一定程度後效能提升會受限甚至collapse ->硬體提升效果不會更好那如何提升網路流向.網路品質? many-core 大於100 CPU core(數量不用明確) multi-core 2.4.6...都叫multi many-core問題會放大例:lock 對共享區塊的記憶體存取導致延遲保持cache一致等共享硬體資源釋放 spinlock在多核有cache line bouncing問題 ![](https://i.imgur.com/yTCUpez.png) 兩獨立core的cache內容不一致 ->強迫一致(coherence)可以但成本高 ->導致更慢甚至出錯 sloppy counter 不更新整個只更新部分降低spinlock成本 ->要求某些變數CPU間不共享 ### Regular expression email表示: /^([a-z0-9_\.-]+)@([a-z0-9\.-]+)\.([a-z\.]{2,6})$/ xxx.xxx@ ``` +:一定要有(1~多) *:可以走好幾次(0~多) \:跳脫字元 .:萬用字元 ``` https://regex101.com https://jex.im/regulex/ 現在的瀏覽器用perl regex 是擴充版的 DFA NFA NFA可轉DFA regex是NFA 編譯是在做NFA轉換 >2021會開linux核心設計 > >linux deadlock detection >恐龍書:可能不處理 >現實:必須處理 lazy/non-greedy operator ### quiz 缺陷:match不是full match LLLLL =(a) < AAAAA =(b) ‘)’ BBBBB =(d) ‘?’ CCCCC =(d) ‘?’ more:我的pattern是否還有效 180行:group pair( ... ) 是否存在 list:用來串接NFA 預先假設list是對的所以先看NFA部分中途有匹配就離開還不匹配就繼續 :::spoiler ```c=1 #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> enum state_behavior { state_single, state_split }; enum special_chars { any_char }; typedef struct state { enum state_behavior type; char matching_value; struct state *output, *output1; } state; typedef struct { state *start; int num_dangling; state ***dangling; } fragment; static state *create_single_state(char matching_value) { state *new_state = malloc(sizeof(state)); new_state->type = state_single; new_state->matching_value = matching_value; return new_state; } static state *create_split_state() { state *new_state = malloc(sizeof(state)); new_state->type = state_split; return new_state; } static fragment *create_fragment(state *start, int num_dangling, state ***dangling) { fragment *frag = malloc(sizeof(fragment)); frag->start = start; frag->num_dangling = num_dangling, frag->dangling = dangling; return frag; } typedef struct { state **list; int capacity; int next_index; } state_list; #define INITIAL_SIZE 100000 static state_list *list_create() { state_list *new_list = malloc(sizeof(state_list)); new_list->capacity = INITIAL_SIZE; new_list->next_index = 0; new_list->list = malloc(sizeof(state *) * INITIAL_SIZE); return new_list; } static void list_grow(state_list *grow) { grow->list = realloc(grow->list, (sizeof(state **) * grow->capacity) * 2); grow->capacity *= 2; } static void list_append(state_list *to_append, state *data) { if (to_append->next_index >= to_append->capacity) list_grow(to_append); to_append->list[to_append->next_index] = data; to_append->next_index++; } static void list_clear(state_list *to_clear) { to_clear->next_index = 0; } #define MAX_STATES 1000000 static int current_index = 0; static char *regex; static bool is_match(state_list *list) { for (int i = 0; i < list->next_index; i++) { state *check = list->list[i]; if (!check) return true; if ((check->type == state_split) && (!check->output || !check->output1)) return true; } return false; } bool nfa_matches(char *string, state *nfa) { state_list *possible = list_create(), *next_possible = list_create(); list_append(possible, nfa); while (*string != '\0') { for (int i = 0; i < possible->next_index; i++) { state *current = possible->list[i]; if (current->type == state_single) { if (current->matching_value == *string || current->matching_value == any_char) { if (!current->output) return true; list_append(next_possible, current->output); } } else if (current->type == state_split) { if (!current->output || !current->output1) return true; list_append(possible, current->output); list_append(possible, current->output1); } } /* swap new list of next states with old clear the new old */ state_list *tmp = possible; possible = next_possible; next_possible = tmp; list_clear(next_possible); string++; } return is_match(possible); } static inline char peek() { return regex[current_index]; } static inline bool eat(char c) { if (regex[current_index] == c) { current_index++; return true; } return false; } static inline char next() { return regex[current_index++]; } static bool more() { return current_index LLLLL strlen(regex); } static void connect_dangling(fragment *frag, fragment *output) { for (int i = 0; i < frag->num_dangling; i++) *(frag->dangling[i]) = output->start; } static fragment *parse_factor(); static fragment *parse_term() { fragment *next = parse_factor(); fragment *first = next; while (more() && peek() != AAAAA && peek() != '|') { fragment *after = parse_factor(); connect_dangling(next, after); first->dangling = after->dangling; first->num_dangling = after->num_dangling; next = after; } return first; } fragment *parse_regex() { fragment *term = parse_term(); if (more() && peek() == '|') { eat('|'); fragment *regex = parse_regex(); state *split = create_split_state(); split->output = term->start, split->output1 = regex->start; state ***dangling = malloc((term->num_dangling + regex->num_dangling) * sizeof(state **)); for (int i = 0; i < term->num_dangling; i++) dangling[i] = term->dangling[i]; for (int i = 0; i < regex->num_dangling; i++) dangling[term->num_dangling + i] = regex->dangling[i]; return create_fragment(split, term->num_dangling + regex->num_dangling, dangling); } return term; } static fragment *parse_base() { char matching_value; switch (peek()) { case '(': eat('('); fragment *regex = parse_regex(); eat(')'); return regex; case '.': matching_value = any_char; next(); break; case '\\': eat('\\'); matching_value = next(); break; default: matching_value = next(); break; } state *single = create_single_state(matching_value); state ***dangling = malloc(1 * sizeof(state **)); dangling[0] = &single->output; single->output = NULL; return create_fragment(single, 1, dangling); } static fragment *parse_factor() { fragment *base = parse_base(); if (more() && peek() == '*') { eat('*'); state *next = create_split_state(); state ***dangling = malloc(1 * sizeof(state **)); dangling[0] = &next->output1; next->output = base->start; next->output1 = NULL; fragment *connected = create_fragment(next, 1, dangling); connect_dangling(base, connected); return connected; } else if (more() && peek() == '+') { eat('+'); state *next = create_split_state(); state ***dangling = malloc(1 * sizeof(state **)); dangling[0] = &next->output1; next->output = base->start; next->output1 = NULL; fragment *connected = create_fragment(next, 1, dangling); connect_dangling(base, connected); base->dangling = connected->dangling; base->num_dangling = connected->num_dangling; return base; } else if (more() && peek() == BBBBB) { eat(CCCCC); state *next = create_split_state(); state ***dangling = malloc((1 + base->num_dangling) * sizeof(state **)); dangling[0] = &next->output1; next->output1 = NULL; next->output = base->start; for (int i = 0; i < base->num_dangling; i++) dangling[1 + i] = base->dangling[i]; fragment *connected = create_fragment(next, 1 + base->num_dangling, dangling); return connected; } return base; } int main(int argc, char **argv) { if (argc < 3) return -1; regex = argv[1]; char *match = argv[2]; fragment *parsed = parse_regex(); /* add .* to make all expressions match inside strings, since we have * basically got an implicit ^ without it. */ state *star_split = create_split_state(); state *star = create_single_state(any_char); star_split->output = star; star_split->output1 = parsed->start; star->output = star_split; bool matches = nfa_matches(match, star_split); printf("Result (%s on %s): %d\n", regex, match, matches); return 0; } ``` ::: 第一次是檢視第二次是驗收 eecheng 可自我編譯的C編譯器 >A-0 System 人類第一個編譯器 tokenizer>parser>semantics tokenizer看這個字元是哪個類型跟regular expression 問題:"==" 方法:取到一個=後要繼續檢查問題:"&"一字兩意-取值、AND、加等號變"&=" parser 組合後確認符不符合 C grammer >BNF >比regular experssion完善 >context free:解析方式與位置無關 > semantics analyzer --- # Lesson 18 ## quiz EXP1=b(d) m[i] || (m[i - 1] && (s[i - 1] == c || c == '.')) EXP2=d(b) m[i - 1] && (s[i - 1] == c || c == '.') COND1=a(a) runner - walker > 4 COND2=a(d) size > 7 COND3=a(a) runner - walker <= 4 COND4=a(d) size == 7 ACT1=a(b) accept_connection() ACT2=c(c) handle_client(events[i].data.fd) ACT3=b(a) send_response(events[i].data.fd) NUM=a(a) 1 --- ### 3 會去讀取檔案"index.html" send_response 嘗試打開檔案讀內容 client連線進來後回復 >在mac上編譯會報錯 epoll.h是linux特有 Mac沒有 epoll重點:I/O multiplexer (blocking) ```c=1 if (events[i].events & (EPOLLERR | EPOLLHUP | EPOLLRDHUP)) { printf("event [%d]: errno %d\n", i, events[i].events); close(events[i].data.fd); perror("closing socket"); } else { if (events[i].data.fd == lfd) ACT1; else if (events[i].events & EPOLLIN) ACT2; else ACT3; } ``` if內都是失敗狀況 EPOLLRDHUP : HUP 對方斷開連線 >grace period 寬限期策略:趕快關閉連線 lfd accept_connection() accept需用到lfd 到底要處理handle還是send send_response() 讓client看到內容發生在連線都完成時第二種條件是連線剛進來所以不是 sendfile 特別的系統呼叫在兩個fd間傳遞資料一口氣在kernel處理完 >原本:資料從kernel->user user再呼叫send到kernel傳出問題:user只能看回傳直不知道確切狀況 kernel越來越大 handle_client() 只檢查client是否可接受用於連線剛開始時 epoll_create(int size) size需>0 --- ## 2 Leetcode 名題苦工題故意寫得很亂目的:要是不用regex會多亂 (但還有改進空間) regex: ``` reV4 = r'^((([2][0-5][0-5])|([1][0-9][0-9])|([1-9][0-9])|([0-9]))\.){3}(([2][0-5][0-5])|([1][0-9][0-9])|([1-9][0-9])|([0-9]))$' reV6 = '^([0-9a-fA-F]{1,4}:){7}[0-9a-fA-F]{1,4}$' ``` 想法: 一次多比較好幾個字元代價:建特別表格、用bit mask >==atoi很危險== >convert string to int >不是早期C規格，C99才進 >"123"->123 >"xyz"->? >man page 完全沒提到轉換失敗回傳結果 >安全: strtol >可指定進位制 >有考慮到失敗跟overflow的情況 regex災難: cloudflare雲端供應商 regex導致非預期狀況 ## 1 regex Leetcode早期題目 >\*:asterisk 一維DP 需二維轉一維共用片段 --- Not a Number NaN有好幾種 function designator --- rv32emu --- # 並行和多執行緒程式設計 https://hackmd.io/@sysprog/concurrency-concepts semaphore 可不用硬體資源 mutex 需特殊設計硬體支援 https://hackmd.io/@sysprog/linux-sync https://hackmd.io/@sysprog/concurrency-ordering https://hackmd.io/@sysprog/posix-threads --- 1. 不需要popcount 不是統計不是& 難在可以滑動今天改成數1 遞迴 3*3分成2*2 結束條件是塞滿/走過了找出最大重疊要實驗&修改 37行要改印出矩陣內容 29行 32~40行是故意的搞清楚範圍在哪(2倍邊長) 寫出規律的程式碼內容從sample卻定範圍改進: translate會多算用例子說明更好的是避免重複運算 (對稱性) hashmap是算過的不要重複去算 hashmap=資料庫 key-value 技巧在算過的不用再算希望看到推理在特定狀況不用全部跑完跑到沒有交疊的地方原本是補0 實際是不用跑如果增加條件:兩者沒交疊 2. 擔心overflow 用質數原因對大質數取餘數 EX:360%2=0 不想太複雜操作 hash成本太高不想看到太多小值不夠分散檢查碼是取10餘數->易偽造質數分布先做乘法(32->64bit)再取餘數 1開頭的數量比其他數字多密碼學把小空間變大空間要看N的範圍決定要取餘數排列問題 - 1.組合數 - 2.宣告對應長度不同都是地址但有效物件空間不同 15行事記憶體操作超範圍會報錯做實驗後推理有效空間答案只有一個要實驗 INIT 3. 把檔案操作變成記憶體操作 mmap 避免檔案開啟成本 fopen檔案大大啟動時要讀很久 mmap是對應記憶體只會有page fault 新酷音啟動很快 IO最佳化 hashtable 60&70行最近的查詢不用重新比對類似cache LRU 1. file->mem 2. hash table 難處一樣在範圍要求 hash存在的原因減少重複查詢成本改進: hash本身改進 hash實作改進比較差異 19號前交自評 1/25交只看表面要實際動過要看到本質上的問題 --- :::spoiler 筆記: 不需要popcount 難在可以滑動要實驗&修改 29行 32~40行是故意的用實驗&例子確定範圍改進: translate有多餘運算兩圖未重疊部分不用計算原作法是補0實際上是不用經過 ::: --- :::spoiler 擔心overflow 對大質數取餘數原因: hash成本太高不想太複雜操作單純取餘數會有不夠分散的問題 ex: 360%2=0 集中在小數值難在組合數與宣告範圍選項都是表示位址但對應有效物件空間範圍不同做實驗後推理有效空間答案只有一個以實驗方式推出正確答案 ::: --- :::spoiler 筆記: I/O最佳化:把檔案操作變成記憶體操作 fopen:詞典檔案太大時啟動時要讀很久 mmap:對應記憶體，發生page fault時才需要讀取成本 hash table 原因: 最近查詢的不用重新比對(類似cache) ::: ---

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.