Tóm tắt

Hãy cẩn trọng với sự gia tăng dữ liệu bùng nổ/ số mũ: Không tối ưu hóa quá sớm, nhưng hãy chú ý đến độ phức tạp thuật toán Big-O. Các thuật toán làm việc với dữ liệu người dùng nên có thời gian thực thi dự đoán được, và tốt nhất là không tệ hơn O(N) (hàm có độ phức tạp tuyến tính so với lượng dữ liệu được xử lý). Khi tối ưu hóa là cần thiết và quan trọng, đặc biệt là khi có xu hướng tăng dữ liệu, hãy tập trung cải thiện độ phức tạp thuật toán Big-O thay vì những tối ưu hóa vi mô như tiết kiệm một hai phép cộng chẳng hạn.

Thảo luận

Mục này minh họa sự cân bằng quan trọng giữa hai quan điểm: “không tối ưu hóa quá sớm” (xem mục 8) và “không làm giảm hiệu suất quá sớm” (xem mục 9). Điều này khiến nội dung này trở nên khó viết, vì dễ bị hiểu lầm là “tối ưu hóa sớm”. Nhưng không phải như vậy!

Bối cảnh và động lực: Dung lượng bộ nhớ và ổ đĩa tiếp tục tăng theo cấp số nhân; ví dụ, từ năm 1988 đến 2004, dung lượng ổ đĩa tăng khoảng 112% mỗi năm (tăng gần 1.900 lần mỗi thập kỷ), trong khi Định luật Moore về mực độ tích hợp Transistor trong ngành bán dẫn chỉ đạt 59% mỗi năm (tăng 100 lần mỗi thập kỷ). Một hậu quả rõ ràng là: bất kỳ điều gì mã của bạn làm hôm nay, ngày mai có thể phải làm với nhiều dữ liệu hơn—rất nhiều dữ liệu hơn.
Một thuật toán có hành vi tiệm cận tệ (tệ hơn O(N)) sẽ sớm hay muộn khiến ngay cả hệ thống mạnh nhất cũng sụp đổ: Chỉ cần đưa vào đủ dữ liệu.

Để bảo vệ trước tương lai đó, chúng ta cần tránh “thiết kế sẵn” những điểm tụt hiệu suất khi phải xử lý: Các tệp lớn hơn (larger files), cơ sở dữ liệu lớn hơn (larger databases), nhiều pixel hơn (more pixels, ví dụ trong đồ họa), nhiều cửa sổ hơn (more windows, ví dụ trong giao diện người dùng), nhiều tiến trình hơn (more processes), nhiều dữ liệu truyền qua mạng hơn (more bits sent over the wire). Những điều này làm tăng khối lượng công việc cho chương trình và có thể khiến nó hoạt động chậm hoặc thậm chí không thể vận hành, đặc biệt nếu chương trình không được thiết kế để mở rộng quy mô (scalability) từ đầu. Một trong những yếu tố quan trọng làm nên thành công của thư viện chuẩn C++ (C++ Standard Library) trong việc “bảo vệ tương lai” chính là các đảm bảo về độ phức tạp hiệu suất (performance complexity guarantees) của các Container STL và Container thuật toán. Các Container như std::vector, std::map, std::set...std::sort, std::find…đều được thiết kế để hoạt động tốt ngay cả khi lượng dữ liệu tăng lên đáng kể; chúng cũng đảm bảo rằng các phép toán cơ bản như thêm, xóa, tìm kiếm, và sắp xếp đều có độ phức tạp rõ ràng và dự đoán được, ví dụ thao tác thêm vào std::vector thường có độ phức tạp trung bình là O(1), sắp xếp bằng std::sort có độ phức tạp O(N log N).

Sự cân bằng: Thật sai lầm khi tối ưu hóa sớm bằng cách sử dụng thuật toán kém rõ ràng với dự đoán rằng lượng dữ liệu lớn sẽ xuất hiện mà thật ra có thể không bao giờ xảy ra. Nhưng cũng rõ ràng là sai lầm khi làm giảm hiệu suất bằng cách phớt lờ độ phức tạp thuật toán Big-O, tức là chi phí tính toán khi số lượng phần tử dữ liệu tăng lên.

Hai lời khuyên cần chú ý:

Thứ nhất, đầu tiên đừng nghĩ ngay về việc liệu lượng dữ liệu đủ lớn nào để gây vấn đề cho một tính toán cụ thể của bạn, mà hãy mặc định tránh sử dụng các thuật toán mở rộng không tốt đối với việc tăng trưởng dữ liệu. Tuy vậy đôi khi chúng ta vẫn phải hy sinh một chút tính mở rộng để ưu tiên cho những trường hợp có lợi ích lớn từ sự rõ ràng, đơn giản trong thuật toán và dễ đọc.
Điều này thường xuyên gây bất ngờ: Bạn viết mười đoạn mã nghĩ rằng chúng sẽ không bao giờ phải xử lý dữ liệu lớn, và chín lần bạn đúng. Nhưng lần thứ mười, bạn sẽ rơi vào “hố sâu hiệu suất”—điều này đã xảy ra với chúng tôi và có thể xảy ra với bạn. Dù cuối cùng bạn có thể sửa lỗi và gửi bản vá cho khách hàng, nhưng tốt hơn là tránh những bối rối và phải làm lại. Vì vậy, nếu như bao gồm cả tính sáng sủa, dễ đọc và toàn bộ các điều kiện là như nhau thì hãy ưu tiên các yếu tố sau đầu tiên và thực hiện chúng:

• Sử dụng dữ liệu linh hoạt, cấp phát động thay cho mảng kích thước cố định. Dùng mảng kích thước “lớn hơn mức lớn nhất mà tôi cần” là một sai lầm lớn về độ chính xác và bảo mật (xem mục 77). Mảng chỉ phù hợp khi kích thước thực sự cố định tại thời gian biên dịch, ví dụ như số lượng ngày trong tuần, số chữ cái Latin.

• Hiểu rõ độ phức tạp thực tế của thuật toán: Cẩn thận với những cạm bẫy tinh vi như thuật toán tưởng chừng tuyến tính nhưng thực tế lại gọi các phép toán tuyến tính khác, khiến thuật toán trở thành bậc hai (O(N²)) (xem mục 81).

• Ưu tiên sử dụng các thuật toán tuyến tính hoặc nhanh hơn nếu có thể:

  • Độ phức tạp O(1) (hằng số), như push_back và tra cứu bảng băm, là hoàn hảo (xem mục 76 và 80).
  • Độ phức tạp O(log N) (logarit), như các thao tác trên set/map hoặc các hàm lower_bound và upper_bound với iterator ngẫu nhiên là tốt (xem mục 76 , 85, 86).
  • Độ phức tạp O(N) (tuyến tính), như vector::insert và for_each, là chấp nhận được (xem mục 76 , 81, 84).

• Cố gắng tránh các thuật toán tệ hơn O(N): Nếu bạn đối mặt với thuật toán O(N log N) hoặc O(N²), hãy dành một số nỗ lực để tìm giải pháp thay thế nhằm tránh tụt dốc hiệu suất nếu lượng dữ liệu tăng đáng kể. Ví dụ, đây là lý do chính mục 81 khuyên sử dụng các hàm thành viên phạm vi (range member functions) thay vì các lời gọi lặp đi lặp lại cho các hàm xử lý từng phần tử (xem mục 81).

• Không bao giờ sử dụng thuật toán bậc mũ (O(2^N)) trừ khi không còn cách nào khác: Hãy tìm kiếm kỹ lưỡng một giải pháp thay thế trước khi chấp nhận thuật toán bậc mũ, vì chỉ cần tăng nhẹ khối lượng dữ liệu cũng có thể gây “sụp đổ hiệu suất” hệ thống.

Thứ hai, sau khi đo đạc cho thấy tối ưu hóa là cần thiết và quan trọng, đặc biệt là khi do dữ liệu tăng trưởng, hãy tập trung cải thiện độ phức tạp Big-O thay vì những tối ưu hóa vi mô như tiết kiệm một hai phép cộng.

Tham khảo