2022q1 Homework5 (quiz8) answer
contribute by < arthurchang09 >
測驗一
第 5 行的 while 是確認字串是否對齊，若沒對齊則跳過這部分的輸入。
接著，若字串長度大於 long ，在 x86_64 處理器上資料寬度為 64 bits ，即 8 個字元，會進入第 12 行的 if 中。
下方的程式碼將要尋找的字元變成 64 bits 的 mask ，用來尋找 64 bits 中 是否有目標字元。假設要尋找 . 這個字元，其 16 進位為 0x2e，經過下方程式，mask 會變成 0x2e2e2e2e2e2e2e2e
在 28 行透過 DETECT_CHAR 判斷這 64 bits 是否存在目標字元，接著第 48 行再用 while 從這 64 bits 找到第一個目標字元並 return。 若都未找到，則回傳 NULL。
比較 Linux 核心原本 (與平台無關) 的實作、 memchr_opt
Linux 核心原本 (與平台無關) 之程式碼如下
其原理不複雜，使用 while 迴圈一個個走訪每一個字元，直到找到第一個目標字元。
在 x86 平台有以下 inline assembly
然而編譯時出現錯誤
根據 AT&T Syntax versus Intel Syntax ， movl 和 decl 之 l 為 long (32 bits)，依據 LP64，long 的資料寬度為 64 bits ，因此將上方程式碼稍作修改，將 movl decl 改成 mov dec 或 movq decq， q 為 quadruple word (64-bit) ，如下：
接著，我測試三者尋找目標字元所花費的時間。我宣告一個長度為 1000 的字元陣列，每個元素初始化為字元 0 ，目標字元 4 會逐一放在第 0 個字元、第 1 個字元直到第 998 個字元，第 999 字元為 \0。採用 struct timespec 測量找到目標字元的時間。總共測量 120 次時間並去掉最小和最大各 10 個數值。
將測試程式碼移到 GitHub 或 gist 上，讓開發紀錄更簡潔。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv
以下為測試程式碼：
Full Code
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <stddef.h>
#include <limits.h>
#include <time.h>
#include <unistd.h>
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))
#define LBLOCKSIZE (sizeof(long))
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)
#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) -0x01010101) & ~(X) & 0x80808080)
#else
#if LONG_MAX == 9223372036854775807L
#define DETECT_NULL(X) (((X) -0x0101010101010101) & ~(X) & 0x8080808080808080)
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
#define DETECT_CHAR(X, MASK) (DETECT_NULL(X ^ MASK))
#define LENGTH 120
#define CUT 10
#define STRLEN 1000
void *memchr_org(const void *s, int c, size_t n)
{
const unsigned char *p = s;
while (n-- != 0) {
if ((unsigned char)c == *p++) {
return (void *)(p - 1);
}
}
return NULL;
}
void *memchr_opt(const void *src_void, int c, size_t length)
{
const unsigned char *src = (const unsigned char *) src_void;
unsigned char d = c;
while (UNALIGNED(src)) {
if (!length--)
return NULL;
if (*src == d)
return (void *) src;
src++;
}
if (!TOO_SMALL(length)) {
unsigned long *asrc = (unsigned long *) src;
unsigned long mask = d << 8 | d;
mask = mask << 16 | mask;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask = (mask << i) | mask;
int index = 0;
while (length >= LBLOCKSIZE) {
if ( !DETECT_CHAR(*asrc, mask)) {
asrc += 1;
length -= LBLOCKSIZE;
}
else
break;
}
src = (unsigned char *) asrc;
}
while (length--) {
if (*src == d)
return (void *) src;
src++;
}
return NULL;
}
void *memchr_x86(const void *cs, int c, size_t count)
{
int d0;
void *res;
if (!count)
return NULL;
asm volatile("repne\n\t"
"scasb\n\t"
"je 1f\n\t"
"mov $1,%0\n"
"1:\tdec %0"
: "=D" (res), "=&c" (d0)
: "a" (c), "0" (cs), "1" (count)
: "memory");
return res;
}
int cmp ( const void *a , const void *b )
{
return *(int *)a > *(int *)b;
}
int main()
{
char str[STRLEN];
memset(str,'0', sizeof(char)*STRLEN);
str[STRLEN - 1] = '\0';
char ch = '4';
int data[3][LENGTH];
memset(data,0,sizeof(data));
int sum[3];
memset(sum,0,sizeof(sum));
struct timespec t1,t2,t3,t4,t5,t6;
for (int k = 0; k < STRLEN - 1; ++k){
memset(str,'0', sizeof(char)*STRLEN);
str[STRLEN - 1] = '\0';
str[k] = '4';
memset(data,0,sizeof(data));
memset(sum,0,sizeof(sum));
for (int i = 0; i < LENGTH; ++i) {
clock_gettime(CLOCK_REALTIME, &t1);
char *ret = memchr_opt(str, ch, strlen(str));
clock_gettime(CLOCK_REALTIME, &t2);
data[0][i] = t2.tv_nsec - t1.tv_nsec;
clock_gettime(CLOCK_REALTIME, &t3);
ret = memchr_x86(str, ch, strlen(str));
clock_gettime(CLOCK_REALTIME, &t4);
data[1][i] = t4.tv_nsec - t3.tv_nsec;
clock_gettime(CLOCK_REALTIME, &t5);
memchr_org(str, ch, strlen(str));
clock_gettime(CLOCK_REALTIME, &t6);
data[2][i] = t6.tv_nsec - t5.tv_nsec;
usleep(1500);
}
printf("%d ",k);
for (int i = 0; i < 3; ++i) {
qsort(data[i],LENGTH,sizeof(int),cmp);
for (int j = CUT; j < LENGTH - CUT; ++j) {
sum[i] += data[i][j];
}
printf("%d ", sum[i] / (LENGTH - (CUT << 1)));
}
printf("\n");
}
return 0;
}
下圖為在虛擬機上的結果：
引入 glibc 之 memchr.S
glibc 之 memchr.S如下:
#include <sysdep.h>
#ifdef USE_AS_WMEMCHR
# define MEMCHR wmemchr
# define PCMPEQ pcmpeqd
#else
# define MEMCHR memchr
# define PCMPEQ pcmpeqb
#endif
.text
ENTRY(MEMCHR)
movd %esi, %xmm1
mov %edi, %ecx
#ifdef USE_AS_WMEMCHR
test %rdx, %rdx
jz L(return_null)
shl $2, %rdx
#else
punpcklbw %xmm1, %xmm1
test %rdx, %rdx
jz L(return_null)
punpcklbw %xmm1, %xmm1
#endif
and $63, %ecx
pshufd $0, %xmm1, %xmm1
cmp $48, %ecx
ja L(crosscache)
movdqu (%rdi), %xmm0
PCMPEQ %xmm1, %xmm0
pmovmskb %xmm0, %eax
test %eax, %eax
jnz L(matches_1)
sub $16, %rdx
jbe L(return_null)
add $16, %rdi
and $15, %ecx
and $-16, %rdi
add %rcx, %rdx
sub $64, %rdx
jbe L(exit_loop)
jmp L(loop_prolog)
.p2align 4
L(crosscache):
and $15, %ecx
and $-16, %rdi
movdqa (%rdi), %xmm0
PCMPEQ %xmm1, %xmm0
pmovmskb %xmm0, %eax
sar %cl, %eax
test %eax, %eax
je L(unaligned_no_match)
bsf %eax, %eax
sub %rax, %rdx
jbe L(return_null)
add %rdi, %rax
add %rcx, %rax
ret
.p2align 4
L(unaligned_no_match):
neg %rcx
add $16, %rcx
sub %rcx, %rdx
jbe L(return_null)
add $16, %rdi
sub $64, %rdx
jbe L(exit_loop)
.p2align 4
L(loop_prolog):
movdqa (%rdi), %xmm0
PCMPEQ %xmm1, %xmm0
pmovmskb %xmm0, %eax
test %eax, %eax
jnz L(matches)
movdqa 16(%rdi), %xmm2
PCMPEQ %xmm1, %xmm2
pmovmskb %xmm2, %eax
test %eax, %eax
jnz L(matches16)
movdqa 32(%rdi), %xmm3
PCMPEQ %xmm1, %xmm3
pmovmskb %xmm3, %eax
test %eax, %eax
jnz L(matches32)
movdqa 48(%rdi), %xmm4
PCMPEQ %xmm1, %xmm4
add $64, %rdi
pmovmskb %xmm4, %eax
test %eax, %eax
jnz L(matches0)
test $0x3f, %rdi
jz L(align64_loop)
sub $64, %rdx
jbe L(exit_loop)
movdqa (%rdi), %xmm0
PCMPEQ %xmm1, %xmm0
pmovmskb %xmm0, %eax
test %eax, %eax
jnz L(matches)
movdqa 16(%rdi), %xmm2
PCMPEQ %xmm1, %xmm2
pmovmskb %xmm2, %eax
test %eax, %eax
jnz L(matches16)
movdqa 32(%rdi), %xmm3
PCMPEQ %xmm1, %xmm3
pmovmskb %xmm3, %eax
test %eax, %eax
jnz L(matches32)
movdqa 48(%rdi), %xmm3
PCMPEQ %xmm1, %xmm3
pmovmskb %xmm3, %eax
add $64, %rdi
test %eax, %eax
jnz L(matches0)
mov %rdi, %rcx
and $-64, %rdi
and $63, %ecx
add %rcx, %rdx
.p2align 4
L(align64_loop):
sub $64, %rdx
jbe L(exit_loop)
movdqa (%rdi), %xmm0
movdqa 16(%rdi), %xmm2
movdqa 32(%rdi), %xmm3
movdqa 48(%rdi), %xmm4
PCMPEQ %xmm1, %xmm0
PCMPEQ %xmm1, %xmm2
PCMPEQ %xmm1, %xmm3
PCMPEQ %xmm1, %xmm4
pmaxub %xmm0, %xmm3
pmaxub %xmm2, %xmm4
pmaxub %xmm3, %xmm4
pmovmskb %xmm4, %eax
add $64, %rdi
test %eax, %eax
jz L(align64_loop)
sub $64, %rdi
pmovmskb %xmm0, %eax
test %eax, %eax
jnz L(matches)
pmovmskb %xmm2, %eax
test %eax, %eax
jnz L(matches16)
movdqa 32(%rdi), %xmm3
PCMPEQ %xmm1, %xmm3
PCMPEQ 48(%rdi), %xmm1
pmovmskb %xmm3, %eax
test %eax, %eax
jnz L(matches32)
pmovmskb %xmm1, %eax
bsf %eax, %eax
lea 48(%rdi, %rax), %rax
ret
.p2align 4
L(exit_loop):
add $32, %edx
jle L(exit_loop_32)
movdqa (%rdi), %xmm0
PCMPEQ %xmm1, %xmm0
pmovmskb %xmm0, %eax
test %eax, %eax
jnz L(matches)
movdqa 16(%rdi), %xmm2
PCMPEQ %xmm1, %xmm2
pmovmskb %xmm2, %eax
test %eax, %eax
jnz L(matches16)
movdqa 32(%rdi), %xmm3
PCMPEQ %xmm1, %xmm3
pmovmskb %xmm3, %eax
test %eax, %eax
jnz L(matches32_1)
sub $16, %edx
jle L(return_null)
PCMPEQ 48(%rdi), %xmm1
pmovmskb %xmm1, %eax
test %eax, %eax
jnz L(matches48_1)
xor %eax, %eax
ret
.p2align 4
L(exit_loop_32):
add $32, %edx
movdqa (%rdi), %xmm0
PCMPEQ %xmm1, %xmm0
pmovmskb %xmm0, %eax
test %eax, %eax
jnz L(matches_1)
sub $16, %edx
jbe L(return_null)
PCMPEQ 16(%rdi), %xmm1
pmovmskb %xmm1, %eax
test %eax, %eax
jnz L(matches16_1)
xor %eax, %eax
ret
.p2align 4
L(matches0):
bsf %eax, %eax
lea -16(%rax, %rdi), %rax
ret
.p2align 4
L(matches):
bsf %eax, %eax
add %rdi, %rax
ret
.p2align 4
L(matches16):
bsf %eax, %eax
lea 16(%rax, %rdi), %rax
ret
.p2align 4
L(matches32):
bsf %eax, %eax
lea 32(%rax, %rdi), %rax
ret
.p2align 4
L(matches_1):
bsf %eax, %eax
sub %rax, %rdx
jbe L(return_null)
add %rdi, %rax
ret
.p2align 4
L(matches16_1):
bsf %eax, %eax
sub %rax, %rdx
jbe L(return_null)
lea 16(%rdi, %rax), %rax
ret
.p2align 4
L(matches32_1):
bsf %eax, %eax
sub %rax, %rdx
jbe L(return_null)
lea 32(%rdi, %rax), %rax
ret
.p2align 4
L(matches48_1):
bsf %eax, %eax
sub %rax, %rdx
jbe L(return_null)
lea 48(%rdi, %rax), %rax
ret
.p2align 4
L(return_null):
xor %eax, %eax
ret
END(MEMCHR)
#ifndef USE_AS_WMEMCHR
strong_alias (memchr, __memchr)
libc_hidden_builtin_def(memchr)
#endif
嘗試編譯時發生以下錯誤
先將這一行暫時註解掉，執行以下指令
得到以下輸出
上方的 error 大多都是格式上的錯誤，參考 baby-steps-in-assembly 將組合語言稍加修改，引入 macro.h ，並將此 memchr define 為 memchr1 ，方便在主程式 test.c 呼叫。部分擷取如下:
在主程式也要宣告相對應之 function
將所有 label 的格式修改，如: L(return_null) 改成 L_return_null。最後幾行的 #ifndef 註解掉使編譯能通過。
執行以下命令編譯 test.c 並與 memchr.S link 起來
執行測驗一之測試程式的結果如下
效能比較
我發現先前分析之程式碼有錯誤，memchr_opt 前面使用之 usleep() 太長，導致測量的時間較長，低估了效率。因此我將每一個 memchr 測試統一延遲 1 個 ，這樣的結果會比較公平，受到的影響皆相同。
我也參考 fibdrv 的 效能分析提示 將測試程式指定在一個 CPU 上，排除干擾效能分析的因素，在我筆電的雙系統上測試，得到下圖：
由此圖很明顯可看出效能由高到低為 glibc > memchr-opt > memchr-x86 > original 。
比較出人意外的是 memchr_opt 比 memchr-x86 快，回顧 memchr-x86 程式碼，
根據 GCC-Inline-Assembly-HOWTO 以及 Extended Asm - Assembler Instructions with C Expression Operands ， Inline Assembly 之架構如下：
output operands 和 input operands 放置 register 對應的變數，會用 %數字 從 output operands 編號，以 memchr_x86 為例， %0 即是 "=D" (res) ， %1 為 "=&c" (d0) ，若 output 和 input 為相同 register ，則會出現 "0" (cs) 的型態，表示 cs 和編號 0 ， 即"=D" (res) 同一個 register 。
在這段組合語言中，變數對應的 register 如下：
| Parameter |
Register |
| cs |
EDI |
| c |
AL(EAX) |
| count |
ECX |
| d0 |
ECX |
| res |
EDI |
根據 Intel Architecture Software Developer’s Manual Volume 2:
Instruction Set Reference ，在第 365 頁，第一個指令 repne (repeat while not equal) 是和 string 操作相關，其執行條件如下:
| Repeat Prefix |
Termination Condition 1 |
Termination Condition 2 |
| REPNE/REPNZ |
ECX=0 |
ZF=1 |
換而言之， repne 的作用類似 while 迴圈，大略可對應 Linux 核心原本 (與平台無關) 中的 while (n-- != 0)。
scasb 是用來比較從記憶體搬來的 1 個 byte 和暫存器 AL 的值是否相等。根據結果設定對應之EFLAGS register 中的 status flag ，應該是 Zero Flag 。比較完後，會依據 EFLAGS register 的 DF Flags 將 EDI register 加一或減一。這裡沒有特別設定，為加一。
當符合 repne 結束條件，即 ZF = 1 或走完整個字串後，je 會判斷 ZF 的值。其功能為 Jump short if equal (ZF=1) ，因此有找到 match 之字元，會跳至 label 1 ，用 dec 將 res 減一，因為找到 match 字串後 EDI register 會自動加一。
反之，ZF = 0 ，則會將 1 放入 res ，後面的 dec 將 res 減一得 0 ，即 NULL。
由以上說明可見 memchr_x86 其實就是 Linux 核心原本 (與平台無關) 換成組合語言，我將這兩個 function 的 assmebly 列出，如下:
gcc -S test.c
memchr_x86
memchr_linux
可看出 memchr_x86 在比較字串方面比 memchr_linux 少不少，推測這應該是效能較佳的原因。
memchr_opt 和 glibc memchr.c
下圖為 memchr_opt 和 glibc-memchr.c 的執行時間比較，測量方式如 memchr 與 strchr 比較 所述，有趣的是兩者執行的時間幾乎相同。
接著觀察 glibc-memchr.c 的程式碼，如下：
其程式碼之想法和 memchr_opt 一樣，都是採用 64 bits 之 mask 來尋找目標字元。程式碼一開始同樣是對字串做 alignment，接著用相近的方式做出 64 bits 之 mask ，比較 64 bits 之方法同樣採用 xor 等等。 memchr_opt 使採用 DETECT_CHAR 來包裝這樣的操作。總而言之，這兩者是用不同的方式實作相同的想法，因此執行時間上也幾乎一樣。
memchr 和 strchr 比較
strchr 的 Linux 組合語言版本尚有問題須解決，如下面所示，先列出其他之比較。
效能分析之模式參考 https://gist.github.com/nico/2624336 ，測量方式依舊使用 struct timespec ，測量執行兩百次之時間再除以兩百得到執行一次之時間。
下圖是 glibc-memchr.S 和直接呼叫 <string.h> 中 memchr 的比較，兩者的執行時間皆是所有 memchr 版本中前二低，推測 <string.h> 中 memchr 應該是 glibc-memchr.S 的實作。
接著比較 memchrr 與 strchr 之差別，
由上圖可見，memchr-linux 比 strchr-linux 還要快，到 glibc-memchr.c 和 glibc-strchr.c 時依舊有領先，但比到 default 的部分，如下圖，strchr 就比 memchr 還快。
組合語言的部分也是如此
HackMD
