“Không ngôn ngữ lập trình nào có thể sinh mã chạy nhanh hơn mã assembly được viết cẩn thận”
Đây là điều đã được nói đến rất nhiều tại nhiều diễn đàn và blog công nghệ nhưng hầu như không có ví dụ minh hoạ nào cụ thể?? Để kiểm chứng tuyên bố trên, mình đã thử viết 1 chương trình bằng ngôn ngữ C, sau đó thử optimize chương trình bằng mã assembly, và cuối cùng đo thời gian chạy của 2 phiên bản. Điều mình rút ra là thực sự 1 chương trình assembly chạy nhanh hơn hẳn chương trình C tương tự, đúng như tuyên bố.
Bài viết này viết về quá trình mình kiểm chứng cũng như những điều rút ra từ quá trình này.
Ta sẽ giải quyết bài toán: “biểu diễn tập con bằng số nhị phân”.
Ta có thể biểu diễn tập hợp con của 1 tập hợp bằng 1 chuỗi bit. Ví dụ xét tập hợp 4 phần tử, thì “0101” là 1 tập con. Ta có thể diễn giải chuỗi trên như sau: tập con có sự xuất hiện của phần tử vị trí 0 và 2. Nói 1 cách mình hoạ xét chuỗi ký tự “abcd” thì với chuỗi nhị phân ở trên ta có tập con “bd”.
Bài toán là làm thế nào để liệt kê tất cả các tập con 2 phần tử của tập hợp trên. Nói cách khác liệt kê các xâu có 2 ký tự từ xâu “abcd”
Ta sẽ sử dụng thuật toán được nghĩ ra bởi Bill Gosper được lưu lại trong HAKMEM số 175 (Hacker Memo) nổi tiếng của phóng thí nghiệm trí tuệ nhân tạo của trường MIT.
Thuật toán như sau: Giả sử có chuỗi bit x = xxx0 1111 0000 (xxx là 1 chuỗi bit 0 bất kỳ). Ta cần tìm cách sinh ra chuỗi bit có số lượng bit 1 không đổi. Nói cách khác kết quả của hàm sinh sẽ từ chuỗi hiện tại phải là xxx1 0000 0111. Các bước sinh diễn ra như sau:
- Thuật toán bắt đầu bằng cách tìm bit 1 cuối cùng bên phải bằng công thức s = x & -x cho ra kết quả xxx0 0001 0000
- Cộng kết quả hiện tại với x cho ra kết quả r = xxx1 0000 0000. Bit 1 ở đây là 1 bit trong kết quả.
- Đối với các bit kết quả còn lại, chúng ta tiến hành điều chỉnh n-1 bit 1, trong đấy n là số lượng bit 1 của nhóm bit 1 nằm bên phải nhất. Cụ thể ở đây là nhóm 1111. Ta có thể làm điều này bằng cách đầu tiên exclusive or (xor) r với x cho kết quả xxx1 1111 0000. Ta chia kết quả này cho s (là luỹ thừa của 2) và dịch kết quả có được thêm 2 vị trí nữa để loại bỏ bit không cần thiết. Kết quả có được là giá trị điểu chỉnh cuối cùng này or với r.
Công thức đại số để tính các bước ở trên như sau:
s <- x & -x y <- s + x y <- r | (((x xor r) >> 2) / s)
Ta sẽ benchmark bằng cách đo thời gian chạy của thuật toán viết bằng ngôn ngữ C và assembly rồi so sánh thời gian chạy của 2 chương trình viết bằng 2 ngôn ngữ với nhau.
Chương trình viết bằng C
Để benchmark ta viết chương trình C biểu diễn thuật toán trên. binreprlà hàm giúp in giá trị nhị phân giúp quá trình kiểm tra được dễ dàng hơn. Nội dung thuật toán được viết trong hàm snoob_c:
Tuyệt thuật toán chạy đúng! Ta sẽ cho thuật toán trên chạy 100 000 000 lần và đo tổng thời gian. Ta sửa lại hàm main như dưới đây:
Chương trình chạy 100 triệu lần hết 0.83s! C quả thực rất nhanh.
Chương trình viết bằng assembly
Để có thể optimize hàm snoob, ta sẽ thử quan sát mã assembly của hàm snoob_c do gcc sinh ra:
Quan sát mã assembly ta có vài nhận xét sau:
- Mã rất dài. Bên cạnh các instruction dùng để tính toán, các instruction dùng để di chuyển dữ liệu cũng chiếm khá nhiều thời gian chạy.
- Các kết quả tính toán trung gian được ghi ra bộ nhớ (do ta dùng các biến smalless, ripples, ones)
Theo như “con số về độ trễ mà mọi lập trình viên nên biết”, thì truy cập bộ nhớ / cache dù rất nhanh (tốn 0.5ns) vẫn chậm hơn rất nhiều so với truy cập trực tiếp từ thanh ghi. Ta đặt câu hỏi liệu có thể giảm thiểu lượt truy cập bộ nhớ cache được không?
Quay trở lại thuật toán, ta thấy công thức đại số dùng 6 phép tính. Số lượng biến sử dụng chỉ có 4 biến. Do đó ta hoàn toàn có thể loại bổ các truy cập bộ nhớ, tính toán trực tiếp bằng các thanh ghi. Ta có hàm snoob viết bằng assembly như sau:
Ta thay code hàm main thay vì gọi đến snoob_c ta gọi đến hàm snoob ở trên:
Chương trình chạy đúng! Giờ đến phẩn benchmark. Ta sử dụng lại đoạn code benchmark, lần này thay vì gọi hàm snoob_c ta gọi hàm snoob viết bằng assembly. Ta có kết quả như sau:
Ta có thể thấy tốc độ thay đổi 1 cách đáng kể! Thời gian chạy chỉ bằng 63.85% thời gian chạy lần trước đấy.
※Các đoạn code được chạy trên máy tính có phần cứng: cpu corei7, 8G Ram
- Bằng việc trực tiếp kiểm chứng, ta công nhận rằng mã viết bằng assembly nếu được optimize cẩn thận sẽ chạy nhanh hơn hẳn mã sinh bởi các ngôn ngữ bậc cao như C.
- Assembly rất thú vị. Ta có cảm giác kiểm soát toàn bộ máy tính!
- Hacker Delights
- HAKMEM
