HackMD
2016q3 Homework1 (clz)
contributed by <KobeYu>
github:https://github.com/kobe0308/clz-tests.git
作業說明: https://hackmd.io/s/B1LHefQ6
tags: kobeyu
status: ongoing
作業目標
實作clz並對各種演算法進行效能分析,須實作下列演算法:
- recursive version
- iteration version
- binary search technique
- byte-shift version
- Harley’s algorithm
執行環境 @c9.io
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 62
Stepping: 4
CPU MHz: 2499.998
BogoMIPS: 4999.99
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 30720K
NUMA node0 CPU(s): 0-7
資料夾結構
我將所有clz的實作方式都放在clz.[ch],而在main.c中呼叫各種演算法並確認結果時否符合預期.
.
├── Makefile
├── README.md
├── clz
├── clz.c
├── clz.h
└── main.c
0 directories, 6 files
Git Branch
過去養成的開發習慣是走git flow的流程,所以至少會開一個develop分支做開發.(git flow)
kobe0308:~/workspace/ncku/2016_fall_system_programming/clz-tests (develop) $ git branch -v
* develop 0f6e3d1 implement clz_iteration
master d3707ca [ahead 1] add all clz api in main.c
TDD in main.c
TDD先寫測試再開發,作業目的是要找出32bit的變數中從最高為元往低位元計算第一個1以前0的總數,所以要傳全0與0x0001左移32次,共33個測試案例.
在我的main.c會觀察目前傳入的x與預期輸出一開始我用事%d去印出x,發現在最後一筆資料(0X8000)印出的是負數,%d是印出有號數的整數,應該要改成%u才能正確印出數值,但仍不直觀,所以最後版本是印出無號數的16進制%x
for (uint32_t x = 1,exp=31; x < ceiling && x; x=x<<1,exp--) {
printf("x:%u, exp:%u\n",x,exp);
在還沒實作之前的函式都先回傳-1,因為無論clz的結果不會是負值.
assert((clz_recursive(0)==32) && "clz_recursive(0) failure!!! ");
assert((clz_iteration(0)==32) && "clz_iteration(0) failure!!! ");
assert((clz_binarySearch(0)==32) && "clz_binarySearch(0) failure!!! ");
assert((clz_byteShift(0)==32) && "clz_recursive(0) failure!!! ");
assert((clz_harley(0)==32) && "clz_harley(0) failure!!! ");
for (uint32_t i = 1,j=31; i < pow(2,31) && i; i=i<<1,j--) {
assert((clz_recursive(i)==j) && "clz_recursive failure!!! ");
assert((clz_iteration(i)==j) && "clz_iteration failure!!! ");
assert((clz_binarySearch(i)==j) && "clz_binarySearch failure!!! ");
assert((clz_byteShift(i)==j) && "clz_byteShift failure!!! ");
assert((clz_harley(i)==j) && "clz_harley failure!!! ");
}
printf("end of clz test\n");
return 0;
量測執行時間
預計量測以下執行時間
1.量測輸入0x0001~0x8000,各種演算法連續執行一萬次的時間
繪製三個維度的圖表:
- x : 0x0001~0x8000
- 迴圈次數 一萬到一百萬,每次增加一萬
- 時間刻度
- 五種資料點:五種演算法
思考次數的意義:
clock_gettime(CLOCK_REALTIME, &startTime);
for (loop_i = 0; loop_i < loop; loop_i++) clz_harley(x);
clock_gettime(CLOCK_REALTIME, &endTime);
double exectime_harley = diff_in_second(startTime, endTime);
