WebAssembly thực chất không phải là một máy Stack: Sự thật về kiến trúc WASM

Ai cũng biết WebAssembly (WASM) là một máy Stack. Wikipedia nói vậy, tài liệu thiết kế chính thức của WASM cũng nói vậy, và bạn cũng có thể đã từng nghe điều đó. Tôi cũng từng nghĩ như vậy.

Đó là cho đến khi tôi bắt đầu viết mã WASM — không phải biên dịch ra WASM, mà là viết các lệnh (instruction) bằng tay. Và tôi đã phát hiện ra một sự khác biệt lớn giữa WASM và các ngôn ngữ dựa trên stack khác, khiến cho nhận định này trở nên gây hiểu lầm.

Hãy lùi lại một chút. Máy Stack thực chất là gì?

Giả sử bạn viết một chương trình bằng ngôn ngữ bậc cao, và tại một thời điểm nào đó bạn muốn tính toán biểu thức 2 * 3 + 5 * 7. Các ngôn ngữ bậc thấp không có khái niệm về biểu thức phức hợp: chúng chỉ có thể thực hiện một phép toán tại một thời điểm. Vì vậy, bạn cần thực hiện hai phép nhân, lưu kết quả của chúng, sau đó thực hiện phép cộng.

Nhiều ngôn ngữ bậc thấp, như ngôn ngữ hợp ngữ x86, sẽ biểu diễn các bước này như sau:

r1 = 2 * 3
r2 = 5 * 7
r3 = r1 + r2

Đây được gọi là máy thanh ghi (register machine). Bạn có các biến (gọi là thanh ghi), có thể được sử dụng để lưu trữ cả giá trị duy trì và kết quả tạm thời, và mỗi lệnh có dạng var1 = var2 op var3.

Các ngôn ngữ khác, như Forth hoặc Hex Casting, sử dụng stack cho mục đích này. Stack có thể lưu trữ một chuỗi các giá trị theo thứ tự, để các biểu thức con đã tính toán có thể nằm đó trong khi bạn đang làm việc trên các phần khác. Trong ngôn ngữ dựa trên stack, phép tính tương tự sẽ trông như sau:

2 3 * 5 7 * +

Hãy lưu ý sự tương đồng giữa hai chương trình: chúng có cùng số lượng bước, và các bước tương ứng thực hiện cùng một phép toán. Sự khác biệt chính là với máy stack, các giá trị được thao tác được mã hóa ngầm định theo thứ tự chương trình, trong khi máy thanh ghi luôn mã hóa các chỉ số.

Tuy nhiên, chúng ta đều biết nén dữ liệu không mất mát luôn thu nhỏ kích thước là không tồn tại, vậy thì sức mạnh biểu hiện nào bị mất đi khi làm cho các chỉ số trở nên ngầm định? Đối với các biểu thức đơn giản, không nhiều. Nhưng khi các giá trị được tái sử dụng, sự khác biệt trở nên rõ ràng.

Giả sử bạn là một trình biên dịch (compiler), và được yêu cầu biên dịch chương trình tính x * x * x.

Một máy stack như mô tả ở trên không cung cấp cách để tham chiếu cùng một giá trị hai lần: lệnh mul luôn nhân hai giá trị ở các vị trí khác nhau trên stack. Để kích hoạt phép tính này, các máy stack thực tế giới thiệu các thao tác thao tác stack (stack manipulation) ngoài tính toán thuần túy. Lệnh chúng ta cần gọi là dup, nó nhân đôi giá trị ở đỉnh stack:

x dup x mul mul

Bạn có thể nhận thấy máy thanh ghi tính (x*x)*x, trong khi máy stack tính x*(x*x). Hai cái này giống nhau đối với phép nhân, nhưng có thể khác nhau đối với các phép toán khác. Để khắc phục điều này, chúng ta cũng cần giới thiệu swap, đúng như tên gọi, hoán đổi hai giá trị ở đỉnh stack:

x dup mul x swap mul

Trong thực tế, nhiều thao tác hơn thường được sử dụng để tạo điều kiện thuận lợi cho tính toán: over (sao chép giá trị thứ hai từ dưới lên lên đỉnh), 2dup (nhân đôi hai giá trị), drop (loại bỏ giá trị cuối cùng), rot (di chuyển giá trị thứ ba từ dưới lên lên đỉnh), v.v.

Dưới góc độ này, máy stack có thể được xem là tách rời các thao tác khỏi các chỉ số mà chúng hoạt động trên đó. Trong khi máy thanh ghi luôn mã hóa các chỉ số và trả giá cao hơn khi chúng thừa thãi, máy stack mã hóa chúng theo nhu cầu, nhưng với cái giá là số lượng lệnh cao hơn.

Nếu bạn nhìn vào JVM, một máy stack nổi tiếng mà Wikipedia so sánh với WebAssembly, bạn sẽ tìm thấy danh sách các lệnh bytecode gần như giống hệt nhau:

iconst_2
iconst_3
imul
iconst_5
iconst_7
imul
iadd

JVM không phải là một máy stack thuần túy: cũng có các lệnh để truy cập biến cục bộ, như iload và istore. Nhưng có thể viết các chương trình JVM mạnh mẽ mà không cần sử dụng chúng, và javac chủ yếu chỉ sử dụng chúng cho các biến được lập trình viên Java tạo ra một cách rõ ràng.

Bây giờ hãy nhìn vào bộ lệnh của WASM:

local.get 0
local.get 0
i32.mul
local.get 0
i32.mul

Thú vị đấy chứ? WASM có rất nhiều lệnh nhận đối số và đặt giá trị trả về trên stack, nhưng hầu như không có lệnh nào có thể sắp xếp lại nó — và theo như tôi biết, drop chỉ tồn tại vì nếu không có nó, bạn sẽ không có cách nào để bỏ qua kết quả đầu ra của một hàm.

Về cơ bản, điều duy nhất mà WASM thuần túy có thể làm là đánh giá các biểu thức đơn giản chính xác như được viết trong mã nguồn. Một trình biên dịch tối ưu hóa không thể thực hiện loại bỏ biểu thức con chung (common subexpression elimination) hoặc tối ưu hóa expr^2 thành expr * expr mà không cần giới thiệu các biến mới. Ngay khi bạn cần bất cứ thứ gì phi tầm thường, bạn phải dùng đến các biến — và kết thúc với một máy thanh ghi, nơi ảo ảnh "máy stack" sụp đổ.

Theo quan điểm của tôi, cách đúng đắn để nhìn nhận WASM là như một máy thanh ghi với các phép toán được khái quát hóa thành các biểu thức phức hợp.

Trong WASM nhị phân, các biểu thức được mã hóa trong Ký pháp Ba Lan ngược (Reverse Polish notation), có thể được đánh giá bằng một stack, nhưng đây chỉ là một mã hóa. Trong WASM văn bản, ví dụ, chúng thay vào đó được biểu diễn trong ký pháp kiểu LISP — không kém hay hiệu quả hơn. Người ta có thể tưởng tượng một thế giới nơi WASM nhị phân sử dụng ký pháp tiền tố (prefix notation) cũng vậy, với ít tác động; nếu phải đoán, ký pháp hậu tố (postfix notation) được ưu tiên để đơn giản hóa các trình thông dịch không tối ưu hóa, hoặc có lẽ kinh nghiệm với các máy ảo dựa trên stack là yếu tố quyết định.

Quan điểm này càng được xác nhận thêm bởi thực tế là, cho đến khi WASM có phần mở rộng đa giá trị (multi-value), các khối luồng điều khiển (control flow blocks) gần như không thể tương tác với stack: các giá trị được đẩy lên stack trước if không thể được truy cập trong thân if, và thân if chỉ có thể trả về một giá trị, vì vậy if thực sự chỉ là một toán tử ternary, và ngay cả các giá trị với một người tiêu dùng duy nhất cũng phải đi qua các biến cục bộ (locals).

Liệu điều đó có thực sự quan trọng không? Hầu như mọi máy đều có thể được chuyển đổi sang SSA (Static Single Assignment), tại thời điểm đó định dạng đầu vào không còn là vấn đề; và tôi đoán sự đơn giản của việc triển khai dựa trên stack là một điều tốt cho việc chấp nhận WASM. Nhưng tôi nghĩ công bằng khi nói rằng kinh nghiệm với các máy ảo dựa trên stack không chuyển đổi tốt sang WASM, vì nó không thực sự là một máy stack.

Không lâu sau khi viết bài đăng này, tôi tìm thấy bài đăng tuyệt vời này bao gồm cùng một vấn đề từ một góc độ khác tập trung vào tối ưu hóa. Hãy đọc nó nhé!