Thu nhỏ {fmt}: giảm kích thước nhị phân xuống 14k và loại bỏ runtime C++

• {fmt} là thư viện định dạng C++ vốn giảm phình to template bằng type erasure; trong thử nghiệm này, một tệp thực thi fmt::print đơn giản đã được giảm từ 75kB xuống 14kB
• Cấu trúc cốt lõi là format ủy quyền cho vformat không phải template, đồng thời kiểu đầu ra cũng được che giấu qua API buffer, nhờ đó có thể giảm cả kích thước nhị phân lẫn thời gian build
• Trên aarch64 Ubuntu 22.04 và GCC 11.4.0, tệp thực thi đã strip của {fmt} 11.0.2 là 75kB; với việc tắt locale, thu gọn các kiểu tích hợp sẵn và macro tối ưu kích thước, kích thước giảm lần lượt 71kB → 31kB → 27kB → 23kB
• Việc loại bỏ runtime C++ trở nên khả thi bằng cách xử lý ngoại lệ qua FMT_THROW thành abort, build với -fno-exceptions, -nodefaultlibs, -lc, rồi thay allocator mặc định của basic_memory_buffer sang nền tảng malloc/free
• Tệp thực thi cuối cùng là 14kB; xét rằng một main C rỗng trên cùng hệ thống là 6kB, phần kích thước mà {fmt} thêm vào dưới 10kB, và ldd cũng không cho thấy phụ thuộc runtime C++

---

Cách {fmt} tạo ra các tệp nhị phân nhỏ

• {fmt} formatting library thường tạo ra lượng mã trên mỗi lần gọi hàm nhỏ hơn nhiều lần so với các lựa chọn thay thế như IOStreams, Boost Format, tinyformat
• Điểm cốt lõi nằm ở cấu trúc áp dụng type erasure ở nhiều tầng để giảm phình to template
• Đối số định dạng được type-erased thành format_args
  • Hàm template format ủy quyền công việc thực tế cho vformat, vốn không phải template
  • Output iterator và các kiểu đầu ra khác cũng được type-erased thông qua API buffer riêng
• Việc dùng template được giới hạn ở một lớp mỏng trên cùng, và cấu trúc này góp phần tạo ra tệp nhị phân nhỏ hơn cũng như thời gian biên dịch C++ nhanh hơn

Kích thước mã gần với printf và độ an toàn mạnh hơn

• Chương trình ví dụ chỉ gọi fmt::print("The answer is {}.", 42);
• Kết quả biên dịch nhỏ hơn nhiều so với IOStreams và ở mức tương tự ví dụ printf
  • Ví dụ {fmt} trên Godbolt: godbolt
  • Ví dụ printf trên Godbolt: godbolt
• Khác với printf, {fmt} cung cấp an toàn kiểu ở runtime
  • Lỗi chuỗi định dạng có thể được bắt ở thời điểm biên dịch
  • Ngay cả khi chuỗi định dạng được xác định ở runtime, lỗi được xử lý bằng ngoại lệ, tránh hành vi không xác định, hỏng bộ nhớ và nguy cơ crash
• Khi dùng đối số theo vị trí (positional arguments), vốn không phù hợp lắm với đối số biến thiên của C, lời gọi {fmt} thường hiệu quả hơn

Kích thước cơ sở và loại bỏ locale

• Trong bài tối ưu kích thước thư viện năm 2020, {fmt} từng được giảm xuống dưới 100kB, và khoảng 57kB với -Os -flto
• Sau đó {fmt} bắt đầu dùng thuật toán Dragonbox do Junekey Jeon đóng góp cho định dạng số dấu phẩy động
• Phép đo lần này lấy kích thước tệp thực thi mà người dùng cuối cảm nhận làm chuẩn, được thực hiện trên aarch64 Ubuntu 22.04 và GCC 11.4.0
• Bản build cơ sở của {fmt} 11.0.2 là 75kB sau -Os -flto -DNDEBUG và strip
  • Dù có nhiều thay đổi trong 4 năm qua, kích thước không thoái lui đáng kể
• Khi tắt hỗ trợ locale bằng FMT_STATIC_THOUSANDS_SEPARATOR, kích thước nhị phân giảm xuống 71kB
  • Định dạng của {fmt} mặc định độc lập với locale
  • Có thể dùng locale tùy chọn qua format specifier L

Thu gọn kiểu tích hợp sẵn và mô hình “không dùng thì không trả chi phí”

• Phân tích bằng Bloaty cho thấy định dạng số, đặc biệt là định dạng số dấu phẩy động, chiếm phần lớn kích thước nhị phân
  • Định dạng số dấu phẩy động cũng dùng bảng, và các bảng đó không xuất hiện trong output của Bloaty
• Gánh nặng cơ bản phát sinh từ việc hàm định dạng phải biết tất cả kiểu có thể định dạng
  • Cách này phù hợp với printf của chuẩn C, nhưng không phải điều kiện bắt buộc với {fmt}
  • {fmt} hỗ trợ API mở rộng có thể định dạng kiểu tùy ý mà không cần biết trước toàn bộ tập kiểu
• Trong triển khai thử nghiệm, thiết lập FMT_BUILTIN_TYPES=0 để chỉ xử lý đặc biệt int, còn các kiểu khác được gửi sang API mở rộng chung
  • int cần thiết để xử lý độ rộng và độ chính xác động
  • Ví dụ: fmt::print("{:{}}\n", "hello", 10); in ra "hello "
• Cách này cung cấp mô hình không trả chi phí cho kiểu không dùng, nhưng kích thước nhị phân trên mỗi lời gọi tăng nhẹ
  • Nếu thực sự định dạng số dấu phẩy động hoặc các kiểu khác, mã liên quan vẫn được đưa vào bản build
• Sau khi áp dụng FMT_BUILTIN_TYPES=0, tệp nhị phân ví dụ giảm xuống 31kB
• Sau đó, các dấu vết locale còn sót lại được loại bỏ trong e582d37 và b3ccc2d, đồng thời có thể tắt rõ ràng hơn bằng macro FMT_USE_LOCALE, đưa kích thước xuống 27kB

Lựa chọn giữa tốc độ và kích thước, và loại bỏ runtime C++

• Bên trong thư viện có nhiều chỗ dùng thêm kích thước để đổi lấy tốc độ
• do_count_digits, hàm tính số chữ số thập phân, dùng một bảng 256 byte
  • Nếu thay đổi triển khai này vô điều kiện, có thể ảnh hưởng tiêu cực đến các trường hợp sử dụng khác
  • Cũng đã có sẵn triển khai fallback cho các trường hợp như constexpr, nơi không thể dùng __builtin_clz
• Thêm macro FMT_OPTIMIZE_SIZE để người dùng có thể kiểm soát việc có dùng triển khai fallback hay không
  • Điều chỉnh này cùng vài thay đổi tương tự đưa kích thước nhị phân xuống 23kB
• Để loại bỏ phụ thuộc vào thư viện chuẩn C++, có thể tắt ngoại lệ bằng FMT_THROW
  • Ví dụ dùng FMT_THROW(s)=abort() và -fno-exceptions
  • Nhìn chung không được khuyến nghị, nhưng có thể chấp nhận trong một số trường hợp sử dụng mà hầu hết lỗi được bắt ở thời điểm biên dịch
• Khi build với -nodefaultlibs -lc, phụ thuộc runtime C++ còn lại phát sinh từ fmt::basic_memory_buffer
  • Buffer này là một buffer nhỏ cấp phát trên stack và mở rộng sang bộ nhớ động khi cần
  • fmt::print thường có thể ghi trực tiếp vào buffer FILE, nên không cần cấp phát động
• Như một giải pháp tổng quát hơn, allocator mặc định được thay bằng nền tảng malloc/free thay vì new/delete
  • Sau thay đổi này, kích thước nhị phân cuối cùng là 14kB
  • Vì chương trình C main rỗng trên cùng hệ thống là 6kB, kích thước mà {fmt} thêm vào dưới 10kB
• Kết quả ldd a.out chỉ hiển thị libc.so.6 và loader, không xuất hiện phụ thuộc runtime C++
• Kết quả cuối cùng cho thấy có thể dùng {fmt} nhỏ gọn hơn trong môi trường nhúng và môi trường bị giới hạn bộ nhớ

[GN⁺]

Ý kiến trên Hacker News

• Đây thực ra là vấn đề thiên về xu hướng của ủy ban, nên tôi không nghĩ thư viện bên thứ ba như fmt lại nhất thiết phải có mặc định tệ như vậy
  Điều đáng ngạc nhiên là khi tính năng này được chuẩn hóa thành std::format trong C++20, ủy ban đã không lặp lại sai lầm này ở nhiều phần khác của tiêu chuẩn
  Vì vậy cũng vẫn còn chút hy vọng cho những người đề xuất đang kêu gọi đừng làm C++ tệ đi một cách không cần thiết chỉ để khiến nó “nhất quán” hơn

• Nhìn lượng mã cần cho định dạng số dấu phẩy động khá là gây sốc
  Dự án Dragonbox [1] được liên kết cũng rất đáng đọc, và ngay cả các nhánh gần như không dùng tới cũng được tối ưu khá kỹ
  [1] https://github.com/jk-jeon/dragonbox

  • Gần đây khi làm việc với Zig, tôi mới nhận ra cần nhiều mã đến mức nào cho việc định dạng số dấu phẩy động
    Thông thường trình biên dịch Zig có thể tạo ra binary nhỏ hơn MSVC trên Windows vì không phụ thuộc vào C runtime, nhưng lần này binary lại lớn bất thường so với công việc mà công cụ thực hiện
    Khi mở bằng Binary Ninja, tôi thấy phần lớn mã là để hỗ trợ định dạng số dấu phẩy động, và khi ép kiểu số dấu phẩy động sang số nguyên trước khi in ra, kích thước đã giảm xuống mức tôi mong đợi
  • https://github.com/jk-jeon/dragonbox/discussions/57#discussioncomment-9340182
    Tôi đang làm các thử nghiệm tối ưu kích thước, và hiện tại có thể giảm xuống khoảng 3k trên AVR 8-bit
    Đây là khi chỉ bao gồm phần cài đặt và bảng cho binary32 đơn chính xác; bản song chính xác cần nhiều hơn đáng kể, nhưng đồng thời phần phình to lên cũng phần lớn do các ràng buộc của AVR
    Trên các nền tảng như x64 thì có thể nhỏ hơn nhiều, nhưng nói 3k vẫn còn lớn cũng không phải là vô lý
  • Nếu muốn làm cho nhanh thì sẽ cần nhiều mã
    Bản cài đặt chuẩn rốt cuộc cũng là một triển khai số học độ chính xác tùy ý, nhưng không tệ đến vậy
    [1] https://research.swtch.com/ftoa
    [2] https://go.dev/src/strconv/ftoa.go
  • {fmt} có một triển khai tùy chọn của thuật toán Dragon4 cũ hơn, kích thước mã nhỏ hơn nhưng tốc độ chậm hơn
  • Có lẽ hầu hết các trường hợp sử dụng đều sẽ giới hạn số chữ số thập phân cần in
    Tôi tự hỏi liệu sẽ hiệu quả hơn nếu nhân với số mũ theo số chữ số thập phân, chuyển sang số nguyên, chạy qua itoa(), rồi chèn dấu thập phân vào vị trí thích hợp

• Với tư cách người mới học C++, tôi thắc mắc liệu allocator mặc định của libc++, tức triển khai new/delete mặc định, có thực sự làm gì khác ngoài việc nội bộ gọi malloc/free của libc không? Nếu có thì tại sao?

  • Tôi không quá giỏi C++, nhưng new[] sẽ gọi toán tử new để lấy bộ nhớ rồi chạy constructor của từng phần tử
    delete[] sẽ chạy destructor của từng phần tử trước khi giải phóng bộ nhớ
    Để delete[] hoạt động, C++ phải theo dõi kích thước cấp phát ở đâu đó; thông tin này có thể đặt gần vùng cấp phát hoặc trong một cấu trúc riêng
    Nếu dùng cấu trúc riêng thì ít có khả năng thông tin bị ghi đè khi ai đó ghi sai vào phần bộ nhớ phía sau đối tượng, nhưng sẽ tốn chi phí tra cứu và cần thêm mã
    Một thư viện C++ tử tế sẽ làm nhiều việc hơn nữa, nhưng như vậy cũng đủ để thấy new/delete không giống malloc/free
  • ISO C++ không yêu cầu triển khai mặc định của new/delete phải gọi malloc()/free()
    Nhiều triển khai làm vậy chỉ vì nó đã có sẵn và dễ dùng
  • Ngoài các overload cấp phát có căn chỉnh thì về cơ bản không khác
    Tuy vậy, ứng dụng vẫn có thể thay thế operator new của thư viện chuẩn mặc định bằng triển khai riêng, kể cả trên những nền tảng không có cơ chế tương đương với ELF symbol interposition
  • Lý do chính để chuyển sang malloc là vì new ném std::bad_alloc, nên dùng nó đồng nghĩa phải liên kết với C++ runtime

• Tôi từng kỳ vọng một thư viện định dạng được thiết kế để nhỏ gọn và có thể in chuỗi cùng số nguyên thì cỡ 50 byte là được
  Với chuỗi, chỉ cần kiểm tra ký tự kết thúc null, in ký tự ra, rồi nhảy lùi hai bước, cỡ khoảng 4 lệnh
  Với số nguyên, chỉ cần kiểm tra số âm rồi in '-', đảo dấu, nạp 1000000000 vào R1 rồi chia và lưu phần dư, cộng thêm ASCII '0', in ký tự, chia R1 cho 10, đưa phần dư vào làm đầu vào, lặp cho tới khi R1=0, nên cỡ khoảng 20 lệnh
  Số dấu phẩy động thì nhiều chương trình không dùng, nên chỉ nên được biên dịch khi cần; số hex, con trỏ, hay đệm số 0 bên trái cũng vậy
  Khi viết mã cho vi điều khiển chỉ có 2KB không gian mã, người ta sẽ không nhét một thư viện định dạng chuỗi 14KB vào

  • Đây không phải thư viện in số nguyên/chuỗi chậm chạp không có modifier, mà là thư viện định dạng nhiều tính năng
    Không thể đồng thời làm một thư viện vừa nhiều tính năng, vừa nhanh, lại vừa nhỏ
  • Thiết kế thư viện cho vi điều khiển và thiết kế một thư viện “tương đương” cho ứng dụng người dùng cuối thông thường khác nhau ở gần như mọi điểm quan trọng
    Tôi không rõ điều này khác gì một lời than phiền chung chung nơi công cộng, chứ không riêng gì fmt
    Chỉ riêng mã của các thuật toán như Dragonbox hay Dragon4 đã vượt quá ngân sách kích thước rồi, nên các tính năng “tùy chọn” cũng không quan trọng lắm
    Và đó mới chỉ là một trong khoảng 20 tính năng mà mọi người muốn
  • Vậy thì có lẽ nên công khai thư viện mà bạn thực sự đang dùng và tài liệu hóa nó hỗ trợ những tính năng định dạng nào
    Khi đó người khác có thể tìm ra cách nhét thêm nhiều tính năng hơn theo cách thông minh hơn
    Nếu không thì tôi không hiểu lắm điểm chính là gì
  • Tôi không nghĩ yêu cầu của một ngách lập trình cụ thể nên ảnh hưởng đến ngôn ngữ theo kiểu đó
    Những yêu cầu ấy là hợp lý, nhưng đó là việc của trình biên dịch vi điều khiển cấu hình thấp nhất phải giải quyết, chứ không phải của đặc tả ngôn ngữ
  • Mục tiêu chính của thư viện này không phải là làm cho thật nhỏ, mà là tạo ra một thư viện định dạng chuỗi đầy đủ, với kích thước là mục tiêu phụ nhưng quan trọng
    Nếu bạn cần cực kỳ nhỏ gọn đến mức chấp nhận không hỗ trợ cả những tính năng cơ bản, thì rõ ràng có lựa chọn tốt hơn
    Nếu không gian mã chỉ có 2KB thì bạn không nên dùng cái này
    May là phần lớn vi điều khiển hiện đại đều lớn hơn nhiều; ví dụ esp32 bắt đầu từ 1MB, nên dùng thư viện định dạng 14KB là hoàn toàn hợp lý

• Quảng cáo một chút: ngay cả khi kèm theo libc có đệm đầu ra, vẫn có thể tạo ra tệp thực thi 1008 byte cho printf(Hello, World!\n");: https://github.com/pts/minilibc686
  Dĩ nhiên so trực tiếp thì giống như so táo với cam

  • Đó là vì trình biên dịch biến nó thành fputs

• Đoạn “nếu một chương trình C với hàm main rỗng là 6kB trên hệ này, thì {fmt} giờ chỉ thêm chưa tới 10kB vào binary” khá thú vị
  Tôi chưa từng thử kiểu kiểm tra này

  • Điều đó khác biệt rất lớn tùy vào việc bạn liên kết động hay tĩnh với thư viện C, cũng như cách bạn build ứng dụng và thư viện C
    Dùng thư viện C nào cũng quan trọng, và dùng ELF hay một dạng container khác cũng có ảnh hưởng đôi chút

• Lúc nào fmt cũng là vấn đề
  Thật buồn cười là nếu đụng đến đủ nhiều kiểu số, đặc biệt là định dạng/phân tích số dấu phẩy động và decimal, thì linker sẽ kéo vào rất nhiều mã liên quan đến số dấu phẩy động và BigInt làm binary phình ra; giờ điều đó cũng đang xảy ra y hệt trong .NET

  • Tôi vẫn đang mong Native AOT rồi sẽ cho trải nghiệm kiểu Delphi, và may là mọi thứ đang dần tốt hơn

• Rất thú vị
  Tôi thích kiểu tối ưu hóa đổi góc nhìn như thế này

• Có lẽ là do tôi chậm hiểu, nhưng tôi mất một lúc mới nhận ra “14k” trong tiêu đề nghĩa là 14kB

  • Tôi không thấy nó còn có thể nghĩa là gì khác
    Ít nhất về mặt lịch sử thì k là cách viết tắt rất phổ biến của kB