Đổi hai dòng vòng lặp, nhân ma trận nhanh gấp 3 mà không thêm phép tính nào

Cache xuất hiện suốt sê-ri này như một thủ phạm giấu mặt. Bài này gọi thẳng tên cái mặt xấu nhất của nó: cache thrashing — khi cách bạn truy cập dữ liệu khiến các dòng cache cứ bị đá ra ngay trước khi bạn kịp dùng lại chúng.

Hình dung bạn có một cái bàn làm việc bé xíu và một cái kho tài liệu ở tít cuối hành lang. Bàn chỉ để được vài tập hồ sơ. Nếu bạn làm việc gọn — lấy vài tập ra, dùng cho xong rồi mới đổi tập khác — thì mọi thứ trên bàn, với tay là có. Nhưng nếu mỗi thao tác lại cần một tập nằm ở tủ khác, bạn phải liên tục cất tập cũ, cuốc bộ ra kho lấy tập mới, quay về, rồi lát sau lại cần đúng tập vừa cất. Cả buổi bạn chạy hành lang thay vì làm việc. Đó là thrashing: cache có đó mà như không, mọi lần chạm đều phải ra tận RAM.

Có hai kiểu đẩy bạn vào cảnh đó. Kiểu thứ nhất là lượng dữ liệu bạn xào đi xào lại lớn hơn cache — quét tới cuối rồi vòng về đầu thì mấy dòng đầu đã bị đá sạch. Kiểu thứ hai là mẫu truy cập tệ: dù tổng dữ liệu vừa cache, nếu bạn nhảy cóc theo cột hay dồn hết vào vài tập, bạn phí gần hết mỗi dòng và đá dữ liệu tốt ra sớm. Tôi đo cả hai.

Cùng số phép, đổi thứ tự, nhanh gấp ba

Ví dụ đẹp nhất là nhân hai ma trận 1024×1024. Dù bạn viết vòng lặp kiểu gì, nó vẫn là đúng 2,1 tỷ phép nhân-cộng — Big-O không đổi một li. Nhưng nhìn cái này:

Bản ijk đọc ma trận B theo cột, mà ma trận lưu theo hàng, nên mỗi lần chạm là một dòng cache mới, dữ liệu tốt bị đá ra liên tục — thrash. Chỉ cần hoán vị hai vòng lặp thành ikj để B và C đều được đọc theo hàng, liền mạch, là nhanh gấp 3,1 lần. Cùng số phép tính, không thêm một dòng logic nào. Còn chia khối (tiling) — cắt ma trận thành ô 64×64 vừa cache rồi làm xong hẳn từng ô — cho tốc độ tương đương. Cùng thuật toán O(n³), mà cách duyệt định đoạt tất cả.

Cái kiểu thrashing thứ hai, tái dùng, tôi đo bằng một vòng quét lặp lại nhiều lượt trên các vùng kích thước khác nhau, đếm thời gian mỗi dòng cache chạm: vùng 64 KB vừa L1 cho 0,232 ns (lượt sau đọc thẳng từ cache), vùng 4 MB vừa L2 cho 0,463 ns, còn vùng 64 MB vượt cache thì 0,909 ns — chậm khoảng 4 lần, vì mỗi lượt quay về đầu thì LRU đã đá sạch, phải nạp lại từ RAM. Đây là quét tuần tự nên prefetch còn đỡ được nhiều; với truy cập ngẫu nhiên khoảng cách này lên tới cả trăm lần.

Hai niềm tin cùng sai

Tôi bước vào bài này với cái đầu của dân thuật toán thuần túy: cùng O(n³), cùng số phép nhân-cộng, thì viết vòng lặp kiểu gì chẳng như nhau, thứ tự chỉ là tiểu tiết. Sai. ijk và ikj làm y hệt 2,1 tỷ phép mà chênh nhau 3,1 lần. Thứ tự vòng lặp không phải tiểu tiết — nó là ranh giới giữa dùng cache và phá cache. Big-O đếm số phép, nhưng nó không đếm dòng cache, mà chính dòng cache mới cầm cái hằng số ẩn.

Nhưng có một niềm tin ngược cũng sai: "chỉ cần dữ liệu nhỏ hơn cache thì không bao giờ thrash". Không hẳn. Nếu bạn quét đi quét lại một vùng lớn hơn cache — chuyện cực thường gặp khi làm nhiều pass trên một mảng — thì mỗi lượt đá sạch trước khi bạn quay lại. Và ngay cả dữ liệu nhỏ hơn cache vẫn thrash được nếu các địa chỉ dồn vào cùng vài tập; đôi khi vài chục byte cũng đủ đá nhau loạn xạ. "Nhỏ hơn cache" chỉ đảm bảo không tràn dung lượng, chứ không đảm bảo bạn tái dùng tốt hay rải đều.

Ngoài đời thì sao

Bài học đầu tiên gần như miễn phí: duyệt dữ liệu theo đúng cách nó nằm trong bộ nhớ. Ma trận lưu theo hàng thì đừng để vòng trong chạy theo cột; hoán vị vòng lặp cho truy cập liền mạch, thế là xong, nhanh mấy lần mà không tốn gì. Nguyên tắc gọn: vòng trong cùng nên chạy trên cái chỉ số biến thiên nhanh nhất trong bố cục bộ nhớ.

Bài học thứ hai là chia khối khi phải xào lại dữ liệu lớn hơn cache — nhân ma trận, tích chập, xử lý ảnh, hay join trong cơ sở dữ liệu. Cắt thành khối vừa cache rồi làm xong hẳn từng khối, để dữ liệu ở lại cache suốt lúc còn cần. Đây chính là bí mật đằng sau tốc độ của BLAS, của các thư viện học sâu, và cũng là lý do numpy nhân ma trận nhanh hơn hẳn ba vòng for bạn tự viết — nó gọi xuống một kernel đã tiling tận răng. Bộ tối ưu truy vấn của database cũng chọn thuật toán join theo đúng tinh thần cache-aware này.

Muốn tự thấy thì nhanh thôi: viết nhân hai ma trận vuông theo thứ tự i, j, k, bấm giờ. Rồi hoán vị thành i, k, j và bấm lại — nhanh hẳn mấy lần dù cùng số phép. Thử thêm bản chia ô 64×64, cũng nhanh tương đương. Cuối cùng cộng dồn một mảng vừa L1 nhiều lượt rồi làm lại với mảng lớn hơn cache: bản lớn lết hẳn, dù mỗi lượt đọc đúng bằng ấy phần tử, chỉ vì lượt nào cũng phải ra RAM nạp lại. Số phép chỉ là một nửa câu chuyện; nửa còn lại là cách bạn đi qua dữ liệu, và nó đo được bằng lần.