Ở bài volatile ta thấy một từ khóa dùng để tắt tối ưu. Bài này là tấm gương của nó: restrict — một từ khóa dùng để bật tối ưu, bằng cách cho trình biên dịch một lời hứa. Lời hứa đó về aliasing (bí danh): hai con trỏ có trỏ chung một vùng nhớ không. Bài này đo restrict giúp sinh mã nhanh hơn thế nào — và tôi vấp đúng cái giá của lời hứa khi tôi phá nó.
restrict: lời hứa con trỏ không trùng
Đặt restrict trên một con trỏ là cam kết với trình biên dịch rằng vùng nhớ con trỏ đó trỏ tới chỉ được truy cập qua chính nó — không có con trỏ nào khác trong phạm vi đó trỏ vào cùng vùng. Nhờ lời hứa này, trình dịch được phép làm một điều nó thường không dám: sau khi ghi qua con trỏ a, nó không cần nạp lại giá trị đọc qua con trỏ b, vì nó tin rằng ghi vào a không thể thay đổi *b (chúng không trùng nhau).
Vì sao đây là vấn đề? Vì mặc định, khi thấy hai con trỏ int *a, int *b, trình dịch phải giả định chúng có thể trùng (a có thể == b) — như bài strict aliasing đã thấy, hai con trỏ cùng kiểu thì luôn có thể alias. Nên sau khi ghi *a, nó buộc phải nạp lại *b để phòng trường hợp *b vừa bị chính lần ghi đó thay đổi. restrict gỡ bỏ nỗi lo đó. Tôi đo một ví dụ nhỏ.
Đo: 4 lệnh thay vì 7
Hàm twice(a, b) cộng *b vào *a hai lần: *a += *b; *a += *b;. Không restrict, assembly ở -O2:
ldr w3, [b] ; đọc *b
ldr w2, [a] ; đọc *a
add ; str [a] ; *a += *b, GHI lại
ldr w1, [b] ; NẠP LẠI *b (vì a có thể == b, lần ghi trên có thể đã đổi *b)
add ; str [a] ; lần cộng thứ hai
Bảy lệnh, với một lần nạp lại *b sau khi ghi *a — trình dịch phải phòng trường hợp a == b. Với restrict:
ldr w2, [a] ; đọc *a
ldr w1, [b] ; đọc *b (MỘT lần)
add w1, w2, w1, lsl 1 ; *a + 2*(*b) (w1 lsl 1 = *b * 2)
str [a] ; ghi một lần
Bốn lệnh: nạp *b một lần, và vì biết a != b, trình dịch gộp cả hai phép cộng thành *a + 2*(*b) (dịch trái 1 bit = nhân 2), rồi ghi một lần. Ít lệnh hơn, ít truy cập bộ nhớ hơn — nhanh hơn. Với một vòng lặp lớn (a[i] = b[i] + c[i]), lợi ích còn rõ hơn vì restrict cho phép vector hóa tự do mà không phải dè chừng các mảng chồng nhau. Đến đây restrict trông như một cờ tăng tốc miễn phí. Rồi tôi thử phá lời hứa.
Một lần tôi đo hớ: restrict là lời hứa, phá là sai
Tôi tưởng restrict chỉ là một gợi ý tăng tốc vô hại — cứ thêm vào là nhanh hơn, như bật một mức -O. Để kiểm, tôi gọi hàm restrict với cùng một con trỏ cho cả a và b — twice_r(&x, &x) với x = 5 — điều mà lời hứa restrict cấm. Đo ra:
twice_n(&x, &x) -> 20 (phiên bản thường: đúng)
twice_r(&x, &x) -> 15 (phiên bản restrict: SAI!)
Phiên bản thường cho 20: khi a == b, *a += *b là x = 5+5 = 10, rồi x = 10+10 = 20 — đúng ngữ nghĩa "cộng chính nó hai lần". Nhưng phiên bản restrict cho 15: nó đã tối ưu dựa trên giả định a != b, tính *a + 2*(giá trị ban đầu của *b) = 5 + 2*5 = 15, không hề đọc lại *b sau lần ghi đầu. Vì tôi phá lời hứa (truyền con trỏ trùng), kết quả sai.
Bài học đo lường: restrict không phải speedup miễn phí — nó là một tối ưu đánh đổi bằng một cam kết về aliasing, và phá cam kết là hành vi không xác định cho kết quả sai. Nó tăng tốc bằng cách gỡ bỏ một phòng bị an toàn (việc nạp lại để phòng alias). Thêm restrict vào chỗ con trỏ có thể trùng là một bug đúng-đắn im lặng: mã chạy đúng với hầu hết đầu vào, rồi cho kết quả sai đúng lúc ai đó truyền vào hai con trỏ chồng nhau. Tôi đã lẫn "công cụ tối ưu" với "công cụ tối ưu vô điều kiện" — mà restrict có một điều kiện rất nghiêm: các con trỏ phải thật sự tách biệt.
Đây cũng là tấm gương đối xứng của volatile: volatile tắt tối ưu bằng cách nói "biến này có thể đổi ngoài tầm kiểm soát, đừng giả định"; restrict bật tối ưu bằng cách nói "vùng nhớ này chỉ tôi động vào, cứ giả định thoải mái". Cả hai đều là cách bạn nói với trình dịch một sự thật về bộ nhớ — và cả hai đều nguy hiểm nếu bạn nói sai.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên là chỉ dùng restrict khi bạn chắc chắn các con trỏ tách biệt. Ví dụ điển hình hợp lệ: một hàm nhận buffer nguồn và buffer đích riêng biệt (memcpy giả định không chồng nhau — đó là lý do có memmove cho trường hợp chồng), các mảng đầu vào và đầu ra khác nhau trong tính toán số học. Đừng thêm restrict một cách máy móc "để cho nhanh"; mỗi restrict là một cam kết bạn phải bảo đảm ở mọi nơi gọi hàm.
Hệ quả thứ hai là restrict cho lợi ích lớn nhất ở vòng lặp số học nặng. Trong xử lý mảng (c[i] = a[i] * b[i] + d[i]), khả năng alias giữa các mảng là thứ chặn trình dịch vector hóa và giữ giá trị trong thanh ghi. restrict (hoặc, tự động hơn, -fstrict-aliasing với các kiểu khác nhau, hoặc dùng thư viện đã tối ưu) tháo bỏ rào cản đó. Đây là kỹ thuật quen thuộc trong mã hiệu năng cao — nhưng phải kèm một chú thích rõ ràng rằng người gọi có trách nhiệm không truyền con trỏ chồng nhau.
Hệ quả thứ ba là bài học đo lường xuyên sê-ri về các "lời hứa với trình dịch": restrict, strict aliasing, assume, [[likely]]... — tất cả đều tăng tốc bằng cách cho trình dịch giả định điều gì đó bạn cam kết là đúng, và tất cả đều biến thành bug im lặng nếu cam kết sai. Con số mang theo: restrict hứa con trỏ không trùng để trình dịch bỏ nạp lại sau ghi (đo được: twice còn 4 lệnh thay vì 7, gộp thành a+2b) — nhanh hơn thật, nhưng là LỜI HỨA: truyền con trỏ trùng cho kết quả SAI (15 thay vì 20), là UB; chỉ dùng khi chắc chắn các con trỏ tách biệt. Tốc độ của restrict không phải cho không; nó là phần thưởng cho một cam kết mà bạn phải giữ đúng ở mọi nơi.
Thử ba mươi giây
Viết hai hàm cộng hai mảng: void addn(int *r, int *a, int *b, int n) và void addr(int *restrict r, int *restrict a, int *restrict b, int n), cùng thân for(i) r[i]=a[i]+b[i];. Dịch gcc -O2 -S file.c -o file.s và so hai hàm trong assembly: bản restrict thường ngắn hơn và dùng lệnh vector (.4s trên ARM), bản thường dài hơn vì phải kiểm tra chồng lấn lúc chạy. Rồi thử gọi bản restrict với addr(a, a, b, n) (r trùng a) và in kết quả — nó có thể sai. Chỉ vài lần đọc .s là bạn thấy restrict mua tốc độ bằng một lời hứa mà bạn phải giữ.
