HackMD
2016q3 Homework1 (clz)
contributed by <ChenYi>
先驗證一下結果是不是正確的
在FB課程討論區裡有看到，老師給的程式碼有問題，先驗證一下各個版本
Iteration , Binary-search , Byte-shift
./a.out 16
27
27
27
正確不需要更改
Recursive
這部份是有問題的
修正一下(參考黃鏡清的筆記裡的方法)
uint32_t count = 16;
uint32_t mask = 0xFFFFFFFF;
int clz(uint32_t x)
{
int result;
// shift upper half down, rest is filled up with 0s
uint16_t upper = (x >> count);
// mask upper half away
mask >>= count;
uint16_t lower = (x & mask);
// stopping condition
if(count == 1) {
return !(x >> 1);
}
// shifting count and go into recursive
count >>= 1;
result = upper ? clz(upper) : (count << 1) + clz(lower);
count <<= 1;
return result;
}
想一想，能不能更快呢？
試著用tail recursion去挑戰
int clz_tail_recursive(uint32_t x , int final_result)
{
if(!x)
return final_result;
return clz_tail_recursive( (x >> 1) , final_result-1 );
}
int main(...)
{
...
result = clz_tail_recursive(input , 32);
...
}
Tail recursion 與一般的 recursive function不同的地方是，tail recursion可以減少stack的使用，增進效率
節錄自 Tail call (tail-recursive)
該頁面的程式碼有使用inline，但我認為那是沒意義的，如果激進一點放入force inline的話執行時應該會出錯，理由是compiler根本不知道你要執行幾次，那請問要怎麼展開呢？所以應該還是會有branch去某區塊的行為存在。
測試
./clz_test 268435456
3
3
3
3
3
全正確！！接下來就是效能問題了
效能測試
這邊使用 clock_gettime() 來作為時間的測量
CLOCK_ID flag使用 CLOCK_MONOTONIC_RAW （不受NTP影響的單調遞增）
CLOCK_MONOTONIC_RAW (since Linux 2.6.28; Linux-specific)
____Similar to CLOCK_MONOTONIC, but provides access to a raw
____hardware-based time that is not subject to NTP adjustments or
____the incremental adjustments performed by adjtime(3).
from http://man7.org/linux/man-pages/man2/clock_gettime.2.html
也可以利用在terminal輸入以下指令來找到我們要的文件
man clock_gettime
恩ˊ~ˋ makefile有陷阱R 一次跑太多會炸裂RRR 還在找原因 先畫圖
run:
for i in `seq 0 1 4294967295`; do \
./clz_test $$i; \
done
想了一下… 應該是硬碟吃不下輸出就炸裂了
假設一次輸出100byte的話 * 4294967296次 ==> 214GB左右 ==> 我的SSD只有240GB-自己的資料 ==>恩…XD
換成取個10w就好QQ
我寫的Tail recursion完全不行阿
- 我想原因是還要長stack巴，這個算法跟單純的iteration基本上是一樣的
- 但由於recursive會一直call function所以多了個function call的instructions
- 這樣的結果會導致，同樣的運算次數下，recursion的速度會低於iteration
- 所以可以看到最快的兩個都是iteration的，recursive是在比慢的
- 而黃鏡清同學的recursion又是採用binary search的作法
- 可以看到他的recursion版本是比我的來的快不少
- 另外一點值得注意的事，未做演算法最佳化的recursion點的分佈幾乎都是在iteration的上面
- 也就是說，真的就是多了那些function call的instruction而導致的
Recursion少數的好處大概是
- 好讀
- code size小
clz的用途
- 區分significant digits
- 科學計算中，常常有許多的不同大小的數字
- 而 clz 可以幫忙減少不必要的計算
- 用在資料壓縮上
- 若已知，資料 bits 數很多，只有幾個奇異點時，可以利用 clz 來幫助壓縮
真要列的話真的很多…
倒不如直接google書籍看看有什麼用途吧:連結
- 若已知，資料 bits 數很多，只有幾個奇異點時，可以利用 clz 來幫助壓縮
