Bỏ qua điều hướng, tới nội dung chính
Học C
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
    ret
Trù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
    ret

Nă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ốngHợp lệVì sao
f(a, b) với a và b là hai mảng riêngCóĐúng như lời hứa
f(a, a) khi f chỉ đọc qua cả haiCóKhông ai ghi nên không có xung đột
f(a, a) khi f ghi qua pKhôngVi 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ôngHai 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 restrictCó restrict
Số lệnh của hàm486
Kiểm tra chồng nhau lúc chạyCóKhông
Số nhánh rẽNhiềuMột
Kết quả cuốiVector hóa có điều kiệnGọi thẳng memcpy
Chi phí cho n nhỏKiểm tra trước rồi mới chépGọ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ốngDùng restrictGhi chú
Hàm nhân ma trận, xử lý tín hiệu, xử lý ảnhNênVòng lặp dài, chênh lệch đo được
Hàm chép hoặc trộn hai bộ đệmNênĐúng mẫu của memcpy
Hàm getter và setter nhỏKhôngKhông có gì để tối ưu
Tham số struct chỉ đọcKhôngDùng const là đủ
Hàm gọi lại do người dùng cung cấpKhôngBạn không kiểm soát được người gọi
Bất cứ chỗ nào bạn chưa đoKhôngRủ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ử

  1. Viết hàm cong có và không có restrict rồi so hợp ngữ ở -O2.
  2. Đếm số lệnh của hàm chép mảng ở -O3 trong hai trường hợp.
  3. Cố tình gọi hàm restrict với hai con trỏ trùng nhau, chạy ở -O0 và -O2.
  4. Xác nhận -Wall -Wextra và UBSan đều im lặng trước vi phạm đó.
  5. Đọc nguyên mẫu của memcpy và memmove trong string.h và giải thích chỗ khác nhau.
  6. Đ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.
  • restrict là 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 -O0 và -O2 mà 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.