Bài giảng Kĩ thuật lập trình - Bài 7: Tăng hiệu năng chương trình - Trịnh Thành Trung

Trịnh Thành Trung (ThS)
trungtt@soict.hust.edu.vn
Bài 7
TĂNG HIỆU NĂNG 
CHƯƠNG TRÌNH
Nội dung
1. Tổng quan
2. Các nguyên lý cơ bản
3. Một số kỹ thuật tăng hiệu năng chương trình
4. Tinh chỉnh mã nguồn
5. Một số kỹ thuật tinh chỉnh mã nguồn
1.
Tổng quan
Tăng hiệu năng chương trình và tinh chỉnh mã nguồn
Làm thế nào để 
tăng hiệu năng chương trình
▪Giải thuật
▫ Dùng giải thuật tốt nhất có thể
▫ Sau đó hãy nghĩ tới việc tăng tính hiệu quả của code
▫ Ví dụ: Tính tổng của n số tự nhiên kể từ m
void main() {
long n,m,i, sum ;
cout << ‘ vào n ‘ ; cin << n;
cout << ‘ vào m ‘ ; cin << m;
sum =0;
for(i = m ; i < m+n; i++) sum += i;
cout << ‘ Tổng = ‘ <<sum;
}
void main() 
{
long n,m ;
cout << ‘ vào n ‘ ; cin << n;
cout << ‘ vào m ‘ ; cin << m;
cout << ‘ Tổng = ‘ 
<< (m + m+ n) * n / 2.0;
}
Dùng chỉ thị
chương trình dịch
▪ Một số compilers có khả năng tối ưu chương trình
▫ Phân tích sâu mã nguồn và tự động tối ưu hóa
▫ Ví dụ GNU g++ compiler trên Linux/Cygwin cho chương trình
viết bằng C
g++ –O5 –o myprog myprog.c
▫ Có thể cải thiện hiệu năng từ 10% đến 300% 
Tự
tối ưu hóa
▪ Tự thực hiện những cải tiến mà trình dịch không thể
▪ Loại bỏ tất cả những chỗ bất hợp lý trong code
▫ Làm cho chương trình hiệu quả nhất có thể
▪ Có thể phải xem lại khi thấy chương trình chạy chậm
▫ Cần tập trung vào đâu để cải tiến nhanh nhất, tốt nhất?
▪ Xác định nguồn gây kém hiệu quả
▫ Dư thừa tính toán - redundant computation
▫ Chủ yếu
▸Trong các hàm
▸Trong các vòng lặp
2.
Các nguyên tắc cơ bản
tăng hiệu năng chương trình
Quy tắc
cơ bản
▪ Đơn giản hóa Code - Code Simplification 
▪ Đơn giản hóa vấn đề - Problem Simplification 
▪ Không ngừng nghi ngờ - Relentless Suspicion
▪ Liên kết sớm - Early Binding
Quy tắc
tăng tốc độ
Caching
▫Dữ liệu thường dùng
cần phải dễ tiếp cận
nhất, luôn hiện hữu. 
Lazy Evaluation
▫Không tính 1 phần tử
cho đến khi cần để
tránh những sự tính
toán không cần thiết. 
Quy tắc
tăng tốc độ
▪ Có thể tăng tốc độ bằng cách sử dụng thêm bộ nhớ (mảng)
▪ Dùng thêm các dữ liệu có cấu trúc: 
▫ Thời gian cho các phép toán thông dụng có thể giảm bằng cách
sử dụng thêm các cấu trúc dữ liệu với các dữ liệu bổ xung hoặc
bằng cách thay đổi các dữ liệu trong cấu trúc sao cho dễ tiếp cận
hơn. 
▪ Lưu các kết quả được tính trước: 
▫ Thời gian tính toán lại các hàm có thể giảm bớt bằng cách tính
toán hàm chỉ 1 lần và lưu kết quả, những yêu cầu sau này sẽ được
xử lý bằng cách tìm kiếm từ mảng hay danh sách kết quả thay vì
tính lại hàm. 
Quy tắc lặp
Loop rules
▪ Những điểm nóng - Hot spots trong phần lớn các chương 
trình đến từ các vòng lặp:
▪ Đưa Code ra khỏi các vòng lặp: 
▫ Thay vì thực hiện việc tính toán trong mỗi lần lặp, tốt nhất thực 
hiện nó chỉ một lần bên ngoài vòng lặp (nếu được)
▪ Kết hợp các vòng lặp – loop fusion: 
▫ Nếu 2 vòng lặp gần nhau cùng thao tác trên cùng 1 tập hợp các 
phần tử thì cần kết hợp chung vào 1 vòng lặp.
Quy tắc lặp
Loop rules
▪ Kết hợp các phép thử - Combining Tests: 
▫ Trong vòng lặp càng ít kiểm tra càng tốt và tốt nhất chỉ một 
phép thử. LTV có thể phải thay đổi điều kiện kết thúc vòng lặp. 
“Lính gác” hay “Vệ sĩ” là một ví dụ cho quy tắc này.
▪ Loại bỏ Loop :
▫ Với những vòng lặp ngắn thì cần loại bỏ vòng lặp, tránh phải 
thay đổi và kiểm tra điều kiện lặp
Quy tắc hàm
Procedure Rules
▪ Khai báo những hàm ngắn và đơn giản (thường chỉ 1 dòng) 
là inline
▫ Tránh phải thực hiện 4 bước khi hàm được gọi, 
▫ Tránh dùng bộ nhớ stack
Tối ưu mã 
C/C++
▪ Đặt kích thước mảng = 2n
▫ Với mảng, khi tạo chỉ số, trình dịch thực hiện các phép nhân, vì 
vậy, hãy đặt kích thước mảng bằng 2n để phép nhân có thể được 
chuyển thành phép toán dịch chuyển nhanh chóng
▪ Đặt các case trong phạm vi hẹp
▫ Nếu số case trong câu lệnh switch nằm trong phạm vi hẹp, trình 
dịch sẽ biến đổi thành if – else if lồng nhau, và tạo thành 1 bảng 
các chỉ số, như vậy thao tác sẽ nhanh hơn
Tối ưu mã 
C/C++
▪ Đặt các trường hợp thường gặp trong lệnh switch lên đầu
▫ Khi số các trường hợp tuyển chọn là nhiều và tách biệt, trình 
dịch sẽ biến lệnh switch thành các nhóm if – else if lồng nhau. Nếu 
bố trí các case thường gặp lên trên, việc thực hiện sẽ nhanh hơn 
▪ Tái tạo các switch lớn thành các switches lồng nhau
▫ Khi số cases nhiều, hãy chủ động chia chúng thành các switch 
lồng nhau, nhóm 1 gồm những case thường gặp, và nhóm 2 gồm 
những case ít gặp=> kết quả là các phép thử sẽ ít hơn, tốc độ 
nhanh hơn
Ví dụ switch (queue) {case 0: letter = ‘D'; break; 
case 1: letter = ‘H'; break; 
case 2: letter = ‘B'; break; 
case 3: letter = ‘K'; break; 
}
// Hoặc có thể là:
if (queue == 0)
letter = ‘D'; 
else if (queue == 1)
letter = ‘H'; 
else if (queue == 2)
letter = ‘B'; 
else letter = ‘K'; 
static char *classes="DHBK"; 
letter = classes[queue]; 
Tối ưu mã 
C/C++
▪ Minimize local variables 
▫ Các biến cục bộ được cấp phát và khởi tạo khi hàm được gọi, và 
giải phóng khi hàm kết thúc, vì vậy mất thời gian
▪ Khai báo các biến cục bộ trong phạm vi nhỏ nhất
▪ Hạn chế số tham số của hàm 
▪ Với các tham số và giá trị trả về > 4 bytes, hãy dùng tham 
chiếu
Tối ưu mã 
C/C++
▪ Đừng định nghĩa giá trị trả về, nếu không sử dụng void
▪ Lưu ý vị trí của tham chiếu tới code và data 
▫ Các dữ liệu hoặc code được lưu trong bộ nhớ cache để tham
khảo về sau (nếu được). Việc tham khảo từ bộ nhớ cache sẽ
nhanh hơn. Vì vậy mã và dữ liệu được sử dụng cùng nhau thì nên
được đặt với nhau. Điều này với object trong C++ là đương nhiên. 
Với C: Không dùng biến tổng thể, dùng biến cục bộ
Tối ưu mã 
C/C++
▪ Nên dùng int thay vì char hay short (mất thời gian convert), nếu
biết int không âm, hãy dùng unsigned int
▪ Hãy định nghĩa các hàm khởi tạo đơn giản
▪ Thay vì gán, hãy khởi tạo giá trị cho biến
▪ Hãy dùng danh sách khởi tạo trong hàm khởi tạo
Employee::Employee(String name, String designation) { 
m_name = name; 
m_designation = designation; 
}
/* === Optimized Version === */ 
Employee::Employee(String name, String designation): 
m_name(name), m_destignation (designation) { } 
▪ Đừng định nghĩa các hàm ảo tùy hứng: "just in case" virtual 
functions 
▪ Các hàm gồm 1 đến 3 dòng lệnh nên định nghĩa inline 
Sử dụng
bộ nhớ và con trỏ
▪ Con trỏ (pointer) có thể được gọi là một trong những “niềm 
tự hào” của C/C++, tuy nhiên thực tế nó cũng là nguyên nhân 
làm đau đầu cho các LTV, vì hầu hết các trường hợp sụp đổ hệ 
thống, hết bộ nhớ, vi phạm vùng nhớ đều xuất phát từ việc 
sử dụng con trỏ không hợp lý. 
▪ Hạn chế pointer dereference: pointer dereference là thao 
tác gán địa chỉ vùng nhớ dữ liệu cho một con trỏ. Các thao tác 
dereference tốn nhiều thời gian và có thể gây hậu quả nghiêm 
trọng nếu vùng nhớ đích chưa được cấp phát. 
Ví dụ
for (int i = 0; i < max_number; i++)
{
SchoolData->ClassData->StudentData->Array[i] = my_value;
}
Di chuyển pointer dereference ra ngoài vòng lặp
unsigned long *Tmp = SchoolData->ClassData->StudentData-
>Array;
for (int i = 0; i < max_number; i++)
{
Tmp[i] = my_value;
}
Tận dụng đặc tính
xử lý của CPU
▪ Để đảm bảo tốc độ truy xuất tối ưu, các bộ vi xử lý (CPU) 32-
bit hiện nay yêu cầu dữ liệu sắp xếp và tính toán trên bộ nhớ
theo từng offset 4-byte. Yêu cầu này gọi là memory 
alignment. 
▪ Khi biên dịch một đối tượng dữ liệu có kích thước dưới 4-
byte, các trình biên dịch sẽ bổ sung thêm các byte trống để
đảm bảo các dữ liệu được sắp xếp theo đúng quy luật. Việc bổ
sung này có thể làm tăng đáng kể kích thước dữ liệu, đặc biệt
đối với các cấu trúc dữ liệu như structure, class 
Ví dụ 
class Test 
{
bool a;
int c;
int d;
bool b; 
};
Theo nguyên tắc alignment 
4-byte (hai biến “c” và “d” có
kích thước 4 byte), các biến
“a” và “b” chỉ chiếm 1 byte 
và sau các biến này là biến
int chiếm 4 byte, do đó trình
biên dịch sẽ bổ sung 3 byte 
cho mỗi biến này. Kết quả
tính kích thước của lớp Test 
sẽ là 16 byte. 
Ví dụ 
class Test 
{
int c;
int d;
bool a;
bool b;
};
Ta có thể sắp xếp lại các
biến thành viên của lớp Test 
như sau theo chiều giảm
dần kích thước
Khi đó, hai biến “a” và “b” 
chiếm 2 byte, trình biên dịch
chỉ cần bổ sung thêm 2 byte 
sau biến “b” để đảm bảo tính
sắp xếp 4-byte. Kết quả tính
kích thước sau khi sắp xếp
lại class Test sẽ là 12 byte.
Số phẩy động
Floating point
So sánh
x = x / 3.0;
và 
x = x * (1.0/3.0);
▪ dùng float thay vì double
▪ Tránh dùng sin, exp và log (chậm gấp 10 lần *)
▪ Lưu ý : nếu x là float hay double thì : 3 * (x / 3) x
▪ Thứ tự tính toán: (a + b) + c a + (b + c). 
Các quy tắc 
khác
▪ Tránh dùng ++, -- trong biểu thức lặp
▫ VD: while ( n--) {}
▪ Dùng x * 0.5 thay vì x / 2.0. 
▪ x+x+x thay vì x*3
▪ Mảng 1 chiều nhanh hơn mảng nhiều chiều
▪ Tránh dùng đệ quy
3.
Một số kỹ thuật
tăng hiệu năng chương trình
Phạm vi 
hàm & biến
Stack, 
Heap
▪ Khi thực hiện , vùng dữ liệu data segment của 1 chương
trình được chia làm 3 phần
▫ static, stack, và heap data. 
▪ Static: global hay static variables
▪ Stack data:
▫ các biến cục bộ của chương trình con
▸ ví dụ: double_array trong ví dụ trên. 
▪ Heap data:
▫ Dữ liệu được cấp phát động (vd, pchar trong ví dụ trên). 
▫ Dữ liệu này sẽ còn cho đến khi ta giải phóng hoặc khi kết thúc
chương trình.
Phạm vi 
biến
▪ Before
▪ After
float f() 
{ double value = sin(0.25);
//
...
} 
double defaultValue = sin(0.25);
float f() 
{ double value = defaultValue; 
//
...
} 
Biến tĩnh
static
▪ Kiểu dữ liệu Static tham chiếu tới global hay static variables, 
chúng được cấp phát bộ nhớ lần đầu khi hàm được gọi và tồn
tại cho đến lúc kết thúc chương trình.
int int_array[100];
int main() { 
static float float_array[100]; 
double double_array[100]; 
char *pchar;
pchar = new char [100];
/* .... */
return (0); 
}
41
Biến tĩnh
static
▪ Các biến khai báo trong chương trình con được cấp phát bộ 
nhớ khi chương trình con được gọi và chỉ bị loại bỏ khi kết 
thúc chương trình con. 
▪ Khi bạn gọi lại chương trình con, các biến cục bộ lại được 
cấp phát và khởi tạo lại. 
▪ Nếu bạn muốn 1 giá trị vẫn được lưu lại cho đến khi kết thúc 
toàn chương trình, bạn cần khai báo biến cục bộ của chương 
trình con đó là static và khởi tạo cho nó 1 giá trị.
▫ Việc khởi tạo sẽ chỉ thực hiện lần đầu tiên chương trình được 
gọi và giá trị sau khi biến đổi sẽ được lưu cho các lần gọi sau. 
▫ Bằng cách này 1 chương trình con có thể “nhớ” một vài mẩu tin 
sau mỗi lần được gọi. 
▪ Dùng biến Static thay vì Global 
Hàm
inline
▪ Nếu 1 hàm trong C++ chỉ gồm những lệnh đơn giản, không
có for, while... thì có thể khai báo inline.
▫ Inline code sẽ được chèn vào bất cứ chỗ nào hàm được gọi. 
▫ Chương trình lớn hơn
▫ Nhanh hơn (không dùng stack– 4 bước khi 1 hàm được gọi)
Ví dụ
Hàm inline
Ví dụ
#include 
#include 
inline double delta (double a, 
double b) 
{
return sqrt (a*a + b*b); 
} 
void main () { 
double k = 6, m = 9; 
cout << delta (k, m) <<‘\n’;
// tương đương với
cout << sqrt (k*k + m*m) <<‘\n’; 
} 
Macro
#define max(a,b) (a>b?a:b)
▪ Các hàm Inline cũng giống như macros vì cả 2 được khai triển khi
dịch - compile time
▫ macros được khai triển bởi preprocessor, còn inline functions được
truyền bởi compiler. 
▪ Điểm khác biệt:
▫ Inline functions tuân thủ các thủ tục như 1 hàm bình thường.
▫ Inline functions có cùng syntax như các hàm khác, chỉ có điều là có
thêm từ khóa inline khi khai báo hàm.
▫ Các biểu thức truyền như là đối số cho inline functions được tính 1 lần. 
Trong 1 số trường hợp, biểu thức truyền như tham số cho macros có thể
được tính lại nhiều hơn 1 lần. 
▫ Bạn không thể gỡ rối cho macros, nhưng với inline functions thì có thể.
Tính toán
trước giá trị
Tính toán
trước giá trị
▪ Nếu bạn phải tính đi tính lại 1 biểu thức, thì nên tính trước 1 
lần và lưu lại giá trị, rồi dùng giá trị ấy sau này
int f(int i) { 
if (i = 0) {
return i * i - i;
} 
return 0; 
} 
static int values[] = 
{0, 0, 2,3*3-3, ..., 9*9-9};
int f(int i) { 
if (i = 0) { 
return values[i];
}
return 0; 
} 
Ví dụ
Hàm sigmoid
▪ Trong mô phỏng Neural Network người ta thường dùng
hàm có tên sigmoid
▪ Với X dương lớn ta có sigmoid(x)  1
▪ Với x âm “lớn” 
sigmoid (x)  0
48
kx
e
xsigmoid
1
1
)(
Tính Sigmoid
float sigmoid (float x )
{
return 1.0 / (1.0 + exp(-x))
};
ex = 1+x/1!+ x2/2! +  + xn/n! 
kx
e
xsigmoid
1
1
)(
Ví dụ
Hàm sigmoid
▪ Hàm exp(-x) mất rất nhiều thời gian để tính!
▫ Những hàm kiểu này người ta phải dùng khai triển chuỗi
▸Chuỗi Taylor /Maclaurin 
▸Tính tổng các số hạng dạng ((-x)n / n!)
▸Mỗi số hạng lại dùng các phép toán với số chấm động
▪ Các mô phỏng neural network gọi hàm này trăm triệu lần
trong mỗi lần thực hiện.
▪ Chính vì vậy , sigmoid(x) chiếm phần lớn thời gian (khoảng 
70-80%)
Ví dụ
Hàm sigmoid
▪ Thay vì tính hàm mọi lúc
▫ Tính hàm tại N điểm và xây dựng 1 mảng.
▫ Trong mỗi lần gọi sigmoid
▸Tìm giá trị gần nhất của x và kết quả ứng với giá
trị ấy
▸Thực hiện nội suy tuyến tính - linear 
interpolation
sigmoid(x0)x0
sigmoid(x0)x1
sigmoid(x0)x2
sigmoid(x0)x3
sigmoid(x0)x4
sigmoid(x0)x5
sigmoid(x0)x6
sigmoid(x99)x99
.
.
.
Ví dụ
Tính sigmoid
sigmoid(x0)x0
sigmoid(x0)x1
sigmoid(x0)x2
sigmoid(x0)x3
sigmoid(x0)x4
sigmoid(x0)x5
sigmoid(x0)x6
sigmoid(x99)x99
.
.
.
if (x > x99) return (1.0);
if (x <x0) return (0.0);
Ví dụ
Hàm sigmoid
▪ Chọn số các điểm (N = 1000, 10000, v.v.) tùy theo độ chính 
xác mà bạn muốn
▫ Tốn kếm thêm không gian bọ nhớ cho mỗi điểm là 2 float hay 
double tức là 8 – 16 bytes/ điểm
▪ Khởi tạo giá trị cho mảng khi bắt đầu thực hiện
Ví dụ
Hàm sigmoid
▪ Bạn đã biết X0
▫ Tính Delta = X1-X0
▫ Tính Xmax = X0 + N * Delta;
▪ Với X đã cho
▫ Tính i = (X – X0)/Delta;
▸1 phép trừ số thực và 1 phép chia số thực
▫ Tính sigmoid(x)
▸1 phép nhân float và 1 phép cộng float 
Ví dụ
Hàm sigmoid
▪ Nếu dùng exp(x) :
▫ Mỗi lần gọi mất khoảng 300 nanoseconds với 1 máy Pentium 4
tốc độ 2 Ghz.
▪ Dùng tìm kiếm trên mảng và nội suy tuyến tính :
▫ Mỗi lần gọi mất khoảng 30 nanoseconds
▪ Tốc độ tăng gấp 10 lần
▫ Đổi lại phải tốn kếm thêm từ 64K to 640 K bộ nhớ.
Tối ưu hóa
biểu thức
Loại bỏ
biểu thức thông thường
▪ KHÔNG tính cùng một biểu thức nhiều lần!
▪ Một số compilers có thể nhận biết và xử lý.
for (i = 1; i<=10; i++) x += strlen(str); 
Y = 15 + strlen(str); 
len = strlen(str); 
for (i = 1; i<=10; i++) x += len; 
Y = 15 + len; 
Dịch chuyển biểu thức bất biến
ra khỏi vòng lặp
▪ Đừng lặp các biểu thức tính toán không cần thiết
▪ Một số Compilers có thể tự xử lý
for (i =0; i<100;i++)
plot(i, i*sin(d)); 
M = sin(d);
for (i =0; i<100;i++)
plot(i, i*M); 
Sử dụng các
biến đổi số học
▪ Trình dịch không thể tự động xử lý
if (a > sqrt(b))
x = a*a + 3*a + 2
if (a * a > b)
x = (a+1)*(a+2); 
Không dùng các
vòng lặp ngắn
for (i =j; i< j+3;i++)
sum += q*i -i*7;
i = j; 
sum += q*i -i*7; 
i ++; 
sum += q*i -i*7; 
i ++; 
sum += q*i-i*7; 
Biểu thức
điều kiện
Tối ưu các
biểu thức điều kiện
- Đưa các điều kiện có xác suất xảy ra cao nhất, tính toán
nhanh nhất lên đầu biểu thức. 
- Đối với các biểu thức luận lý, ta có thể linh động chuyển các
biểu thức điều kiện đơn giản và xác suất xảy ra cao hơn lên
trước, các điều kiện kiểm tra phức tạp ra sau. 
- Ví dụ: ((A || B ) && C ) => (C && ( A || B )) Vì điều kiện C 
chỉ cần một phép kiểm tra TRUE, trong khi điều kiện (A || B) 
cần đến 2 phép kiểm tra TRUE và một phép OR (||). Như vậy
trong trường hợp C có giá trị FALSE, biểu thức logic này sẽ có
kết quả FALSE và không cần kiểm tra thêm giá trị (A || B). 
Tối ưu các
biểu thức điều kiện
▪ Đối với các biểu thức kiểm tra điều kiện phức tạp, ta có
thể viết đảo ngược bằng cách kiểm tra các giá trị cho kết
quả không thoả trước, giúp tăng tốc độ kiểm tra. 
▪ Ví dụ: Kiểm tra một giá trị thuộc một miền giá trị cho
trước. 
if (p = min && q = min)
{ ... }
else
{ ..... }
=> 
if (p > max || p max || q < min)
{ ... }
else
{ ... }
Tối ưu các
biểu thức điều kiện
▪ (x >= min && x <= max) có thể chuyển thành
(unsigned)(x - min) < (max - min)
▪ fact2_func nhanh hơn, vi phép thử != đơn giản hơn <=
int fact1_func(int n) {
int i, fact = 1;
for (i = 1; i <= n; i++) fact *= i;
return (fact);
}
int fact2_func(int n) {
int i, fact = 1;
for (i = n; i != 0; i--) fact *= i;
return (fact);
}
Lính canh
Sentinels
Lính canh
Sentinels
▪ Tránh những kiểm tra không cần thiết
Ví dụ
char s[100], searchValue;
int pos, tim, size; 
//Gán giá trị cho s, searchValue
size = strlen(s);
pos = 0; 
while (pos < size) && (s[pos] != searchValue) {
pos++;
}
if (pos >= size) tim = 0;
else tim = 1; 
Lính canh
Sentinels
▪ Ý tưởng chung
▫ Đặt giá trị cần tìm vào cuối xâu
▫ Luôn tìm thấy!
▫ Nếu vị trí > size => không tìm thấy !
size = strlen(s);
strcat(s, searchValue);
pos = 0; 
while (s[pos] != searchValue) {
pos++;
}
if (pos >= size) tim = 0 
else tim = 1; 
4.
Tinh chỉnh mã nguồn
Code tuning
Tăng hiệu năng
chương trình
▪ Sau khi áp dụng các kỹ thuật xây dựng chương trình phần
mềm
▪ Chương trình đã có tốc độ đủ nhanh
▫ Không nhất thiết phải quan tâm đến viêc tối ưu hóa hiệu năng
▫ Chỉ cần giữ cho chương trình đơn giản và dễ đọc
▪ Hầu hết các thành phần của 1 chương trình có tốc độ đủ
nhanh
▫ Thường chỉ một phần nhỏ làm cho chương trình chạy chậm
▫ Tối ưu hóa riêng phần này nếu cần
Tăng hiệu năng
chương trình
▪ Các bước làm tăng hiệu năng thực hiện chương trình
▫ Tính toán thời gian thực hiện của các phần khác nhau trong 
chương trình
▫ Xác định các “hot spots” – đoạn mã lệnh đòi hỏi nhiều thời gian 
thực hiện
▫ Tối ưu hóa phần chương trình đòi hỏi nhiều thời gian thực hiện
▫ Lặp lại các bước nếu cần
Tăng hiệu năng
chương trình
▪ Cấu trúc dữ liệu tốt hơn, giải thuật tốt hơn
▫ Cải thiện độ phức tạp tiệm cận (asymptotic complexity)
▸Tìm cách khống chế tỉ lệ giữa số phép toán cần thực hiện và số
lượng các tham số đầu vào
▸Ví dụ: thay giải thuật sắp xếp có độ phức tạp O(n2) bằng giải
thuật có độ phức tạp O(n log n)
▫ Cực kỳ quan trọng khi lượng tham số đầu vào rất lớn
▫ Đòi hỏi LTV phải nắm vững kiến thức về CTDL và giải thuật
Tăng hiệu năng
chương trình
▪ Mã nguồn tốt hơn: viết lại các đoạn lệnh sao cho chúng có 
thể được trình dịch tự động tối ưu hóa và tận dụng tài nguyên 
phần cứng
▫ Cải thiện các yếu tố không thể thay đổi 
▸Ví dụ: Tăng tốc độ tính toán bên trong các vòng lặp: từ 1000n 
thao tác tính toán bên trong vòng lặp xuống còn 10n thao tác tính 
toán
▫ Cực kỳ quan trọng khi 1 phần của chương trình chạy chậm
▫ Đòi hỏi LTV nắm vững kiến thức về phần cứng, trình dịch và quy 
trình thực hiện chương trình
Tinh chỉnh
mã nguồn
▪ Thay đổi mã nguồn đã chạy thông theo hướng hiệu quả hơn 
nữa
▪ Chỉ thay đổi ở phạm vi hẹp, ví dụ như chỉ liên quan đến 1 
chương trình con, 1 tiến trình hay 1 đoạn mã nguồn
▪ Không liên quan đến việc thay đổi thiết kế ở phạm vi rộng, 
nhưng có thể góp phần cải thiện hiệu năng cho từng phần 
trong thiết kế tổng quát
Tinh chỉnh
mã nguồn
▪ Có 3 cách tiếp cận để cải thiện hiệu năng thông qua cải thiện
mã nguồn
▫ Lập hồ sơ mã nguồn (profiling): chỉ ra những đoạn lệnh tiêu tốn
nhiều thời gian thực hiện
▫ Tinh chỉnh mã nguồn (code tuning): tinh chỉnh các đoạn mã
nguồn
▫ Tinh chỉnh có chọn lựa (options tuning): tinh chỉnh thời gian
thực hiện hoặc tài nguyên sử dụng để thực hiện chương trình
Tinh chỉnh
mã nguồn
▪ Khi nào cần cải thiện hiệu năng theo các hướng này
▪ Sau khi đã kiểm tra và gỡ rối chương trình
▫ Không cần tinh chỉnh 1 chương trình chạy chưa đúng
▫ Việc sửa lỗi có thể làm giảm hiệu năng chương trình
▫ Việc tinh chỉnh thường làm cho việc kiểm thử và gỡ rối trở nên
phức tạp
▪ Sau khi đã bàn giao chương trình
▫ Duy trì và cải thiện hiệu năng
▫ Theo dõi việc giảm hiệu năng của chương trình khi đưa vào sử
dụng
Tinh chỉnh mã nguồn và
tăng hiệu năng chương trình
▪ Việc giảm thiểu số dòng lệnh viết bằng 1 NNLT bậc cao
KHÔNG có nghĩa là 
▫ Làm tăng tốc độ chạy chương trình
▫ Làm giảm số lệnh viết bằng ngôn ngữ máy
for (i = 1;i<11;i++) a[i] = i;
a[ 1 ] = 1 ; a[ 2 ] = 2 ;
a[ 3 ] = 3 : a[ 4 ] = 4 ;
a[ 5 ] = 5 ; a[ 6 ] = 6 ;
a[ 7 ] = 7 ; a[ 8 ] = 8 ;
a[ 9 ] = 9 ; a[ 10 ] = 10 ;
Tinh chỉnh mã nguồn và
tăng hiệu năng chương trình
▪ Luôn định lượng được hiệu năng cho các phép toán
▪ Hiệu năng của các phép toán phụ thuộc vào: 
▫ Ngôn ngữ lập trình
▫ Trình dịch / phiên bản sử dụng
▫ Thư viện / phiên bản sử dụng
▫ CPU
▫ Bộ nhớ máy tính
▪ Hiệu năng của việc tinh chỉnh mã nguồn trên các máy khác 
nhau là khác nhau. 
Tinh chỉnh mã nguồn và
tăng hiệu năng chương trình
▪ Một số kỹ thuật viết mã hiệu quả được áp dụng để tinh
chỉnh mã nguồn
▪ Nhưng nhìn chung không nên vừa viết chương trình vừa
tinh chỉnh mã nguồn
▫ Không thể xác định được những nút thắt trong chương trình
trước khi chạy thử toàn bộ chương trình
▫ Việc xác định quá sớm các nút thắt trong chương trình sẽ gây ra 
các nút thắt mới khi chạy thử toàn bộ chương trình
▫ Nếu vừa viết chương trình vừa tìm cách tối ưu mã nguồn, có thể
làm sai lệch mục tiêu của chương trình
5.
Một số kỹ thuật
Tinh chỉnh mã nguồn
Một số kỹ thuật
tinh chỉnh mã nguồn
▪ Tinh chỉnh các biểu thức logic
▪ Tinh chỉnh các vòng lặp
▪ Tinh chỉnh việc biến đổi dữ liệu
▪ Tinh chỉnh các biểu thức
▪ Tinh chỉnh dãy lệnh
▪ Viết lại mã nguồn bằng ngôn ngữ Assembler
Tinh chỉnh các
biểu thức logic
▪ Không kiểm tra khi đã biết kết quả rồi
▫ Initial code
▫ Tuned code
if ( 5 < x ) && ( x < 10 ) .
if ( 5 < x ) 
if ( x < 10 )
.
Tinh chỉnh các
biểu thức logic
▪ Không kiểm tra khi đã biết kết quả rồi
Ví dụ negativeInputFound = False; 
for ( i = 0; i < iCount; i++ ) { 
if ( input[ i ] < 0 ) { 
negativeInputFound = True; 
} 
} 
Dùng break
Tinh chỉnh các
biểu thức logic
▪ Sắp xếp thứ tự các phép kiểm tra theo tần suất xảy ra kết 
quả đúng
▫ Initial code Select inputCharacter
Case "+", "=" 
ProcessMathSymbol( inputCharacter ) 
Case "0" To "9" 
ProcessDigit( inputCharacter ) 
Case ",", ".", ":", ";", "!", "?" 
ProcessPunctuation( inputCharacter ) 
Case " " 
ProcessSpace( inputCharacter ) 
Case "A" To "Z", "a" To "z" 
ProcessAlpha( inputCharacter ) 
Case Else
ProcessError( inputCharacter ) 
End Select 
Tinh chỉnh các
biểu thức logic
▪ Sắp xếp thứ tự các phép
kiểm tra theo tần suất xảy
ra kết quả đúng
▫ Tuned code
Select inputCharacter
Case "A" To "Z", "a" To "z" 
ProcessAlpha( inputCharacter ) 
Case " " 
ProcessSpace( inputCharacter ) 
Case ",", ".", ":", ";", "!", "?" 
ProcessPunctuation( inputCharacter ) 
Case "0" To "9" 
ProcessDigit( inputCharacter ) 
Case "+", "=" 
ProcessMathSymbol( inputCharacter ) 
Case Else
ProcessError( inputCharacter ) 
End Select 
Tinh chỉnh các
biểu thức logic
▪ Sắp xếp thứ tự các phép kiểm tra theo tần suất xảy ra kết 
quả đúng
▫ Tuned code: chuyển lệnh switch thành các lệnh if - then - else
Tinh chỉnh các
biểu thức logic
▪ So sánh hiệu năng của các lệnh có cấu trúc tương đương
Tinh chỉnh các
biểu thức logic
▪ Thay thế các biểu thức logic phức tạp bằng bảng tìm kiếm 
kết quả
if ( ( a && !c ) || ( a && b && c ) ) { 
category = 1; 
} 
else if ( ( b && !a ) || ( a && c && !b 
) ) { 
category = 2; 
} 
else if ( c && !a && !b ) { 
category = 3; 
} 
else { 
category = 0; 
} Initial code
Tinh chỉnh các
biểu thức logic
▪ Thay thế các biểu thức logic phức tạp bằng bảng tìm kiếm 
kết quả
// define categoryTable 
static int categoryTable[2][2][2] = { 
// !b!c !bc b!c bc 
0, 3, 2, 2, // !a 
1, 2, 1, 1 // a 
}; 
... 
category = categoryTable[ a ][ b ][ c ];Tuned code
Tinh chỉnh các
vòng lặp
▪ Loại bỏ bớt việc kiểm tra điều kiện bên trong vòng lặp
▫ Initial code for ( i = 0; i < count; i++ ) { 
if ( sumType == SUMTYPE_NET ) { 
netSum = netSum + amount[ i ]; 
} 
else { 
grossSum = grossSum + amount[ i ]; 
} 
} 
Tinh chỉnh các
vòng lặp
▪ Loại bỏ bớt việc kiểm
tra điều kiện bên trong
vòng lặp
▫ Tuned code
if ( sumType == SUMTYPE_NET ) { 
for ( i = 0; i < count; i++ ) { 
netSum = netSum + amount[ i ]; 
} 
} 
else { 
for ( i = 0; i < count; i++ ) { 
grossSum = grossSum + amount[ i ]; 
} 
} 
Tinh chỉnh các
vòng lặp
▪ Nếu các vòng lặp lồng nhau, đặt vòng lặp xử lý nhiều công
việc hơn bên trong
▫ Initial code
▫ Tuned code
for ( column = 0; column < 100; column++ ) 
{ 
for ( row = 0; row < 5; row++ ) { 
sum = sum + table[ row ][ column ]; 
} 
}
for (row = 0; row < 5; row++ ) { 
for (column = 0; column < 100; column++) { 
sum = sum + table[ row ][ column ]; 
} 
}
Tinh chỉnh các
vòng lặp
▪ Một số kỹ thuật viết các lệnh lặp hiệu quả đã học
▫ Ghép các vòng lặp với nhau
▫ Giảm thiểu các phép tính toán bên trong vòng lặp nếu có thể
for (i=0; i<n; i++) {
balance[i] += purchase->allocator->indiv->borrower;
amounttopay[i] = balance[i]*(prime+card)*pcentpay;
}
newamt = purchase->allocator->indiv->borrower;
payrate = (prime+card)*pcentpay;
for (i=0; i<n; i++) {
balance[i] += newamt;
amounttopay[i] = balance[i]*payrate;
}
Tinh chỉnh việc
biến đổi dữ liệu
▪ Một số kỹ thuật viết mã hiệu quả đã học:
▫ Sử dụng kiểu dữ liệu có kích thước nhỏ nếu có thể
▫ Sử dụng mảng có số chiều nhỏ nhất có thể
▫ Đem các phép toán trên mảng ra ngoài vòng lặp nếu có thể
▫ Sử dụng các chỉ số phụ
▫ Sử dụng biến trung gian
▫ Khai báo kích thước mảng = 2n
Tinh chỉnh các
biểu thức
▪ Thay thế phép nhân bằng phép cộng
▪ Thay thế phép lũy thừa bằng phép nhân
▪ Thay việc tính các hàm lượng giác bằng cách gọi các hàm
lượng giác có sẵn
▪ Sử dụng kiểu dữ liệu có kích thước nhỏ nếu có thể
▫ long int int
▫ floating-point fixed-point, int
▫ double-precision single-precision
▪ Thay thế phép nhân đôi / chia đôi số nguyên bằng các toán
tử bit: >
▪ Sử dụng hằng số hợp lý
▪ Tính trước kết quả
▪ Sử dụng biến trung gian
▪ Sử dụng các hàm inline
Viết lại mã nguồn
bằng Assembler
▪ Viết chương trình hoàn chỉnh bằng 1 NNLT bậc cao
▪ Kiểm tra tính chính xác của toàn bộ chương trình
▪ Nếu cần cải thiện hiệu năng thì áp dụng kỹ thuật lập hồ sơ 
mã nguồn để tìm “hot spots” (chỉ khoảng 5 % chương trình
thường chiếm 50% thời gian thực hiện, vì vậy ta có thể 
thường xác định đc 1 mẩu code như là hot spots)
▪ Viết lại những mẩu nhỏ các lệnh bằng assembler để tăng tốc 
độ thực hiện
Tận dụng khả năng
của trình dịch
▪ Trình dịch có thể thực hiện 1 số thao tác tôi ưu hóa tự động
▫ Cấp phát thanh ghi
▫ Lựa chọn lệnh để thực hiện và thứ tự thực hiện lệnh
▫ Loại bỏ 1 số dòng lệnh kém hiệu quả
▪ Nhưng trình dịch không thể tự xác định
▫ Các hiệu ứng phụ (side effect) của hàm hay biểu thức: ngoài việc trả ra
kết quả, việc tính toán có làm thay đổi trạng thái hay có tương tác với
các hàm/biểu thức khác hay không
▫ Hiện tượng nhiều con trỏ trỏ đến cùng 1 vùng nhớ (memory aliasing)
▪ Tinh chỉnh mã nguồn có thể giúp nâng cao hiệu năng
▫ Chạy thử từng đoạn chương trình để xác định “hot spots”
▫ Đọc lại phần mã viết bằng assembly do trình dịch sản sinh ra
▫ Xem lại mã nguồn để giúp trình dịch làm tốt công việc của nó
Khai thác hiệu quả
phần cứng
▪ Tốc độ của 1 tập lệnh thay đổi khi môi trường thực hiện thay đổi
▪ Dữ liệu trong thanh ghi và bộ nhớ đệm được truy xuất nhanh hơn dữ
liệu trong bộ nhớ chính
▫ Số các thanh ghi và kích thước bộ nhớ đệm của các máy tính khác
nhau
▫ Cần khai thác hiệu quả bộ nhớ theo vị trí không gian và thời gian
▪ Tận dụng các khả năng để song song hóa
▫ Pipelining: giải mã 1 lệnh trong khi thực hiện 1 lệnh khác
▸ Áp dụng cho các đoạn mã nguồn cần thực hiện tuần tự
▫ Superscalar: thực hiện nhiều thao tác trong cùng 1 chu kỳ đồng hồ
(clock cycle)
▸ Áp dụng cho các lệnh có thể thực hiện độc lập
▫ Speculative execution: thực hiện lệnh trước khi biết có đủ điều kiện để
thực hiện nó hay không
Tổng kết
▪ Hãy lập trình một cách thông minh, đừng quá cứng nhắc
▫ Không cần tối ưu 1 chương trình đủ nhanh
▫ Tối ưu hóa chương trình đúng lúc, đúng chỗ
▪ Tăng tốc chương trình
▫ Cấu trúc dữ liệu tốt hơn, giải thuật tốt hơn: hành vi tốt hơn
▫ Các đoạn mã tối ưu: chỉ thay đổi ít
▪ Các kỹ thuật tăng tốc chương trình
▫ Tinh chỉnh mã nguồn theo hướng
▸Giúp đỡ trình dịch 
▸Khai thác khả năng phần cứng
Thanks!
Any questions?
Email me at trungtt@soict.hust.edu.vn
Presentation template by SlidesCarnival