contributed by < aa860630
>
先是使用 來找最高有效位數(a
),判斷 result + a
平方是否小於等於 N 的同時,不斷透過位移 a
與運算 result+a
的方式逼近 N
以 N = 36 為例 : (下方表示方法來自 kevinzxc1217 )
迭帶次數 | a | result | (result + a) * (result + a) <= N) | result+=a |
---|---|---|---|---|
0 | 32 | 0 | False | 0 |
1 | 16 | 0 | False | 0 |
2 | 8 | 0 | False | 0 |
3 | 4 | 0 | True | |
4 | 2 | 4 | True | + |
5 | 1 | 6 | False | ++ |
方法與<版本一>一致,差別為使用 while
迴圈來找到最高有效位元
在程式開發中,除法運算的複雜度高,對於硬體的限制也極高,因此我們利用加法與乘法來取代除法,在提高程式效能的同時,在某些情況下可以提供更好的精確度和硬體實現的簡單性
透過不斷右移來判斷 i 是否為零,為了找到最高有效位元
按照順序判斷 i
是否大於 、、、,若有則將該冪加到 result
並將 i
右移相對應的冪,最後得出的 result
為最高有效位元
在<版本一>程式碼中,無論輸入的數值是多少位元,處理的時間都是與該數值的位元數成正比的。因此,如果最高有效位元是最高位元,則需要處理整個32位元或64位元
然而,在<版本二>程式碼中,根據數值的大小,處理的時間會根據不同的條件而有所不同。當輸入的數值足夠大時,透過逐步將數值除以較大的數(例如65536、256、16),可以快速地減小數值,因此在處理時間上會更有效率。這種方法類似於對數運算,每次除以一個較大的數相當於對數運算中的一次除法。因此,在一定的情況下,<版本二>程式碼只需處理較少的位元,其時間複雜度可以表示為 ,其中 是輸入的數值。
在 GCC, THE GNU Compiler Collection中提到 GCC 提供一系列的 built-in 函數用來優化編譯結果,這些函數以__builtin_
作為前綴,以下介紹一些 built-in 函數及其作用
__builtin_clz(int x)
: 傳回x中前導 0 位的數量(從最高有效位元位置開始)。如果x為 0,則結果未定義 __builtin_ctz(int x)
: 傳回x中尾隨 0 位的數量(從最低有效位位置開始)。如果x為 0,則結果未定義 __builtin_ffs(int x)
: 返回 x 中最後一個為 1 的位數最高位元減掉 v
的前導 0 位的數量即為最高有效位元,程式碼如下:
在 __builtin_clz()
函數中引數若直接為 v
,多數情況下是對的,但由於此函數在 v
為0的情況下結果未被定義,因此該處應為 v | 1
internal
: 是用來儲存內部表示的加權移動平均值,會隨著新的輸出被加到 moving average 中而更新factor
: 用來表示 internal 的縮放倍率,掌控 internal 的精度。weight
: 代表輸出的權重,不同 weight 表示輸出對整體平均影響的大小。通常會被設定為 2 的冪使得計算有效率ewma_int
在資料初始化的過程順勢將avg->weight
與avg->factor
都取了 ,方便在之後透過位移avg->weight
或avg->factor
的方式達到更好的運算效果
根據 Exponentially Weighted Moving Average 得出以下公式 :
在ewma_add
函式中,首先判斷avg->internal
是否有值,若avg->internal
不為0,則進行以下操作(為了方便解釋,所有參數皆省略前綴avg->
):
func1 : internal = (((internal << weight) - internal) + (val << factor)) >> weight
為了更好的與上述公式做連結我們粗魯地將上述運算再簡化成以下 :
func2: internal = ((internal - (internal >> weight)) + (val << factor) >> weight)
其中weight
對應到 ,val << factor
對應到
既然可以用更吻合公式的 func2 來編寫,為何此處會使用 func1 的方式?
是因為在進行 bit 右移運算時可能會導致最右邊的 bit 移失,導致精準度下降,事先左移 bits 可以改善這個問題
x--
: 將 x 減1。這是因為如果 x 已經是2的冪次方,我們想要得到的 r 應該是 x 的對數,而不是對數加1。舉例來說,如果 x 是4(即2^2
),我們想要得到的 r 是2。如果 x 是3或者4,減去1之後都會得到2,然後我們會找到2的對數是 1,最後函數會返回 1 + 1 = 2
根據數值大小逐步縮小範圍,同時累計需要的 bit 移位數來表示對數 r, r = (x > 0xFFFF) << 4;
: 判斷 x 是否大於0xFFFF
(即65535
)。如果是,r
被設置為16
,否則為0
。
下面的步驟重複上述過程,但範圍更小,並逐步累積 r 的值:
shift = (x > 0xFF) << 3;
: 檢查 x 是否大於 255
(0xFF
),如果是,shift 被設置為 8
,否則為 0
。x >>= shift
: 根據 shift 的結果,進一步右移 x。r |= shift
: 使用位元或運算(|
),將 shift 的結果累加到 r 上最後一行 return (r | shift | x > 1) + 1;
:
r | shift
:將 r 和最後的 shift 結果進行位元或運算。x > 1
:如果經過所有的右移之後 x 大於1,表示還需要額外加1到結果中。ceil_ilog2()
實作linux/tools/testing/selftests/mm
/thuge-gen.c
函式通過不斷地左移 1 來找到給定數字,當 (1UL << l)
大於或等於給定的v
時,迴圈停止運行。這意味著找到了最小的l
值,此時的l
即為原程式碼ceil_ilog2(v)
的結果
Huge page 是作業系統中使用的一種記憶體管理技術。它們比標準記憶體分頁更大,通常是 2MB 或更大。
Huge page 的主要目的是提高記憶體管理效率和系統性能。在傳統的記憶體中,作業系統為每個進程維護一個 page,將 virtual address 映射到 pysical address。當存在大量的小 pages 時,頁表可能變得非常大,導致性能下降,因為作業系統花費更多時間在管理它們上。Huge page 減少了映射給定記憶體範圍所需的頁表項目數量,從而提高了效率。
ilog2(ps)
計算出每個 pages 大小,假設 pages 大小為 2MB,我們知道 ,因此其對數為 21SHM_HUGE_SHIFT
預設為 26,<< MAP_HUGE_SHIFT
的目的是確保 huge page 大小可以正確地對應到虛擬記憶體的地址空間。test_mmap
函式用於測試在指定條件下是否能夠成功使用 huge page 進行內存映射