contributed by <hsiehong
>
github
進階電腦系統理論與實作
MMM = 0x8080808080808080
因為有效的 ASCII 範圍是 0 - 127,二進制表示是 0x0000 0000
- 0x0111 1111
,所以可以透過 alpha & 1000 0000
來檢測字母的 MSB
是否為 1,為 1
表示不為有效的 ASCII 字元 (ASCII > 127),在 64 位元觀點此 mask 即為 0x8080808080808080
memcpy
?參閱 memcpy - Linux manual page 可以得知若系統沒有 memory alignment,在 memcpy
會做 memory alignment,可以避免 Unaligned Memory Accesses,因為並不是所有的硬體都有支援 unaligned memory acces,memcpy
就是透過軟體來達到 memory alignment,雖然執行速度會較硬體慢,但不在這邊的討論範圍。
其中 OPSIZ
會因不同的架構而異,可能是 8 bytes 或 16 bytes,而把多出來不足 8( or 16) bytes 的部分先行複製
Question
A
Z
的 MSB 判斷是否是大寫字母,利用 a
z
的 MSB 判斷是否是小寫字母,並利用 PACK_BYTE
來增加可讀性TODO
reference: eecheng
MASK = 0x40
AAA = 3
BBB = 6
觀察一個 byte 的狀況
字元 | ASCII(in) | output(dec) | output(bin) |
---|---|---|---|
'0' | 0011 0000 | 0 | 0000 0000 |
'6' | 0011 0110 | 6 | 0000 0110 |
'9' | 0011 1001 | 9 | 0000 1001 |
'A' | 0100 0001 | 10 | 0000 1010 |
'a' | 0110 0001 | 10 | 0000 1010 |
'F' | 0100 0110 | 15 | 0000 1111 |
'f' | 0110 0110 | 15 | 0000 1111 |
MASK
為 0100 0000
,推測是判斷字元是數字還是字母,若是字母則 letter
為0100 0000
,數字的話 letter
為0000 0000
從 line5 回傳值 (in + shift) & 0xf
推測,0xf
二進制為 0000 1111
,即保留 (in + shift)
末四位,所以只須探討這末四位是何方神聖
若字元是字母,A
和 a
的末四位都是 0001
,要變成正確輸出的 1010
需要加上 1001
,可以推斷正確的 offset
為 1001
。這裡利用 letter
0100 0000
來產生 shift,letter >> 3 | letter >> 6
可以得到正確的 offset 0000 1001
。
若字元是數字,letter
就是 0
,line 5 就沒有作用,in
末四碼就是正確的結果
0x
),並檢查是否為 HexspeakXXX = 0xFFFFFFFFFFFFFFFF
根據數學式
line 6 可以推得是除以,所以 N 應為64,((__uint128_t) M * n) >> 64
即為 的整數部份( quotient )
精確值 XXX
應為 ,但 XXX
最大只能儲存 ,就是 0xFFFFFFFFFFFFFFFF
,最後 +1
代表無條件進位,確保 與 的整數部份是會相同的
從上述可以得知, M
是對應到
line7 算出商之後,n - q * D
即可得到餘數
對 fast_mod
與 normal_mod
分別跑 10 萬次
比較不做最佳化與做 O1, O2, O3 最佳化的結果
可以看出有做最佳化的話其實結果不會差太多,但 normal 版本還是會稍微較好
O0
O1
O2
O3
Question
fast_mod
在全部的情況下表現都沒有比較優異?由 Facebook 公司所維護的 jemalloc 是個高效能的記憶體配置器 (memory allocator,即 malloc 和 free 函式對應的實作),特別在多核多執行緒的環境有優異表現,在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也運用類似的技巧,請閱讀原始程式碼,並抽離快速除法實作為獨立的程式碼,說明運作原理,也該撰寫測試程式,比較透過處理器的整數除法指令及本技巧的效能差距
假設 , 都是整數,已知 求 ,,可以轉換成下面的形式
,其中 = mod
,因為 ,所以 為整數
,推導到這邊,只要能確保 ,就代表 可以被改寫成
其中 = mod ,可以確定 ,而 可以令 來確保其
推導完再來看快速除法的資料結構 div.h
在 structure div_info_s
中有一個 uint32_t magic
,magic
就是上述推導中的 ,在 div.c 中實做
div_compute
回傳的是
再來實做部份 div.c (省略推導過程)
6.5.5-5
The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined.
two_to_k
即
magic
為 ,但 /
預設是取 floor,所以在 line 24 中還要做取 ceiling 的動作
Questions
.h
file 與 .c
file 的區分 ?div.c
中使用到 %
,影響?測試程式
下面分別比較編譯時分別使用不同最佳化的結果
O0
O1
O2
O3
YYY = M-1
0xFFFFFFFFFFFFFFFF / 3
= 0x5555555555555556
= M
,又 d
= 3,n
只可能有 3 種情況: 3k + 1
, 3k + 2
, 3k
,k 為正整數,分別討論 n
可能的 3 種狀況n
= 3k
: n
= 3k + 1
: n
= 3k + 2
: n = 3k
時 n
才能被整除,所以 n * M = 2k
才有可能,也可以表示成 n * M <= M - 1
或 n * M < M
(k
有可能為 0)VV1 = 0x80
VV2 = 0
VV3 = -1
VV4 = 0x80
define PACKED_BYTE(b)
PACKED_BYTE(b)
的作用是取出 b 的最後 8 個位元並複製 8 次形成 8 個 byte,比如說 b
的後 8 bits 是 0xab
,則 PACKED_BYTE(b)
= 0xabababababababab
line13: 要確認是否為有效的 ASCII 字元,使用技巧同第一題,又這裡要一次處理 8 個 char (8 bytes),故將 0x80
-> 0x8080808080808080
line17,推測 mask
的作用,若大寫字母才需要做轉換,小寫字母不須轉換,字母為大寫的話 mask
是 0b0010 0000
(原本是0x80
,在 line16 做了 >> 2
的動作),反之是小寫字母的話 mask
為 0b0000 0000
我們要判斷一個字母 c
是否在大寫字母範圍簡單的方法如下,有兩個部分, c
> 'A' 且 c
< 'Z'
128 二進制表示是 1000 0000
,這裡設計兩個變數 A
Z
檢查字母是否在 A
-Z
之間,變數 A
判斷 c 是否大於等於 'A',若 c 大於 'A' 的話 128 - 'A' + VV2
的 MSB 會是 1 (>127),故 vv2 = 0
。變數 Z
同理,紀錄字母 c 是否大於 'Z',但因為 'Z' 是允許的(計算127 - 'Z'
的距離就好,故 vv3 = -1
),大於 'Z' 的話變數 Z
的 MSB 才要為 1,故要再減 1 。
這裡只需要 A^Z
MSB 的資訊來判斷是否在大寫字母的範圍,所以此處 mask 取 0x1000 0000
,取出 MSB 的資訊,來判斷要做大寫還是小寫的動作。
char str[] ...
改成 char *str ...
執行時會產生錯誤參閱 ISO/IEC 9899 (即 C99 規格)
6.4.5
A character string literal is a sequence of zero or more multibyte characters enclosed in double-quotes, as in "xyz".
5.1.1.2-6
Adjacent string literal tokens are concatenated.
In translation phase 7, a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals. The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence. For character string literals, the
array elements
have typechar
, and are initialized with the individual bytes of the multibyte character sequence; for wide string literals, the array elements have typewchar_t
, and are initialized with the sequence of wide characters corresponding to the multibyte character sequence, as defined by thembstowcs
function with an implementation-defined current locale. The value of a string literal containing a multibyte character or escape sequence not represented in the execution character set is implementation-defined.
It is unspecified whether these arrays are distinct provided their elements have the
appropriate values. If the program attempts to modify such an array, the behavior is undefined.
array of char
null byte
的)mbstowcs
function in 7.20.8.1The mbstowcs function converts a sequence of multibyte characters that begins in the initial shift state from the array pointed to by s into a sequence of corresponding wide characters and stores not more than n wide characters into the array pointed to by pwcs. No multibyte characters that followanull character (which is converted into a null wide character) will be examined or converted. Each multibyte character is converted as if by a call to the mbtowc function, except that the conversion state of the mbtowc function is not affected.
wchar_t
in 7.17which is an integer type whose range of values can represent distinct codes for all members of the largest extended character set specified among the supported locales; the null character shall have the code value zero. Each member of the basic character set shall have a code value equal to its value when used as the lone character in an integer character constant if an implementation does not define
char str[]
與 char *str
的差別參考:defines plain char array objects
s
whose elements are initialized with character string literals.
The contents of the arrays are modifiable.
定義一個字元陣列,其內容是 string literal 所初始的,且陣列的內容是可以更改的
defines
p
with type pointer to char and initializes it to point to an object with type array of char with length 4 whose elements are initialized with a character string literal. If an attempt is made to usep
to modify the contents of the array, the behavior is undefined.
首先會宣告一個指向 char
的 pointer,並將其初始化,初始化會指向一個
字元陣列,這個陣列是 string literal 的,如上所述,嘗試對其內容修改是 undefined behavior 的
LeetCode 題目敘述,完成以下程式碼
KKK = ~higher
JJJ = ~lower
higher
, lower
}current state | input | after state |
---|---|---|
00 | 0 | 00 |
00 | 1 | 01 |
01 | 0 | 01 |
01 | 1 | 10 |
10 | 0 | 10 |
10 | 1 | 00 |
將 nums[i]
加入 lower
(LSB),用 xor
operation。若此 bit 是 1
(代表前面已經出現過1次了),那會被消成 0
,代表這個位置出現兩次了,後面要再加入 higher
檢查 higher
的狀態,若 higher
是 1
(表示前面已經出現過 2 次了),那最終的狀態應該要是 0
0
。若 higher
是 0 ,表示還沒出現過,所以做 ~higher
運算可以達到這個效果
將 nums[i]
加入 higher
(MSB),用 xor
operation,若此 bit 是 1
(代表前面已經出現過 2 次了,現在是第 3 次出現,這樣狀態應該要是 0
),那會被消成 0
檢查 lower
的狀態,若 lower
是 1 (表示這個 bit 是第 1 次出現,所以並不用加到 higher
),那狀態應該要是 0
1
。若 lower
是 0 ,表示不是第 1 次出現,可能是第 2 或 3 次,此時上一個動作就已經幫我們做好處理了,所以做 ~higher
運算可以達到這個效果
* 思路:利用一個陣列 `bitCnt[32]`,記錄每個位置的 bit 出現的次數,利用本題只會有出現3次或1次的狀況,所以可以用 `bitCnt[i] % 3` 來判斷該位置的 bit 是否是只出現一次的數字
* 缺點:另外宣告了一個 int 陣列,問題是這個陣列並不會被有效的使用,而且下面的迴圈內用到了 mod 運算,所以還有蠻多地方可以加強的
xor
operation 的特性: A ^ A = 0
,出現偶數次的 bit 在運算時可以直接被消去,所以只需記錄兩種狀態,出現 1 次或出現偶數次,這樣一個 bit 就可以代表了,實作方式跟 Single Nnumber 一樣討論奇數次的狀況,若出現 n 次,理論上需要 log2n 個變數來記錄狀態
比較直覺的方法同上面,利用 1 個大小為 32 個 int 的 int
陣列 bitCnt
記錄每個 bit 出現的次數,最後改成 bitCnt[i] % n
即可,但問題也相同,可能大多數並不需要用到 32 個 int,只需要 log2n 個 int 即可,在 n < 231 的情況下都能較有效的利用到 memory,同時也盡量避免 module operation
參考 這篇 的解說我覺得講的非常仔細,圖示也把核心概念解釋得很清楚如下:
其中的 m
就是 log2n ,也是所需 counter 的數量
這裡考慮出現 5 次的要求,因為最多會出現 5 次,所以需要 log25 = 3 個 counter x1
, x2
, x3
, bit 的轉換狀態如下:
注意第 Xi 個 bit 從 0 -> 1
的過程中,Xi-1, Xi-2, … , X1 這些 bits 必須全為 1 才能成立,要注意實做時要 Xm 計算到 X1 ,不然會 data loss 導致進位錯誤,到這邊我們已經可以正常統計每個位置的 bit 出現的次數,但接下來會有一個問題,m bits counter 理論上會統計到 2m - 1 而不是我們要的 n,根據上面的範例解釋就是該如何讓 100 -> 000
而不是 100 -> 101
,所以還需要設立一個機制能統計到 m 時歸零而不是繼續累計。
這裡很巧妙的利用到了 cutting
的機制,當 counter 累積到 n
的時時候會歸零,可以透過使用一個 mask
對所有的 counter 做檢查,mask 是個人覺得這題最 tricky 的地方,mask 的建制如下:
mask = ~ (y1 & y2 & … & ym)
yi = xi if ki is 1
yi = ~ xi if ki is 0
(ki 是數字出現次數二進制表示的第 i 個 bit)
說明:假設各 counter 的狀態如下 MSB 是 101
,即將要備歸零,而 LSB 的狀態是 110
,各 counter
表示如下:
做取 mask 的動作後 MSB
會得到 1
(需要歸零的 signal) (1 & ~0 & 1),LSB
會得到 0
(不需要歸零,所以並沒有效果)(1 & ~1 & 0),mask 再取 ~
即可達到將 counter
歸零的效果
mask
建立完成之後再依序對每個 counter 做檢查即可
執行結果
陣列
的形式紀錄 counter
就可以了