Tối ưu mã nguồn C/C++

Trong lập trình C/C++ hay bất cứ ngôn ngữ nào khác, việc tối ưu mã lệnh để tăng tốc độ xử lý là rất quan trọng. Đặc biệt ứng dụng C/C++ thực hiện ở tầng dưới như tầng service hay tầng driver.

Dưới đây là một số thủ thật giúp tối ưu mã lệnh trong C/C++.

 

Công thức tính mức độ tối ưu

Khi lập trình tối ưu bạn cần nhớ công thức tính sau của Ahmdal (Ahmdal’s Law):

Trong đó:

• func_cost: Tỉ lệ % thời gian thực thi của chương trình sử dụng hàm func.
• func_speedup: Hệ số tăng tốc độ xử lý cho hàm,

Ví dụ: Bạn tối ưu hàm TriangleIntersect(). Hàm này chiếm 40% của chương trình. Sau khi bạn tối ưu, hàm này chạy nhanh gấp đôi. Áp dụng công thức tính như sau:

=> Như vậy ứng dụng của bạn sẽ chạy nhanh thêm 25%.

Theo như công thức này nên tập trung vào tối ưu các hàm/lớp có tần suất sử dụng nhiều

Lập trình đúng rồi mới tối ưu

Đầu tiên bạn phải cài đặt/lập trình đúng trước đã. Sau đó khi bạn biết hàm nào có tần suất gọi nhiều, bạn mới thực hiện tối ưu. Khi tối ưu code bạn cần tìm ra các nút thắt (bottlenecks) để loại bỏ nó. Có nhiều cách để thực hiện việc này:

• Tối ưu mã lệnh
• Cải tiến thuật toán

Nhiều lập trình viên tốt đã nói rằng: Họ thường phải mất ít lần tối ưu trong khi viết code.

Tối ưu các bước nhảy gọi hàm

Các bước nhảy thường rất đắt, trong khi đó các lời gọi hàm yêu cầu hai bước nhảy, thêm vào đó là các thao rác ngăn xếp. Vì thế việc tối ưu gọi hàm là cần thiết.

• Ưu tiên phép lặp hơn là đệ quy. 
• Nên sử dụng các hàm inline cho các các hàm ngắn.
• Nên dịch chuyển các vòng lặp vào trong hàm. Ví dụ đoạn code dưới:
  for(i=0;i<100;i++) DoSomething();
  Nên thay bằng:
  DoSomething() { for(i=0;i<100;i++) { ... } } 

Tối ưu các lệnh rẽ nhánh

• Với lệnh có chuỗi if...else if...else if...else if... dài yêu cầu rất nhiều bước nhảy cho trường hợp ở cuối chuỗi. Trường hợp này nếu có thể hãy chuyển sang câu lệnh switch case, trình dịch sẽ tối ưu hóa bằng một bước nhảy thông qua kỹ thuật tra bảng. Trường hợp không thể chuyển sang lệnh switch, hãy để các điều kiện hay xảy ra ở đầu của chuỗi.

Tối ưu các các vòng lặp

• Cố gắng kết thúc vòng lặp sớm và trả về kết quả sớm. Ví dụ bạn cần cài đặt tìm giao giữa một đường và một tam giác. Trường hợp phổ biến hay xảy ra là đường nằm ngoài tam giác. Vì vậy khi xử lý, bạn phải tối ưu hóa cho trường hợp này, case này nên được xử lý trước để trả về sớm.
• Khi tính toán vòng lặp, trong mỗi vòng lặp xem xét tính toán phần gia tăng thay vì tính lại từ đầu.

Chú ý thứ tự các chỉ số của mảng

• Mảng hai hay nhiều chiều được lưu trữ trong vùng nhớ một chiều. Điều này có nghĩa (Với C/C++), phần tử array[i][j] và array[i][j+1] nằm sát nhau, trong khi phần tử array[i][j] và array[i+1][j] thì ở xa nhau.
• Truy cập dữ liệu theo cách tuần tự trên bộ nhớ giúp đoạn mã của bạn chạy nhanh hơn.
• Với dòng CPU mới, khi tải dữ liệu từ bộ nhớ chính vào bộ nhớ cache, chúng sẽ không chỉ lấy đúng dữ liệu yêu cầu mà sẽ lấy khối dữ liệu chứa dữ liệu yêu cầu (Gọi là một cache line). Điều này có nghĩa là sau khi phần tử array[i][j] nằm trong bộ nhớ cache của CPU, thì phần tử array[i][j+1] có xác xuất ở trong bộ nhớ cache rất cao, trong khi phần tử array[i+ 1][j] thì có thể vẫn đang trong bộ nhớ chính.

Tránh/Giảm số lượng các biến cục bộ

• Các biến cục bộ thường được lưu trữ trong stack. Tuy nhiên, nếu các biến cục bộ đủ ít, chúng có thể được lưu trữ trong các thanh ghi. Trong trường hợp này, các hàm thực thi nhanh hơn do tốc độ truy cập nhanh và hạn chế sử dụng stack.
• Hạn chế khai báo biến cục bộ không cần thiết. Khi khai báo biến cục bộ đối tượng sẽ luôn luôn gọi hàm khởi tạo. Do vậy chỉ khai báo biến khi nào cần sử dụng.

Tối ưu các tham số và giá trị trả về của hàm

• Giảm số lượng tham số của hàm: Các tham số trong hàm cũng được lưu trữ trong stack. Vì thế giảm số lượng tham số của hàm sẽ giúp giảm thao tác lưu trữ trong vùng stack.
• Truyền cấu trúc dữ liệu thông qua tham chiếu, chứ không sử dụng giá trị: Việc này sẽ giúp giảm chi phí sao chép dữ liệu và cũng đồng thời giảm dữ liệu lưu trữ vùng stack.
• Các hàm không cần thiết phải trả về giá trị, thì bạn không cần cài đặt để trả về giá trị.
• Trả về đối tượng hoặc cấu trúc thì nên trả về dạng tham chiếu hoặc con trỏ.

Chú ý khi thao tác với đối tượng C++

• Nên sử dụng hàm khởi tạo thay vì sử dụng phép gán. Ví dụ sử dụng { Color c(black); } sẽ nhanh hơn { Color c; c = black; }
• Tạo các hàm khởi tạo mặc định càng nhẹ càng tốt, vì thường hàm này được gọi rất nhiều, nhiều khi ở những nơi mà bạn không mong muốn. Đặc biệt với các lớp hay sử dụng như Color, Vector, Point...
• Tối ưu cách thức thực hiện khởi tạo.Ví dụ sử dụng khởi tạo dạng { Color::Color() : r(0), g(0), b(0) {} } sẽ nhanh hơn { Color::Color() { r = g = b = 0; } }
• Với các đối tượng sử dụng toán tử tiền tố (++obj) thay cho toán tử hậu tố (obj++). Một bản sao của đối tượng sẽ được tạo khi sử dụng toán tử hậu tố, trong khi toán tử tiền tố thì không cần tạo bản sao.
• Với các lớp, sử dụng toán tử +=, -=, *= và /= thay vì sử dụng toán tử +, -, *, /. Điều này giúp tránh việc tạo nhiều đối tượng trung gian. Ví dụ:
  Vector v = Vector(1,0,0) + Vector(0,1,0) + Vector(0,0,1);
  Thao tác trên sẽ tạo ra 5 đối tượng trung gian gồm: Vector(1,0,0), Vector(0,1,0), Vector(0,0,1), Vector(1,0,0) + Vector(0,1,0), và Vector(1,0,0) +
  Vector(0,1,0) + Vector(0,0,1)
  Tối ưu hơn hãy sử dụng code sau:
   Vector v(1,0,0);
   v+= Vector(0,1,0);
   v+= Vector(0,0,1);
   Chỉ tạo ra hai đối tượng trung gian Vector(0,1,0) và Vector(0,0,1). Tức là giảm 3 đối tượng trung gian, hay sẽ giảm gọi 6 hàm gồm 3 hàm khởi tạo và 3 hàm hủy.
• Cẩn thận khi sử dụng template: Template giúp giảm lặp code đi rất nhiều, nhưng bạn phải biết cách sử dụng để tăng hiệu năng, không thì sẽ khá chậm. Thư viện template chuẩn std là thư viện đã được  tối ưu, nhưng bạn phải cần chú ý khi sử dụng để đạt hiệu năng tối đa. Mặc khác việc debug thư viện template khá chậm.

Tối ưu bộ nhớ

• Tránh cấp phát động khi tính toán:
  • Bộ nhớ động rất hiệu quả cho việc lưu dữ liệu lớn như Scene, Resource,... và các dữ liệu này không thay đổi trong quá trình tính toán.
  • Việc cấp phát dữ liệu trên vùng Heap sẽ mất nhiều chi phí hơn khi cấp phát trên vùng Stack. Vì hệ điều hành cần thực hiện một vài thao tác để tìm vùng nhớ với kích thước cần thiết.
• Tìm và sử dụng thông tin về bộ nhớ cache của hệ thống:
  • Nếu một cấu trúc dữ liệu phù hợp mới một cache line, thì chỉ cần nạp một lần từ bộ nhớ chính để xử lý toàn bộ lớp.
  • Đảm bảo rằng tất cả các dữ liệu được sắp xếp trên 1 cache line. Nếu kích thước dữ liệu của bạn là 128 byte và kích thước 1 cache line là 128 byte thì vẫn có trường hợp hiệu năng không tốt khi 1 byte của bạn trong 1 cache line và 127 byte khác ở trong cache line thứ 2.
• Cẩn thận khi sử dụng các hàm tra bảng (table-lookup functions):
  • Nhiều người khuyến khích sử dụng các bảng giá trị được tính trước cho các hàm phức tạp. Ví dụ như các hàm lượng giác. Với các hàm phức tạp, kỹ thuật bảng tra giúp tăng tốc độ chương trình nên khá nhiều.
  • Nhưng trong nhiều trường hợp thì điều này là không cần thiết và gây tốn bộ nhớ, nhưng trong nhiều trường hợp thì nó lại hữu ích. Trong lập trình GPU, bảng tra rất hay được sử dụng cho các hàm phức tạp.

Tính toán số nguyên và số thực

Sự khác biệt giữa tính toán trên số nguyên (integer), dấu phẩy tĩnh (fixed point), dấu phẩy động 32-bit (32-bit float), và dấu phẩy động  64 bit (64-bit double) không lớn như bạn nghĩ. Trên các CPU hiện đại, các phép toán dấu phẩy động (floating point) về cơ bản giống với phép tính trên số nguyên. Các thao tác với dấu phẩy động độ chính xác kép (Double precision floating-point) không chậm hơn so với tính toán số dấu phẩy động => Vì thế bạn không cần thiết phải quá đau đầu trong việc tìm cách tối ưu bằng cách chuyển về trên tính toán số nguyên.

Tối ưu về mặt toán học

• Đơn giản hóa phương trình trên giấy trước khi thực hiện cài đặt => Việc cài đặt chỉ thực hiện trên phương trình đã đơn giản hóa, qua đó cải thiện nhiều hiệu năng.
• Bạn có thể tránh được sử dụng sqrtkhi so sánh bằng cách thay thế bằng phép toán bình phương. Ví dụ thay vì so sánh { if (sqrt(a)<b) { ... } } thì bạn có thể chuyển thành { if (a<b*b) { ... } } để tối ưu.

Chú ý một số thao tác khác hay dùng trong C/C++

• Cố gắng tránh ép kiểu ở bất cứ nơi nào có thể: Các chỉ lệnh với số nguyên và số thực thường hoạt động trên các thanh ghi khác nhau, vì thế ép kiểu sẽ tạo ra một thao tác copy. Các kiểu như char và short vẫn yêu cầu sử dụng toàn bộ kích thước của thanh ghi. Do đó chúng sẽ được padding khi đưa vào thành ghi và convert ngược lại thành kích thước nhỏ hơn khi lưu trữ ngược trở lại bộ nhớ. Vì thế, khi dùng kiểu này nên xem xét xem có chuyển sang sử dụng kiểu int luôn không.
• Sử dụng toán tử dịch bit <<, >> cho các thao tác nhân chia số nguyên bất cứ khi nào có thể
• Với các kiểu cơ bản sử dụng toán tử + , - , * , và / thay vì toán tử += , -= , *= , và /=
• Tránh khởi tạo dữ liệu không cần thiết. Trong trường hợp cần khởi tạo, với dữ liệu lớn nên sử dụng hàm memset