[performance] 반복보다 반복이 더 빠릅니까?

루프보다 재귀가 더 빠릅니까?

아니요, 반복은 항상 재귀보다 빠릅니다. (Von Neumann 아키텍처에서)

설명:

일반 컴퓨터의 최소 작업을 처음부터 작성하는 경우 “반복”이 먼저 빌딩 블록으로 제공되고 “재귀”보다 리소스 집약도가 낮 으면 ergo가 더 빠릅니다.

의사 컴퓨팅 머신을 처음부터 구축 :

스스로 에게 질문하십시오 : 알고리즘을 따르고 결과에 도달 하기 위해 값 을 계산 하려면 무엇이 필요 합니까?

우리는 처음부터 시작하여 기본 핵심 개념을 처음부터 정의한 후 개념의 두 번째 레벨 개념을 구축하는 등 개념의 계층 구조를 설정합니다.

1. 첫 번째 개념 : 메모리 셀, 저장, 주 . 무언가를하려면 최종 및 중간 결과 값을 저장할 장소 가 필요 합니다. Memory , M [0..Infinite] 라는 “정수”셀의 무한 배열이 있다고 가정 해 봅시다 .

2. 지침 : 무언가를하십시오-셀을 변형시키고 그 값을 변경하십시오. 상태를 변경하십시오 . 모든 흥미로운 명령은 변형을 수행합니다. 기본 지침은 다음과 같습니다.

   a) 메모리 셀 설정 및 이동

   • 값을 메모리에 저장한다. 예 : store 5 m [4]
   • 값을 다른 위치로 복사하십시오. 예 : store m [4] m [8]

   b) 논리와 산술

   • 그리고, 또는, 또는
   • 추가, 하위, mul, div. 예를 들어 m [7] m [8] 추가

3. Executing Agent : 최신 CPU 의 핵심 . “에이전트”는 명령어를 실행할 수있는 것입니다. 에이전트는 또한 종이에 알고리즘 다음과 같은 사람이 될 수 있습니다.

4. 단계 순서 : 일련의 명령 : 즉 : 먼저 수행하고, 이후에 수행하십시오. 명령의 필수 순서. 한 줄 식 조차도 “필수적인 명령 순서”입니다. 특정 “평가 순서”가있는 표현식이있는 경우 단계가 있습니다. 이는 하나의 작성된 표현식조차도 암시 적 “단계”를 가지며 암시 적 로컬 변수도 갖습니다 ( “결과”라고 함). 예 :

   4 + 3 * 2 - 5
   (- (+ (* 3 2) 4 ) 5)
   (sub (add (mul 3 2) 4 ) 5)
   

   위의 표현은 암시 적 “결과”변수가있는 3 단계를 의미합니다.

   // pseudocode
   
          1. result = (mul 3 2)
          2. result = (add 4 result)
          3. result = (sub result 5)
   

   따라서 특정 평가 순서가 있으므로 삽입 표현식도 명령의 필수 순서입니다 . 이 표현 은 특정 순서로 수행되는 일련의 작업을 의미 하며, 단계 가 있기 때문에 암시적인 “결과”중간 변수도 있습니다.

5. 지시 포인터 : 일련의 단계가 있으면 암시적인 “명령 포인터”도 있습니다. 명령 포인터는 다음 명령을 표시하고 명령을 읽은 후 명령이 실행되기 전에 진행합니다.

   이 의사 컴퓨팅 머신에서 명령어 포인터는 Memory의 일부입니다 . (참고 : 일반적으로 명령어 포인터 는 CPU 코어에서 “특수 레지스터”가되지만 여기서는 개념을 단순화하고 모든 데이터 (레지스터 포함)가 “메모리”의 일부라고 가정합니다.

6. 점프 -순서가 지정된 단계와 명령 포인터 가 있으면 ” store “명령을 적용 하여 명령 포인터 자체의 값을 변경할 수 있습니다. 점포 명령어 의 이러한 특정 사용을 새로운 이름 인 Jump라고 합니다. 우리는 새로운 개념으로 생각하기 쉽기 때문에 새로운 이름을 사용합니다. 명령 포인터를 변경하여 에이전트에게 “x 단계로 이동”하도록 지시합니다.

7. 무한 반복 : 뒤로 건너 뛰어 에이전트가 특정 단계를 “반복”할 수 있습니다. 이 시점에서 무한 반복이 있습니다.

                      1. mov 1000 m[30]
                      2. sub m[30] 1
                      3. jmp-to 2  // infinite loop
   

8. 조건부 -조건부 명령 실행. “조건부”절을 사용하면 현재 상태 (이전 명령어로 설정할 수 있음)를 기반으로 여러 명령어 중 하나를 조건부로 실행할 수 있습니다.

9. 적절한 반복 : 이제와 조건 절, 우리는의 무한 루프 탈출 할 수 점프 다시 지시를. 이제 조건부 루프가 있고 적절한 반복이 있습니다.

   1. mov 1000 m[30]
   2. sub m[30] 1
   3. (if not-zero) jump 2  // jump only if the previous
                           // sub instruction did not result in 0
   
   // this loop will be repeated 1000 times
   // here we have proper ***iteration***, a conditional loop.
   

10. 이름 지정 : 데이터를 보유하거나 단계를 보유한 특정 메모리 위치에 이름을 지정 합니다 . 이것은 단지 “편의”입니다. 메모리 위치에 “이름”을 정의 할 수있는 용량을 가짐으로써 새로운 지침을 추가하지 않습니다. “네이밍”은 에이전트의 지시가 아니며 단지 우리에게 편의 일뿐입니다. 이름을 지정 하면 코드 (이 시점)를보다 쉽게 ​​읽고 변경할 수 있습니다.

       #define counter m[30]   // name a memory location
       mov 1000 counter
    loop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop
    

11. 1 단계 서브 루틴 : 자주 실행해야하는 일련의 단계가 있다고 가정합니다. 단계를 메모리의 명명 된 위치에 저장 한 다음 실행해야 할 때 해당 위치 로 이동할 수 있습니다 (호출). 시퀀스가 끝나면 실행을 계속하려면 호출 지점으로 돌아 가야 합니다 . 이 메커니즘을 사용하면 핵심 명령어를 작성 하여 새 명령어 (서브 루틴)를 만듭니다.

    구현 : (새로운 개념이 필요하지 않음)

    • 현재 명령어 포인터를 사전 정의 된 메모리 위치에 저장
    • 점프 서브 루틴에
    • 서브 루틴의 끝에서 사전 정의 된 메모리 위치에서 명령어 포인터를 검색하여 원래 호출 의 다음 명령어로 효과적으로 되돌아갑니다.

    단일 레벨 구현 의 문제점 : 서브 루틴에서 다른 서브 루틴을 호출 할 수 없습니다. 그렇게하면 반환 주소 (전역 변수)를 덮어 쓰므로 호출을 중첩 할 수 없습니다.

    서브 루틴에 대한 더 나은 구현을 위해서는 STACK이 필요합니다

12. 스택 : “스택”으로 작동 할 메모리 공간을 정의하고 스택에서 값을 “푸시”하고 마지막 “푸시”값을 “팝”할 수 있습니다. 스택을 구현하려면 스택 의 실제 “헤드”를 가리키는 스택 포인터 (명령 포인터와 유사)가 필요합니다 . 값을 “푸시”하면 스택 포인터가 감소하고 값을 저장합니다. “팝”하면 실제 스택 포인터에서 값을 얻은 다음 스택 포인터가 증가합니다.

13. 서브 루틴 이제 스택 이 생겼으므로 중첩 된 호출을 허용 하는 적절한 서브 루틴을 구현할 수 있습니다 . 구현은 비슷하지만 사전 정의 된 메모리 위치에 명령어 포인터를 저장하는 대신 스택 의 IP 값을 “밀어 넣습니다” . 서브 루틴이 끝나면 스택에서 값을 “팝핑”하여 원래 호출 후 명령으로 효과적으로 되돌아갑니다 . “스택”이있는이 구현은 다른 서브 루틴에서 서브 루틴을 호출 할 수 있습니다. 이 구현 을 통해 핵심 명령어 나 다른 서브 루틴을 빌딩 블록으로 사용하여 새 명령어 를 서브 루틴으로 정의 할 때 여러 수준의 추상화를 만들 수 있습니다 .

14. 재귀 : 서브 루틴이 자신을 호출하면 어떻게됩니까? 이것을 “재귀”라고합니다.

    문제점 : 로컬 중간 결과를 겹쳐 쓰면 서브 루틴이 메모리에 저장 될 수 있습니다. 당신이 호출되기 때문에 / 같은 단계를 재사용하는 경우 중간 결과가 미리 정의 된 메모리 위치 (전역 변수)에 저장되어 그들이 중첩 된 호출에 덮어 쓰게됩니다.

    솔루션 : 재귀를 허용하려면 서브 루틴은 로컬 중간 결과 를 스택에 저장해야 하므로 각 재귀 호출 (직접 또는 간접)에서 중간 결과는 다른 메모리 위치에 저장됩니다.

…

재귀에 도달하면 여기서 멈 춥니 다.

결론:

Von Neumann Architecture에서 “반복” 은 “재귀” 보다 단순하고 기본적인 개념이며 , “재귀” 는 개념 계층의 14 단계에있는 반면, 7 단계 에서는 “반복” 의 형태를 갖습니다 .

명령이 적으므로 CPU 사이클이 적기 때문에 머신 코드에서 반복 이 항상 빠릅니다.

어느 쪽이 더 낫습니까?

• 단순하고 순차적 인 데이터 구조를 처리 할 때 “간단한 루프”가 수행 할 때마다 “반복”을 사용해야합니다.

• 재귀 데이터 구조를 처리해야하는 경우 ( “Fractal Data Structures”라고 함) 재귀 솔루션이 더 “우아한”경우에는 “재귀”를 사용해야합니다.

조언 : 작업에 가장 적합한 도구를 사용하되 현명하게 선택하려면 각 도구의 내부 작동을 이해하십시오.

마지막으로 재귀를 사용할 수있는 많은 기회가 있습니다. 당신은 어디에서나 재귀 데이터 구조를 가지고 있고, 지금보고 있습니다 : 읽고있는 것을 지원하는 DOM의 일부는 RDS이고, JSON 표현식은 RDS이며, 컴퓨터의 계층 파일 시스템은 RDS입니다. 파일과 디렉토리를 포함하는 루트 디렉토리, 파일과 디렉토리를 포함하는 모든 디렉토리, 파일과 디렉토리를 포함하는 모든 디렉토리 …

답변

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}