編譯器構造/執行時考慮因素
在計算中，當開發人員找到能夠支援它們的科技時，總會有新工具等待出現。一個很好的例子是，50 年前，John L. McCarthy 想出了一個想法，可以在執行 Lisp 程式時自動回收不再需要的物件的記憶體。它是計算機科學中垃圾回收概念的起源。
在執行時執行的任務之一 - 當用戶執行已編譯的程式時 - 是管理分配的記憶體塊，以便透過釋放不再使用的塊來最大限度地減少記憶體使用。這被稱為“垃圾回收”。垃圾回收並非所有語言和編譯器都提供，但它已在許多最廣泛使用的語言和編譯器中實現。當正確實現時，它可以將記憶體管理的負擔從程式設計師身上卸除，並提高效能。
理想情況下，垃圾收集器（以下簡稱 GC）會刪除所有永遠不會再使用的分配。在實踐中，我們可以假設，如果存在任何引用塊的方法，它可以再次使用；如果不是，它將不會被使用（除了意外）。因此，GC 透過跟蹤某個時刻的每個引用路徑來保留可以訪問的記憶體塊，並釋放其餘記憶體塊。例如，
function concat (string1, string2)
{
new_string = alloc (string1.length + string2.length);
copy (string1, new_string);
copy (string2, new_string + string1.length);
return new_string;
}
此函式返回一個新分配的記憶體塊，它是給定兩個字串的連線。因為該函式只返回一個新字串，並且不知道它將如何使用，所以呼叫該函式的函式負責釋放它，例如
var old = null
var string = 'Writing compilers is '
if you have not finished this book {
string := concat (string, 'anything but ')
old := string
}
string := concat (string, 'fun!')
if old != null {
free (old)
}
透過讓 GC 在需要時釋放記憶體塊，以上可以簡化為
string = 'Writing compilers is '
if you have not finished this book {
string := concat (string, 'anything but ')
}
string := concat (string, 'fun!')
在實踐中，執行路徑和引用依賴關係可能比上述要複雜得多；因此，應該很容易想象 GC 將是多麼大的幫助。
在最初，有靜態分配，一段時間內，它很好。FORTRAN（大約在 1950 年代中期）根本沒有垃圾回收。一旦分配了一塊記憶體，它就會一直保持分配狀態。程式設計師無法取消分配它，即使他們嘗試了也是如此。
大約在 1958 年，Algol 實現了稱為堆疊分配的記憶體管理形式。隨後，像 C 這樣的語言實現了堆分配，它允許程式設計師隨意從可用記憶體堆中分配和取消分配記憶體。在 C 中，這是透過呼叫 malloc() 完成的。雖然這允許程式設計師非常靈活地分配和取消分配記憶體，但粗心（誤用）經常會導致記憶體洩漏和懸空指標；程式設計師錯誤不會由編譯器或執行時環境處理。
為了克服程式設計師錯誤的障礙，我們必須要麼更好地指導我們的程式設計師，要麼為記憶體管理提供更好的系統。在美國似乎湧現的一系列非認證技術學院顯然對解決前一個問題毫無作用，因此，我們必須著手解決後一個問題。
垃圾收集有兩種基本方法：引用計數和批處理（或跟蹤）。
在引用計數中，引用計數器與每個分配的物件相關聯。每當對該物件進行引用時，計數器都會遞增。當取消引用該物件時，計數器就會遞減。當計數器達到 0 時，就不存在對該分配物件的現有引用，因此可以安全地將其刪除（因為將來無法訪問它）。
當建立物件 O 時，我們還為 O 建立一個引用計數器，稱為 rc[O]。在建立時，rc[O] = 0。當我們建立對 O 的引用時，我們執行 rc[O]++。當我們銷燬對 O 的引用時，rc[O]--。當我們遞減時，我們會檢查計數器是否現在為 0。如果是，我們釋放 O。
為了允許分配記憶體，我們維護一個空閒記憶體塊列表。當我們分配塊時，我們從空閒列表中刪除它們。當我們取消分配時，我們將其新增到列表中。顯然，這種分配方法的主要缺點是碎片化；必須對記憶體進行碎片整理以允許以請求的大小分配記憶體，這會導致記憶體分配莫名其妙地變慢。為了防止這種情況，可以在某些設定時間間隔內對記憶體進行碎片整理，或者執行更復雜的取消分配以使記憶體保持連續，但解決這個問題的方案可能並不簡單。
引用計數的主要優點是易於實現，不需要在任何時間間隔內進行工作，因此避免了暫停當前操作來整理垃圾收集的必要性（這會導致在看似普通的操作期間出現難以解釋的暫停）。
但是，引用計數有一些嚴重的侷限性，即它無法檢測迴圈指標（例如，A 引用 B，B 引用 A，在這種情況下，A 和 B 都不會被收集），它對指標操作和空間的使用成本，以及由於碎片化導致的分配計算成本。其中一些問題可以透過增強引用計數來解決，但有些問題最好透過使用其他形式的垃圾收集來解決。
在批處理中，堆被視為一個有向圖，指標是分配空間（我們將其視為圖中的節點）之間的邊。要進行垃圾收集，我們遍歷圖並標記我們遇到的每個節點。如果一個節點沒有被標記，它就無法被訪問，可以安全地取消分配。
與引用計數不同，這種方法必須在特定時間執行（當然，引用計數是在普通分配和釋放的特性中執行的）。垃圾回收——當它必須在特定時間執行，而不是像引用計數那樣簡單地隨著程式執行時執行——可以在儲存空間耗盡時執行，在需要快速執行的程式碼段之前執行，或者簡單地在計算機無事可做時的空閒時間執行。最佳方法在一定程度上取決於執行的程式型別；例如，在 Microsoft Word 中，有足夠的空閒時間（使用者坐在那裡思考有趣的括號語句時），因此第三種選擇是最好的。然而，在即時系統中，最好總是在某些程式碼執行之前進行垃圾回收。
批處理依賴於對記憶體指標的準確識別。這裡有許多問題；看起來像整數的東西可能是指標，而看起來像指標的東西可能不是指標。可以專門設計一種語言來避免這種混淆，但許多流行的語言，如 C 和 C++，並非如此設計。編譯器可以在編譯時將用作指標的任何東西標記為指標，但這同樣需要額外的開銷。一些相同的方法可以在執行時應用，但會帶來額外的執行時成本。然而，無論如何實現這一點，重要的是對指標識別保持謹慎。有疑問時，最好假設某個東西是指標，而不是不是指標。畢竟，擁有額外的未收集垃圾比消除稍後將使用的塊要好得多。