Các quy tắc lập trình của Rob Pike (1989)
(users.ece.utexas.edu)- Bài viết về 5 quy tắc lập trình của Rob Pike năm 1989
- Quy tắc 1: Đừng giả định chương trình sẽ dành phần lớn thời gian ở đâu; điểm nghẽn có thể xuất hiện ngoài dự kiến. Hãy tránh các mẹo tối ưu tốc độ cho đến khi điểm nghẽn được chứng minh.
- Quy tắc 2: Luôn đo đạc trước khi tinh chỉnh vì tốc độ. Chỉ tối ưu hóa khi một phần của mã có ảnh hưởng đáng kể đến phần còn lại.
- Quy tắc 3: Khi n nhỏ, các thuật toán phức tạp sẽ chậm. Đây là trường hợp của hầu hết tình huống. Chỉ dùng thuật toán phức tạp khi n thường xuyên lớn, và ngay cả khi đó cũng hãy áp dụng Quy tắc 2 trước.
- Quy tắc 4: Các thuật toán và cấu trúc dữ liệu đơn giản là điều đáng mong muốn. Chúng ít dễ phát sinh lỗi hơn và dễ triển khai hơn so với những thứ phức tạp.
- Quy tắc 5: Cấu trúc dữ liệu đúng là yếu tố mang tính quyết định trong lập trình. Nếu dữ liệu được tổ chức tốt, thuật toán sẽ trở nên hiển nhiên.
- Quy tắc 1 và 2 của Pike phản ánh châm ngôn của Tony Hoare: "tối ưu hóa sớm là cội nguồn của mọi điều xấu".
- Ken Thompson diễn đạt lại Quy tắc 3 và 4 của Pike thành: "khi còn nghi ngờ, hãy dùng sức mạnh thô bạo".
- Quy tắc 3 và 4 hiện thực hóa triết lý thiết kế KISS (Keep It Simple, Stupid).
- Quy tắc 5 phù hợp với phát biểu trong 'The Mythical Man-Month' của Fred Brooks, thường được rút gọn thành "hãy viết đoạn mã ngốc sử dụng các đối tượng thông minh".
1 bình luận
Ý kiến trên Hacker News
Hoàn toàn đồng ý với câu “dữ liệu mới là thứ chi phối”
Vì vậy các buổi phỏng vấn LeetCode lúc nào cũng khiến tôi thấy kỳ lạ. Thường chúng tập trung vào thuật toán, nhưng trong thực tế, nhiều trường hợp không nên tiếp cận như vậy ngay từ đầu, mà cấu trúc dữ liệu mới nên là trọng tâm hơn
Tất nhiên, nếu hoàn toàn không biết thuật toán thì có thể không nhận ra các tình huống ngoại lệ hoặc những lúc cần dựa vào một thuật toán cụ thể vì một lý do nào đó. Dù vậy, thuật toán có thể được dạy tương đối nhanh, còn việc có trực giác nên dùng cấu trúc dữ liệu nào thì có vẻ mọi người thấy khó hơn
Khoảnh khắc đó, không khí chuyển sang kiểu “à, một kỹ sư senior thật sự đã bước vào”, các vấn đề kỹ thuật được bàn mở hơn và thái độ muốn chứng minh “có biết code không” cũng giảm đi
Ngược lại, những đội khó làm việc nhất trong việc tạo ra thay đổi tốt, đạt milestone và hợp tác nhóm là những nơi không có ai nắm cho đúng cấu trúc dữ liệu và kiến trúc code. Có vẻ ngày càng nhiều người quen với kiểu framework sẽ làm hết, nếu không được thì một plugin hay middleware do ai đó thông minh hơn tạo ra sẽ giải quyết hộ
Kỹ sư né tránh cấu trúc dữ liệu chẳng khác nào tự bắn vào chân mình, từ bỏ một trong những công cụ hữu ích nhất, nên giới hạn sẽ bộc lộ trong công việc hằng ngày
Ví dụ, code có thể được dùng nhiều để tìm đường đi dài nhất trong đồ thị có hướng không chu trình (DAG) có trọng số, nhưng điểm mấu chốt là nhận ra rằng bài toán có thể được biểu diễn thành DAG có trọng số. Nếu không thấy được điều đó, vẫn có thể giải, nhưng lời giải sẽ chậm và phức tạp hơn nhiều
Người phỏng vấn sẽ không nói trước rằng phải dùng hàng đợi ưu tiên, ma trận kề hay trie. Nếu bí thì có thể cho gợi ý, nhưng dẫn dắt quá nhiều thì khó xem là tín hiệu tuyển dụng mạnh
Liên quan đến câu “thuật toán đẹp thì chậm khi n nhỏ, mà n thường nhỏ”, điều tôi cảm nhận trong một dự án gần đây là n lớn có thể lớn hơn ta tưởng rất nhiều
Dễ nghĩ rằng “phải thực hiện 100.000 phép tính, chắc chắn phải tối ưu”, nhưng máy tính rất nhanh và cỡ 100.000 phép nhân thường quá nhanh đến mức có thể không cần suy nghĩ quá sâu
Không phải là không cần nghĩ gì, nhưng phần cứng hiện đại nhanh một cách điên rồ đến mức thường khiến ta ngạc nhiên
Tôi từng thấy sự cố production do code vô tình chạy thời gian bậc hai; dù 99% người dùng luôn dùng n nhỏ, một số người dùng vẫn thường gặp n lớn và phải chịu một ứng dụng rất chậm
Trong hầu hết trường hợp, tôi muốn chọn một thuật toán tốt hơn bậc hai, dù nó hơi chậm hơn ở trường hợp thông thường và triển khai hơi phức tạp hơn. Các đường chậm phổ biến sẽ được tối ưu, còn các đường chậm hiếm gặp thì developer không tự đi qua nên bỏ sót, hoặc nổ trên production
Tất nhiên, nếu thuật toán quá phức tạp thì có thể chọn cách triển khai bậc hai đơn giản, nhưng mặc định tôi cố đặt mục tiêu dưới bậc hai nếu có thể. Tôi cũng có viết một bài liên quan: https://kevincox.ca/2023/05/09/less-than-quadratic/
Vì vậy, điều này có thể đúng hơn vào 40 năm trước, khi CPU chưa nhanh hơn bộ nhớ đến vậy và phần cứng tiêu dùng chưa quá phải bận tâm đến lỗi dự đoán nhánh
Mỗi lần phỏng vấn, chuyện xảy ra là hiring manager thì muốn, nhưng một người mới với LeetCode chưa từng trải qua vết sẹo production lại từ chối quyết định đó
https://www.frankmcsherry.org/assets/COST.pdf
Nghĩ đến mức tăng hiệu năng máy tính trong 20 năm qua, việc nâng ngưỡng đó lên 100.000 có vẻ khá hợp lý
Câu châm ngôn nổi tiếng “tối ưu hóa sớm là nguồn gốc của mọi điều xấu” thực ra không phải của Tony Hoare mà là từ Donald Knuth, và thường bị dùng ngoài ngữ cảnh như một câu phản đối việc tối ưu hóa nói chung
Câu đầy đủ là: “Chúng ta nên quên đi những hiệu quả nhỏ nhặt, có thể nói là trong 97% trường hợp. Tối ưu hóa sớm là nguồn gốc của mọi điều xấu. Tuy nhiên, chúng ta không nên bỏ lỡ cơ hội trong 3% quan trọng”
Ý chính là hãy dành thời gian tối ưu hóa ở những nơi có tác động
Có khả năng Tony nói trước, rồi Knuth chỉnh lại và xuất bản. Việc đặt kèm trích dẫn dài để cung cấp ngữ cảnh cần thiết luôn là điều tốt
Lập trình thời đó rất khác với bây giờ. “Tối ưu hóa sớm” khi ấy không hẳn là “cứ dùng thư viện phổ biến có khả năng mở rộng tốt”, mà gần với “hãy dùng một thuật toán thao tác bit khó hiểu chỉ chạy trên phần cứng này” hơn
Ý này đã nằm sẵn trong câu “tối ưu hóa sớm là nguồn gốc của mọi điều xấu”, và câu châm ngôn không phải là “tối ưu hóa là nguồn gốc của mọi điều xấu”
Trong các buổi phỏng vấn cấu trúc dữ liệu và thuật toán ở công ty, tôi đã thấy vô số lập trình viên frontend nói rằng bubble sort là lựa chọn tốt nhất. Không cần họ phải suy diễn ra ngay tại chỗ; chỉ cần biết vài lựa chọn và nói được lựa chọn tốt phù hợp với bài toán là đủ
Nếu sống quá cực đoan theo kiểu “đừng tối ưu hóa sớm” đến mức cả phương pháp hiệu quả cũng không biết, thì làm sao biết chỗ nào là quan trọng?
Câu “cấu trúc dữ liệu là cốt lõi” còn quan trọng gấp đôi trong cơ sở dữ liệu
Những người dùng DB như một kho chứa bit ngu ngốc hoặc chỉ là phản ánh 1:1 của định nghĩa object thường ngạc nhiên khi DB xem đó là chuyện cá nhân và phá hỏng hiệu năng
Nếu tôi lại phải nhìn thấy một schema DB do ORM sinh ra nữa thì có lẽ đó sẽ là một cuộc tái ngộ quá sớm
Vấn đề là một số, hoặc nhiều, lập trình viên không biết SQL và cũng không có kiến thức DB cần thiết để dùng ORM
ORM là một abstraction khá rò rỉ, đòi hỏi bạn phải biết bên dưới có gì. Nếu hiểu điều đó, bạn vẫn có thể tạo schema ổn bằng hầu hết ORM
Để tổ chức tốt cấu trúc dữ liệu và duy trì như vậy ngay cả khi thiết kế thay đổi, cần tách dữ liệu và code ở cấp độ tổ chức
Thiết kế schema DB, các use case, và phần mapping giữa chúng nên được tách khỏi phần triển khai còn lại, và nhóm này cũng nên viết các kiểm tra tính toàn vẹn. Nếu cấu trúc tổ chức không tách dữ liệu và code, rất khó tách code và dữ liệu
Quy tắc bổ sung của tôi là các lãng phí hiệu năng nhỏ khi tích tụ lại, dù từng cái không đáng kể, cuối cùng vẫn làm chương trình chậm đi
Nếu không ảnh hưởng đến độ phức tạp, khả năng đọc, khả năng bảo trì, hay chi phí triển khai, thì không nên cứ bỏ mặc hiệu năng. Khi các điều kiện khác gần như tương đương, chọn phương án chậm hơn trong hai lựa chọn là không ổn
Ngoài ra, nếu giả định n nhỏ thì gần như cách nào cũng chạy được. Nhưng nếu viết code chạy tốt khi n dưới 100 và hỏng khi n trên 10000, chẳng hạn như O(n²), thì nên đặt giới hạn luôn. Khi giả định n nhỏ bị phá vỡ, việc báo lỗi lớn còn tốt hơn một hóa đơn AWS khổng lồ hoặc một chương trình bị treo
Khá nhiều chỉ dẫn trong số này rốt cuộc quy về các chiến lược ngăn thiết kế quá mức
Theo kinh nghiệm của tôi, tối ưu hóa sớm là một trong những cái bẫy đắt đỏ nhất. Nếu né tránh các vấn đề tiềm tàng quá sớm, giả định đó không được kiểm chứng, và nhóm tiếp theo phải tạo ra những giải pháp tốn kém để xử lý độ phức tạp không cần thiết
Cách tiếp cận tôi học được là thế này: tối ưu hóa dựa vào ước đoán, mà các ước đoán ban đầu thường sai
Tôi cũng nhận ra rằng để ngăn mọi người viết code quá phức tạp, việc quản lý cái tôi và hiểu tâm lý là khá quan trọng
Sản xuất dư thừa thường được xem là loại lãng phí tệ nhất, vì nó không chỉ tạo ra thứ không cần thiết mà còn tiêu tốn công sức lẽ ra có thể dùng cho thứ thực sự cần. Thiết kế quá mức cũng tương tự
Ví dụ, dù chỉ có 100 người dùng, vẫn bắt đầu bằng kiến trúc microservices vì cho rằng nếu một ngày có 1 triệu người dùng thì sẽ khó thiết kế lại monolith
Vì vậy trước hết cần xử lý lý do vì sao code trở nên kém mềm dẻo hơn theo thời gian
Nhìn chung đây là các quy tắc hay, nhưng trên thực tế quy tắc số 1 không hoàn toàn đúng như vậy
Khi bắt đầu, cần có một giả thuyết về thứ gì sẽ trở thành nút thắt cổ chai. Không phải lúc nào cũng có thể cứ triển khai XYZ rồi đo xem thứ gì chậm và sửa nó. Vì X, Y, Z liên kết với nhau, đôi khi để làm Y nhanh hơn thì phải xây X và Z theo một cách nhất định, và có những trường hợp ta đã biết Y sẽ là nút thắt cổ chai
Ngay cả sau này khi đo và biết được thứ gì chậm, ta vẫn phải đặt cược vào một cách tiếp cận để làm nó nhanh hơn. Càng là một phép đặt cược có cơ sở thì càng tốt
Lập trình viên giỏi có đo đạc, nhưng họ cũng dự đoán được thứ gì sẽ chậm, nhiều lỗi, tốn nhiều bộ nhớ, nên phải lặp lại ít hơn. Nếu nói như một quy tắc rằng không thể dự đoán hành vi hiệu năng, thì chẳng khác nào phớt lờ kinh nghiệm và kỹ năng mà lập trình viên giỏi đã tích lũy
Vì chính quá trình tuân thủ quy tắc số 1 là cách tốt nhất để có được kinh nghiệm và nền tảng thực nghiệm cần thiết cho trực giác tốt về việc dự đoán nút thắt cổ chai
Nếu dự đoán tốc độ sai, bạn sẽ phải ôm mã phức tạp không cần thiết trong suốt vòng đời dự án
Người ta rất hay đoán sai tốc độ thuật toán. Nếu máy tính dùng 99% thời gian để lấy n từ DB server, thì O(n) và O(n²) nhiều khi trông như có thời gian thực tế giống nhau
Cũng có lúc thuật toán viết bằng C chậm hơn đoạn mã Python tương đương, có thể vì trình biên dịch bytecode đã làm điều gì đó thông minh
Tôi đã làm khá nhiều việc tăng tốc mã legacy, và thường nó dễ hơn tưởng nhiều, chậm vì những lý do không hiển nhiên với tác giả ban đầu. Thực tế, nhiều trường hợp chậm là do codebase đã trở nên quá phức tạp đến mức tác giả gốc không còn suy luận được nữa. Với tôi thì có ví dụ cụ thể về việc “quá chậm”, nên rất dễ chạy, quan sát chỗ chậm và debug
Nếu bạn đang làm một video game có nhiều đối tượng vật lý, và từ kinh nghiệm biết chắc phát hiện va chạm sẽ là vấn đề lớn, thì thiết kế game và hệ thống xoay quanh việc đó không phải là speed hack
Nếu bạn biết hiệu năng sẽ là mối quan tâm lớn, thì đương nhiên phải đo. Không phải để xác nhận nó có phải mối quan tâm hay không, mà để kiểm tra bạn đang xử lý mối quan tâm đó tốt đến đâu
Nếu xây một hệ thống mới cho yêu cầu mới, nhiều khi cứ bắt đầu trước cũng ổn. Làm, kiểm thử·đo đạc, bỏ đi hoặc refactor, rồi lặp lại
Lấy Rust làm ví dụ, nó bắt đầu từ một ngôn ngữ nháp và trình biên dịch viết bằng OCaml rồi lặp dần. Dù có biết một ngày nào đó có thể chuyển từ OCaml sang tự host, tôi cũng không chắc điều đó có tạo khác biệt lớn hay không
Nếu không có người dùng, thì một hàm mất vài giờ vẫn đủ nhanh so với một hàm có thể tối ưu xuống mili-giây. Tôi không rõ có ai đã chứng minh được rằng mình có thể dự đoán chính xác những thứ như vậy hay chưa
Để phản biện quy tắc số 5, thuật toán phức tạp trên dữ liệu đơn giản có thể mang lại lợi ích hiệu năng lớn, loại bỏ chướng ngại và thậm chí làm mọi thứ đơn giản hơn
Ví dụ, nếu dùng tìm kiếm nhị phân trên mảng đã sắp xếp thay vì đối tượng BinaryTree, thao tác gộp sẽ đơn giản thành concat rồi sắp xếp; không có con trỏ nên dễ serialize; và trong một số trường hợp thậm chí không cần serialize. Mảng có thể nằm trên đĩa, trong bộ nhớ, hoặc cả hai qua mmap; có thể xử lý dữ liệu lớn hơn RAM; và cũng có thể cold start bằng cách chỉ trỏ tới file hoặc mapping rồi chạy ngay. Nó cũng có đặc tính cache-oblivious
Huffman coding cũng là một ví dụ. Ở đại học thường học thuật toán dựa trên cây với độ phức tạp O(n log n), nhưng tôi không biết rằng có cách xây dựng cây Huffman tại chỗ trên mảng trong thời gian tuyến tính
Tất nhiên 99% thời gian ta làm backend microservice và dùng các cấu trúc dữ liệu collection chuẩn. Nhưng nếu ở công ty phải làm việc với big data, tôi sẽ thích xử lý trên một máy đơn có ổ đĩa cục bộ lớn hơn nhiều so với việc đưa vào họ MapReduce đang thịnh hành lúc đó
Nếu là Rob Pike, có lẽ ông ấy sẽ bảo trước tiên hãy profile mã, rồi sau đó xem mã hào nhoáng hoặc cấu trúc dữ liệu thay thế có thực sự nhanh hơn không
Tôi đọc bài này lần đầu trên cat-v hơn 10 năm trước, và nó đã để lại ảnh hưởng không thể xóa nhòa lên cách tôi tiếp cận và suy nghĩ về thiết kế cũng như độ phức tạp
http://doc.cat-v.org/bell_labs/pikestyle
Tôi không hiểu làm thế nào từ quy tắc gốc “cấu trúc dữ liệu là cốt lõi” lại được rút gọn thành “viết mã ngớ ngẩn dùng đối tượng thông minh”
Cách diễn đạt “smart objects” quá tệ, còn quy tắc gốc dù dài hơn vẫn hay hơn nhiều