Bài 32.326 phút đọc
restrict
Sau bài này bạn sẽ làm được
- Giải thích trùng bí danh và vì sao nó cản trở tối ưu
- Đọc hợp ngữ để thấy khác biệt giữa có và không có restrict
- Nêu hậu quả khi vi phạm lời hứa restrict
- Giải thích vì sao memcpy có restrict còn memmove thì không
restrict là từ khóa duy nhất trong C mà bạn hứa một điều với trình biên dịch chứ không phải yêu cầu nó làm gì. Lời hứa là: trong phạm vi này, không có con trỏ nào khác dùng để chạm vào cùng vùng nhớ.
#Vấn đề trùng bí danh
re.c
void cong(int *a, int *b, int *c) {
*a += *c;
*b += *c;
}terminal
gcc -O2 -S -masm=intel -o - re.c
cong:
mov eax, DWORD PTR [r8] ; doc *c
add DWORD PTR [rcx], eax ; *a += *c
mov eax, DWORD PTR [r8] ; DOC LAI *c
add DWORD PTR [rdx], eax ; *b += *c
retTrùng bí danh (aliasing)
Hai con trỏ khác nhau cùng trỏ tới một vùng nhớ. Khi có khả năng trùng bí danh, trình biên dịch phải giữ đúng thứ tự đọc ghi và không được dùng lại giá trị đã nạp vào thanh ghi.
Thêm restrict
void cong_r(int *restrict a, int *restrict b, int *restrict c) {
*a += *c;
*b += *c;
}terminal
gcc -O2 -S -masm=intel -o - re.c
cong_r:
mov eax, DWORD PTR [r8] ; doc *c MOT lan
add DWORD PTR [rcx], eax ; *a += *c
add DWORD PTR [rdx], eax ; *b += *c
retNăm lệnh xuống bốn. Lệnh mov thừa biến mất vì trình biên dịch bây giờ được phép giữ *c trong thanh ghi eax.
#restrict là một lời hứa
| Tình huống | Hợp lệ | Vì sao |
|---|---|---|
| f(a, b) với a và b là hai mảng riêng | Có | Đúng như lời hứa |
| f(a, a) khi f chỉ đọc qua cả hai | Có | Không ai ghi nên không có xung đột |
| f(a, a) khi f ghi qua p | Không | Vi phạm lời hứa, hành vi không xác định |
| f(a, a + 100) với hai vùng 50 phần tử | Có | Hai vùng không chồng nhau |
| f(a, a + 1) với hai vùng 50 phần tử | Không | Hai vùng chồng nhau 49 phần tử |
#Trong vòng lặp, chênh lệch rất lớn
Hai bản sao chép mảng
void chep(int *d, const int *s, size_t n) {
for (size_t i = 0; i < n; ++i) d[i] = s[i];
}
void chep_r(int *restrict d, const int *restrict s, size_t n) {
for (size_t i = 0; i < n; ++i) d[i] = s[i];
}terminal
gcc -O3 -S -masm=intel re.c && grep -c '' <(sed -n '/^chep:/,/ret/p' re.s)
48
sed -n '/^chep_r:/,/ret/p' re.s
chep_r:
test r8, r8
je .L22
sal r8, 2
jmp memcpy
.L22:
ret| Không restrict | Có restrict | |
|---|---|---|
| Số lệnh của hàm | 48 | 6 |
| Kiểm tra chồng nhau lúc chạy | Có | Không |
| Số nhánh rẽ | Nhiều | Một |
| Kết quả cuối | Vector hóa có điều kiện | Gọi thẳng memcpy |
| Chi phí cho n nhỏ | Kiểm tra trước rồi mới chép | Gọi hàm ngay |
Trường hợp restrict thật sự đáng giá
/* Nhan ma tran: vong lap trong doc B va ghi C.
Khong co restrict, trinh bien dich phai gia dinh
C co the trung voi A hoac B, nen khong giu duoc
tong trong thanh ghi. */
void nhan(double *restrict C,
const double *restrict A,
const double *restrict B,
size_t n)
{
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < n; ++j) {
double t = 0.0;
for (size_t k = 0; k < n; ++k)
t += A[i * n + k] * B[k * n + j];
C[i * n + j] = t;
}
}
/* Bien cuc bo t da giai quyet phan lon van de o vong trong.
Nhung restrict van giup o vong ngoai: khong co no,
trinh bien dich phai gia dinh viec ghi C[i*n+j] co the
sua A hoac B, nen phai nap lai chung o vong sau. */#Cái giá khi thất hứa
Thất hứa
#include <stdio.h>
void cong_r(int *restrict a, int *restrict b, int *restrict c) {
*a += *c;
*b += *c;
}
int main(void) {
int x = 1, y = 10;
cong_r(&x, &y, &x); /* a va c TRUNG NHAU: pha loi hua */
printf("x = %d, y = %d\n", x, y);
return 0;
}terminal
gcc -O0 -o th th.c && ./th
x = 2, y = 12
gcc -O2 -o th th.c && ./th
x = 2, y = 11
restrict không có tài liệu
/* Trong tep .h phat hanh ra ngoai */
void xu_ly(float *restrict ra, const float *restrict vao, size_t n);
/* Khong mot chu tai lieu nao. Nguoi dung thu vien cua ban
se goi xu_ly(a, a, n) de xu ly tai cho, va no se sai. */Ghi rõ trong tài liệu, kèm bản thay thế
/*
* Xu ly n mau tu vao ra ra.
*
* YEU CAU: hai bo dem ra va vao KHONG duoc chong nhau.
* Muon xu ly tai cho, dung xu_ly_tai_cho().
*/
void xu_ly(float *restrict ra, const float *restrict vao, size_t n);
/* Ban tai cho, khong co restrict: */
void xu_ly_tai_cho(float *bo_dem, size_t n);#Khi nào nên dùng
| Tình huống | Dùng restrict | Ghi chú |
|---|---|---|
| Hàm nhân ma trận, xử lý tín hiệu, xử lý ảnh | Nên | Vòng lặp dài, chênh lệch đo được |
| Hàm chép hoặc trộn hai bộ đệm | Nên | Đúng mẫu của memcpy |
| Hàm getter và setter nhỏ | Không | Không có gì để tối ưu |
| Tham số struct chỉ đọc | Không | Dùng const là đủ |
| Hàm gọi lại do người dùng cung cấp | Không | Bạn không kiểm soát được người gọi |
| Bất cứ chỗ nào bạn chưa đo | Không | Rủi ro có, lợi ích chưa biết |
Thay thế: quy tắc trùng bí danh nghiêm ngặt
/* GCC va Clang o -O2 mac dinh bat -fstrict-aliasing.
Quy tac: hai con tro KHAC KIEU thi trinh bien dich duoc phep
gia dinh chung khong trung nhau. */
void f(int *a, float *b) {
*a = 1;
*b = 2.0f; /* trinh bien dich gia dinh khong dung *a */
}
/* Nghia la doi khi ban duoc toi uu MIEN PHI, khong can restrict,
chi vi kieu khac nhau.
Nhung dieu do cung nghia la ma nhu sau la SAI: */
float f_bit(int x) {
return *(float *)&x; /* vi pham quy tac trung bi danh */
}
float f_dung(int x) {
float y;
memcpy(&y, &x, sizeof y); /* dung: memcpy luon hop le */
return y;
}
/* Hoac union, trong C11 thi doc thanh vien khac cua union
la hop le va co dinh nghia: */
float f_union(int x) {
union { int i; float f; } u = { .i = x };
return u.f;
}
/* Phan 13 se noi ky ve quy tac nay va ve char *, kieu duy nhat
duoc phep tro vao bat cu thu gi. */Tự làm thử
- Viết hàm
congcó và không córestrictrồi so hợp ngữ ở-O2. - Đếm số lệnh của hàm chép mảng ở
-O3trong hai trường hợp. - Cố tình gọi hàm
restrictvới hai con trỏ trùng nhau, chạy ở-O0và-O2. - Xác nhận
-Wall -Wextravà UBSan đều im lặng trước vi phạm đó. - Đọc nguyên mẫu của
memcpyvàmemmovetrongstring.hvà giải thích chỗ khác nhau. - Đo tốc độ hàm nhân ma trận 256x256 có và không có
restrict.
Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.
Tóm tắt
- Không có
restrict, trình biên dịch phải giả định mọi con trỏ cùng kiểu đều có thể trùng nhau, nên phải nạp lại giá trị sau mỗi lần ghi. restrictlà lời hứa của bạn, không phải yêu cầu với trình biên dịch, và không công cụ nào kiểm tra được nó.- Trong vòng lặp chép mảng, chênh lệch đo được là 48 lệnh xuống 6, vì phần kiểm tra chồng nhau lúc chạy biến mất.
- Thất hứa cho ra kết quả khác nhau giữa
-O0và-O2mà không có cảnh báo nào. - Chỉ dùng khi đủ bốn điều kiện: có vòng lặp, đã đo, chứng minh được không trùng, và ghi vào tài liệu.