Vài ghi chép về Elixir Compiler (phần 1)
Bài viết được sự cho phép của tác giả Huỳnh Quán Cẩm
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:
HeavyComputation
được biên dịch trước, trường hợp này thì không có gì đáng bàn.Foo
được biên dịch trước. Biên tới khúc gọi hàm thì nó phát hiệnHeavyComputation
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ịchHeavyComputation
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 fileX
chưa tồn tại,X
sẽ dừng lại, nói cho coordinator biết nó đang đợi moduleY
, 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 choX
để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ưngCHA CHA
chưa biên dịch xong. Coordinator đưaCHA -> CHA CHA
vào waiting list.- Sau khi
CHA CHA
biên dịch xong, coordinator báo choCHA
biên dịch tiếp.
- Sau khi
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
Bài viết gốc được đăng tải tại quan-cam.com
Có thể bạn quan tâm:
- Một vài ghi chép về lệnh Iterator trong JavaScript
- Elixir – Ngôn ngữ được viết bằng macros
- 5 ngôn ngữ lập trình mới bạn cần phải biết
Xem thêm các tuyển dụng IT hấp dẫn tại TopDev
- i iOS 18 có gì mới? Có nên cập nhật iOS 18 cho iPhone của bạn?
- G Gamma AI là gì? Cách tạo slide chuyên nghiệp chỉ trong vài phút
- P Power BI là gì? Vì sao doanh nghiệp nên sử dụng PBI?
- K KICC HCMC x TOPDEV – Bước đệm nâng tầm sự nghiệp cho nhân tài IT Việt Nam
- T Trello là gì? Cách sử dụng Trello để quản lý công việc
- T TOP 10 SỰ KIỆN CÔNG NGHỆ THƯỜNG NIÊN KHÔNG NÊN BỎ LỠ
- T Tìm hiểu Laptop AI – So sánh Laptop AI với Laptop thường
- M MySQL vs MS SQL Server: Phân biệt hai RDBMS phổ biến nhất
- S SearchGPT là gì? Công cụ tìm kiếm mới có thể đánh bại Google?
- C Cách tích hợp ChatGPT vào Google Search siêu dễ