Vài ghi chép về Elixir Compiler (phần 1)

Image by Octavian A Tudose from Pixabay

Chuyện là vài hôm trước, tui có fix được một lỗi tồn tại khá lâu của Nabo liên quan đến Elixir compiler. Bản fix thì chỉ vài dòng thôi, cơ mà nguồn cơn sâu xa thì hơi dài dòng. Giải thích trong PR không hết. Hơn nữa, từ lâu tui cũng đã muốn viết bài về chủ đề compiler của Elixir vì thấy nó cũng khá hay ho. Nhân cơ hội này, xin được chia sẻ cùng các bác.

Để tiện theo dõi, tui tạm chia Elixir Compiler ra làm 2 phần: Compiler và Parallel Compiler. Compiler chịu trách nhiệm compile một file ra Erlang binaries (BEAM byte code). Parallel Compiler cho phép compile nhiều file song song, nhằm tăng tốc quá trình compile.

Bài viết hơi khô khan, vui lòng tự tra dầu nhớt trước khi đọc!

Compiler

DQ;ĐĐ (Dài quá; đếu đọc)

Elixir compiler biên dịch một đoạn mã nguồn Elixir thành BEAM byte code.

DĐ;ĐĐ (Dài đó; đọc đi)

Mục tiêu của Elixir compiler là sinh ra BEAM byte code. Sau đó, byte code được sử dụng tùy theo mục đích biên dịch: mix compile, IEx, v.v.

Về bản chất, Elixir compiler là một chương trình Erlang. Khi cần biên dịch một file, đầu tiên nó sẽ bật máy ảo Erlang lên và bootstrap các module cần thiết (Kernel, code server).

Tương tự như các trình biên dịch khác, Elixir compiler cũng tokenize và parse source code thành abstract syntax tree (AST, cây cú pháp trừu tượng), thường gọi là quoted form trong Elixir. Mọi language construct trong Elixir đều được biểu diễn bằng quoted form.

AST của Elixir là một tuple gồm 3 phần tử: toán tử, metadata, và các tham số của toán tử đó. Ví dụ AST của câu lệnh a + b * c là:

# +(a, *(b, c))
{
  :+,
  [...],
  [
    {:a, [], Elixir},
    {
      :*,
      [...],
      [{:b, [], Elixir}, {:c, [], Elixir}]
    }
  ]
}

Quoted form là building block của ngôn ngữ Elixir. Nó là code dưới dạng data, thao tác với nó cho phép ta dùng code để viết code. Elixir cung cấp interface quote, unquote và Macro để làm việc với quoted form. Để biết chi tiết hơn bạn có thể đọc qua bài Elixir—Ngôn ngữ được biết bằng macros.

Sau đó, từng bước một, compiler sẽ biên dịch AST thành BEAM byte code. Đây là một quá trình dài bao gồm nhiều bước:

• expand—triển khai quoted form và thực hiện kiểm tra tính đúng đắn của quoted form.
• translate: dịch từ expanded form sang Erlang Abstract Format, còn gọi là Erlang parse tree.
• compile: biên dịch từ Erlang Abstract Format sang Core Erlang, cuối cùng là BEAM bytecode.

Thật ra thì trong các bước này chia ra nhiều bước và nhánh nhỏ khác, mà trong khuôn khổ bài viết này không thể trình bày hết. Xin được khất lại sang một bài khác.

Compiler ghi BEAM bytecode vào code path, cụ thể là /ebin, kết thúc quá trình biên dịch.

Một số câu hỏi thường được đặt ra

Nếu code Elixir được biên dịch ra Erlang, vậy nó có chậm hơn Erlang không?

Không và không hẳn. Code Elixir được biên dịch ra BEAM byte code (không phải Erlang). Code Erlang cũng vậy, tuy các bước có khác, nhưng output vẫn là BEAM byte code. Erlang không phải là ngôn ngữ bậc cao hơn Elixir.

Một số trường hợp Elixir sẽ chậm hơn đôi chút, ví dụ khi bạn làm việc với Enum. Đôi lúc code Elixir sẽ nhanh hơn, khi bạn sử dụng binary thay vì char list như Erlang. Cơ mà sự khác biệt chỉ là rất rất rất nhỏ, không thật sự đáng kể.

Vì sao compiler phải bỏ BEAM byte code vào trong ebin?

Erlang VM trong interactive mode có cơ chế autoload module vào code server ở lần đầu tiên bạn gọi module, từ ebin. Cơ chế autoloading chính là yếu tố làm nên sự thú vị của Elixir parallel compiler mà tui sẽ trình bày tiếp theo.

Elixir Parallel Compiler

Trước khi đi vào parallel compiler, hãy cùng tui kinh qua 2 thứ: Code Server và :error_handler.

Code Server là nơi chứa code của Erlang VM. Trước khi một module được thực thi, code của nó cần phải được nạp vào code server. (Ờ ha, không nạp code sao chạy ha.)

Module :code trong Erlang Kernel cung cấp một số interface để bạn thao tác với code server. Ví dụ :code.load_binary(Foo, "", beam) sẽ nạp module Foo với beam là byte code; trong khi :code.purge hoặc :code.delete giúp bạn xóa code ra khỏi code server.

iex> defmodule Foo do
...> def foo(), do: true
...> end
{:module, Foo,
 <<70, 79, 82, ...>>, {:foo, 0}}
iex> Foo.foo()
true
iex> :code.delete(Foo)
true
iex> Foo.foo()
** (UndefinedFunctionError) function Foo.foo/0 is undefined (module Foo is not available)
    Foo.foo()

Elixir compiler chạy trên Erlang VM interactive mode. Compile-time của chúng ta chính là run-time của compiler ( Mr. Obvious!). Compiler của Elixir vừa biên dịch code, vừa thực thi code.

Đọc tới đây, một độc giả tinh ý phán xét: Quào, khúc này bối rối quá Quần Cam ơi. Vừa biên dịch code vừa chạy code là sao? Chẳng phải ông vừa chém là compiler phải dịch ra byte code, nạp nó vào code server thì mới thực thi được sao. Mâu thuẫn, mâu thuẫn! Trả lại tiền 2 tô sủi cảo đi.

Để tui cho bạn một ví dụ:

defmodule Foo do
  @heavy_computation 1 + 1

  def foo(), do: @heavy_computation
end

Ở đây, ta muốn tính @heavy_computation ở compile time để tăng tốc hàm foo(), thay vì cứ phải tính đi tính lại ở run time. Cho nên khi biên dịch tới khúc đó, compiler cần phải thực thi code.

Để cho gọn code, đôi khi ta muốn bỏ tách phần code @heavy_computation vào một module khác cho code đẹp. Thế là code viết lại thành:

# heavy_computation.ex
defmodule HeavyComputation do
  def compute(), do: 1 + 1
end

# foo.ex
defmodule Foo do
  @heavy_computation HeavyComputation.compute()

  def foo(), do: @heavy_computation
end

Tuy nhiên, việc này sẽ làm nảy sinh ra một vấn đề: compiler cần đảm bảo rằng HeavyComputation được biên dịch trước Foo. Hay nói cách khác, Foo có compile-time dependency vào HeavyComputation.

Để đảm bảo điều đó, cách giải quyết thông thường là sinh ra một cái dependency graph. Rồi dựa vào graph này để biết thứ tự biên dịch của các file. Cơ mà sẽ không có thuật toán liên quan đến dependency graph ở bài viết này đâu .

Đó là vì Elixir … không làm như thế mà chọn một lối đi riêng, dựa vào cơ chế :error_handler trong interactive mode. Nó tự tìm dependency on-the-fly (không biết dịch on-the-fly sao cho gọn).

Trong interactive mode, nếu module không tồn tại, Erlang VM sẽ kích hoạt callback trong :error_handler. :error_handler sẽ thử nạp module đang thiếu lên. Nếu load được, nó chạy tiếp như không có gì xảy ra. Nếu không load được, nó sẽ chửi vào mặt chúng ta.

Ngoài ra, Erlang cho phép chúng ta tự định nghĩa cách xử lý các lỗi liên quan tới module loading. Bạn có thể tạo một module implement các callback cần thiết của :error_handler, sau đó thay đổi biến cờ :error_handler. Bạn nào code Ruby có thể tưởng tượng nó hao hao method_missing (mặc dù không phải vậy).

Bạn có thể thử chơi với :error_handler trên IEx hoặc production tùy theo nồng độ liều trong máu bạn cao hay không:

iex(1)> defmodule FooHandler do
...(1)>   def undefined_function(mod, fun, args) do
...(1)>     IO.puts("Could not find " <> inspect({mod, fun, args}))
...(1)>     :error_handler.undefined_function(mod, fun, args)
...(1)>   end
...(1)> end
iex(2)> :erlang.process_flag(:error_handler, FooHandler)
:error_handler
iex(3)> ABC.foo()
Could not find {ABC, :foo, []}
Could not find {Exception, :blame...}
Could not find {ErlangError, :normalize ...}
** (UndefinedFunctionError) function ABC.foo/0 is undefined (module ABC is not available)
    ABC.foo()

Vậy error handler liên quan gì đến điều mà ta đang nói tới? Ở ví dụ đó, ngẫu nhiên 2 trường hợp có khả năng xảy ra:

1. HeavyComputation được biên dịch trước, trường hợp này thì không có gì đáng bàn.
2. Foo được biên dịch trước. Biên tới khúc gọi hàm thì nó phát hiện HeavyComputation không tồn tại (nhờ error handler). Nó sẽ tạm dừng lại, spawn ra một process khác để biên dịch module đang thiếu. Sau khi biên dịch HeavyComputation xong, Foo sẽ tiếp tục được biên dịch.

Về cơ bản thì cách này chạy được. Cơ mà spawn process vô tội vạ thì hay bị dính họa vào thân. Hơn nữa còn dễ xảy ra deadlock. Giả sử Foo và HeavyComputation có compile-time dependency lên lẫn nhau, HeavyComputation sẽ tiếp tục đẻ ra Foo, Foo lại đẻ ra HeavyComputation. Tốc độ lây lan nhanh như con virus Vũ Hán.

Process ở đây có thể hiểu nôm na là lightweight thread (mặc dù không hẳn vậy) trong Erlang VM. Ta có thể spawn hàng triệu process như thế. Bạn đọc có thể xem bài Elixir/Erlang, Actors model và Concurrency nếu muốn hiểu thêm.

Vì thế, ta cần phải có một con coordinator đứng ra làm nhiệm vụ điều tiết, với một số yêu cầu sau:

• Các file source code không được sắp xếp theo một thứ tự nào cả.
• Khi bạn có dependency graph kiểu A -> B, B -> C, C -> A, bạn có một cái cyclic deadlock. Coordinator phải detect được deadlock.
• Coordinator sẽ spawn ra compiler process cho từng file, cho phép biên dịch nhiều file song song.
• Tuy nhiên, khả năng xử lý song song của bạn bằng với số lượng online scheduler mà bạn có (nôm na là CPU cores). Có spawn hàng triệu task thì máy tính của bạn cũng không làm được hơn thế. Thậm chí nó còn làm giảm hiệu năng bởi vì scheduler phải tốn thêm công điều tiết.

Thuật toán xử lý của coordinator không phức tạp chút nào, có thể tóm gọn lại như sau:

• Coordinator spawn ra một compiler process riêng cho mỗi file, duy trì số lượng process theo ý muốn bằng cách giữ một biến counter.
• Mỗi con compiler này sẽ biên dịch file của nó. Nếu trong compile-time dependency Y trong file X chưa tồn tại, X sẽ dừng lại, nói cho coordinator biết nó đang đợi module Y, rồi khoanh tay đứng yên không làm gì cả.
• Coordinator ghi nhận X -> Y (X đợi Y) vào trong waiting list của mình, rồi tiếp tục đẻ ra compiler process cho file tiếp theo trong danh sách.
• Khi Y được biên dịch xong, coordinator sẽ báo cho X để X tiếp tục biên dịch.

Ví dụ

Tui hy vọng tới khúc này bạn đã hiểu. Nếu chưa thì bạn thể theo dõi ví dụ sau:

Cho một gia đình Quần Cam. Quần Cam phụ thuộc vào Cha và Mẹ, Cha và Mẹ phụ thuộc vào Cha và Mẹ của họ.

Bắt đầu với CODE server rỗng (chưa có module nào được load/compile). QUEUE chứa danh sách file cần biên dịch với thứ tự ngẫu nhiên. Coordinator duy trì mức 2 task song song.

CODE    []

                 QUẦN CAM
             /             \
          CHA               MẸ
          / \               / \
   CHA CHA   MẸ CHA   CHA MẸ   MẸ MẸ

QUEUE   [CHA CHA, CHA, QUẦN CAM, MẸ, MẸ MẸ, MẸ CHA, CHA MẸ]
WAITING []

2 file đầu tiên là CHA CHA và CHA được đưa vào biên dịch.

CODE    []

                 QUẦN CAM
             /             \
          [CHA]              MẸ
          /   \             /  \
   [CHA CHA]   MẸ CHA   CHA MẸ  MẸ MẸ

QUEUE   [QUẦN CAM, MẸ, MẸ MẸ, MẸ CHA, CHA MẸ]
WAITING []

CHA CHA không có dependency, nên được biên dịch ngay và bỏ vào code server.

CHA có dependency là CHA CHA và MẸ CHA, nên compiler vào trong code server để kiểm tra.

Vì CHA CHA và CHA được biên dịch song song, 2 tình huống có thể xảy ra:

• CHA CHA được biên dịch xong thì CHA mới gọi. Không có quá nhiều để nói, CHA tiếp tục biên dịch.

• CHA gọi nhưng CHA CHA chưa biên dịch xong. Coordinator đưa CHA -> CHA CHA vào waiting list.

  • Sau khi CHA CHA biên dịch xong, coordinator báo cho CHA biên dịch tiếp.

CODE    [CHA CHA]

                 QUẦN CAM
             /             \
          [CHA]              MẸ
          /   \             /  \
   (CHA CHA)   MẸ CHA   CHA MẸ  MẸ MẸ

QUEUE   [QUẦN CAM, MẸ, MẸ MẸ, MẸ CHA, CHA MẸ]
WAITING []

Vì CHA có một dependency khác là MẸ CHA chưa được biên dịch, nó tiếp tục vào waiting list.

Lúc này coordinator sẽ biên dịch các file tiếp theo trong queue.

CODE    [CHA CHA]

                [QUẦN CAM]
             /             \
          =CHA=             [MẸ]
          /   \             /  \
   (CHA CHA)   MẸ CHA   CHA MẸ  MẸ MẸ

QUEUE   [MẸ MẸ, MẸ CHA, CHA MẸ]
WAITING [CHA -> MẸ CHA]

QUẦN CAM cần CHA mà chưa có, nên QUẦN CAM -> CHA được đưa vào waiting list.

Tương tự, CHA MẸ cũng chưa chưa được biên dịch nên MẸ -> CHA MẸ được đưa vào waiting list.

CODE    [CHA CHA]

                =QUẦN CAM=
             /             \
          =CHA=             =MẸ=
          /   \             /  \
   (CHA CHA)   MẸ CHA   CHA MẸ  MẸ MẸ

QUEUE   [MẸ MẸ, MẸ CHA, CHA MẸ]
WAITING [CHA -> MẸ CHA, QUẦN CAM -> CHA, MẸ -> CHA MẸ]

Tiếp theo MẸ MẸ và MẸ CHA được biên dịch. 2 file này không có dependency nên dễ dàng biên dịch thành công và load vào code server.

Vì trong waiting list có CHA -> MẸ CHA, CHA được coordinator cho tiếp tục biên dịch. Sau đó CHA biên dịch thành công.

CODE    [CHA CHA, MẸ MẸ, MẸ CHA, CHA]

                =QUẦN CAM=
             /             \
          (CHA)             =MẸ=
          /   \             /  \
   (CHA CHA)  (MẸ CHA)  CHA MẸ (MẸ MẸ)

QUEUE   [CHA MẸ]
WAITING [QUẦN CAM -> CHA, MẸ -> CHA MẸ]

Coordinator cho phép QUẦN CAM tiếp tục biên dịch. Tuy nhiên nó lại được đưa vào waiting list vì chờ MẸ.

CODE    [CHA CHA, MẸ MẸ, MẸ CHA, CHA]

                =QUẦN CAM=
             /             \
          (CHA)             =MẸ=
          /   \             /  \
   (CHA CHA)  (MẸ CHA)  CHA MẸ (MẸ MẸ)

QUEUE   [CHA MẸ]
WAITING [QUẦN CAM -> MẸ, MẸ -> CHA MẸ]

File cuối cùng trong QUEUE là CHA MẸ được compile. Nhờ đó, lần lượt MẸ và QUẦN CAM biên dịch thành công.

Bài viết đã giúp tui tăng lương như thế nào?

Tới khúc này, tui hy vọng bài viết đã giúp làm sáng tỏ phần nào về Elixir compiler.

• Elixir compiler biên dịch một source code Elixir thành BEAM byte code, và ghi nó vào code path tương ứng.

• Elixir parallel compiler spawn ra nhiều process để biên dịch song song các file nguồn.

  • Một con coordinator để điều tiết các compiler process con.
  • Compiler process con sẽ gửi thông báo tới coordinator khi cần một module nào đó.
  • Coordinator sẽ thông báo lại cho các process con đang chờ khi module được chờ đã sẵn dùng.

Vì bài viết đã khá dài, tui xin hẹn phần xử lý deadlock sang phần kế tiếp.

Ủa chưa nói gì vụ Nabo hết mà? E hèm, hẹn các bạn phần kế tiếp luôn.

Tham khảo

• https://elixir-lang.org/blog/2012/04/24/a-peek-inside-elixir-s-parallel-compiler/
• https://github.com/elixir-lang/elixir