Apa yang dimaksud dengan optimasi panggilan ekor?

Sederhananya, apa itu optimasi tail-call?

Lebih khusus, potongan kode kecil apa yang bisa diterapkan, dan di mana tidak, dengan penjelasan mengapa?

Optimasi tail-call adalah di mana Anda dapat menghindari alokasi bingkai stack baru untuk suatu fungsi karena fungsi panggilan hanya akan mengembalikan nilai yang didapatnya dari fungsi yang dipanggil. Penggunaan yang paling umum adalah tail-recursion, di mana fungsi rekursif yang ditulis untuk mengambil keuntungan dari optimasi tail-call dapat menggunakan ruang stack yang konstan.

Skema adalah salah satu dari sedikit bahasa pemrograman yang menjamin dalam spesifikasi bahwa setiap implementasi harus menyediakan optimasi ini (JavaScript juga, dimulai dengan ES6) , jadi berikut adalah dua contoh fungsi faktorial dalam Skema:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

Fungsi pertama bukanlah rekursif ekor karena ketika panggilan rekursif dibuat, fungsi tersebut perlu melacak perkalian yang harus dilakukan dengan hasil setelah panggilan kembali. Dengan demikian, tumpukan terlihat sebagai berikut:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

Sebaliknya, jejak tumpukan untuk faktorial rekursif ekor terlihat sebagai berikut:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Seperti yang Anda lihat, kita hanya perlu melacak jumlah data yang sama untuk setiap panggilan ke fakta karena kita hanya mengembalikan nilai yang kita dapatkan sampai ke atas. Ini berarti bahwa bahkan jika saya menelepon (fakta 1000000), saya hanya membutuhkan jumlah ruang yang sama dengan (fakta 3). Ini tidak terjadi dengan fakta non-ekor-rekursif, dan karena nilai-nilai besar seperti itu dapat menyebabkan stack overflow.

Mari kita berjalan melalui contoh sederhana: fungsi faktorial diimplementasikan dalam C.

Kita mulai dengan definisi rekursif yang jelas

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

Suatu fungsi berakhir dengan panggilan ekor jika operasi terakhir sebelum fungsi kembali adalah panggilan fungsi lain. Jika panggilan ini memanggil fungsi yang sama, itu adalah ekor-rekursif.

Meskipun fac()terlihat rekursif pada pandangan pertama, tidak seperti apa yang sebenarnya terjadi

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

yaitu operasi terakhir adalah perkalian dan bukan pemanggilan fungsi.

Namun, dimungkinkan untuk menulis ulang fac()menjadi ekor-rekursif dengan meneruskan nilai akumulasi ke rantai panggilan sebagai argumen tambahan dan hanya meneruskan hasil akhir lagi sebagai nilai pengembalian:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Sekarang, mengapa ini berguna? Karena kita segera kembali setelah tail tail, kita dapat membuang stackframe sebelumnya sebelum memanggil fungsi pada posisi tail, atau, jika terjadi fungsi rekursif, gunakan kembali stackframe apa adanya.

Optimalisasi panggilan ekor mengubah kode rekursif kami menjadi

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Ini bisa disimpulkan fac()dan kita sampai

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

yang setara dengan

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

Seperti yang dapat kita lihat di sini, pengoptimal yang cukup canggih dapat menggantikan rekursi ekor dengan iterasi, yang jauh lebih efisien karena Anda menghindari overhead panggilan fungsi dan hanya menggunakan jumlah ruang stack yang konstan.

TCO (Tail Call Optimization) adalah proses di mana kompiler pintar dapat melakukan panggilan ke suatu fungsi dan tidak mengambil ruang stack tambahan. Satu- satunya situasi di mana ini terjadi adalah jika instruksi terakhir dieksekusi dalam fungsi f adalah panggilan ke fungsi g (Catatan: g dapat menjadi f ). Kuncinya di sini adalah bahwa f tidak lagi membutuhkan ruang stack - ia hanya memanggil g dan kemudian mengembalikan apa pun yang akan kembali g . Dalam hal ini optimasi dapat dibuat bahwa g hanya berjalan dan mengembalikan nilai apa pun yang diperlukan untuk hal yang disebut f.

Optimasi ini dapat membuat panggilan rekursif mengambil ruang stack konstan, daripada meledak.

Contoh: fungsi faktorial ini tidak TCOptimasi:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Fungsi ini melakukan hal-hal selain memanggil fungsi lain dalam pernyataan pengembaliannya.

Fungsi di bawah ini TCOptimizable:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

Ini karena hal terakhir yang terjadi di salah satu fungsi ini adalah memanggil fungsi lain.

Mungkin deskripsi tingkat tinggi terbaik yang saya temukan untuk panggilan ekor, panggilan ekor rekursif dan optimasi panggilan ekor adalah posting blog

"Apa-apaan ini: Panggilan ekor"

oleh Dan Sugalski. Pada optimasi panggilan ekor ia menulis:

Pertimbangkan, sesaat, fungsi sederhana ini:

sub foo (int a) {
  a += 15;
  return bar(a);
}

Jadi, apa yang bisa Anda, atau lebih tepatnya kompiler bahasa Anda, lakukan? Nah, yang bisa dilakukan adalah mengubah kode formulir return somefunc();menjadi urutan tingkat rendah pop stack frame; goto somefunc();. Dalam contoh kita, itu berarti sebelum kita memanggil bar, foomembersihkan dirinya dan kemudian, daripada memanggil barsebagai subrutin, kita melakukan gotooperasi tingkat rendah ke awal bar. FooSudah membersihkan dirinya sendiri dari tumpukan, jadi ketika barmulai sepertinya siapa pun yang dipanggil foobenar-benar memanggil bar, dan ketika barmengembalikan nilainya, ia mengembalikannya langsung ke siapa pun yang dipanggil foo, alih-alih mengembalikannya fooyang kemudian mengembalikannya ke pemanggilnya.

Dan pada rekursi ekor:

Ekor rekursi terjadi jika suatu fungsi, sebagai operasi terakhirnya, mengembalikan hasil pemanggilan itu sendiri . Rekursi ekor lebih mudah untuk ditangani karena daripada harus melompat ke awal beberapa fungsi acak di suatu tempat, Anda cukup melakukan kebalikan dari permulaan diri Anda, yang merupakan hal sederhana untuk dilakukan.

Jadi ini:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

diam-diam berubah menjadi:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

Apa yang saya sukai dari deskripsi ini adalah betapa ringkas dan mudahnya untuk memahami bagi mereka yang berasal dari latar belakang bahasa imperatif (C, C ++, Java)

Perhatikan pertama-tama bahwa tidak semua bahasa mendukungnya.

TCO berlaku untuk kasus rekursi khusus. Inti dari itu adalah, jika hal terakhir yang Anda lakukan dalam suatu fungsi adalah memanggil dirinya sendiri (misalnya memanggil dirinya sendiri dari posisi "tail"), ini dapat dioptimalkan oleh kompiler untuk bertindak seperti iterasi alih-alih rekursi standar.

Anda lihat, biasanya selama rekursi, runtime perlu melacak semua panggilan rekursif, sehingga ketika seseorang kembali dapat melanjutkan pada panggilan sebelumnya dan seterusnya. (Coba tuliskan secara manual hasil dari panggilan rekursif untuk mendapatkan ide visual tentang bagaimana ini bekerja.) Melacak semua panggilan membutuhkan ruang, yang menjadi signifikan ketika fungsi panggilan itu sendiri banyak. Tetapi dengan TCO, itu hanya bisa mengatakan "kembali ke awal, hanya saja kali ini mengubah nilai parameter ke yang baru." Itu bisa melakukan itu karena tidak ada setelah panggilan rekursif merujuk pada nilai-nilai itu.

Contoh minimal GCC runnable dengan analisis pembongkaran x86

Mari kita lihat bagaimana GCC dapat secara otomatis melakukan optimasi panggilan ekor untuk kita dengan melihat rakitan yang dihasilkan.

Ini akan menjadi contoh yang sangat konkret dari apa yang disebutkan dalam jawaban lain seperti https://stackoverflow.com/a/9814654/895245 bahwa pengoptimalan dapat mengonversi panggilan fungsi rekursif ke loop.

Hal ini pada gilirannya menghemat memori dan meningkatkan kinerja, karena akses memori sering kali merupakan hal utama yang membuat program menjadi lambat saat ini .

Sebagai masukan, kami memberikan GCC faktorial berbasis naive stack yang tidak dioptimalkan:

tail_call.c

#include <stdio.h>
#include <stdlib.h>

unsigned factorial(unsigned n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(int argc, char **argv) {
    int input;
    if (argc > 1) {
        input = strtoul(argv[1], NULL, 0);
    } else {
        input = 5;
    }
    printf("%u\n", factorial(input));
    return EXIT_SUCCESS;
}

GitHub hulu .

Kompilasi dan bongkar:

gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
  -o tail_call.out tail_call.c
objdump -d tail_call.out

di mana -foptimize-sibling-callsnama generalisasi panggilan ekor menurut man gcc:

   -foptimize-sibling-calls
       Optimize sibling and tail recursive calls.

       Enabled at levels -O2, -O3, -Os.

seperti yang disebutkan di: Bagaimana cara saya memeriksa apakah gcc melakukan optimasi rekursi ekor?

Saya memilih -O1karena:

• optimasi tidak dilakukan dengan -O0. Saya menduga bahwa ini karena diperlukan transformasi menengah yang hilang.
• -O3 menghasilkan kode efisien yang tidak saleh yang tidak akan sangat mendidik, meskipun juga dioptimalkan untuk panggilan ekor.

Disassembly dengan -fno-optimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       89 f8                   mov    %edi,%eax
    1147:       83 ff 01                cmp    $0x1,%edi
    114a:       74 10                   je     115c <factorial+0x17>
    114c:       53                      push   %rbx
    114d:       89 fb                   mov    %edi,%ebx
    114f:       8d 7f ff                lea    -0x1(%rdi),%edi
    1152:       e8 ee ff ff ff          callq  1145 <factorial>
    1157:       0f af c3                imul   %ebx,%eax
    115a:       5b                      pop    %rbx
    115b:       c3                      retq
    115c:       c3                      retq

Dengan -foptimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       b8 01 00 00 00          mov    $0x1,%eax
    114a:       83 ff 01                cmp    $0x1,%edi
    114d:       74 0e                   je     115d <factorial+0x18>
    114f:       8d 57 ff                lea    -0x1(%rdi),%edx
    1152:       0f af c7                imul   %edi,%eax
    1155:       89 d7                   mov    %edx,%edi
    1157:       83 fa 01                cmp    $0x1,%edx
    115a:       75 f3                   jne    114f <factorial+0xa>
    115c:       c3                      retq
    115d:       89 f8                   mov    %edi,%eax
    115f:       c3                      retq

Perbedaan utama antara keduanya adalah:

• yang -fno-optimize-sibling-callsmenggunakan callq, yang merupakan khas non-dioptimalkan fungsi panggilan.

  Instruksi ini mendorong alamat kembali ke tumpukan, sehingga menambahnya.

  Selanjutnya, versi ini juga tidak push %rbx, yang mendorong %rbxke tumpukan .

  GCC melakukan ini karena ia menyimpan edi, yang merupakan argumen fungsi pertama ( n) ke ebx, kemudian panggilan factorial.

  GCC perlu melakukan ini karena sedang mempersiapkan panggilan lain factorial, yang akan menggunakan yang baru edi == n-1.

  Ia memilih ebxkarena register ini disimpan dengan sendirinya : Apa register disimpan melalui fungsi panggilan x86-64 linux sehingga subkunci untuk factorialtidak akan mengubahnya dan kehilangan n.

• yang -foptimize-sibling-callstidak menggunakan instruksi yang mendorong ke stack: hanya melakukan gotomelompat dalam factorialdengan petunjuk jedan jne.

  Oleh karena itu, versi ini setara dengan loop sementara, tanpa panggilan fungsi apa pun. Penggunaan tumpukan konstan.

Diuji di Ubuntu 18.10, GCC 8.2.

Lihat di sini:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

Seperti yang mungkin Anda ketahui, panggilan fungsi rekursif dapat mendatangkan malapetaka pada tumpukan; mudah kehabisan ruang stack. Optimasi panggilan ekor adalah cara Anda membuat algoritma gaya rekursif yang menggunakan ruang stack konstan, oleh karena itu tidak tumbuh dan tumbuh dan Anda mendapatkan kesalahan stack.

1. Kita harus memastikan bahwa tidak ada pernyataan kebagian fungsi itu sendiri .. dijaga dengan panggilan fungsi menjadi hal terakhir dalam fungsi callee.

2. Rekursi skala besar dapat menggunakan ini untuk optimisasi, tetapi dalam skala kecil, overhead instruksi untuk membuat panggilan fungsi panggilan ekor mengurangi tujuan sebenarnya.

3. TCO dapat menyebabkan fungsi yang berjalan selamanya:

   void eternity()
   {
       eternity();
   }
   

Pendekatan fungsi rekursif memiliki masalah. Itu membangun tumpukan panggilan ukuran O (n), yang membuat total biaya memori kami O (n). Ini membuatnya rentan terhadap kesalahan stack overflow, di mana tumpukan panggilan terlalu besar dan kehabisan ruang.

Skema Tail Tail Optimization (TCO). Di mana ia dapat mengoptimalkan fungsi rekursif untuk menghindari penumpukan panggilan yang tinggi dan karenanya menghemat biaya memori.

Ada banyak bahasa yang melakukan TCO seperti (JavaScript, Ruby dan beberapa C) sedangkan Python dan Java tidak melakukan TCO.

Bahasa JavaScript telah dikonfirmasi menggunakan :) http://2ality.com/2015/06/tail-call-optimization.html

Dalam bahasa fungsional, optimisasi panggilan ekor adalah seolah-olah panggilan fungsi dapat mengembalikan ekspresi yang dievaluasi sebagian sebagai hasilnya, yang kemudian akan dievaluasi oleh pemanggil.

f x = g x

f 6 berkurang menjadi g 6. Jadi jika implementasinya dapat mengembalikan g 6 sebagai hasilnya, dan kemudian memanggil ekspresi itu akan menghemat bingkai tumpukan.

Juga

f x = if c x then g x else h x.

Mengurangi ke f 6 ke g 6 atau h 6. Jadi jika implementasi mengevaluasi c 6 dan menemukan itu benar maka itu dapat mengurangi,

if true then g x else h x ---> g x

f x ---> h x

Penerjemah optimasi panggilan non-ekor sederhana mungkin terlihat seperti ini,

class simple_expresion
{
    ...
public:
    virtual ximple_value *DoEvaluate() const = 0;
};

class simple_value
{
    ...
};

class simple_function : public simple_expresion
{
    ...
private:
    simple_expresion *m_Function;
    simple_expresion *m_Parameter;

public:
    virtual simple_value *DoEvaluate() const
    {
        vector<simple_expresion *> parameterList;
        parameterList->push_back(m_Parameter);
        return m_Function->Call(parameterList);
    }
};

class simple_if : public simple_function
{
private:
    simple_expresion *m_Condition;
    simple_expresion *m_Positive;
    simple_expresion *m_Negative;

public:
    simple_value *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive.DoEvaluate();
        }
        else
        {
            return m_Negative.DoEvaluate();
        }
    }
}

Juru bahasa optimasi panggilan ekor mungkin terlihat seperti ini,

class tco_expresion
{
    ...
public:
    virtual tco_expresion *DoEvaluate() const = 0;
    virtual bool IsValue()
    {
        return false;
    }
};

class tco_value
{
    ...
public:
    virtual bool IsValue()
    {
        return true;
    }
};

class tco_function : public tco_expresion
{
    ...
private:
    tco_expresion *m_Function;
    tco_expresion *m_Parameter;

public:
    virtual tco_expression *DoEvaluate() const
    {
        vector< tco_expression *> parameterList;
        tco_expression *function = const_cast<SNI_Function *>(this);
        while (!function->IsValue())
        {
            function = function->DoCall(parameterList);
        }
        return function;
    }

    tco_expresion *DoCall(vector<tco_expresion *> &p_ParameterList)
    {
        p_ParameterList.push_back(m_Parameter);
        return m_Function;
    }
};

class tco_if : public tco_function
{
private:
    tco_expresion *m_Condition;
    tco_expresion *m_Positive;
    tco_expresion *m_Negative;

    tco_expresion *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive;
        }
        else
        {
            return m_Negative;
        }
    }
}