Tối ưu hiệu năng Bytecode - Virtual Machine

Tối ưu hiệu năng Bytecode - Virtual Machine

Mình đã viết một ngôn ngữ lập trình script và rất quan tâm đến hiệu năng và tốc độ xử lý của nó. Trong bài viết này, mình muốn chia sẻ kinh nghiệm của mình khi xử lý phần máy ảo cho ngôn ngữ.

Trong bài viết này, mình sẽ đi vào chi tiết về cách tạo và tối ưu máy ảo (virtual machine) để thực thi bytecode của một ngôn ngữ lập trình trên các trình biên dịch phổ biến (cross-compiler).

Bài viết này sẽ hữu ích cho những ai đam mê nghiên cứu viết ngôn ngữ lập trình hoặc sử dụng máy ảo cho các mục đích khác nhau như viết giả lập.

Bytecode

Bytecode, còn được gọi là portable code hoặc p-code, là cách lưu trữ dạng mã chỉ thị (instructions - opcode) trong lập trình máy tính, được thiết kế để phần mềm thông dịch thực hiện hiệu quả trên nền tảng máy ảo (theo Wiki).

Đơn giản hơn, bytecode là một chuỗi các chỉ thị được tạo ra sau khi biên dịch mã nguồn và được đưa vào máy ảo để thực thi.

Hiện nay, có hai dạng opcode instruction phổ biến:

32bit

Theo kiểu nguyên mẫu của ISA, giống với các chỉ thị được sử dụng trên CPU thật. Gói gọn trong 32bit đó, sẽ chứa cả opcode và các tham số phụ như dấu, đối số khác, địa chỉ register...

Từ phiên bản Lua 5.0, người ta đã chuyển sang sử dụng register-based và 32bit instruction. Bạn có thể thấy ví dụ về điều này trong The Implementation of Lua 5.0 và Lua 5.0 source code.

• 6 bit đầu chứa opcode
• 8 bit dành cho arg A
• 18 bit còn lại được chia đều cho B và C
• 18 bit cuối cùng dành cho Bx, để biểu diễn số hạng đơn lớn hơn. sBx được sử dụng cho số có dấu.

8bit (1 byte đơn)

Phương pháp này ít phổ biến hơn, nhưng có ưu điểm là tốn ít byte hơn so với 32bit, ví dụ:

• Opcode NOTHING, không cần thực hiện gì cả. Khi gặp nó, máy ảo chỉ cần next đến opcode tiếp theo. Nếu dùng 32bit (4 byte) thì sẽ tốn đến 3 byte.
• Một điểm yếu khác là cần dùng nhiều mã hơn để biểu diễn trong một số trường hợp, chẳng hạn muốn có số nguyên 64bit, thì cần tới 8 byte tiếp theo.

Bạn có thể dễ dàng thấy ví dụ về phương pháp này trong ebook Crafting Interpreters.

Tối ưu hiệu năng Bytecode - Virtual Machine

• OP_RETURN chỉ cần 1 byte
• OP_CONSTANT cần thêm 1 byte để lấy vị trí đã lưu của constant (giới hạn là 256 constant, nếu muốn tăng thêm thì cần 1 byte hoặc hơn).

Virtual machine

Máy ảo ở đây là một môi trường được xây dựng trên máy thật, giống như mô phỏng CPU hay máy thật và được dùng để thực thi các chỉ thị đã được đưa vào (bytecode).

Trong ngôn ngữ lập trình sử dụng máy ảo, có hai kiểu xây dựng thông dụng:

• Registers based (các thanh ghi), giống như một CPU, thường thấy trong JVM và Lua VM.
• Stack based (mô hình ngăn xếp), thay vì giới hạn nghiêm ngặt số thanh ghi chứa giá trị, cách này rộng hơn và tốn nhiều tài nguyên hơn, nhưng các giá trị có thể lưu trữ lâu dài hơn trên stack ảo.

Triển khai máy ảo

Mục đích của máy ảo trong bài viết này là tương tác với hai giá trị constant và value (đơn giản chỉ là số nguyên) thông qua các chỉ thị đã thiết lập sẵn. Khi chương trình kết thúc, nó sẽ trả về giá trị value.

Phần này, mình sẽ chỉ sử dụng ngôn ngữ C đơn giản vì hai lý do:

• C là ngôn ngữ cấp hệ thống, dễ dàng tương tác với bộ nhớ.
• Hầu hết các máy ảo cần hiệu năng cao đều được viết bằng C.

Khai báo:

#include 
#include 

typedef uint8_t u8; // for opcode
typedef uint16_t u16; // _ arg
typedef uint32_t u32; // _ instruction
typedef uint64_t u64; // _ value, constant

Đầu tiên, ta cần một số loại dữ liệu cơ bản và chỉ sử dụng thư viện chuẩn để có thể chạy trên nhiều nền tảng.

Xây dựng mã chỉ thị:

typedef enum {
  OP_HLT = 0, // return value
  OP_LDK = 1, // constant = constants[arg]
  OP_ADD = 2, // value += constant
  OP_SUB = 3, // value -= constant
  OP_LEQ = 4  // if value <= constant, pc -= arg
} OpCode;

Trong đó:

• OP_HLT (halt) dừng chương trình và trả về value
• OP_LDK (load constant) load một giá trị constant
• OP_ADD (add) cộng value với constant
• OP_SUB (subtract) trừ value cho constant
• OP_LEQ (less than or equal) nếu value bé hơn hoặc bằng constant thì nhảy đến một vị trí trong bytecode (để tạo vòng lặp, kéo dài chương trình)

Tiếp theo là emit code, mình dùng macro để viết theo hai cách biểu diễn bytecode đã nói ở trên:

#ifdef OPCODE_BYTE
  #define EMIT_HLT() (OP_HLT)
  #define EMIT_LDK(k) (OP_LDK), ((k) & 0xff), (((k) >> 8) & 0xff)
  #define EMIT_ADD() (OP_ADD)
  #define EMIT_SUB() (OP_SUB)
  #define EMIT_LEQ(n) (OP_LEQ), ((n) & 0xff), (((n) >> 8) & 0xff)
#else
  #define EMIT_HLT() ((Inst) { .op = OP_HLT })
  #define EMIT_LDK(k) ((Inst) { .op = OP_LDK, .arg = (k) })
  #define EMIT_ADD() ((Inst) { .op = OP_ADD })
  #define EMIT_SUB() ((Inst) { .op = OP_SUB })
  #define EMIT_LEQ(n) ((Inst) { .op = OP_LEQ, .arg = (n) })
#endif

Đến phần cốt lõi của máy ảo, hàm exec() để thực thi code:

static u64 exec(Inst *code, u64 *consts) {
  const Inst *pc;
  u64 value, constant;
  // code omitted
  return value;
}

Trong đó:

• code là bytecode hay các chỉ thị đầu vào
• consts là mảng các giá trị, ở đây sử dụng số nguyên 64bit
• pc là program counter, trỏ đến chỉ thị hiện tại
• value và constant sẽ giống như hai thanh ghi
  • value là biến lưu giá trị chính và cũng là giá trị trả về của hàm
  • constant sẽ chứa giá trị sau khi load từ mảng consts

Tiếp theo là khởi tạo giá trị:

value = 0;
constant = 0;
pc = code;

Phần đọc code của máy ảo sẽ là một vòng lặp, khi đọc đến các opcode sẽ nhảy đến nhánh tương ứng bằng switch...case, nhưng để tiện cho các phần sau của bài viết, mình sẽ chuyển chúng sang dạng macro:

#define DISPATCH() for (;;) switch(GET_OP())
#define CODE(op) case op
#define NEXT() continue

Ở đoạn DISPATCH sẽ rẽ nhánh theo opcode, với for (;;) giữ cho vòng lặp vô hạn, GET_OP(pc) sẽ lấy opcode từ instruction, và động từ dispatch có nghĩa là gửi công văn đi, chỉ đạo thực hiện.

Tiếp theo là điều hướng các nhánh opcode:

DISPATCH() {
  CODE(OP_HLT): {
    return value;
  }
  CODE(OP_ADD): {
    value += constant;
    NEXT();
  }
  CODE(OP_SUB): {
    value -= constant;
    NEXT();
  }
  CODE(OP_LDK): {
    int slot = GET_ARG();
    constant = consts[slot];
    NEXT();
  }
  CODE(OP_LEQ): {
    int offset = GET_ARG();
    if (value <= constant)
      pc -= offset;
    NEXT();
  }
}

Ở đây, tiếp tục sử dụng macro GET_OP và GET_ARG để lấy opcode và argument trong instruction.

Cuối cùng, ta cần một phần main để kiểm tra máy ảo:

int main() {
  u64 consts[] = {...};
  Inst code[] = {...};

  u64 result = exec(code, consts);
  printf("result: %lld\n", result);
}

Ở phần này, ta cần đưa ra các giá trị cho máy ảo thực thi trước. Dưới đây là một ví dụ đơn giản:

val = 0
loop:
  val -= 4
  val += 5
  if val <= 1234567890:
    goto loop

Ta sẽ có 3 giá trị trong mảng consts:

u64 consts[] = {4, 5, 1234567890};

Tiếp theo là phần emit code:

Inst code[] = {
  EMIT_LDK(0), // 0. load 4
  EMIT_SUB(), // 1. subtract
  EMIT_LDK(1), // 2. load 5
  EMIT_ADD(), // 3. add
  EMIT_LDK(2), // 4. load 1234567890
  EMIT_LEQ(4), // 5. if <= 1234567890, jump back 4
  EMIT_HLT() // 6. halt
};

Trong đó, chỗ [?] cần tính toán. Từ CODE(OP_LEQ), ta có pc -= offset, offset là [?].

Ở mảng code, vị trí tương ứng của label "loop" (trong mẫu code) chính là code[0]. Chỉ cần tính khoảng cách giữa EMIT_LDK(0) và EMIT_LEQ([?]). Ðiểm mấu chốt là opcode LDK đã tăng pc lên, nên chúng ta cần trừ đi 1, tức là 5-0-1.

Ta cần thay đổi emit code như sau:

EMIT_LDK(2), // 4. load 1234567890
#ifdef OPCODE_BYTE
EMIT_LEQ(10), // 5. if <= 1234567890, jump back 10
#else
EMIT_LEQ(4), // _ if <= 1234567890, jump back 4
#endif
EMIT_HLT() // 6. halt

Giờ ta có thể thử nghiệm, ta sẽ nhìn thấy kết quả nhanh hơn đáng kể:

$ gcc -w -O3 -o main -DOPCODE_BYTE main.c && time ./main
real 0m1.656s
$ gcc -w -O3 -o main main.c && time ./main
real 0m1.874s
$ clang -w -O3 -o main -DOPCODE_BYTE main.c && time ./main
real 0m1.848s
$ clang -w -O3 -o main main.c && time ./main
real 0m1.853s

Kết quả trên cho thấy, hai phương pháp bytecode không khác biệt nhiều và phụ thuộc vào trình biên dịch.

Bài viết sẽ kết thúc ở đây, hẹn gặp lại trong các bài viết tiếp theo!