ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • Tail Call Optimization and Java
      JAVA 2017. 10. 10. 17:01
      반응형

      이 문서는 영문으로된 내용을 구글 번역기를 활용하여 번역한 내용입니다. 
      개인적인 공부 및 추후 다시 볼 수 있도록 하기 위해 개인 블로그에 번역 내용을 옮겨 놓았습니다.
      원문과 내용이 다를시 책임지지 않으며, 저작권 문제가 발생시 언제든 삭제 될 수 있습니다. 

      원문보기 : http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044


      By Eric Bruno, April 15, 2014

      Java 8은 당분간 자신의 꼬리 호출(tail call)을 최적화하기 위해 함수 언어를 필요로 합니다. 그게 정확히 무엇을 포함합니까?
      최근 Java SE 8에 특수 호출 기능인 tail 호출에 대한 최적화가 포함되었는지 여부에 대한 질문을 받았습니다. 이 최적화는 재귀 호출에 가장 관련이 있습니다. 재귀 호출은 종종 재귀적 디자인 및 코딩 패턴에 의존하기 때문에 함수 언어에서 특히 중요합니다. 이 기사에서는 꼬리 호출이 무엇인지, 어떻게 효과적으로 최적화 할 수 있는지, 그리고 Java 8이 이 최적화를 구현할 수 있는지에 대해 알아 봅니다.
      깊이 들어가기 전에 꼬리 호출을 정의합시다.

      What is A Tail Call?

      꼬리 호출은 메서드나 함수 호출이 다른 메서드나 함수 내부의 마지막 명령어인 상황을 나타내는 멋진 용어입니다 (간단히 하기 위해 모든 호출을 지금부터 함수 호출이라고 부름). 앤드류 코닉 (Andrew Koenig)은 최적화에 관한 블로그 시리즈에서 주제를 다루었습니다. 예를 들어, 여기에 정의 된 foo () 함수를 사용하십시오.
      1
      2
      3
      4
      int foo(int a) {
        a = a + 1;
        return func(a);
      }
      		cs
      함수 func()에 대한 호출은 함수 foo()에서 마지막 문장이므로 꼬리 호출입니다. foo()가 func()을 호출 한 후에 return 이외의 명령어를 실행하면 func()은 더 이상 tail 호출이 아닙니다.
      왜 이러한 의미가 중요한지 궁금할 것입니다. 꼬리 호출이 재귀 함수인 재귀 프로그래밍을 고려할때 까지는 별로 중요하지 않거나 흥미롭지 않습니다. 예:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      int fact(int i, int acc) {
        if ( i == 0 ) 
          return acc;
        else
          return fact( i – 1, acc * i);
      }
       
      int factorial(int n) {
        if ( n == 0 )
          return 1;
        else
          return fact( n – 1, 1 );
      }
      		cs
      fact()에 대한 어셈블리 언어는 C 소스의 오른쪽에 있는 그림 1에 나와 있습니다. 빨간색 화살표는 fact() 함수의 마지막 두 명령어 (fact() 자체에 대한 호출과 return 문에 대한 MOV)를 가리 킵니다. 이는 꼬리 호출의 정의에 맞습니다.
      Figure 1: Function fact is a tail call, as seen in the assembly code.
      연관된 어셈블리 코드를 표시하는 것이 쉬웠기 때문에 C에서 이것을 설명하기로 선택했지만 Java에서도 마찬가지입니다. 실제로 함수의 소스 코드를 그대로 Java 클래스에 복사하면 컴파일되고 작동합니다. 그렇다면 정확히 무엇을 최적화 할 수 있습니까?

      Tail Call Optimization Described

      재귀 함수가 아닌 모든 꼬리 호출을 사용하면 함수 호출 자체를 최적화하여 효과적으로 goto로 변환 할 수 있습니다. 즉, 함수 호출 전에 스택을 설정하고 이후에 복원하는 작업 (각각 프롤로그 및 에필로그)을 모두 제거 할 수 있습니다. 예를 들어 아래 코드를 사용하십시오.
      1
      2
      3
      4
      int func_a(int data) {
        data = do_this(data);
        return do_that(data);
      }
      		cs

      do_that() 함수는 꼬리 호출입니다. 최적화되지 않은 어셈블리 코드는 다음과 같이 보일 수 있습니다.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      ...     ! executing inside func_a()
      push EIP    ! push current instruction pointer on stack
      push data   ! push variable 'data' on the stack
      jmp do_this ! call do_this() by jumping to its address
      ...     ! executing inside do_this()
      push EIP    ! push current instruction pointer on stack
      push data   ! push variable 'data' on the stack
      jmp do_that ! call do_that() by jumping to its address
      ...     ! executing inside do_that()
      pop data    ! prepare to return value of 'data'
      pop EIP ! return to do_this()
      pop data    ! prepare to return value of 'data'
      pop EIP ! return to func_a()
      pop data    ! prepare to return value of 'data'
      pop EIP ! return to func_a() caller
      ...
      		cs

      데이터와 EIP 레지스터 (데이터 값을 반환하고 명령 포인터를 복원)에 대한 여러 POP 명령이 연속적으로 발생합니다. 이 에필로그와 관련 프롤로그 (데이터와 EIP 레지스터가 스택에 저장되는)의 한 세트는 제거되고 단순한 JMP 어셈블리 명령어로 대체 될 수 있습니다. 이것은 do_that() 함수가 호출 함수 func_a()에 대한 에필로그 코드를 실행하기 때문에 수행 될 수 있습니다.
      do_that()가 반환된 후 func_a()가 의미있는 명령어를 수행하지 않기 때문에 이 최적화가 안전합니다. (주의 : do_that() 호출이 반환된 후에 반환값을 사용하여 무언가가 완료되면 do_that()가 더 이상 꼬리 호출이 아니기 때문에 이 최적화를 수행 할 수 없습니다.)
      다음은 꼬리 호출 최적화의 결과입니다.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      ...     ! executing inside func_a()
      push EIP    ! push current instruction pointer on stack
      push data   ! push variable 'data' on the stack
      jmp do_this ! call do_this() by jumping to its address
      ...     ! executing inside do_this()
      push EIP    ! push current instruction pointer on stack
      push data   ! push variable 'data' on the stack
      jmp do_that ! call do_that() by jumping to its address
      ...     ! executing inside do_that()
      pop data    ! prepare to return value of 'data'
      pop EIP ! return to do_this()
      pop data    ! prepare to return value of 'data'
      pop EIP ! return to func_a()
      pop data    ! prepare to return value of 'data'
      pop EIP ! return to func_a() caller
      ...
      		cs

      약간 다르게 표현하면 최적화 전의 코드입니다.
      int func_a(int data) {
      data = do_this(data);
      push EIP ! prolog
      push data ! prolog
      jmp do_this ! call
      ...
      pop data ! epilog
      pop EIP ! epilog
      return do_that(data);
      push EIP ! prolog
      push data ! prolog
      jmp do_that ! call
      ...
      pop data ! epilog
      pop EIP ! epilog
      }
      pop data ! epilog
      pop EIP ! epilog
      이것은 꼬리 호출 최적화후 입니다.
      int func_a(int data) {
      data = do_this(data);
      push EIP ! prolog
      push data ! prolog
      jmp do_this ! call
      ...
      pop data ! epilog
      pop EIP ! epilog
      return do_that(data);
      jmp do_that ! goto
      ...
      }
      pop data ! epilog
      pop EIP ! epilog
      두 가지 모두에서 음영 처리된 행을 비교하면 최적화된 버전에서 실행될 기계 코드의 양을 알 수 있습니다. 그러나 이것만으로는 변화의 진정한 가치를 나타내는 것이 아닙니다. 이 최적화는 재귀와 결합할 때 정말 빛이 납니다.
      앞서 살펴본 재귀적 팩토리얼 예제를 검토하면 이 최적화와 함께 반복적으로 필요한 모든 프롤로그 및 에필로그 어셈블리 코드를 제거 할 수 있음을 알 수 있습니다. 이것은 효과적으로 이 재귀적 의사 코드를 여기에 나타냅니다 (위키 백과 예제에서 가져옴).
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      call factorial(3)
        call fact(3,1)
          call fact(2,3)
            call fact(1 6)
              call fact(0,6)
              return 6
            return 6
          return 6
        return 6
      return 6
      		cs

      반복적인 의사 코드로 :
      1
      2
      3
      4
      5
      6
      7
      call factorial(3)
        call fact(3,1)
        update variables with (2,3)
        update variables with (1,6)
        update variables with (0,6)
        return 6
      return 6
      		cs

      바꾸어 말하면 재귀 코드를 루프로 대체 합니다. 대부분의 C, C ++ 또는 Java 프로그래머가 이렇게 사용할 것입니다. 이 최적화는 수많은 재귀 호출에 대한 함수 호출 프롤로그 및 에필로그 어셈블리를 줄일뿐만 아니라 스택에 대한 압력을 크게 감소시킵니다. 이 최적화가 없다면 매우 큰 수의 계승을 계산하거나 다른 큰 재귀 연산을 수행하면 스택을 날릴 수 있습니다. 즉, 로컬 스택에 할당 된 모든 RAM을 사용합니다. 코드를 루프로 줄이면 위험이 사라집니다. 함수 언어 프로그래머는 재귀를 자주 사용하기 때문에 대부분의 함수형 언어 인터프리터는 꼬리 호출 최적화를 수행합니다.

      How Is Java Involved?

      위에서 언급했듯이 자바 프로그래머는 루프를 사용하여 재귀를 피하는 경향이 있습니다. 예를 들어, 다음은 Java에서 팩토리얼을 반복적으로 구현 한 것입니다.
      1
      2
      3
      4
      5
      6
      int factorial(int n) {
         int result = 1;
         for (int t=n; t > 1; t--)
             result *= t;
         return result;
       }
      		cs

      따라서 대부분의 Java 개발자에게는 Java가 꼬리 호출 최적화를 수행하지 않는 것이 큰 문제는 아닙니다. 사실, 제 생각에 많은 Java 개발자는이 최적화에 대해 들어 본 적이 없습니다. 그러나 JVM 위에 관련 함수 언어를 실행할 때 문제가 됩니다. 해당 언어의 인터프리터로 정상적으로 돌아가는 모든 재귀 코드가 JVM에서 실행될 때 스택을 불기 시작할 수 있습니다.
      이것은 JVM의 버그가 아니라는 점에 유의해야 합니다. 재귀를 사용하는 기능적 프로그래머를 돕기 위해 구현할 수있는 최적화입니다. 이러한 재귀는 언어에서 훨씬 더 일반적이며 정상입니다. 최근 Oracle에 Brian Goetz에게 이 최적화에 대해 말했고, JVM에 추가 할 항목 목록에 있지만 매우 중요하지는 않습니다. 지금 당장은 JVM에서 함수 언어를 코딩 할 때 심도있는 재귀 함수를 피함으로써 가능한 직접 최적화를 하는 것이 가장 좋습니다.

      Further Reading

      For more information on the assembly language details behind function calls, see this computer-science lecture. [PDF]
      Eric Bruno is the Java blogger for Dr. Dobb's.



      java8 에서 람다를 활용하여 꼬리 호출 최적화가 가능합니다. 

      코드는 http://blog.daum.net/compert/54 에서 확인 할 수 있습니다.

      반응형

      'JAVA' 카테고리의 다른 글

      육각형 아키텍처(Hexagonal architecture)  (0) 2018.03.24
      Java10이 당신의 코드 방식을 어떻게 바꿀 것인가  (0) 2018.02.28
      Object Pool 에 대한 간략한 설명  (0) 2017.09.27
      람다 표현식을 사용한 잠금(lock) 관리  (0) 2017.03.17
      Java 8의 parallelStream 을 사용할때 Log4j 의 MDC 문제 해결하기  (0) 2017.03.13

      관련글 관련글 더보기

    Designed by Tistory.

    티스토리툴바