vi
new
Avatar
Aisha
Yêu cầu thg 5 17, 2019 7:12 CH
Yêu cầu thg 5 17, 2019 7:12 CH• 333 0 1
  • 333 0 1
+3

Optimize trong GNU

Recursive Function
Chia sẻ
  • 333 0 1

Khi thực hiện tính dãy Fibonacci bằng C, mình viết như sau:

long int Fibonacci(long int index) {
    if (index <= 1) return index;
    return Fibonacci(index - 1) + Fibonacci(index - 2);
}

Khi thực hiện ở optimize Os, nó vẫn gọi đệ quy rất nhiều lần. Tuy nhiên khi viết kiểu đưa lên tham số:

long int Fibonacci(long int index, long int first, long int second) {
    if (index == 0) return first;
    return Fibonacci(index - 1, second, first + second);
}

Biên dịch ra file Assembly ở mode Os nhận được một vòng lặp thông thường:

_Fibonacci:
LFB0:
	movq	%rsi, %rax
L3:
	testq	%rdi, %rdi
	je	L4
	leaq	(%rax,%rdx), %rcx
	decq	%rdi
	movq	%rdx, %rax
	movq	%rcx, %rdx
	jmp	L3
L4:
	ret

Tương tự với hàm sumArray với hai cách viết như sau:

long int sumArray(long int* seq, long int size) {
    if (size == 1) return *seq;
    return sumArray(seq, 1) + sumArray(seq + 1, size - 1);
}

long int sumArray(long int* seq, long int size) {
    if (size == 0) return 0;
    return *seq + sumArray(seq + 1, size - 1);
}

Hàm ở trên gọi đệ quy, nhưng hàm ở dưới thì chỉ là vòng lặp. Việc tương tự cũng xảy ra với một hàm phức tạp hơn:

#include <stdlib.h>

struct node {
    int data;
    struct node* next;
};

int deallocate(struct node* List) {
    if (List->next != NULL) {
        struct node* temp = List->next;
        free(List);
        return deallocate(temp);
    }
    return 0;
}

File Assembly là:

_deallocate:
LFB3:
	pushq	%rbx
LCFI0:
L3:
	movq	8(%rdi), %rbx
	testq	%rbx, %rbx
	je	L2
	call	_free
	movq	%rbx, %rdi
	jmp	L3
L2:
	xorl	%eax, %eax
	popq	%rbx
LCFI1:
	ret

Và nó chẳng đệ quy chút nào cả. Vậy cho em hỏi có phải khi gọi đệ quy, mà giá trị trả chỉ liên quan đến một giá trị đệ quy thì trình dịch sẽ tự động tạo vòng lặp phải không ạ?

Avatar
Aisha @AmagaiAisha
333 11 2 0
Thêm một bình luận

1 CÂU TRẢ LỜI

Avatar
Ndaadn
Đã trả lời thg 5 18, 2019 6:01 SA
Đã trả lời thg 5 18, 2019 6:01 SA
Đã được chấp nhận
+10

Hiếm khi gặp được bác nào tìm hiểu sâu đến mức compile xong xem cả Assembly code 😄 Mình vốn cũng không hiểu sâu về việc Optimize của compiler lắm nhưng đọc được câu hỏi này thì có hứng thú tìm hiểu 😄

Đầu tiên là về flag Os:

-Os Optimize for size. -Os enables all -O2 optimizations except those that often increase code size:
-falign-functions -falign-jumps
-falign-labels -falign-loops
-fprefetch-loop-arrays -freorder-blocks-algorithm=stc
It also enables -finline-functions, causes the compiler to tune for code size rather than execution speed, and performs further optimizations designed to reduce code size.

Có nghĩa là flag -Os sẽ bằng flag -O2 cộng thêm các flag tối ưu khác. Ctrl + F lên flag -O2 nội dung như sau:

-O2
Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff. As compared to -O, this option increases both compilation time and the performance of the generated code.
-O2 turns on all optimization flags specified by -O. It also turns on the following optimization flags:
.....
-foptimize-sibling-calls
.....

Vậy là flag -O2 bao gồm flag -O và thêm rất nhiều flag optimize khác của compiler. Và để ý flag -foptimize-sibling-calls trên.

-foptimize-sibling-calls
Optimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.

Tức là nó sẽ tối ưu sibling (sibling là lời gọi đệ quy chéo, tức là 2 hàm gọi đệ quy lẫn nhau) và các lời gọi đệ quy đuôi.
Có nhiều cách phân loại kiểu đệ quy, nhưng thường sẽ phân loại là đệ quy đuôi (tail-recursion) và đệ quy không phải là đệ quy đuôi (non tail-recursion) hay gọi đơn giản là đệ quy thường.

  • Đệ quy đuôi là hàm đệ quy mà lệnh gọi đệ quy là lệnh cuối cùng được gọi của hàm.

Đệ quy đuôi có dạng như thế này (mình viết psuedo code thôi, hy vọng dễ hiểu):

P(U):
begin
    if C then 
             D
             P(a(U))
    else
            T
    endif
end
  • Với U là danh sách tham số.
  • C là biểu thức điều kiện nào đó.
  • D là các câu lệnh xử lý cơ bản nào đó.
  • a(U) là một sự chuyển đổi tham số nào đó, ví dụ như ở hàm Fibonacci: Fibonacci(index - 1, second, first + second) thì a(U) là index-1, second, first+second chẳng hạn.
  • T là xử lý dừng, tức là câu lệnh return.

Đệ quy đuôi có thể tối ưu bằng cách khử đệ quy thành vòng lặp. Dạng hàm sau khi khử đệ quy đuôi của hàm trên như sau:

P2(U):
begin
     while C do
            D
            U = a(U)
     endwhile
     T
end

Ví dụ hàm Fibonacci trong câu hỏi là một dạng đệ quy đuôi:

long int Fibonacci(long int index, long int first, long int second) {
    if (index == 0) return first;
    return Fibonacci(index - 1, second, first + second);
}

Khi khử đệ quy nó sẽ có dạng giống như tính bằng vòng lặp:

long int Fibonacci(long int index, long int first, long int second) {
    while(index != 0) {
        index = index - 1;
        first = second;
        second = first + second
    }    
    return second;
}

Đệ quy thường có dạng như thế này:

Q(U):
begin
    if C then
        D1(U)
        Q(a(U))
        D2(U)
    else
        T
    endif
end

Khử đệ quy cần phải dùng thêm Stack S:

Q2(U):
begin
    create(S)
    while C do
        D1(U)
        push(S, U)
        U = a(U)
    endwhile
    T
    while not isempty(S) do
        U = top(S)
        D2(U)
        pop(S)
    endwhile
end

======================================================================
Phần trên là về lý thuyết. Còn đây là suy nghĩ của mình, đối với đệ quy đuôi, việc khử đệ quy thành vòng lặp giúp tối ưu chương trình bằng cách bỏ bớt việc tạo stack. Còn với kiểu đệ quy thường, việc khử đệ quy thành vòng lặp vẫn cần phải tạo Stack để lưu trữ, vậy nên sẽ không có nhiều ý nghĩa tối ưu. Nên khi thêm flag -Os vào lệnh compile, nó sẽ tối ưu cho đệ quy đuôi bằng cách khử đệ quy thành vòng lặp. Các ví dụ trong câu hỏi có dạng đệ quy đuôi đều được tối ưu bằng cách khử đệ quy. Riêng trường hợp

long int sumArray(long int* seq, long int size) {
    if (size == 0) return 0;
    return *seq + sumArray(seq + 1, size - 1);
}

Theo định nghĩa trường hợp này không phải là đệ quy đuôi, vì thực chất lời gọi đệ quy không phải là bước thực hiện cuối cùng của hàm. Thực tế hàm này có dạng như thế này:

long int sumArray(long int* seq, long int size) {
    if (size == 0) return 0;
    long int k = sumArray(seq + 1, size - 1);
    return *seq + k;
}

Vậy nên câu trả lời cho câu hỏi sẽ là, với flag -O2 trở lên, compiler sẽ thực hiện tối ưu khử đệ quy thành vòng lặp cho các lời gọi đệ quy đuôi và đệ quy chéo (bài viết mình không nói về đệ quy chéo nhưng bác có thể tự tìm kiếm dễ dàng bằng google).

Nên nó không phải là đệ quy đuôi! Có thể xem về ví dụ dễ nhầm lẫn này ở link sau: https://stackoverflow.com/questions/310974/what-is-tail-call-optimization

Và câu trả lời về việc GCC hay G++ có tối ưu đệ quy đuôi hay không ở link sau: https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization

Chia sẻ
Avatar
Ndaadn @ndaand
80 2 0 1
Avatar Aisha @AmagaiAisha
•
thg 5 18, 2019 7:29 CH

Em đã test và nó hoàn toàn chính xác luôn anh 😄 Em mới test thử deallocate một cây nhị phân bằng đệ quy theo kiểu này và kết quả rất tốt, tạo vòng lặp trong mã nguồn và không đệ quy:

#include <stdlib.h>

struct node {
    int data;
    struct node* left;
    struct node* right;
};

void deallocate(struct node* first, struct node* second) {
    if (first->left != NULL) {
        struct node* _first = first->left;
        first->left = second;
        return deallocate(_first, first);
    } else if (first->right != NULL) {
        struct node* _first = first->right;
        first->left = second;
        first->right = NULL;
        return deallocate(_first, first);
    }
    free(first);
    if (second == NULL)
        return;
    else
        return deallocate(second, NULL);
}

Em nghĩ là nếu mình lợi dùng đặc điểm tối ưu hóa đệ quy này thì mình có thể viết một hàm đơn giản bằng đệ quy, nhưng hiệu năng và bộ nhớ thì tương tự như vòng lặp được.

Thêm một bình luận
Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí