Great code 독후감 - 5~6장
5~6장은 별다른 내용이 없습니다.
사실 점점 내용이 부실해지는게 아닌가 하는 생각이 듭니다.
그런데 이 책에서 던져주는 질문은 많은 것 같습니다.
설명이 없고 그런게 있다라고만 던져주는 주제들이 있어서
그 주제들을 찾아서 공부하는 방식으로 읽고 있습니다.
책을 대충써줘서 찾아서 공부하는 습관이 생기도록 해주었다..무슨 대륙의 기상 시리즈 같네요.
아직 7장을 읽고 있기 때문에 책 전체에 대한 평가는 못하겠습니다만
아직까지는 약간 아리송합니다.
아참. 이 자료는 어셈러브 오프라인 스터디를 위해서 만든 자료입니다.
격주로 스터디를 하기 때문에 2주간 제가 읽은 범위에 대해서
독후감을 쓰고, 발표를 하게 됩니다.
스터디 안내는 http://www.asmlove.co.kr 에 공지 게시판에 있습니다.
====================================================
5장
- 최적화의 정의
만약 다음과 같은 코드가 있다면
i <- 5
j <- i
k <- j
m = m + k
다음과 같은 코드로 최적화 된다.
k <- 5
m = m + k
이것은 i, j 변수를 없애는 공간의 최적화이면서 동시에 연산 갯수를 줄이는 속도의 최적화이다.
(공간과 속도를 동시에 최적화할 수 있는가에 대한 문제는 안드로메다에 잠시 보내자.)
- 최적화가 컴파일 시간에 미치는 영향
최적화 문제는 복잡도 이론에서 말하는 NP-complete (Non-deterministic Polynomial time)이다!!
(P 문제 : 답을 구하기 위해 시행되는 연산의 수가 입력 길이에 대한 다항식으로 결정되는 알고리즘을 다항시간 알고리즘이라 부르고, 다항시간 알고리즘이 존재하는 문제의 집합을 P 라고 나타낸다. 정렬이나 탐색 알고리즘들은 Big-O 표기법으로 나타낼 수 있는 것들이 있고, 이것들은 P 집합에 속한다. 물론 이론적으로 계산 시간을 예측할 수 있다는 것이지 실제로 동작할 때 짧은 시간에 끝난다는 것은 아니다.)
(하오이의 탑 문제: 이 문제는 T(n) = 2^n - 1 이라는 식으로 나타낼 수 있다. 이것은 연산의 길이가 이론적으로는 입력 길이에 대한 다항식으로 결정되므로 P 문제이지만 사실상 입력에 비해 기하급수적으로 연산 시간이 늘어난다. 하지만 이것도 연산 시간이 결정되는 문제이다.)
(도저히 판정될 수 없는, 즉 그 답을 구할 수 없는 문제를 NP 문제라고 한다. 그 예가 Hilbert의 열번째 문제이다. 일반 정수방정식 p(x1, ... , xn) = 0 이 정수해를 가지는 지를 판정할 수 있는 알고리즘이 존재하는가에 대한 문제인데 판정할 수 없다는 것이 밝혀졌다. 문제가 풀리고 안풀리고는 둘째치고 이것이 해답이 존재할 수 있는가에 대한 판정도 할 수 없다. 해가 존재할 것인가? 그러면 그 해는 유일한 것인가?
시간적 복잡성, NP 문제 등에 대한 기본 개념 : http://jubilate.tistory.com/43?srchid=BR1http%3A%2F%2Fjubilate.tistory.com%2F43)
컴파일러가 최적화를 하기 위해 코드를 분석하는 연산은 NP 문제에 속한다.
(각 명령에 레지스터를 할당하는 문제, 명령어의 순서를 어떻게 배열하는 것이 가장 효율적인지를 찾아내는 문제 등 다양한 컴파일러 문제들은 어떻게보면 존재론적인 문제이기도 하다. 가장 먼저 최적의 혹은 효율적인 코드란 무엇인가에 대한 문제가 생긴다. 컴파일러가 최적화를 해서 출력할 최종 결과물이 어떤 모습이어야 하는가에 대한 존재성과 유일성에 대한 문제가 생긴다. 나는 나비인가 나비꿈을 꾸는 장자인가?
http://minjang.egloos.com/1389165
http://cyberyanne.tistory.com/category/%EC%BB%B4%ED%8C%8C%EC%9D%BC%EB%9F%AC)
컴파일러의 최적화 툴은 단지 사용자가 최적화 작업에 기꺼이 투잘할만한 시간동안에 얻을 수 있는 최선의 결과를 목표로 한다. 몇줄의 코드를 최적화하기 위해서 몇시간의 컴파일 시간이 필요하다면 경제적으로 불필요한 작업이 될 것이다.
현대의 최적화 도구는 모든 경우의 수를 보아 최선의 결과를 고르는 것이 아니라. 휴리스틱과 상황별 알고리즘을 사용해서 기계 코드를 출력한다. 따라서 어떤 상황이나 조건에서 최적화 도구가 동작하는지를 알아야 한다.
- 기본 블록 단위의 최적화
컴파일러의 최적화 도구는 코드 분석을 할 때 프로그램의 실행 순서에 따라 변수 값을 추적한다. 이렇게 변수의 값을 추적하는 것을 데이터 흐름 분석이라고 한다. 데이터 흐름 분석 과정에서 어떤 변수가 초기화되지 않고 사용되는지 혹은 더이상 사용되지 않는지, 어떤 값이 대입되는 시점과 언제까지 사용되는지 등을 조사한다.
path = 5;
if (i == 2) printf("Path = %d\n", path);
i = path + 1;
if (i < 20) {
path = path + 1;
i = 0;
}
이 코드의 변수 값을 조사하면 다음과 같은 코드와 동치가 됨을 알 수 있다.
if (i ==2 ) printf("Path = %d\n", 5);
i = 0;
path = 6;
컴파일 시 최적화 과정에 들어가는 시간을 결정하는 것은 프로그램의 한 부분에서 성능 개선점을 최대한 얼마나 많이 찾아내는지에 달려있다. 따라서 컴파일러를 혼동시키는 프로그래밍 스타일을 사용한다면 컴파일러가 고려할 사항이 너무 많아져서 좋은 최적화를 할 수 없어진다.
(이런 컴파일러의 특성 때문에 volatile 이라는 변수 속성이 나온 것 같다. 만약 위의 코드에서 path 가 특정 하드웨어 레지스터의 값이라면, 이런 최적화는 오히려 프로그램을 파괴하는 것이다. 임베디드 프로그래밍에서 이미 보편화된 개념이지만 다시 한번 생각해보면
char *path = 0x80000000; (Memory mapped 하드웨어 레지스터의 주소)
*path = 0;
usleep(10000); (여기서 *path의 값이 0이 아닌 다른 값이 될 수 있다)
while (*path != 0x0) printf("WAIT\n");
이런 코드가 있을 때 컴파일러의 최적화 툴은 while 절을 없애버릴 수도 있다. 이것을 막기 위해
volatile char *path = 0x80000000;
이렇게 volatile 선언을 사용해야 한다.)
다음은 코드를 기본 블럭으로 나누는 예제이다.
----------------------
x=2;
j=5;
i=(f&x, j);
j=i*2+j;
----------------------
if (j < 10)
{
j=0;
i = i+10;
x=x+i;
------------------
} else
temp = i;
i = jl
j = j+x;
x = temp;
}
------------------
x=x*2;
++i;
--j;
조건분기/점프, 호출명령, 무조건 점프 명령이 기본 블럭의 마지막 문장이 된다. goto나 setjmp 등의 특이한 분기 방법을 사용하면 최적화가 어려워지며, 최적화 작업의 시작이 오래 걸린다.
좋은 흐름 그래프를 가지는 프로그램은 축소 가능해지며 더 좋은 최적화를 할 수 있다.
(축소 가능에 대한 설명이 없어서 이해할 수 없음)
(그 외에 오브젝트 파일의 구조에 대해서 나오지만 프로그램이 코드/데이터 섹션으로 나눠진다는 것만 이해하면 될만한 내용임)
- 공간 최적화를 하는 이유
메모리는 4K단위로 접근되므로 프로그램의 각 섹션들은 최소 하나의 메모리 프레임에 저장된다. 메모리 프레임 단위로 실행 가능이나 쓰기 가능 속성이 지정되므로 다른 섹션이 하나의 프레임에 같이 저장될 수는 없기 때문이다. 따라서 프로그램을 하드디스크에 저장할 때도 각 섹션이 4K 바이트 경계로 저장되도록 한다. 비록 한 섹션이 512바이트 크기이고 하드디스크의 한 섹터에만 저장된다고 해도 컴파일러는 오브젝트 코드를 만들 때 4K바이트 크기로 만들어서, 로더가 프로그램을 메모리로 읽어볼 때 빠르게 읽어올 수 있도록 해준다.
만약 4K바이트 경계로 섹터가 저장되어 있지 않고, 하드디스크의 블록 경계에도 정렬되어 있지 않으면, 운영체제는 여러 블록을 메모리 버퍼에 읽어온 후 다시 페이지 크기로 정렬된 메모리로 복사해주어야 한다. 이렇게 추가적인 로드가 필요해진다.
컴파일러가 실행 파일을 만들 때 실행 시간을 희생해서 크기를 작게 만들 수도 있고, 크기는 크지만 빨리 실행될 수 있도록 만들 수도 있다. 따라서 실행 파일의 크기만으로 컴파일러를 비교해서는 안된다. 확실한 방법은 실행 파일이나 오브젝트 파일을 직접 비교해보는 것이다.
(하드웨어 캐시의 Hit ratio를 높이기 위해 하드웨어 캐시의 정렬 크기에 따라 함수/변수의 시작 주소를 정렬하는 것도 일반적인 최적화방식이다. 구조체의 크기를 4바이트로 맞추기 위해 패딩 바이트를 채우는 것또한 같은 맥락이다.)
=================================================================
6장
참고 자료
- 스택 구조에 대한 이해 http://www.linuxfocus.org/Korean/March2001/article183.shtml
- 응용 프로그램이 로딩되서 실행되는 과정 http://smilk.egloos.com/486882
(위의 참고 자료에서 2번째 자료를 읽고 이해하면 6장을 따로 읽을 필요가 없음!!
6장을 읽으면서 내가 실습하려던 것이 2번째 자료의 내용임, 자세한 설명은 스터디 시간에 말로~~)
다음 예제 소스가 컴파일된 결과를 확인해보자.
#include
int main(int argc, char **argv)
{
int i;
int j;
i = argc;
j = **argv;
if (i == 2)
++j;
else
--j;
printf("i = %d, j = %d\n", i, j);
return 0;
}
먼저 gcc -S 6_2_3.c 명령으로 최적화없이 컴파일된 어셈블리 코드이다.
.file "6_2_3.c"
.section .rodata
.LC0:
.string "i = %d, j = %d\n"
.text
.globl main
.type main, @function
main:
leal 4(%esp), %ecx
andl $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %ecx
subl $36, %esp
movl (%ecx), %eax
movl %eax, -12(%ebp)
movl 4(%ecx), %eax
movl (%eax), %eax
movzbl (%eax), %eax
movsbl %al,%eax
movl %eax, -8(%ebp)
cmpl $2, -12(%ebp)
jne .L2
addl $1, -8(%ebp)
jmp .L4
.L2:
subl $1, -8(%ebp)
.L4:
movl -8(%ebp), %eax
movl %eax, 8(%esp)
movl -12(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf
movl $0, %eax
addl $36, %esp
popl %ecx
popl %ebp
leal -4(%ecx), %esp
ret
.size main, .-main
.ident "GCC: (GNU) 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)"
.section .note.GNU-stack,"",@progbits
다음은 gcc -S -O1 6_2_3.c 명령으로 1단계 최적화를 실행한 어셈블리 코드이다.
.file "6_2_3.c"
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "i = %d, j = %d\n"
.text
.globl main
.type main, @function
main:
leal 4(%esp), %ecx
andl $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %ecx
subl $20, %esp
movl (%ecx), %edx
movl 4(%ecx), %eax
movl (%eax), %eax
movsbl (%eax),%eax
cmpl $2, %edx
jne .L2
addl $1, %eax
jmp .L4
.L2:
subl $1, %eax
.L4:
movl %eax, 8(%esp)
movl %edx, 4(%esp)
movl $.LC0, (%esp)
call printf
movl $0, %eax
addl $20, %esp
popl %ecx
popl %ebp
leal -4(%ecx), %esp
ret
.size main, .-main
.ident "GCC: (GNU) 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)"
.section .note.GNU-stack,"",@progbits
다음은 각 objdump 명령으로 실행 파일의 기계 코드를 읽은 것이다
gurugio:great$ objdump -S a.out
a.out: file format elf32-i386
Disassembly of section .init:
08048278 <_init>:
8048278: 55 push %ebp
8048279: 89 e5 mov %esp,%ebp
804827b: 53 push %ebx
804827c: 83 ec 04 sub $0x4,%esp
804827f: e8 00 00 00 00 call 8048284 <_init+0xc>
8048284: 5b pop %ebx
8048285: 81 c3 f4 12 00 00 add $0x12f4,%ebx
804828b: 8b 93 fc ff ff ff mov -0x4(%ebx),%edx
8048291: 85 d2 test %edx,%edx
8048293: 74 05 je 804829a <_init+0x22>
8048295: e8 1e 00 00 00 call 80482b8 <__gmon_start__@plt>
804829a: e8 b1 00 00 00 call 8048350
804829f: e8 8c 01 00 00 call 8048430 <__do_global_ctors_aux>
80482a4: 58 pop %eax
80482a5: 5b pop %ebx
80482a6: c9 leave
80482a7: c3 ret
Disassembly of section .plt:
080482a8 <__gmon_start__@plt-0x10>:
80482a8: ff 35 7c 95 04 08 pushl 0x804957c
80482ae: ff 25 80 95 04 08 jmp *0x8049580
80482b4: 00 00 add %al,(%eax)
...
080482b8 <__gmon_start__@plt>:
80482b8: ff 25 84 95 04 08 jmp *0x8049584
80482be: 68 00 00 00 00 push $0x0
80482c3: e9 e0 ff ff ff jmp 80482a8 <_init+0x30>
080482c8 <__libc_start_main@plt>:
80482c8: ff 25 88 95 04 08 jmp *0x8049588
80482ce: 68 08 00 00 00 push $0x8
80482d3: e9 d0 ff ff ff jmp 80482a8 <_init+0x30>
080482d8 :
80482d8: ff 25 8c 95 04 08 jmp *0x804958c
80482de: 68 10 00 00 00 push $0x10
80482e3: e9 c0 ff ff ff jmp 80482a8 <_init+0x30>
Disassembly of section .text:
080482f0 <_start>:
80482f0: 31 ed xor %ebp,%ebp
80482f2: 5e pop %esi
80482f3: 89 e1 mov %esp,%ecx
80482f5: 83 e4 f0 and $0xfffffff0,%esp
80482f8: 50 push %eax
80482f9: 54 push %esp
80482fa: 52 push %edx
80482fb: 68 c0 83 04 08 push $0x80483c0
8048300: 68 d0 83 04 08 push $0x80483d0
8048305: 51 push %ecx
8048306: 56 push %esi
8048307: 68 74 83 04 08 push $0x8048374
804830c: e8 b7 ff ff ff call 80482c8 <__libc_start_main@plt>
8048311: f4 hlt
8048312: 90 nop
8048313: 90 nop
8048314: 90 nop
8048315: 90 nop
8048316: 90 nop
8048317: 90 nop
8048318: 90 nop
8048319: 90 nop
804831a: 90 nop
804831b: 90 nop
804831c: 90 nop
804831d: 90 nop
804831e: 90 nop
804831f: 90 nop
08048320 <__do_global_dtors_aux>:
8048320: 55 push %ebp
8048321: 89 e5 mov %esp,%ebp
8048323: 83 ec 08 sub $0x8,%esp
8048326: 80 3d 9c 95 04 08 00 cmpb $0x0,0x804959c
804832d: 74 0c je 804833b <__do_global_dtors_aux+0x1b>
804832f: eb 1c jmp 804834d <__do_global_dtors_aux+0x2d>
8048331: 83 c0 04 add $0x4,%eax
8048334: a3 98 95 04 08 mov %eax,0x8049598
8048339: ff d2 call *%edx
804833b: a1 98 95 04 08 mov 0x8049598,%eax
8048340: 8b 10 mov (%eax),%edx
8048342: 85 d2 test %edx,%edx
8048344: 75 eb jne 8048331 <__do_global_dtors_aux+0x11>
8048346: c6 05 9c 95 04 08 01 movb $0x1,0x804959c
804834d: c9 leave
804834e: c3 ret
804834f: 90 nop
08048350 :
8048350: 55 push %ebp
8048351: 89 e5 mov %esp,%ebp
8048353: 83 ec 08 sub $0x8,%esp
8048356: a1 a0 94 04 08 mov 0x80494a0,%eax
804835b: 85 c0 test %eax,%eax
804835d: 74 12 je 8048371
804835f: b8 00 00 00 00 mov $0x0,%eax
8048364: 85 c0 test %eax,%eax
8048366: 74 09 je 8048371
8048368: c7 04 24 a0 94 04 08 movl $0x80494a0,(%esp)
804836f: ff d0 call *%eax
8048371: c9 leave
8048372: c3 ret
8048373: 90 nop
08048374 :
8048374: 8d 4c 24 04 lea 0x4(%esp),%ecx
8048378: 83 e4 f0 and $0xfffffff0,%esp
804837b: ff 71 fc pushl -0x4(%ecx)
804837e: 55 push %ebp
804837f: 89 e5 mov %esp,%ebp
8048381: 51 push %ecx
8048382: 83 ec 14 sub $0x14,%esp
8048385: 8b 11 mov (%ecx),%edx
8048387: 8b 41 04 mov 0x4(%ecx),%eax
804838a: 8b 00 mov (%eax),%eax
804838c: 0f be 00 movsbl (%eax),%eax
804838f: 83 fa 02 cmp $0x2,%edx
8048392: 75 05 jne 8048399
8048394: 83 c0 01 add $0x1,%eax
8048397: eb 03 jmp 804839c
8048399: 83 e8 01 sub $0x1,%eax
804839c: 89 44 24 08 mov %eax,0x8(%esp)
80483a0: 89 54 24 04 mov %edx,0x4(%esp)
80483a4: c7 04 24 7c 84 04 08 movl $0x804847c,(%esp)
80483ab: e8 28 ff ff ff call 80482d8
80483b0: b8 00 00 00 00 mov $0x0,%eax
80483b5: 83 c4 14 add $0x14,%esp
80483b8: 59 pop %ecx
80483b9: 5d pop %ebp
80483ba: 8d 61 fc lea -0x4(%ecx),%esp
80483bd: c3 ret
80483be: 90 nop
80483bf: 90 nop
080483c0 <__libc_csu_fini>:
80483c0: 55 push %ebp
80483c1: 89 e5 mov %esp,%ebp
80483c3: 5d pop %ebp
80483c4: c3 ret
80483c5: 8d 74 26 00 lea 0x0(%esi),%esi
80483c9: 8d bc 27 00 00 00 00 lea 0x0(%edi),%edi
080483d0 <__libc_csu_init>:
80483d0: 55 push %ebp
80483d1: 89 e5 mov %esp,%ebp
80483d3: 57 push %edi
80483d4: 56 push %esi
80483d5: 53 push %ebx
80483d6: e8 4f 00 00 00 call 804842a <__i686.get_pc_thunk.bx>
80483db: 81 c3 9d 11 00 00 add $0x119d,%ebx
80483e1: 83 ec 0c sub $0xc,%esp
80483e4: e8 8f fe ff ff call 8048278 <_init>
80483e9: 8d bb 18 ff ff ff lea -0xe8(%ebx),%edi
80483ef: 8d 83 18 ff ff ff lea -0xe8(%ebx),%eax
80483f5: 29 c7 sub %eax,%edi
80483f7: c1 ff 02 sar $0x2,%edi
80483fa: 85 ff test %edi,%edi
80483fc: 74 24 je 8048422 <__libc_csu_init+0x52>
80483fe: 31 f6 xor %esi,%esi
8048400: 8b 45 10 mov 0x10(%ebp),%eax
8048403: 89 44 24 08 mov %eax,0x8(%esp)
8048407: 8b 45 0c mov 0xc(%ebp),%eax
804840a: 89 44 24 04 mov %eax,0x4(%esp)
804840e: 8b 45 08 mov 0x8(%ebp),%eax
8048411: 89 04 24 mov %eax,(%esp)
8048414: ff 94 b3 18 ff ff ff call *-0xe8(%ebx,%esi,4)
804841b: 83 c6 01 add $0x1,%esi
804841e: 39 f7 cmp %esi,%edi
8048420: 75 de jne 8048400 <__libc_csu_init+0x30>
8048422: 83 c4 0c add $0xc,%esp
8048425: 5b pop %ebx
8048426: 5e pop %esi
8048427: 5f pop %edi
8048428: 5d pop %ebp
8048429: c3 ret
0804842a <__i686.get_pc_thunk.bx>:
804842a: 8b 1c 24 mov (%esp),%ebx
804842d: c3 ret
804842e: 90 nop
804842f: 90 nop
08048430 <__do_global_ctors_aux>:
8048430: 55 push %ebp
8048431: 89 e5 mov %esp,%ebp
8048433: 53 push %ebx
8048434: bb 90 94 04 08 mov $0x8049490,%ebx
8048439: 83 ec 04 sub $0x4,%esp
804843c: a1 90 94 04 08 mov 0x8049490,%eax
8048441: 83 f8 ff cmp $0xffffffff,%eax
8048444: 74 0c je 8048452 <__do_global_ctors_aux+0x22>
8048446: 83 eb 04 sub $0x4,%ebx
8048449: ff d0 call *%eax
804844b: 8b 03 mov (%ebx),%eax
804844d: 83 f8 ff cmp $0xffffffff,%eax
8048450: 75 f4 jne 8048446 <__do_global_ctors_aux+0x16>
8048452: 83 c4 04 add $0x4,%esp
8048455: 5b pop %ebx
8048456: 5d pop %ebp
8048457: c3 ret
Disassembly of section .fini:
08048458 <_fini>:
8048458: 55 push %ebp
8048459: 89 e5 mov %esp,%ebp
804845b: 53 push %ebx
804845c: 83 ec 04 sub $0x4,%esp
804845f: e8 00 00 00 00 call 8048464 <_fini+0xc>
8048464: 5b pop %ebx
8048465: 81 c3 14 11 00 00 add $0x1114,%ebx
804846b: e8 b0 fe ff ff call 8048320 <__do_global_dtors_aux>
8048470: 59 pop %ecx
8048471: 5b pop %ebx
8048472: c9 leave
8048473: c3 ret
예제 C 코드를 오브젝트 파일로 만들면 코드만 어셈블된 기계 코드를 얻을 수 있다.
실행 파일을 역어셈블하는 것보다 이해하기 쉽다.
gurugio:great$ objdump -S ex.o
ex.o: file format elf32-i386
Disassembly of section .text:
00000000 :
0: 8d 4c 24 04 lea 0x4(%esp),%ecx
4: 83 e4 f0 and $0xfffffff0,%esp
7: ff 71 fc pushl -0x4(%ecx)
a: 55 push %ebp
b: 89 e5 mov %esp,%ebp
d: 51 push %ecx
e: 83 ec 24 sub $0x24,%esp
11: 8b 01 mov (%ecx),%eax
13: 89 45 f4 mov %eax,-0xc(%ebp)
16: 8b 41 04 mov 0x4(%ecx),%eax
19: 8b 00 mov (%eax),%eax
1b: 0f b6 00 movzbl (%eax),%eax
1e: 0f be c0 movsbl %al,%eax
21: 89 45 f8 mov %eax,-0x8(%ebp)
24: 83 7d f4 02 cmpl $0x2,-0xc(%ebp)
28: 75 06 jne 30
2a: 83 45 f8 01 addl $0x1,-0x8(%ebp)
2e: eb 04 jmp 34
30: 83 6d f8 01 subl $0x1,-0x8(%ebp)
34: 8b 45 f8 mov -0x8(%ebp),%eax
37: 89 44 24 08 mov %eax,0x8(%esp)
3b: 8b 45 f4 mov -0xc(%ebp),%eax
3e: 89 44 24 04 mov %eax,0x4(%esp)
42: c7 04 24 00 00 00 00 movl $0x0,(%esp)
49: e8 fc ff ff ff call 4a
4e: b8 00 00 00 00 mov $0x0,%eax
53: 83 c4 24 add $0x24,%esp
56: 59 pop %ecx
57: 5d pop %ebp
58: 8d 61 fc lea -0x4(%ecx),%esp
5b: c3 ret
댓글
재미있게 잘읽었습니다... :)
어셈러브가 리뉴얼중이군요...
굉장히 이쁘게 바꾸네요..
--------------------------------------------
혼자있고 싶습니다. 모두 지구밖으로 나가주세요.
--------------------------------------------
혼자있고 싶습니다. 모두 지구밖으로 나가주세요.
틀린부분이
틀린부분이 있군요.
먼저 T(n) = 2^n - 1은 다항식이 아닙니다.
그리고 NP 문제도 답을 구할수 없는 문제가 아닙니다.
예
예 감사합니다.
무식한게 바로 탄로나버렸네요~
바로 수정하겠습니다. ;-)
정말 감사합니다.
NP문제가 답을 구할 수 없는 문제라고 쓰려고 했는데
제가 반대로 썼나봅니다.
----
세상을 바꾸는 것은 단 한 사람. 오직 하나님의 사람뿐이다.
http://www.asmlove.co.kr
P, NP, NP-Complete의
P, NP, NP-Complete의 관계를 잘 모르시는거 같은데 간략하게 설명하면요..
먼저 P는 본문에 쓰신 내용이 맞고요.
NP는 미결정적 튜링기계라는 가상의 기계에서 다항시간 알고리즘이 존재하는 문제들의 집합입니다.
그리고 명백히 P에 속하는 문제는 모두 NP에도 속합니다. (P는 NP의 부분집합)
그러나 P와 NP가 같은 집합인지 여부는 증명되지 않았고 이것은 백만불의 상금이 걸린 대표적인 수학문제죠.
NP-Complete는 쉽게 말하면 NP에 속한 문제중 가장 '어려운' 문제들의 집합입니다.
NP-Complete에 속한 문제중 하나라도 P에 속한다는 증명을 하게 되면 자동으로 모든 NP문제는 P에 속한다는 증명을 얻게 됩니다. (따라서 P = NP가 되고 백만불을 받게 됩니다. (물론 최초 증명일 경우만...) ^^;)
의외로 상당히 많은 문제들이 NP-Complete임이 밝혀졌고 http://en.wikipedia.org/wiki/List_of_NP-complete_problems 에 리스트가 있습니다. (Code Generation에 관한 문제들도 몇개 있군요..)
(본문에 처음에는 프로그램 최적화 문제가 NP-Complete라고 했다가 나중에 NP라고 했는데 물론 둘다 맞는 소리긴 하지만 이 문제가 '어려운' 문제라는걸 말하기 위함이니까 NP-Complete라고 하는게 적절하겠죠. NP에는 P에도 속하는 '쉬운' 문제들도 있으니까요..)
어떤 문제가 NP-Complete에 속한다는것이 밝혀졌다면 이 문제를 풀기 위해서 어떻게 하느냐..... 일단 다항시간 알고리즘 찾는것을 포기 -_- 합니다. (백만불 짜리 수학문제에 도전할게 아니라면요...) 그리고 다음 둘중에 하나를 하겠죠...
1. 다항시간이 아닌(지수시간 또는 그보다 더한) 알고리즘을 찾는다. -> 그러나 입력의 크가가 커짐에 따라서 수행시간이 어마어마하게 늘어나므로 일정 크기 이상의 입력에 대해서는 포기해야 됩니다.
2. 문제가 최적화 문제라면 최적해(제일 좋은 해) 대신에 근사해를 찾는 빠른 알고리즘을 찾는다. -> 그러나 판단문제는 어쩔수 없겠죠...
하지만 이런 논의들은 컴파일러에서 그다지 큰 의미는 없는거 같네요. 왜냐면 다항시간 알고리즘이라고 다 컴파일러에 쓰이는것은 아니고, 컴파일러에서는 거의 선형시간(O(n))이하의 알고리즘만 씁니다. O(n^2)만 돼도 거의 쓰이지 않습니다.
댓글 달기