Vì sao bung vòng x8 lại chậm hơn x4? Tôi đếm lệnh và tìm ra thủ phạm: CPU hết thanh ghi

Hình dung mặt bàn làm việc của bạn. Những giấy tờ đang dùng dở nằm ngay trên bàn, với tay là lấy được — nhanh. Nhưng mặt bàn chỉ rộng chừng ấy: quá một số lượng, bạn buộc phải cất bớt vào ngăn kéo, và mỗi lần cần lại phải mở ngăn ra lấy, dùng xong lại cất, để chỗ cho tờ khác. Càng nhiều việc dở tay cùng lúc, bạn càng tốn thời gian mở-đóng ngăn kéo thay vì làm việc. Thanh ghi CPU chính là mặt bàn đó — cực nhanh nhưng cực ít chỗ — và cái "mở ngăn kéo" là thứ giải thích một bí ẩn tôi để ngỏ ở bài bung vòng lặp.

Ở bài mức tối ưu, ta thấy -O0 chậm gấp mấy lần -O2 vì nó để mọi biến trên ngăn xếp thay vì trong thanh ghi CPU. Bài này đo sâu vào chính cơ chế đó — cấp phát thanh ghi — và cái xảy ra khi nó không đủ chỗ: biến bị tràn ra ngăn xếp. Đo trong container gcc:13 (ARM). Và tôi tìm thấy lời giải cho một bí ẩn từ bài trước: vì sao bung vòng lặp với tám biến tích lũy lại chậm hơn với bốn.

Thanh ghi có hạn, và tràn khi hết chỗ

CPU tính toán trên thanh ghi — những ô nhớ cực nhanh nằm ngay trong lõi, đọc/ghi trong chưa tới một chu kỳ. Nhưng số thanh ghi rất hữu hạn: trên AArch64 (ARM 64-bit) có 31 thanh ghi số nguyên (x0–x30), trừ vài cái dành riêng (con trỏ ngăn xếp, địa chỉ trả về...) còn khoảng 28 dùng được. Trên x86-64 còn ít hơn — chỉ 16. Đó là kích thước mặt bàn.

Cấp phát thanh ghi (register allocation) là bài toán trình biên dịch xếp các biến của bạn vào số thanh ghi ít ỏi đó, giữ những biến đang sống (đang được dùng, chưa tính xong) trong thanh ghi càng nhiều càng tốt. Nó làm việc này rất giỏi. Nhưng có một giới hạn cứng nó không vượt được: khi số biến sống cùng lúc vượt số thanh ghi, nó buộc phải TRÀN (spill) — lưu tạm một biến xuống ngăn xếp (một lệnh str), giải phóng thanh ghi cho việc khác, rồi nạp lại (ldr) khi cần biến đó. Đúng cái mở-đóng ngăn kéo. Mỗi lần spill thêm một cặp store/load chạm bộ nhớ, và trong một vòng nóng, chúng cộng dồn.

Đo: qua ngưỡng, load/store leo dốc

Tôi viết các hàm với số biến tích lũy sống cùng lúc tăng dần — 4, 8, 16, 24, 32, 48 biến, mỗi biến một chuỗi độc lập cập nhật mỗi vòng lặp — rồi đếm số lệnh load/store trong vòng nóng của mỗi hàm (bằng objdump):

Số biến sống cùng lúc | lệnh ldr/str trong vòng nóng
   4 biến             |   1
   8 biến             |   7
  16 biến             |  19
  24 biến             |  30
  32 biến             |  55
  48 biến             | 103   <- tràn stack nặng

Với 4 biến, vòng nóng chỉ có 1 lệnh chạm bộ nhớ (đọc mảng đầu vào) — bốn biến tích lũy nằm gọn trong bốn thanh ghi, không spill. Nhưng số load/store leo dốc khi thêm biến: 7, rồi 19, rồi 30, và bùng lên 103 ở 48 biến. Đó là spill: khi số biến sống vượt ~28 thanh ghi, trình biên dịch phải liên tục đẩy biến xuống ngăn xếp và kéo lại trong mỗi vòng lặp. 48 biến sống chéo nhau tạo ra 103 lần chạm bộ nhớ mỗi vòng, thay vì 1.

Về thời gian, hiệu ứng tinh tế hơn: thời gian mỗi biến-mỗi-phần-tử đạt tốt nhất (~0,11 ns) quanh 16–32 biến, rồi nhích lên ở 48 (0,114 ns). Trên con chip này, các lần spill rơi vào cache L1 (rất nhanh), nên phạt thời gian nhẹ (~3%); nhưng số lệnh thì phình rõ, và trên một máy có áp lực thanh ghi cao hơn hay khi spill trượt khỏi L1, cái phạt đó sẽ cắn mạnh hơn nhiều.

Cú vấp: biến cục bộ không "miễn phí", và bí ẩn x8

Định kiến của tôi: "biến cục bộ chỉ là tên gọi, khai bao nhiêu tùy thích, trình biên dịch lo hết". Con số bác bỏ: biến cục bộ không miễn phí — mỗi biến sống chiếm một thanh ghi, và thanh ghi thì đếm được. Viết một vòng nóng với hàng chục giá trị sống chéo nhau là tự ép trình biên dịch spill, và mã chậm đi (hoặc ít nhất phình lệnh) đo được.

Và đây là lúc bí ẩn từ bài bung vòng lặp sáng tỏ. Ở đó, bung vòng với 4 biến tích lũy nhanh 3,72 lần, nhưng bung với 8 biến lại chậm hơn với 4 — tôi đã ghi nhận "vượt sức song song của CPU" mà chưa chỉ ra cơ chế. Giờ thì rõ: một phần của sự thoái lui đó chính là áp lực thanh ghi. Tám (hay hơn) biến tích lũy độc lập, cộng các biến điều khiển vòng và con trỏ, bắt đầu chạm trần thanh ghi, và trình biên dịch spill — thêm load/store nuốt mất cái lợi song song. Điểm ngọt của bung vòng không phải ngẫu nhiên ở ~4: nó là nơi số chuỗi song song vừa đủ lấp đơn vị thực thi mà chưa vượt số thanh ghi. Đây cũng là mặt kia của bài mức -O: -O0 chậm vì nó không cấp phát thanh ghi chút nào — mọi biến spill, cho ra 72 lệnh load/store thay vì 26.

Về đến code hằng ngày

Điều đầu tiên: giữ số giá trị sống cùng lúc trong vòng nóng ở mức nhỏ. Bạn hiếm khi khai báo biến với ý thức về thanh ghi, nhưng khi tối ưu một vòng nóng, để ý: nếu bạn có hàng chục biến tạm cùng sống, hay bung vòng quá tay tạo ra nhiều biến tích lũy, bạn đang ép spill. Chia vòng thành các phần nhỏ hơn với ít biến sống mỗi phần đôi khi nhanh hơn một vòng "làm hết mọi thứ cùng lúc". Đây cũng liên quan tới độ phức tạp không gian ở tầng vi mô nhất: thanh ghi là bộ nhớ nhanh nhất và ít nhất, và tràn nó là một dạng "hết chỗ".

Điều thứ hai: tin trình biên dịch cấp phát thanh ghi, nhưng đừng làm khó nó. Register allocation là một trong những phần tinh vi nhất của trình biên dịch, và nó làm tốt hơn con người trong hầu hết trường hợp — đừng cố "giúp" bằng cách viết mã máy trong đầu. Nhưng nó bị chặn bởi số thanh ghi vật lý, nên hãy giúp nó bằng cách giảm số giá trị sống đồng thời. Và biết rằng x86 (16 thanh ghi) dễ spill hơn ARM (31), nên cùng một code có thể spill trên máy này mà không trên máy kia.

Và đây là chỗ đáng nhớ, vì "tài nguyên nhanh nhưng hữu hạn, vượt ngưỡng là tràn xuống tầng chậm hơn" là một mô hình lặp lại ở mọi tầng của máy tính, không riêng thanh ghi. JVM cho thấy đúng cùng đường cong ở tầng cao: một HashMap cực nhanh khi vừa cache CPU, nhưng khi heap phình quá bộ nhớ vật lý thì OS swap ra đĩa — cùng ý "tràn khỏi tầng nhanh", chỉ khác quy mô hàng triệu lần. Bộ nhớ đệm của CSDL cũng vậy: work_mem của Postgres đủ thì sort/hash chạy trong RAM, thiếu thì tràn ra file tạm trên đĩa (đúng chữ "spill" mà Postgres dùng trong EXPLAIN), chậm hẳn. Và mọi cache LRU đều là câu chuyện này. Mẫu số chung, một mô hình đáng mang theo suốt nghề: máy tính là một chuỗi tầng nhớ nhanh-dần-nhỏ-dần (thanh ghi → cache → RAM → đĩa), mỗi tầng có sức chứa hữu hạn, và mỗi lần dữ liệu sống vượt sức chứa một tầng, nó "tràn" xuống tầng chậm hơn — hiệu năng sụt ở đúng cái ngưỡng đó, dù là 28 thanh ghi hay vài GB RAM.

Muốn tự thấy thì viết một hàm với chừng tám biến long tích lũy độc lập trong một vòng nóng, biên dịch gcc -O2 -S -o out.s file.c, và đếm số lệnh str/ldr (x86: mov với [rsp...] hay [rbp...]) trong vòng. Rồi tăng lên bốn mươi biến tích lũy và đếm lại: bạn sẽ thấy số lệnh chạm ngăn xếp tăng vọt — đó là spill, biến bị đẩy ra bộ nhớ vì hết thanh ghi. Đối chiếu với số thanh ghi của kiến trúc (x0–x30 trên ARM, 16 thanh ghi đa dụng trên x86-64) và bạn sẽ thấy ngưỡng khớp. Ba mươi giây đó cho bạn cảm nhận trực tiếp rằng thanh ghi là hữu hạn, và biến cục bộ, ở tầng sâu nhất, không hề miễn phí.