or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
2023q1 Homework2 (quiz2)
tags:
linux2023
contributed by <
Paintako
>測驗一
說明
考慮 next_pow2 可針對給定無號 64 位元數值 x,找出最接近且大於等於 2 的冪的值
原始程式碼是使用了
binary search
的概念去找出最接近且大於等於 2 的冪的值而改寫後的版本:
首先,給的數值範圍是
64 bit, 且 unsigned
只要把給的數值的
MSB
右邊全部補 1,再 + 1 , 這樣即可得出最接近且大於等於 2 的冪的值例如:
數值為
00001001
,MSB 之後補 1 後變成00001111
,最後 + 1 得00010000
但是,如果情況變成原本的數值等於 2 的冪的值,則會得到比正確答案還大的數值
例如:
數值為
00001000
,MSB 之後補 1 後變成00001111
,最後 + 1 得00010000
所以針對以上情況,要結束前需要對原本的數值作
XOR
確保原本數值是 2 的冪的值的情形例如:
數值為
00001000
,MSB 之後補 1 後變成00001111
和原本的數值做
XOR
,00001000 ^ 00001111
所以答案變成00000111
,故 +1 仍然是正確答案!經 paulpeng 提醒後,仍然需要一個
if
來判斷原本數值是否 2 的冪的值的情形,依舊會有一個 branch 的 overhead程式碼應該改寫成:
為了解決這個 branch 的 overhead,可以把原本數值 -1 使得原本等於 2 的冪的數值不等於 2 的冪,解決了這個不必要的 branch
延伸問題:
使用
__builtin_clzl
改寫此函式返回
leading 0-bits in x
, 得知leading 0
的數量後, 將64 - leading 0-bits數
算出後再對1做算數位移,即可得此數最接近且大於等於 2 的冪的值但同樣需要考慮此數原本就是 2 的冪的情況,如果算出的大於等於 2 的冪的值 % 原本的值 =0 的話代表此數原本就是 2 的冪
在 Linux 核心原始程式碼找出類似的使用案例並解釋
使用
$ grep -r "<<" ./include/linux/
來找出相似程式碼有一個看起來也是跟數字處理相關的案例
./include/linux/log2.h
#define const_ilog2(n)
這是一個定義了常數log2的C程式碼的巨集(macro)。對於給定的正整數 n,該 define 返回最大的 k,使得 2^k ≤ n,即 2 的 k 次冪不超過 n。
這個 define 使用了GCC inline function __builtin_constant_p(n) ,該函數在編譯時會計算是否為常數,如果是,則返回 true,否則返回 false。 如果 n 是一個常量,那麼 define 使用二進制運算來快速找到最大的 k。 如果 n 不是常量,則使用逐位檢查的方法來找到 k。
From Chatgpt
測驗二
原本的程式碼中已經有提示了,如果這個數字是 2 的冪的話,則
len++
, 此 len 表示ans
的位移量例如:
開發過程中,原本的程式碼如下:
其中
i & (i-1)
用於判斷此數是否是 2 的冪但是這是錯的! 因為忘記了其實 1 也是 2 的冪(\(2^0\)),原本的寫法中忘記了這點才 + 1 的,故正確的版本如下
嘗試使用
__builtin_{clz,ctz,ffs}
改寫把
(i & (i-1)
改成(__builtin_ffs(i) == (64 - __builtin_clzl(i))
即可但是這樣改寫後會變得比較快嗎? Todo: 使用 perf 來判斷 cycle數的增減情況
測驗三
SIMD:
Single Instruction Multi Data
指在同個
clock cycle
中,同時處理多個向量例如:
沒有支援 SIMD 執行 \(B*=2\), 其中 B 是 1*n 的向量
有支援 SIMD:
而 SWAR 表示在
同一個 Register 中做 SIMD
在筆記中的程式碼中,發現了一些可能是白作工的部份
這裡的
(y + 0L) & (-1L >> 32)
y + 0L
還算好理解,要把 y 擴充成 64 bit但是
-1L >> 32
這裡就匪夷所思了,即便 -1L 寫成二進位是 64個 1,對這 64 個 1 做 32次算數位移仍然是 64個 1,而且跟y + 0L
做 and 也是白做工,因為擴充完 32 bit 的y+0L
前半部份也全部都是 0, 0 跟任何東西做 and 都是 0 ,所以應該可以把程式碼改寫成:參考以下程式:
這段程式在做的事情是: 找出一個字串中所有合法的
UTF-8
字元組其中,
magic number
為何是 -65?因為對應到 ASCII 的規則, 除了首位元組外,後續位元組皆是以
10xx xxxx
的形式存在故只要某一個數字大於
1011 1111
的話,那此數必不會是後續位元組,而是一個新的 ASCII !( 不是新的 ASCII, ASCII 的 MSB 皆是 0)使用
SWAR
改寫程式碼:參考小考中的提示,如果某個 byte 可以寫成
10xx xxxx
的形式,那此 byte 必是某 ASCII 的後續位元組,並且可以將這種表達方式寫成not bit6 and bit7
,也就是第七個 bit 必 1,第六個 bit 必 0,找出所有這種特殊 pattern 的位元組只保留把每一個 byte 中的 6、7 bit , 其餘 bit 全部設為 0 , 再使用
__builtin_popcount
即可得答案也可參考老師上課的說法,"找到
10
交接處"上述方式用
SWAR
的方式呈現出來首先,
qwords
代表一次讀取的 byte 數,這裡指定uint64
,代表一次讀取8 byte
,用意是配合 64 bit 系統,當 pointer ++ 時,移動的步伐等於 64 bit,也就是每一次比較的 Byte 數為 8Note: 即便使用者的系統是 32 bit 的系統 , 仍存在 64 bit 的操作 ( 例如乘法 )
這邊
len
沒有更詳細的說明,只能用推測的,因為是改寫自原本的題目,從下面程式碼來推測,是整個字串的字元組( Bytes ) 大小len >> 3 的目的在於把無法湊到 8 個 byte的去除掉(因為無法對它做 64 bit 的運算),故減去,所以
*end
代表了傳入的字串有多少的 Byte!以上程式碼,根據 C語言規格書 ( from ChatGpt ),得知符號的結合律優先度,故會先做
加法
再做>>
>> 3
代表以 8 個 byte為單位每一次都對 64 bit 做 SWAR,結束後統計 1 的個數即可得知這 8 Byte 中包含幾個後續位元組
當傳入的字串長度不是 Byte 的倍數時 ( i.e. 字串 / 8 != 0 ),則需要考慮剩餘的 Byte 中是否含後續位元組
首先,
len/8
代表 "可以完整湊出 8 Bytes的個數",乘上 8 bit 即可得完整的位元組數,再減去continuation byte
即可得目前合法的UTF-8
數這段
len & 7
很好理解,原本剩下的 Byte 數量不足 8,所以跟 7 做 &,可以得到剩餘的 Byte數而後面的
if/ else
也很好理解,將剩下的範圍丟入count_utf8
可得後續位元組數量測驗四
Note:
x <<= 1 可以寫成 x = x<<1
參考: TimChen731
程式碼要的是: 給定一個 pattern ,不斷向右移的過程中如果有符合該 pattern 就 return true
該 pattern 是只有MSB是 1 其餘皆是 0
字串要符合該 pattern ,並且不斷向左移動時不跳出 for 迴圈的話,那此字串必須符合:
MSB是1 且 1 後續不能有 0
先對 x 做
not
,再 +1 的話,則跟原本的字串做xor
後原本字串中最右邊的 1 會消失例如:
在和原本的字串做比較,如果比較小的話代表它符合此 pattern
在和原本的字串做比較,如果比較大的話代表它不符合此 pattern