source: twitter
USD $5995 (而且是 35 年前的物價!) 只能買到 8-bit 微處理器,搭配 64 KB 主記憶體和 10 MB 硬碟。有趣的是,當時軟體開發的模式部分還延續至今
延伸閱讀: Code Reading
尤拉猜想是 Euler 在 1769 年對費馬定理的延伸: n 個正整數的 k 次方的總和,若是另一個正整數的 k 次方,則 n 不可能小於 k。n = 2 就是費馬最後定理,不過這個猜想在 1966 年被號稱「最短論文」給否定。
延伸閱讀:
source: twitter
"No pain, no gain"
source: CSAIL at MIT twitter
計算機結構的改變
[ source ]
早年計算能力相對低的年代,常常有用查表法代替計算,有空間換取時間的做法,來增進效能。… 那個時候 個人電腦的 CPU 可以在一個時脈週期中讀取一筆資料,但是要做乘法計算則需要幾十個時脈週期,所以用查表的比較快。除法和超越函數更是如此,而現在還有一些低階的處理器,還在用這些技巧。
後來當 CPU 時脈提高,但記憶體存取相對變慢的時候,我們必須反過來減少記憶體存取的次數,所以高階處理器 cache 越來越大,做 data prefetch 來提早取得資料、使用 multi-threaded architecture 來容忍資料遲到的狀況、使用壓縮的方式傳送資料,甚至還會用 speculation 的方式來猜測資料是在哪裡和是什麼。
在多處理機和多核心電腦上,存取資料的問題更嚴重,除了時間延遲和頻寬之外,還要考慮到尖峰時刻塞車的問題,所以有時候簡單的工作,就可能就不分工了,要不就由一個 CPU 代表去做,做完把結果給大家,要不就大家都做同樣的事情。前者多半在有共享記憶體的多核心處理器上看到,後者多半在分散式的系統看到。
到了異質計算的年代,CPU 和 GPU 的分工,更需要好好地做效能分析。因為傳統 GPU 和 CPU 不共享記憶體,透過較慢的 PCIe Bus 交換資料,所以有些工作 CPU 自己做比較快。另一方面,當 GPU 有超過 2000 個核心的時候,用重複的計算 (redundant computation)取代資料交換,也是常見的事。
更進一步談巨量資料,為了節省資料的取得時間,我們往往費盡心思。我們花時間將資料和計算擺在同一個地方,做所謂的 data computation co-location,將重複出現的資料利用 data deduplication 技術節省儲存空間和取得時間,用一堆目錄 (indexing) 讓資料可以快速被找到。
當計算機結構有所不同時,優化的策略可能會隨之而變,不能食古不化。但原理雖然簡單,系統和實作技巧卻越來越複雜,軟硬體優化的機會越來越多,可惜能夠真正連通理論和實務的人則越來越少。
以上這些技術,講起來很容易,但在實作上,必須先搞清楚運算和資料的相對位置、距離、時間先後、相依性、數量等等,才知道該如何取捨。但很多人根本不會用效能分析工具,就在那邊瞎子摸象,隨便亂講,這時候要解決問題,就需要瞎貓遇到死耗子的運氣。
i586 和 i686 看起來指令相似,但本質不同!
因為現在計算機結構改變很大
( 從測驗來刺激思考: Quiz-0 )
「你所不知道的 C 語言」系列講座
A circuit-like notation for lambda calculus
然後原本涉及到分支的陳述:
if (b < 0) a++;
可更換為沒有分支的版本: # superscalar https://en.wikipedia.org/wiki/Superscalar_processor
a -= b >> 31;
為什麼呢?一旦 b 右移 31 個 bit,在右移 >>
時在前面補上 sign bit ,所以移完會是 0xffff 也就是-1,故結果會是 a -= -1
,即 a++
,於是,原本為負數的值就變成 1 ,而原本正數的值就變成 0,又因為原本的行為是有條件的 a++,如此就是數值操作,沒有任何分支指令。
介紹完編譯工具後,來講點大概編譯的流程還有格式
**Compile flow **
先來看這張圖:
.c 和 .s 我想大家比較常見,所以就解釋一下 .coff 和 .elf 是什麼:
GAS program format (AT&T)
由一個簡短的 code 來介紹,在程式的section 會看到 .
,是定義一些 control information,如 .file , .global 等
注意,在後來的 ARM 中,一律以 "SVC" (Supervisor Call) 取代 "SWI",但指令編碼完全一致
==> ARM Instruction Set Quick Reference Card
以下簡介 ELF 中個別 section 的意義: (注意: ELF section 的命名都由 .
開頭)
寫程式的要點
Procedures
來複習一下名詞
==> "argument" 和 "parameter" 在中文翻譯一般寫「參數」或「引數」,常常混淆
==> "argument" 的重點是「傳遞給函式的形式」,所以在 C 語言程式寫 int main(int argc, char *argv[])
時,我們稱 argc 是 argument count,而 argv 是 argument vector
==> "parameter" 的重點是「接受到的數值」,比方說 C++ 有 parameterized type,就是說某個型態可以當作另外一個型態的「參數」,換個角度說,「型態」變成像是數值一樣的參數了。
==> https://en.wikipedia.org/wiki/Parameter_(computer_programming
在撰寫程式常常會使用呼叫( call ),在上圖中高階語言直接將參數傳入即可,那麼在組語的時候是如何實作的呢?是透過暫存器? Stack ? memory ? In what order ?我們必須要有個 protocol 來規範
ARM Procedure Call Standard (AAPCS)
以下測試一個參數數量為 4 和 5的程式:
程式編譯後,用 objdump 組譯會得到類似以下:
紅框標注的是比左邊多出的程式碼,從這裡可以看到參數 1-4 是存在 R0-R3,而第 5個參數存在原本 sp + 4 的位置,隨著程式碼進行 R0-R3 存在 stack 中,圖下為 stack 恢復前的樣子:
因此若寫到需要輸入5個或以上的參數時,就必須存取外部記憶體,這也導致效能的損失。
==> xorg xserver 的最佳化案例
Standard ARM C program address space
下圖為 ARM C program 標準配置記憶體空間的概念圖:
Accessing operands
通常 procedure 存取 operands 透過以下幾種方式:
用幾張圖來表現出存取 operands 時,stack 的變化:
圖下為 passed on a register:
圖下為存取 local variables:
在使用 Cross Compiler 時,gcc 前面總有一串術語,例如:
這樣 arm-none-linux-gnueabi-
稱為 target triple,通常規則如下:
<target>[<endian>][-<vender>]-<os>[-<extra-info>]
先以常見 x86 的平台為例子:
gcc 下 -v 可以看到以下:
Target: x86_64-redhat-linux
<target>-<vendor>-<os> 的形式
Android Toolchain:
Target: arm-linux-androideabi
<target>-<os>-<extra-info>
androideabi : 雖然 Android 本身是 Linux 但其 ABI 細節跟一般 linux 不太一樣
Linaro ELF toolchain:
Target: arm-none-eabi
<target>-<vender>-<extra-info>
vender = none
extra-info = eabi
Linaro Linux toolchain:
Target: arm-linux-gnueabihf
<target><endian>-<os>-<extra-info>
extra-info:
eabi: EABI
hf : Hard float, 預設有 FPU
Linaro big-endian Linux toolchain:
Target: armeb-linux-gnueabihf
<target><endian>-<vender>-<extra-info>
endian = be = big-endian
Buildroot 2015-02
Target: arm-buildroot-linux-uclibcgnueabi
<target>-<vender>-<os>-<extra-info>
extra-info:
uclibc 用 uclibc (通常預設是 glibc, uclibc 有些細節與 glibc 不同)
gnu : 無意義
eabi : 採用 EABI
NDS32 Toolchain:
Target: nds32le-elf
<target><endian>-<os>
Andes 家的,應該淺顯易懂不用解釋
由以上眾多 pattern 大概可以歸納出一些事情:
vender 欄位變化很大,os 欄位可不填。若不填的話,通常代表 Non-OS (Bare-metal)
source: http://kitoslab.blogspot.tw/2015/08/target-triple.html
為何我們要理解編譯器?這是電腦科學最早的思想體系
GCC 會透過 builtins 來達到最佳化,在 GCC flag -funit-at-a-time 指定時 (-O3 implies),原本的:
在 front-end 會被改寫為:
printf 本身就是一個小型的 interpreter,所以 GCC 的作法就是簡化複雜度,這對一般情況下是 正面的,不過涉及 function rewriting 的議題,對系統程式或設計一個作業系統核心來說,就是一個潛在的問題。
[ Interpreter, Compiler, JIT from scratch ]
[ Virtual Machine Constructions for Dummies ]
[ A brief history of just-in-time ]
[ Making an Embedded DBMS JIT-friendly ]
值得注意的是,program loader 也很關鍵
好比在金庸《射雕英雄傳》,馬鈺教郭靖修煉內功的方式,無外乎就是一些呼吸、走路、睡覺的法子。
(圖片來源:獵人 Hunter x Hunter)
[ 舊有的資料處理模式 ]
[ 以簡馭繁 ]
[ 進一步改善 ]
No virtual function dispatches
Intermediate data in memory vs CPU registers
Loop unrolling and SIMD
AutoFDO, Google
該機制出現於 GCC 2.x,由 Cygnus (現為 RedHat) 所提出,在 GCC 中對應的選項為:"finstrument-functions"
測試 GCC Function Instrumentation 的小程式: (hello.c)
但 profiling 的成本在許多環境,像是雲端運算來說,實在太沈重,所以 Google 提出透過 perf 工具來取得 profiling 資料的 AutoFDO:
Core software optimization: a strategy
Case Study: OpenStack
Skymizer 針對日前釋出的 GCC 6.1,翻譯部份 GCC Release note:
"so you all hate on C++. all right. all right. tell me. does your favorite language have a concept of friendship, then? eh?
thought so." from twitter
"C++ Is my favorite garbage collected language because it generates so little garbage."
int p(int i, int N);
use it to print the numbers from i up to N and then down to i again, one number per line
Don’t use those keywords: do, while, for, switch, case, break, continue, goto, if.
Don’t use ’:?’
You can only use ONE statement!
==>
void add(int a, int b) { … }
=>
Reference: http://stackoverflow.com/questions/14695051/how-to-simulate-a-4-bit-binary-adder-in-c
實做得以交換存在 list 中兩個節點的函式: (考慮 HEAD 與 TAIL)
int swap_list(List **head, List *a, List *b) {
…
}
==>
https://github.com/shengwen1997/sys2016_homework/blob/master/linked_list_swap/main.c