Thần chú giúp code chạy nhanh hơn theo nghĩa đen

Nguyễn Hoàng Sơn 2021-12-21 5:14:26

Trong Hội trại mùa xuân JOI 2018, một thiên tài trẻ tuổi nhật bản QCFium, đã viết một thuật toán O(NQ) ngây thơ trong bài Examination và đạt điểm tuyệt đối. Code như sau:

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//Naive Solution as follows...

Thực tế, ngay cả N, Q≤100.000 , với 3 dòng ma thuật trên, độ phức tạp O(NQ) với thuật toán ngây thơ đã thực sự AC. Để kiểm tra xem việc tăng tốc này có thực sự hiệu quả hay không, tôi đã viết hai code sau: một code dùng ma thuật và một code không như bên dưới

Code A (With speedup)

#include <iostream>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int cnt = 0;

int main() {
	for (int i = 1; i <= 30000; i++) {
		for (int j = 1; j <= 30000; j++) {
			if (i % j <= 10) cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

Code B (Without speedup)

#include <iostream>
using namespace std;

int cnt = 0;

int main() {
	for (int i = 1; i <= 30000; i++) {
		for (int j = 1; j <= 30000; j++) {
			if (i % j <= 10) cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

Khi tôi kiểm tra 2 code trên Codeforces thì kết quả là: code A sử dụng 2074ms nhưng code B sử dụng 2292ms. code A nhanh hơn ~10,5%. Thực tế trùm code Nhật Bản QCFium đã nói rằng "Code càng đơn giản thì càng nhanh với ma thuật 3 dòng tăng tốc." Vì vậy, có thể là khi dùng 3 dòng ma thuật trên, tốc độ tính toán tăng thành x1,2 hoặc x1,5.

Cảm ơn bạn đã đọc topic, hãy cho mình biết ý kiến của bạn phía dưới nhé ^_^

Tổng cộng 2 trả lời

Nguyễn Hoàng Sơn

Em cũng chưa gặp được bài nào trong thực tế mà sử dụng trâu với 3 dòng trên mà AC được Có lẽ tỉ lệ thật hiếm đáng kinh ngạc khi gặp được một bài như này trong một cuộc thi lớn như JOI, và ông QCFium kia thì thích chơi trội ¯_(ツ)_/¯

Chùm CUỐI

Thực ra, cái nhanh hơn ở đây (10-20%) là do cách trình biên dịch tối ưu hóa theo chỉ thị biên dịch thôi.

Trên các trang chấm bài sẽ để tham số biên dịch cố định, cí dụ như trang này C++ sử dụng trình biên dịch clang++ hoặc g++, tham số biên dịch:

clang++/g++ source_file.cpp -o exec_file -O2 -lm -DONLINE_JUDGE -mx32 -std=c++03;

(đối với C++ 11 và C++ 17, thay thế -std= số tương ứng)

Ta có thể thấy mặc định, chỉ thị biên dịch tối ưu là O2.

3 dòng "thần chú" ở trên:

#pragma GCC target ("avx2")

Cái này có lẽ là tần dụng sức mạnh phần cứng (avx2) để tăng tốc các phép toán số học và xử lí bit

#pragma GCC optimization ("O3")

Là chỉ thị biên dịch tối ưu thành O3

#pragma GCC optimization ("unroll-loops")

Chỉ thị này có lẽ tối ưu hóa các vòng lặp gì đó

Và như vậy, về cơ bản các dòng "thần chú" này là các chỉ thị tối ưu cho việc biên dịch mã nguồn, tăng tốc được khoảng 10-20%.

Việc tăng 10-20% tốc độ thực thi nhưng việc biên dịch sẽ chậm hơn. Và trong lập trình thi đấu thì tăng khoảng 10% tốc độ cũng không có nhiều ý nghĩa.