- Để trực quan hóa quá trình biên dịch JavaScript·WebAssembly của engine SpiderMonkey, nhóm đã đại tu toàn bộ công cụ nội bộ và triển khai khả năng tạo đồ thị tương tác
- iongraph dựa trên Graphviz trước đây có bố cục thiếu ổn định và cấu trúc khó trực quan, làm giảm hiệu quả gỡ lỗi; vì vậy nhóm đã tự thiết kế thuật toán bố cục mới để thay thế
- Thuật toán mới đơn giản hóa phương pháp Sugiyama để biểu diễn rõ cấu trúc vòng lặp, đồng thời hiện thực bố cục ổn định, tốc độ cao chỉ với chưa tới 1000 dòng mã JavaScript
- Đồ thị dùng các cạnh thẳng theo phong cách sơ đồ đường sắt để tăng khả năng đọc, đồng thời đạt tốc độ dựng hình nhanh hơn Graphviz tới hàng nghìn lần
- Công cụ này đã được tích hợp vào Firefox Profiler và còn có kế hoạch mở rộng thêm các tính năng như tìm kiếm và trực quan hóa thanh ghi
Cải tổ công cụ trực quan hóa của SpiderMonkey
- Đã xây dựng lại công cụ để trực quan hóa các đồ thị nội bộ do trình biên dịch tối ưu hóa Ion của SpiderMonkey tạo ra
- Người dùng có thể nhập mã JavaScript trên trang web để khám phá theo thời gian thực quá trình tối ưu hóa hàm dưới dạng đồ thị
- Có thể kiểm tra các thay đổi theo từng bước bằng thao tác kéo, thu phóng và thanh trượt
- iongraph dựa trên Graphviz trước đây tạo đầu ra PDF, nhưng không khớp với cấu trúc mã nguồn và có vấn đề nghiêm trọng về độ ổn định đầu ra
- Chỉ một thay đổi nhỏ trong mã cũng có thể làm vị trí nút thay đổi lớn, khiến việc so sánh giữa các pass trở nên khó khăn
- Cấu trúc vòng lặp và câu lệnh điều kiện bị méo khi hiển thị, khiến luồng điều khiển khó nắm bắt bằng trực quan
Giới hạn của Graphviz và cách tiếp cận mới
- Thuật toán Sugiyama của Graphviz phù hợp để tối ưu hóa đồ thị tổng quát, nhưng không phản ánh được đặc tính của đồ thị luồng điều khiển (CFG)
- Các vòng lặp trong JavaScript·WebAssembly chỉ có một điểm vào duy nhất, và có luồng điều khiển rút gọn được (reducible)
- Nhóm SpiderMonkey đã tận dụng các ràng buộc này để thiết kế một thuật toán chuyên dụng được đơn giản hóa
- Loại bỏ chu trình: bỏ qua các backedge của vòng lặp
- Phân tầng (Leveling): đặt các khối sau vòng lặp xuống phía dưới để phản ánh luồng mã
- Bỏ qua tối thiểu hóa giao cắt: ưu tiên tính ổn định nên cố định thứ tự nhánh true/false
- Bảo toàn cấu trúc cây vòng lặp: biểu diễn trực quan rõ ràng các vòng lặp lồng nhau
- Kết quả là đạt được bố cục gọn gàng, nhanh và ổn định, với bản triển khai ban đầu chỉ khoảng 1000 dòng JavaScript
Các bước của thuật toán bố cục iongraph
- Bước 1: Layering
- Sắp xếp các khối theo từng tầng và phản ánh quan hệ bên trong/bên ngoài vòng lặp
- Các khối sau khi thoát vòng lặp sẽ được đặt xuống dưới bằng đúng chiều cao của toàn bộ vòng lặp
- Bước 2: Tạo nút giả
- Thêm nút giả cho các cạnh băng qua nhiều tầng để tránh va chạm trực quan
- Các cạnh hướng tới cùng một đích được gộp lại để giảm nhiễu thị giác
- Bước 3: Căn thẳng cạnh (Straighten)
- Căn chỉnh các nút cha/con để giữ dạng đường thẳng đứng, đồng thời áp dụng thụt đầu dòng cho vòng lặp
- Các nút giả cũng tham gia quá trình căn chỉnh để tránh chồng lấp và bảo toàn cấu trúc
- Bước 4: Theo dõi cạnh ngang
- Sắp xếp các cạnh ngang theo từng track để chúng không chồng lên nhau
- Tách lên/xuống theo hướng cạnh, và các cạnh có thể hợp nhất thì được gom lại thành một
- Bước 5: Dàn theo chiều dọc (Verticalize)
- Gán tọa độ Y cho từng tầng để bố trí chiều cao đồng đều, tăng khả năng đọc
- Bước 6: Dựng hình (Render)
- Sử dụng các cạnh thẳng theo phong cách sơ đồ đường sắt
- Các cạnh chỉ giao nhau theo phương dọc/ngang, nên hướng đi và cấu trúc rất rõ ràng
Hiệu quả của một thuật toán đơn giản
- Thay vì tối ưu hóa phức tạp, cách bố trí dựa trên quy tắc có thể dự đoán đã đảm bảo tính dễ đọc và độ ổn định
- Cố định thứ tự nút và đơn giản hóa cạnh để duy trì tính nhất quán giữa các pass
- Nhờ loại bỏ constraint solver, nhóm đã hiện thực một cấu trúc dễ cho con người hiểu
- Có thể thiết kế theo ngữ nghĩa, như bố trí bên trong vòng lặp hay đặt các khối tiếp theo xuống dưới
- Cải thiện hiệu năng: đồ thị hàm zlib vốn mất 10 phút với Graphviz nay được dựng trong 20 mili giây
- Đạt tốc độ nhanh hơn hàng nghìn lần cùng khả năng khám phá tốt hơn
Kế hoạch sắp tới
- Đã hoàn tất tích hợp iongraph vào Firefox Profiler, nên có thể xem đồ thị khi phân tích hiệu năng
- Hiện mới chỉ dùng được trong bản build SpiderMonkey shell, chưa bao gồm trong bản build trình duyệt
- Các đề xuất tính năng trong tương lai
- Tính năng điều hướng nâng cao, tìm kiếm, trực quan hóa phân bổ thanh ghi v.v.
- Chưa có lộ trình rõ ràng, và nhóm hoan nghênh đóng góp mã nguồn mở
- Có thể thử nghiệm cục bộ bằng cách đặt
IONFLAGS=logs để tạo /tmp/ion.json, sau đó
tải lên tại bản triển khai độc lập
- Mã nguồn được công khai trên GitHub,
và có thể trao đổi trực tiếp với nhà phát triển qua phòng chat Matrix
1 bình luận
Ý kiến trên Hacker News
Nếu so sánh cho chính xác thì đây không phải so với toàn bộ Graphviz mà là so với dot(1)
Graphviz là một framework trực quan hóa bao gồm nhiều layout engine (dot, neato, fdp, sfdp, circo, twopi, v.v.)
Nếu thuật toán mới được đề xuất có thể đóng góp vào Graphviz thì sẽ rất tuyệt
Có thể tham khảo mô tả ngôn ngữ Graphviz và tài liệu về dot layout engine
Với các control flow graph (CFG) có reducible control flow thì có thể nó hoạt động tốt, nhưng có vẻ sẽ có nhiều ngoại lệ phức tạp
Hơn nữa iongraph là nền tảng JavaScript, nên nếu muốn tích hợp vào Graphviz thì sẽ phải chuyển sang C bằng công cụ kiểu Claude
Khả năng tự mình đọc trực tiếp bản triển khai gốc của thuật toán đúng là một siêu năng lực
Với góc nhìn của người từng làm trực quan hóa phức tạp bằng Graphviz, ban đầu tôi thấy khá bất ngờ khi có ai đó tự triển khai lại
Nhưng sau khi nhìn vào cấu trúc thuật toán thì tôi nhận ra có lẽ nó đơn giản hơn mình tưởng
Dù vậy, vẫn rất khó biết được độ phức tạp ẩn cho đến khi thực sự hoàn thành việc triển khai
Nếu tối ưu một thuật toán tổng quát cho một miền bài toán cụ thể thì có thể đạt kết quả tốt hơn rất nhiều
Nhưng trong đa số trường hợp, chúng ta vẫn tiện tay dùng luôn thuật toán đa dụng
Thiết kế hệ thống phù hợp với một ứng dụng cụ thể có thể cải thiện lớn về hiệu năng, khả năng mở rộng và khả năng chịu lỗi
Nhưng nếu nhắm tới mức cải thiện gấp 1000 lần thì 1~2 năm sẽ trôi qua rất nhanh
Các hệ thống graph layout tổng quát phải xử lý nhiều trường hợp đa dạng hơn rất nhiều nên khó tránh khỏi việc trở nên phức tạp
Vì vậy tôi nghĩ một cách dung hòa tốt là phân tích đầu vào để dùng thuật toán nhanh cho các trường hợp đặc biệt, còn lại thì dùng thuật toán tổng quát có bảo đảm
Bài viết rất hay. Nhân tiện, dot của Graphviz không phải là một bản triển khai thuần túy của thuật toán Sugiyama
Bản triển khai thực tế được mô tả chi tiết trong bài báo trên website
Nếu xem ảnh so sánh dot và iongraph trên các đồ thị lớn thì có thể thấy dot được tối ưu cho việc giảm thiểu diện tích, còn iongraph thì không
Trực quan hóa đồ thị lớn trông thì ấn tượng, nhưng trên thực tế hiếm khi thực sự hữu ích
Trực quan hóa chỉ còn hiệu quả đến khoảng vài chục nút, vượt quá mức đó thì độ phức tạp của các cạnh khiến việc hiểu trở nên rất khó
Cuối cùng nó chỉ hoạt động tốt với ví dụ đơn giản, còn trong môi trường phức tạp thì lại thành cản trở
Phần lớn vấn đề có thể thu nhỏ về các đơn vị nhỏ hơn
Tuy nhiên, ngay cả với đồ thị nhỏ thì Graphviz cũng không đẹp về mặt thẩm mỹ, còn iongraph thì độ dễ đọc của các đường nối tốt hơn hẳn
Về lâu dài, tôi nghĩ cần có các yếu tố tương tác như tìm kiếm, tô sáng/ẩn bớt
Điều gây khó chịu là sơ đồ có giới hạn là không thể xuất hoặc nhận liên kết
Mermaid có hỗ trợ liên kết văn bản, nhưng liên kết trong chính sơ đồ thì còn hạn chế
Cũng đáng xem thảo luận liên quan trên StackOverflow
Cần có những công cụ mà kiểu tính năng này được xem là tính năng hạng nhất ngay từ khâu thiết kế
Điểm mạnh thực sự của Graphviz là ngôn ngữ dot
Các đồ thị được định nghĩa bằng dot có khả năng tương thích giữa nhiều công cụ rất tốt, cú pháp lại đơn giản và dễ đọc
Dù đã có các lựa chọn thay thế như Mermaid, tôi nghĩ dot vẫn sẽ còn tồn tại rất lâu như một định dạng tiêu chuẩn
Bài viết thực sự rất ấn tượng
Không biết những kỹ thuật kiểu này có được dùng trong TALA layout engine của D2 hay không
Xem ví dụ TALA
Nếu quan tâm đến graph drawing thì tôi khuyên xem bài giảng của Will Evans (liên kết)
Trước đây tôi từng đóng góp một bản sửa lỗi cho Dot lexer của Open Graph Drawing Framework (OGDF),
và OGDF triển khai các thuật toán ít giao cắt hơn và nhanh hơn so với Graphviz
Theo kinh nghiệm của tôi thì kết quả của OGDF gọn gàng hơn nhiều
Có thể xem lịch sử PR liên quan tại liên kết GitHub
Khá thú vị. Tôi tò mò cách chạy các ví dụ là như thế nào
Điểm hay của dự án này là hỗ trợ khám phá tương tác với giả định môi trường web client
Vì đây là layout chuyên cho control flow graph (CFG), nó cho phép trực quan hóa theo miền chuyên biệt
Graphviz cũng có các tính năng polyline, điều khiển thứ tự cạnh, nhưng tài liệu còn thiếu
Có vẻ sẽ tốt nếu tích hợp thuật toán edge routing của Brandes và Kopf
Graphviz là một dự án đã gần 40 năm tuổi, hiện nay chỉ còn vài tình nguyện viên thế hệ thứ hai duy trì
Làm công cụ luôn là một thị trường khó, và người dùng thì thông minh nhưng lại thuộc những bộ phận có ngân sách thấp
Thật đáng tiếc khi sự phát triển của các công cụ sơ đồ 2D khai báo vẫn chậm chạp
Ai làm việc trong lĩnh vực này thì lúc nào cũng đáng được +1 ủng hộ
Tôi cũng từng dùng mermaid và graphviz, nhưng cuối cùng lại quay về FigJam — dễ đọc hơn và đẹp hơn
graphviz là một binary khổng lồ, còn mermaid thì phụ thuộc vào việc trình duyệt render SVG nên khá bất tiện
Điều tôi cần đơn giản là một công cụ giúp tạo sơ đồ bằng văn bản thật dễ dàng
Tôi nghĩ cách tiếp cận mà tác giả đưa ra là một nỗ lực tốt để kiểm soát điểm đánh đổi đó
Trừ việc chưa xử lý vòng lặp, tôi khá hài lòng
Đầu ra SVG/HTML cũng thuận tiện cho việc chỉnh style và sao chép
Nếu muốn một công cụ sơ đồ dựa trên văn bản thì tôi khuyên dùng TikZ
Xem thêm wiki TikZ
Tuy nhiên nó không có phản hồi thị giác tức thì như FigJam
Tôi không thích việc mermaid có quá nhiều phụ thuộc và thiếu tính nhất quán trong mã nguồn
Thay vào đó, nomnoml (liên kết) có mã nguồn gọn gàng hơn, và còn có graphre được port sang Typescript (liên kết)
Nếu muốn dùng mermaid cùng resvg-js thì sẽ cần refactor phần liên quan đến đo độ rộng văn bản SVG