Khi trình biên dịch khiến bạn bất ngờ

 (xania.org)
1 điểm bởi GN⁺ 2025-12-26 | 1 bình luận | Chia sẻ qua WhatsApp
  • Một trường hợp quan sát thấy sự khác biệt trong tối ưu hóa giữa GCC và Clang khi biên dịch một hàm cộng số nguyên đơn giản
  • GCC thực hiện tối ưu hóa vòng lặp theo dạng x*2 + 1 để cộng hai số cùng lúc trong vòng lặp
  • Clang loại bỏ hoàn toàn vòng lặp và thay phép tính bằng công thức dạng đóng v(v - 1)/2
  • Nhờ phép biến đổi này, mã được chuyển từ O(n) sang O(1), với việc rút gọn toán học được thực hiện tự động
  • Đây là một ví dụ cho thấy mức độ tối ưu hóa thông minh của trình biên dịch, đến mức ngay cả tác giả đã làm việc với trình biên dịch hơn 20 năm cũng phải ngạc nhiên

Tối ưu hóa vòng lặp của GCC

  • Khi viết một hàm cộng số nguyên đơn giản, GCC tạo ra mã cộng hiệu quả dựa trên vòng lặp
    • Bên trong vòng lặp, nó dùng lệnh lea edx, [rdx+1+rax*2] để cộng đồng thời hai số
    • Đây là cách biến phép cộng x và x+1 thành biểu thức x*2 + 1
  • Khi nâng mức tối ưu hóa lên -O3, vòng lặp được xử lý nhanh hơn thông qua phép cộng song song (vectorization)
  • Đây là kiểu tối ưu hóa truyền thống giúp tối đa hiệu quả tính toán mà vẫn giữ nguyên cấu trúc vòng lặp

Tối ưu hóa toán học của Clang

  • Khi biên dịch cùng đoạn mã bằng Clang, vòng lặp biến mất hoàn toàn
    • Clang kiểm tra xem giá trị đầu vào có dương hay không, sau đó thực hiện tính toán bằng một chuỗi lệnh lea, imul, shr
    • Kết quả là phép tính được biến đổi thành (v² - v)/2, tức công thức dạng đóng của tổng số nguyên
  • Phép biến đổi này loại bỏ vòng lặp và thay bằng phép tính thời gian hằng số (O(1))
  • Tác giả mô tả kết quả này là “tự mình tìm ra lời giải toán học cho bài toán tổng số nguyên”

Quá trình khai triển công thức

  • Nếu lần ngược mã assembly do Clang tạo ra theo góc nhìn toán học, ta sẽ thấy phép biến đổi sau
    • v + ((v - 1)(v - 2) / 2) - 1
    • Khi khai triển và rút gọn, biểu thức này trở thành (v² - v)/2
  • Cuối cùng, nó có dạng v(v - 1)/2, trùng với công thức tổng từ 1 đến v
  • Quá trình này được đưa ra như một ví dụ về việc trình biên dịch nhận diện mẫu toán học và tối ưu hóa

Cách hoạt động thông minh của trình biên dịch

  • Lý do Clang dùng chuỗi lệnh cụ thể này được giải thích là do cách tránh overflow và cơ chế theo dõi induction variable
  • Dù nguyên nhân chính xác bên trong chưa hoàn toàn rõ ràng, bài viết cho rằng đây là kết quả của logic tối ưu hóa nội bộ của Clang cùng tác động
  • Tác giả gọi đây là một trải nghiệm “khiêm nhường và đầy cảm hứng”

Kết lại và bối cảnh của series

  • Bài viết này là bài thứ 24 trong series ‘Advent of Compiler Optimisations 2025’
  • Nội dung khám phá cách trình biên dịch đạt được rút gọn toán học và cải thiện hiệu năng thông qua biến đổi mã
  • Tác giả nhấn mạnh rằng “trình biên dịch vẫn tiếp tục khiến tôi ngạc nhiên”, cho thấy cảm giác kỳ thú công nghệ vẫn còn nguyên dù đã có nhiều năm kinh nghiệm

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-12-26
Ý kiến trên Hacker News

  • Mã triển khai tính năng này nằm trong ScalarEvolution.cpp và IndVarSimplify.cpp

    • Thật đáng ngạc nhiên, đồng thời cũng hơi bất an, khi gần 16.000 dòng mã lại nằm trong một tệp

  • Kiểu tối ưu hóa này thực sự rất thú vị
    Tối ưu hóa trình biên dịch nhìn chung được chia thành hai loại — phân tích luồng dữ liệu và nhận diện mẫu rồi thay thế
    Loại đầu hiệu quả với hầu hết chương trình, còn loại sau là công việc tích lũy các mẫu với lợi ích giảm dần theo thời gian
    Ví dụ được liên kết khá thông minh và thú vị, nhưng trên thực tế không có nhiều giá trị. Tôi chưa từng viết một vòng lặp như vậy suốt 45 năm qua
    Tất nhiên, các phép thay thế mẫu như thế này vẫn quan trọng vì chúng thường được tự động sinh ra từ mã cấp cao
    Nói thật thì có khi tôi chỉ đang hơi càm ràm vì optimizer của mình không làm được kiểu tối ưu hóa này

    • Thực ra nó có thể giá trị hơn ta nghĩ. SCEV (Scalar Evolution) của LLVM chủ yếu được dùng cho phân tích, và còn giúp mở ra các tối ưu hóa khác ngoài những vòng lặp toán học
    • Chưa rõ chính xác tối ưu hóa nào đã được thực hiện. Trước đây khi làm một trình biên dịch cho thị trường ngách, tôi nhớ mình đã ngạc nhiên khi thấy trình biên dịch xử lý thông minh hơn cả những tối ưu hóa tôi tự viết

  • Đây là tính năng gọi là Scalar Evolution (SCEV), và trong LLVM nó được triển khai khá phức tạp

  • Một ví dụ tối ưu hóa tương tự là bài viết “Do not optimize away”

    • Phần giải thích đầu bài đó hơi sai. Mã cộng từ 0 đến N nhưng không bao gồm N, nên thực ra phải là N(N-1)/2. Về mặt toán học, tổng từ 1 đến N là N(N+1)/2, nên nếu loại trừ cận trên thì phải thay N bằng (N-1)
    • Tôi nghĩ trình biên dịch vẫn có thể tối ưu được việc này. Có vẻ chỉ cần tạo riêng phiên bản constant folding và phiên bản không hằng, rồi rẽ nhánh lúc runtime

  • Điểm thực sự hay của tối ưu hóa này là nó được khái quát hóa (generic)
    Không chỉ đơn giản nhận diện mẫu “tổng của dãy số nguyên hữu hạn”, mà việc nó được áp dụng theo cách tổng quát mới là điều ấn tượng

  • Có vẻ trình biên dịch còn có thể thêm nhiều closed form hơn nữa. Tôi tò mò liệu điều đó có đáng làm không
    Một khái niệm liên quan là Wilf–Zeilberger pair

  • Lại thêm một lần nữa tôi ngạc nhiên khi thấy GCC chậm hơn Clang
    Dù GCC đi trước tới 20 năm, vẫn có những trường hợp Clang tạo ra mã nhanh hơn
    Trước đây khi trích xuất bit, Clang chỉ cần hai lần shift, còn GCC lại làm tới ba lần

    • Giữa GCC và LLVM/Clang có một khác biệt thế hệ về công nghệ trình biên dịch. GCC vẫn là một dự án đáng nể, nhưng tôi nghe nói cấu trúc của nó khiến việc áp dụng các kỹ thuật tối ưu hóa hiện đại trở nên khó khăn
    • Hiệu năng thực tế của hai trình biên dịch khá tương đồng. Chúng có các pass tối ưu hóa khác nhau nên kết quả thay đổi tùy trường hợp
    • Ban đầu GCC có thiết kế theo chủ nghĩa lý tưởng đặt giấy phép làm trung tâm, nên khả năng mở rộng kém. Giờ điều đó đã dịu đi nhiều, nhưng bộ sinh mã của nó vẫn rất phức tạp. Ngược lại, Clang có cấu trúc đơn giản hơn nên việc hiện thực tối ưu hóa dễ hơn. Cá nhân tôi thấy đầu ra của MSVC hay ICC cũng khá ổn
    • Có phải là mã liên quan đến bitfield không? GCC đặc biệt yếu trong phần tối ưu hóa đó

  • Tôi tự hỏi đã có ai thử tối ưu hóa bằng cách thay bài toán tô màu đồ thị (graph coloring) bằng hằng số chưa

    • Tô màu đồ thị là bài toán NP-hard, nên khó mà biến thành O(1). Nếu là đồ thị phẳng thì có định lý bốn màu, nhưng không phải lúc nào cũng ra cùng một đáp án. Tôi chỉ muốn nói chuyện về lý thuyết đồ thị thôi

  • Đây là một ví dụ làm mờ ranh giới giữa hiện thực và đặc tả
    Chúng ta nghĩ mình đang viết phần hiện thực, nhưng thực ra lại đang viết một đại diện cho đặc tả
    Nói cách khác, trình biên dịch đang tạo ra ảo giác về một cỗ máy mệnh lệnh

  • Lúc đầu tôi ngạc nhiên khi Matt không biết về cách hoạt động này
    Hồi đại học tôi cũng từng nghịch LLVM IR và bị sốc khi thấy đệ quy được rút gọn thành phép nhân
    Việc Matt không biết có thể cũng có nghĩa là tối ưu hóa này chỉ áp dụng cho những trường hợp đơn giản mà anh ấy không đụng tới

    • Thực ra anh ấy đã biết rồi. Trong bài thuyết trình năm 2017, anh ấy đã trực tiếp nhắc tới chính ví dụ này
      Liên kết video YouTube