Lỗi của đoạn mã Stack Overflow được sao chép nhiều nhất mọi thời đại (2019)

 (programming.guide)
3 điểm bởi GN⁺ 2023-09-28 | 1 bình luận | Chia sẻ qua WhatsApp
  • Câu trả lời Java humanReadableByteCount được viết năm 2010 đã được xác nhận trong một nghiên cứu năm 2018 là đoạn mã Stack Overflow bị sao chép nhiều nhất, nhưng lại cho kết quả sai ở các giá trị biên khi định dạng kích thước byte
  • Đoạn mã này dùng tính chất các tiền tố như kB, MB, GB là lũy thừa của 1000 hoặc 1024, và chọn đơn vị bằng phép tính log thay vì dùng vòng lặp
  • Lỗi chính là vấn đề ngưỡng làm tròn khiến 999,999 bytes được in thành "1000.0 kB" trong chế độ SI, trong khi theo đặc tả nếu phần số phải nằm trong khoảng 1 đến 999.9 thì kết quả đúng phải là "1.0 MB"
  • Với các giá trị lớn hơn, giới hạn độ chính xác số thực dấu chấm động của double còn khiến đầu vào 999,949,999,999,999,999 cho ra 1000.0 PB, và việc sửa cần đến tính toán ngưỡng, thu nhỏ thang đo, hiệu chỉnh mẫu bit và strictfp
  • Mã cuối cùng xử lý cả số âm lẫn Long.MIN_VALUE, nhưng đánh mất sự ngắn gọn ban đầu; việc sao chép mã từ Stack Overflow cần đi kèm kiểm thử các trường hợp biên và ghi nguồn

Sự đơn giản hóa mà câu trả lời năm 2010 nhắm tới

  • Bài toán là định dạng số byte thành chuỗi dễ đọc với con người
    • Ví dụ: in 123,456,789 bytes thành "123.5 MB"
    • Đặc tả ngầm là phần số trong chuỗi kết quả phải nằm trong khoảng từ 1 đến 999.9, kèm hậu tố kích thước phù hợp
  • Câu trả lời trước đó dùng cách tiếp cận dựa trên vòng lặp: duyệt EB, PB, TB, GB, MB, kB, B từ đơn vị lớn xuống nhỏ và chọn đơn vị đầu tiên nhỏ hơn số byte
  • Câu trả lời mới dùng Math.log và Math.pow để giảm vòng lặp và nhánh điều kiện
    • Trong chế độ SI, đơn vị là 1000
    • Trong ký hiệu nhị phân, đơn vị là 1024
    • Giá trị exp = log(bytes) / log(unit) được chuyển thành số nguyên để dùng làm chỉ số tiền tố
    • Tiền tố dùng "kMGTPE" cho SI và "KMGTPE" cho nhị phân, rồi thêm "i" vào chế độ nhị phân

Thực trạng sao chép và câu chuyện OpenJDK

  • Bài báo của Sebastian Baltes Usage and Attribution of Stack Overflow Code Snippets in GitHub Projects phân tích cách các đoạn mã Stack Overflow được dùng trong các dự án GitHub và cách chúng được ghi nguồn
  • Cách phân tích là trích xuất các đoạn mã từ bản dump dữ liệu Stack Overflow rồi đối chiếu với mã trong các kho GitHub công khai
    • Câu hỏi trọng tâm là liệu việc ghi nguồn có tuân thủ giấy phép CC BY-SA 3.0 của Stack Overflow hay không
    • Kết quả là đa số người dùng không kèm ghi nguồn đúng cách
  • Câu trả lời ID 3758880 đứng đầu bảng trong bài báo, và khi đó đã có hàng trăm nghìn lượt xem cùng hơn 1.000 upvote
  • Tìm humanReadableByteCount trên GitHub cho ra hàng nghìn trường hợp sử dụng, và trong kho cục bộ có thể kiểm tra bằng lệnh sau
git grep humanReadableByteCount
  • Một trường hợp trùng khớp cũng được tìm thấy trong kho OpenJDK
    • Đoạn mã đó không có ghi nguồn, và giấy phép OpenJDK không tương thích với CC BY-SA 3.0
    • Sebastian Baltes đã hỏi trên mailing list phát triển OpenJDK rằng mã được sao chép từ Stack Overflow sang OpenJDK hay theo chiều ngược lại
    • Tác giả câu trả lời cho biết mình chưa gia nhập Oracle trước khi commit đó được merge, và cũng không đóng góp cho bản vá đó
    • Sau đó một issue đã được tạo và đoạn mã bị xóa bỏ

Lỗi đầu tiên: giá trị biên với chuỗi 999 lặp lại

  • Những điểm đáng nghi bề ngoài thực ra không phải nguyên nhân
    • Giá trị lớn nhất của long là 2^63 - 1, khoảng 9.2 × 10^18, nên không vượt sang đơn vị sau EB
    • Trường hợp bytes < unit đã được if đầu tiên xử lý, nên exp không trở thành 0 để charAt(exp - 1) bị lỗi
  • Vấn đề thực sự là ngưỡng làm tròn
    • Đầu vào 999,999 bytes trong chế độ SI trở thành "1000.0 kB"
    • Theo đặc tả rằng phần số phải nằm trong khoảng từ 1 đến 999.9, kết quả đúng phải là "1.0 MB"
  • Tại thời điểm đó, cả 22 câu trả lời đã được đăng, kể cả các câu trả lời dùng Apache Commons và thư viện Android, đều mắc lỗi này hoặc một biến thể của nó
  • Trọng tâm của cách sửa là ngưỡng quyết định khi nào số mũ exp phải tăng lên đơn vị tiếp theo
    • Điểm chuyển từ k sang M là 999,950, khi giá trị gần 1 MB hơn 999.9 k
    • Điểm chuyển từ M sang G là 999,950,000
    • Trong chế độ nhị phân, ngưỡng không phải số nguyên nên cần ceil
if (bytes >= Math.ceil(Math.pow(unit, exp) * (unit - 0.05)))
    exp++;

Lỗi thứ hai: giới hạn độ chính xác của double

  • Ngay cả sau khi áp dụng phần sửa trên, đầu vào 999,949,999,999,999,999 vẫn được in thành 1000.0 PB, trong khi kết quả đúng là 999.9 PB
  • Nguyên nhân không nằm ở công thức toán học mà ở giới hạn độ chính xác của double
    • Trong biểu diễn IEEE 754, các giá trị dấu chấm động gần 0 thì dày đặc, còn các giá trị lớn thì rất thưa
    • Với double rất lớn, trừ đi cả Long.MAX_VALUE cũng có thể không làm giá trị thay đổi
double a = Double.MAX_VALUE;
double b = a - Long.MAX_VALUE;
System.err.println(a == b); // prints true
  • Phép tính gây vấn đề xuất hiện ở hai chỗ
    • Phép chia được thực hiện trong đối số của String.format
    • Phần tính ngưỡng để quyết định có tăng exp hay không
  • Vấn đề thứ nhất được xử lý bằng cách giảm giá trị bytes trung gian xuống một phạm vi có độ chính xác tốt hơn và điều chỉnh exp
    • Tiền đề là kết quả cuối cùng dù sao cũng sẽ bị làm tròn, nên có thể bỏ đi các chữ số thấp hơn
if (exp > 4) {
    bytes /= unit;
    exp--;
}
  • Ở vấn đề thứ hai, các bit thấp lại rất quan trọng
    • 999,949,99…9 và 999,950,00…0 phải được phân loại vào các số mũ khác nhau
    • Có tổng cộng 12 ngưỡng khả dĩ khi gộp cả SI và nhị phân, và chỉ một trong số đó cho kết quả sai
    • Kết quả sai được nhận diện bằng mẫu bit kết thúc bằng D00 để hiệu chỉnh
    • Vì cách làm này phụ thuộc vào mẫu bit của kết quả dấu chấm động cụ thể, nên cần thêm strictfp

Đầu vào âm và mã cuối cùng

  • Vì Java không có long unsigned, nên việc xử lý số byte âm cũng được bổ sung
    • Trước đó, đầu vào -10,000 sẽ được in thành -10000 B
    • absBytes được đưa vào để các phép tính liên quan tới exp thực hiện theo giá trị tuyệt đối
  • Long.MIN_VALUE cần xử lý đặc biệt
    • Vì -Long.MIN_VALUE == Long.MIN_VALUE
    • Do đó nếu bytes == Long.MIN_VALUE thì dùng Long.MAX_VALUE, còn lại thì dùng Math.abs(bytes)
  • Phiên bản cuối cùng bao gồm strictfp, hiệu chỉnh ngưỡng, xử lý Long.MIN_VALUE và thu nhỏ thang đo ở các số mũ lớn
  • Đoạn mã vốn muốn tránh vòng lặp và các nhánh điều kiện quá mức, sau khi xử lý hết mọi corner case, lại trở nên khó đọc hơn cả phiên bản ban đầu
  • Có thể tham khảo mã hiện đại đạt chất lượng production trong bài viết riêng Formatting byte size to human readable format

Bài học rút ra trong thực tế

  • Các đoạn mã trên Stack Overflow dù có hàng nghìn upvote vẫn có thể chứa lỗi
  • Mã được sao chép đặc biệt cần kiểm thử các trường hợp biên
  • Số học dấu chấm động rất khó xử lý ở các giá trị biên và số lớn
  • Khi sao chép mã, cần ghi nguồn phù hợp; nếu không, điều đó có thể trở thành vấn đề thực sự

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-09-28
Các ý kiến trên Hacker News

  • Điều thú vị là các câu trả lời dùng giá trị hard-code và câu lệnh if (hoặc while) đều thực hiện tối đa 5 lần so sánh
    Nếu đơn vị chỉ đến B, KiB, MiB, GiB, TiB, EiB thì cũng có thể giải quyết bằng tối đa 3 câu lệnh if. Chỉ cần kiểm tra xem có từ GiB trở lên hay không thì biết ngay không phải B/KiB/MiB, nên tìm kiếm nhị phân thắng
    Ngay cả khi mở rộng tới ZiB và YiB thì tối đa 3 lần so sánh vẫn đủ, còn cách hard-code lên tới tối đa 7 lần. Nếu tự viết, tôi sẽ không dùng log/pow/số thực dấu phẩy động vì khả năng sai sót quá lớn; có lẽ vẫn hard-code các câu lệnh if nhưng theo kiểu tìm kiếm nhị phân

    • Cách tìm kiếm nhị phân có thể chậm hơn việc chỉ kiểm tra 6 lần. Cách sau nhiều khả năng chỉ đi qua 1 nhánh, mà rẽ nhánh thì rất chậm, nên tốt nhất là giữ luồng mã càng tuyến tính càng tốt
    • Còn tùy phân bố đầu vào. Nếu các giá trị nhỏ rất phổ biến thì tìm kiếm tuyến tính có thể tốt hơn
    • Tôi cho rằng đây là một phán đoán kỹ thuật tệ. Giải pháp đơn giản thì đồng nghiệp dễ review, các điều kiện biên cũng hiện rõ, và dễ kiểm tra xem test có bao phủ chúng không
      Kiểu mã này chẳng khác nào làm rất nhiều việc để viết ra đoạn mã chậm hơn, phức tạp hơn, khó test và khó review hơn

  • (2019) Các thảo luận trước đây:
    https://news.ycombinator.com/item?id=21693431
    https://news.ycombinator.com/item?id=21698619
    https://news.ycombinator.com/item?id=27533684

  • Tôi không hiểu. Nếu có 7 hậu tố thì cứ dùng tìm kiếm nhị phân để chọn cái đúng, chỉ cần 3 lần so sánh. Hoặc làm đơn giản thì cũng chỉ 6 lần so sánh
    Tôi không hiểu vì sao dùng hai lần log(), một lần pow() và ceil() lại tốt hơn cách đơn giản. Bản thân lỗi được mô tả ở đây là ví dụ hoàn hảo của việc cố tỏ ra quá thông minh

    • Có vẻ tác giả thừa nhận là khó đọc và đã quay lại cách dùng vòng lặp: https://programming.guide/java/formatting-byte-size-to-human...
      Dù vậy, vì có xét đến lỗi làm tròn nên vẫn tốt hơn một chút so với ví dụ mã đầu tiên trong bài gốc
    • Ngay từ đầu tác giả cũng nói rằng thực tế nó không tốt hơn vòng lặp
      Ngoài ra, 6 lần so sánh chỉ là khi gặp giá trị lớn nhất, mà trong sử dụng thực tế có vẻ khó xảy ra. Nếu phần lớn giá trị nằm trong phạm vi B hoặc KB thì cách tuyến tính có thể tốt hơn

  • Quảng bá hơi trơ trẽn, nhưng thay vì sao chép từ S/O, nếu muốn định dạng kích thước nhanh và chính xác theo dạng dễ đọc cho con người, bạn cũng có thể dùng thư viện mã nguồn mở PrettySize của chúng tôi. Có bản cho Rust [0] và .NET [1], đồng thời giúp thực hiện an toàn và dễ dàng các phép toán logic type-safe trên kích thước tệp
    Đoạn mã S/O chỉ có 4 dòng, nhưng các thư viện này toàn diện hơn nhiều và bao gồm test, tùy chọn định dạng đầu ra, chuyển đổi kích thước, v.v.
    [0]: https://github.com/neosmart/prettysize-rs
    [1]: https://github.com/neosmart/PrettySize.net

    • Văn hóa thay thế một giải pháp 4 dòng bằng một thư viện đồ sộ chính là thứ đã sinh ra left-pad

  • Tôi thật sự tò mò: có nhiều lập trình viên cứ sao chép mã không đáng tin cậy trên Stack Overflow rồi dán thẳng vào ứng dụng không?
    Việc người ta cứ sao chép từ Stack Overflow là một giả định nổi tiếng, nhưng cho đến khi tận mắt thấy ai đó làm vậy thì tôi vẫn nghĩ nó gần như chỉ là chuyện đùa. Tôi cũng dùng Stack Overflow làm điểm xuất phát khi giải quyết vấn đề trong những lĩnh vực mình chưa quen, nhưng chưa từng sao chép nguyên xi mã
    Thường thì các đoạn mã không làm đúng chính xác những gì tôi cần, nên tôi phải xem API và dựa trên cách tiếp cận được mô tả để tự xây dựng lời giải của mình. Đặc biệt với Python, Stack Overflow nhiều lần chỉ cho tôi hướng đến những API ngách hữu ích

    • Trước đây tôi từng làm việc với một lập trình viên mà không ai có thể ngăn anh ta sao chép vào mã ngay khi nhìn thấy câu trả lời. Anh ta thậm chí không đọc câu hỏi để kiểm tra xem có đúng vấn đề mình gặp không, và cũng không đọc câu trả lời
      Đúng nghĩa là Google → nhấp vào liên kết Stack Overflow đầu tiên hiện ra → sao chép/dán khối mã đầu tiên nhìn thấy, đôi khi còn khác cả ngôn ngữ. Khi lập trình đôi, tôi đã phải giật thiết bị nhập liệu theo đúng nghĩa đen. Nếu nói là sai, anh ta đã dán đoạn mã thứ hai trên trang trước khi tôi kịp nói hết câu, và nhanh đến kỳ lạ
      Đây là trường hợp cực đoan, nhưng có nhiều lập trình viên mang tư duy “cần mã; Stack Overflow có mã; xong!” mà hoàn toàn không nghĩ xem đó có phải là lời giải phù hợp hay không
    • Chuyện đó thực sự xảy ra, và càng là phần chương trình mà tôi cảm thấy nằm ngoài phạm vi mình quan tâm thì càng xảy ra thường xuyên hơn
      Dù sao thì chúng ta lúc nào cũng lấy mã thư viện do người lạ viết cho những phần việc đường ống mà mình không mấy bận tâm. Nếu muốn đào sâu để hiểu, nhiều khả năng ta sẽ tự viết; nhưng nếu chỉ muốn phần này “cứ chạy được” rồi tiếp tục dự án, thì nó trở thành phát triển dựa trên lỗi trình biên dịch
    • Vì những lý do tác giả nêu, tôi hầu như không sao chép/dán nguyên xi. Thay vào đó tôi cố hiểu lời giải, và nếu cần thì chép tay từng dòng để hiểu cho đúng rồi refactor từ đó
      Tôi cũng đổi tên biến. Vì có quá nhiều foo, bar, baz, thường khiến người đọc khó hiểu. Khi gặp lại cùng vấn đề, tôi cũng dễ nhớ mình đã làm gì hơn so với khi sao chép mù quáng
    • Thực sự là người ta làm vậy. Sau khi thấy cực kỳ nhiều mã và cấu hình TLS sai trên StackOverflow, tôi khá tin rằng phần lớn hệ thống đang chạy mà không xác minh chứng chỉ đúng cách
    • Có lẽ bạn vẫn chưa được tận hưởng niềm vui làm việc trên codebase do những người 23 tuổi dùng Adderall tạo ra

  • Cần log 2 thì tôi không hiểu sao lại dùng log dấu phẩy động
    Nếu tôi không bỏ sót gì, biểu thức dưới đây cho floor(log2(value)) chính xác với các số dương nhỏ hơn 2^63 byte và nhanh hơn nhiều:
    Long.bitCount( (Long.highestOneBit(value) << 1) - 1) - 1

    • Vì các đơn vị “thông thường” là lũy thừa của 10, nên cách này không đúng

  • Vừa nhìn đoạn mã là tôi thấy phép log dấu phẩy động và phép chia trên số nguyên, nên tôi lập tức loại nó khỏi đầu vì cho rằng đây là mã cố tỏ ra quá khôn khéo và về bản chất dễ sinh lỗi

    • Về cơ bản đó chính là ý chính của bài viết

  • Chuỗi tri thức kéo dài xuống tận cùng. Nó cho thấy ngay cả một mẩu kiến thức rất nhỏ, một khi đã lấy ra, cũng khó nhét lại vào chỗ cũ đến mức nào
    Trong bối cảnh Stack Exchange đang nhanh chóng mất đi những người đóng góp tích cực, tôi tự hỏi cần gì để sửa lại các câu trả lời rút súng nhanh về sau hóa ra là sai lệch. Và tôi cũng tự hỏi việc những câu trả lời “hơi sai” như thế này ngày càng đóng cứng trong lịch sử tìm kiếm và cả lịch sử LLM sẽ có ý nghĩa gì đối với tri thức tập thể của chúng ta

  • Làm tôi nhớ đến hồi huấn luyện quân sự cơ bản. Các huấn luyện viên thường cố ý giao cho tân binh một nhiệm vụ không ai biết làm, không đưa hướng dẫn gì rồi bỏ đi
    Thế là luôn có ai đó bắt đầu theo cách sai, và tất cả những người còn lại làm theo người đó

    • Tôi tự hỏi liệu xu hướng con người không muốn trông tệ hơn người khác có làm chuyện này trầm trọng hơn không. Nó có thể dẫn đến kết quả ngớ ngẩn là cả những người thông minh cũng đi theo ý tưởng tệ hoặc vội vàng
      Trong dự báo kinh tế công khai cũng có chuyện tương tự. Người một mình dự đoán sai trong khi những người khác đúng sẽ bị đối xử khắc nghiệt hơn nhiều so với người sai cùng với tất cả mọi người
    • Mục tiêu của bài huấn luyện đó là gì?

  • Tôi không nhất thiết xem lỗi dấu phẩy động trong những thuật toán như thế này là “khiếm khuyết”. Nếu mã định nghĩa một lời giải đúng về mặt logic và toán học, thì bản thân nó là “đúng”
    Xử lý lỗi dấu phẩy động là một tầng cao hơn, và chỉ làm khi nó thực sự quan trọng. Tôi có thể tưởng tượng một ngôn ngữ lập trình hoàn hảo trong tương lai, nơi lỗi dấu phẩy động không tồn tại nên cũng không cần xét đến; 99% thuật toán của tôi coi như đang nhắm tới một ngôn ngữ như vậy