摘要：廣告位出售垃圾回收機(jī)制淺析與理解對(duì)垃圾回收進(jìn)行分析前，我們先來(lái)了解一些基本概念基本概念內(nèi)存管理內(nèi)存管理對(duì)于編程語(yǔ)言至關(guān)重要。里面的變量通常是局部變量函數(shù)參數(shù)等。

對(duì)垃圾回收進(jìn)行分析前，我們先來(lái)了解一些基本概念

內(nèi)存管理：內(nèi)存管理對(duì)于編程語(yǔ)言至關(guān)重要。匯編允許你操作所有東西，或者說(shuō)要求你必須全權(quán)處理所有細(xì)節(jié)更合適。C 語(yǔ)言中雖然標(biāo)準(zhǔn)庫(kù)函數(shù)提供一些內(nèi)存管理支持，但是對(duì)于之前調(diào)用 malloc 申請(qǐng)的內(nèi)存，還是依賴于你親自 free 掉。從C++、Python、Swift 和 Java 開(kāi)始，才在不同程度上支持內(nèi)存管理。

內(nèi)存壓縮：對(duì)內(nèi)存碎片進(jìn)行壓縮。（和win10的那個(gè)“內(nèi)存壓縮”不太一樣啦）

win10內(nèi)存壓縮：物理內(nèi)存已經(jīng)見(jiàn)底，將一部分不常使用的內(nèi)存數(shù)據(jù)打包壓縮起來(lái)，等到有程序需要訪問(wèn)那些數(shù)據(jù)的時(shí)候，再解壓縮出來(lái)。

引用與指針：

引用被創(chuàng)建的同時(shí)必須被初始化（指針則可以在任何時(shí)候被初始化）。

不能有NULL 引用，引用必須與合法的存儲(chǔ)單元關(guān)聯(lián)（指針則可以是NULL）。

一旦引用被初始化，就不能改變引用的關(guān)系（指針則可以隨時(shí)改變所指的對(duì)象）。

引用只是某塊內(nèi)存的別名。

實(shí)際上“引用”可以做的任何事情“指針”也都能夠做，為什么還要“引用” 這東西？

答案是“用適當(dāng)?shù)墓ぞ咦銮∪缙浞值墓ぷ鳌薄１热缯f(shuō)，某人需要一份證明，本來(lái)在文件上蓋                上公章的印子就行了，如果把取公章的鑰匙交給他，那么他就獲得了不該有的權(quán)利。（什么情況下，就用什么對(duì)策）
6. 為什么還要說(shuō)“只有指針，沒(méi)有引用是一個(gè)重要改變？”？
 答案是雖然引用在某些情況下好用，但他也會(huì)導(dǎo)致致命錯(cuò)誤。如下：
```
 char *pc = 0; // 設(shè)置指針為空值 
 char& rc = *pc; // 讓引用指向空值 
```
 這是非常有害的，毫無(wú)疑問(wèn)。結(jié)果將是不確定的（編譯器能產(chǎn)生一些輸出，導(dǎo)致任何事情都有可能發(fā)生），應(yīng)該躲開(kāi)寫出這樣代碼的人除非他們同意改正錯(cuò)誤。如果你擔(dān)心這樣的代碼會(huì)出現(xiàn)在你的軟件里，那么你最好完全避免使用引用，要不然就去讓更優(yōu)秀的程序員去做。   
7. 最后上附圖，幫助理解

堆（heap）和棧（stack）

平常說(shuō)的“堆?！逼鋵?shí)是棧。

棧，就是那些由編譯器在需要的時(shí)候分配，在不需要的時(shí)候自動(dòng)清除的變量的存儲(chǔ)區(qū)。里面的變量通常是局部變量、函數(shù)參數(shù)等。

堆，就是那些由new分配的內(nèi)存塊，他們的釋放編譯器不去管，由我們的應(yīng)用程序去控 制，一般一個(gè)new就要對(duì)應(yīng)一個(gè)delete。如果程序員沒(méi)有釋放掉，那么在程序結(jié)束后，操作系統(tǒng)會(huì)自動(dòng)回收。

程序的棧結(jié)構(gòu)

程序的地址空間布局： 程序運(yùn)行靠四個(gè)東西：代碼、棧、堆、數(shù)據(jù)段。代碼段主要存放的就是可執(zhí)行文件(通常可執(zhí)行文件內(nèi)，含有以二進(jìn)制編碼的微處理器指令，也因此可執(zhí)行文件有時(shí)稱為二進(jìn)制文件)中的代碼；數(shù)據(jù)段存放的就是程序中全局變量和靜態(tài)變量；堆中是程序的動(dòng)態(tài)內(nèi)存區(qū)域，當(dāng)程序使用malloc或new得到的內(nèi)存是來(lái)自堆的；棧中維護(hù)的是函數(shù)調(diào)用的上下文，離開(kāi)了棧就不可能實(shí)現(xiàn)函數(shù)的調(diào)用。

棧幀： 也叫活動(dòng)記錄，保存的是一個(gè)函數(shù)調(diào)用所需要維護(hù)的所有信息。如下：
1.函數(shù)的返回地址和參數(shù)
2.臨時(shí)變量：包括函數(shù)的非靜態(tài)局部變量以及編譯器自動(dòng)生成的其它臨時(shí)變量
3.保存的上下文：包括在函數(shù)調(diào)用前后需要保存不變的寄存器值

就是它，先上圖

]

 1.返回地址:一個(gè)main函數(shù)中斷執(zhí)行的執(zhí)行點(diǎn).
 2.ebp:指向函數(shù)活動(dòng)記錄的一個(gè)固定位置，ebp又被稱為幀指針.固定位置是，這樣在函數(shù)返回的時(shí)候，ebp就可以通過(guò)這個(gè)恢復(fù)到調(diào)用前的值。
 3.esp始終指向棧頂，因此隨著函數(shù)的執(zhí)行，它總是變化的。
 4.入棧順序：先壓此次調(diào)用函數(shù)參數(shù)入棧，接著是main函數(shù)返回地址，然后是ebp等寄存器。

Link：C程序的函數(shù)棧作用機(jī)理（這個(gè)講得好，有實(shí)例，所以不再熬述）

這里我們對(duì)比了解不同的 “找到需要標(biāo)記的對(duì)象”的方法

引用計(jì)數(shù)法

給對(duì)象中添加一個(gè)引用計(jì)數(shù)器，每當(dāng)有一個(gè)地方引用它時(shí)，計(jì)數(shù)器值就加1；當(dāng)引用失效時(shí)， 計(jì)數(shù)器值就減1；任何時(shí)刻計(jì)數(shù)器為0的對(duì)象就是不可能再被使用的。如下圖所示：

優(yōu)點(diǎn)：引用計(jì)數(shù)收集器可以很快地執(zhí)行，交織在程序的運(yùn)行之中。這個(gè)特性對(duì)于程序不能被長(zhǎng)時(shí)間打斷的實(shí)時(shí)環(huán)境很有利。
缺點(diǎn)：很難處理循環(huán)引用，比如圖中相互引用的兩個(gè)對(duì)象則無(wú)法釋放。
應(yīng)用：Python 和 Swift 采用引用計(jì)數(shù)方案。   

可達(dá)性分析算法（根搜索算法）

從GC Roots（每種具體實(shí)現(xiàn)對(duì)GC Roots有不同的定義）作為起點(diǎn)，向下搜索它們引用的對(duì)象，可以生成一棵引用樹，樹的節(jié)點(diǎn)視為可達(dá)對(duì)象，反之視為不可達(dá)。如下圖所示：

接下來(lái)補(bǔ)充幾個(gè)概念幫助理解（以java為例）：

GC Roots對(duì)象：
虛擬機(jī)棧（幀棧中的本地變量表）中引用的對(duì)象。
方法區(qū)中靜態(tài)屬性引用的對(duì)象。
方法區(qū)中常量引用的對(duì)象。
本地方法棧中JNI引用的對(duì)象。

本地方法棧則為虛擬機(jī)所使用的Native方法服務(wù)。
Native方法是指本地方法，當(dāng)在方法中調(diào)用一些不是由java語(yǔ)言寫的代碼或者在方法中用java語(yǔ)言直接操縱計(jì)算機(jī)硬件。
JNI：Java Native Interface縮寫，允許Java代碼和其他語(yǔ)言寫的代碼進(jìn)行交互。
上述如圖，關(guān)于root區(qū)域的詳細(xì)解釋參考這里

這里我們介紹幾種不同的 “標(biāo)記對(duì)象”的方法

保守法

將所有堆上對(duì)齊的字都認(rèn)為是指針，那么有些數(shù)據(jù)就會(huì)被誤認(rèn)為是指針。于是某些實(shí)際是數(shù)字的假指針，會(huì)背誤認(rèn)為指向活躍對(duì)象，導(dǎo)致內(nèi)存泄露（假指針指向的對(duì)象可能是死對(duì)象，但依舊有指針指向——這個(gè)假指針指向它）同時(shí)我們不能移動(dòng)任何內(nèi)存區(qū)域。

編譯器提示法

如果是靜態(tài)語(yǔ)言，編譯器能夠告訴我們每個(gè)類當(dāng)中指針的具體位置，而一旦我們知道對(duì)象時(shí)哪個(gè)類實(shí)例化得到的，就能知道對(duì)象中所有指針。這是JVM實(shí)現(xiàn)垃圾回收的方式，但這種方式并不適合JS這樣的動(dòng)態(tài)語(yǔ)言

標(biāo)記指針?lè)?/p>

標(biāo)記指針?lè)ǎ哼@種方法需要在每個(gè)字末位預(yù)留一位來(lái)標(biāo)記這個(gè)字段是指針還是數(shù)據(jù)。這種方法需要編譯器支持，但實(shí)現(xiàn)簡(jiǎn)單，而且性能不錯(cuò)。V8采用的是這種方式。

位圖標(biāo)記(Go語(yǔ)言為例)

非侵入式標(biāo)記位定義
既然垃圾回收算法要求給對(duì)象加上垃圾回收的標(biāo)記，顯然是需要有標(biāo)記位的。一般的做法
會(huì)將對(duì)象結(jié)構(gòu)體中加上一個(gè)標(biāo)記域，一些優(yōu)化的做法會(huì)利用對(duì)象指針的低位進(jìn)行標(biāo)記，這
都只是些奇技淫巧罷了。Go沒(méi)有這么做，它的對(duì)象和C的結(jié)構(gòu)體對(duì)象完全一致，使用的是
非侵入式的標(biāo)記位。

具體實(shí)現(xiàn)
堆區(qū)域?qū)?yīng)了一個(gè)標(biāo)記位圖區(qū)域，堆中每個(gè)字(不是byte，而是word)都會(huì)在標(biāo)記位區(qū)域
中有對(duì)應(yīng)的標(biāo)記位。每個(gè)機(jī)器字(32位或64位)會(huì)對(duì)應(yīng)4位的標(biāo)記位。因此，64位系統(tǒng)中
相當(dāng)于每個(gè)標(biāo)記位圖的字節(jié)對(duì)應(yīng)16個(gè)堆中的字節(jié)。

雖然是一個(gè)堆字節(jié)對(duì)應(yīng)4位標(biāo)記位，但標(biāo)記位圖區(qū)域的內(nèi)存布局并不是按4位一組，而是
16個(gè)堆字節(jié)為一組，將它們的標(biāo)記位信息打包存儲(chǔ)的。每組64位的標(biāo)記位圖從上到下依
次包括：

16位的 特殊位 標(biāo)記位
16位的 垃圾回收 標(biāo)記位
16位的 無(wú)指針/塊邊界 的標(biāo)記位
16位的 已分配 標(biāo)記位

這樣設(shè)計(jì)使得對(duì)一個(gè)類型的相應(yīng)的位進(jìn)行遍歷很容易。

前面提到堆區(qū)域和堆地址的標(biāo)記位圖區(qū)域是分開(kāi)存儲(chǔ)的，其實(shí)它們是以
mheap.arena_start地址為邊界，向上是實(shí)際使用的堆地址空間，向下則是標(biāo)記位圖區(qū)
域。以64位系統(tǒng)為例，計(jì)算堆中某個(gè)地址的標(biāo)記位的公式如下：

偏移 = 地址 - mheap.arena_start
標(biāo)記位地址 = mheap.arena_start - 偏移/16 - 1
移位 = 偏移 % 16
標(biāo)記位 = *標(biāo)記位地址 >> 移位

然后就可以通過(guò) (標(biāo)記位 & 垃圾回收標(biāo)記位),(標(biāo)記位 & 分配位),等來(lái)測(cè)試相應(yīng)的位。

(也就是說(shuō)，本來(lái)64位是一個(gè)字，需要4位標(biāo)記位。但是，為了與字長(zhǎng)相對(duì)，16個(gè)標(biāo)記位
放一起（剛好一個(gè)字長(zhǎng)）一起表示16個(gè)字。并且每類標(biāo)記位都放在一起
AA..AABB...BB)

接下來(lái)補(bǔ)充幾個(gè)概念幫助理解：

為什么要判斷哪些是數(shù)據(jù)，哪些是指針？
假設(shè)堆中有一個(gè)long的變量，它的值是8860225560。但是我們不知道它的類型是
long，所以在進(jìn)行垃圾回收時(shí)會(huì)把個(gè)當(dāng)作指針處理，這個(gè)指針引用到了0x2101c5018位
置。假設(shè)0x2101c5018碰巧有某個(gè)對(duì)象，那么這個(gè)對(duì)象就無(wú)法被釋放了，即使實(shí)際上已
經(jīng)沒(méi)任何地方使用它。

由于沒(méi)有類型信息，我們并不知道這個(gè)結(jié)構(gòu)體成員不包含指針，因此我們只能對(duì)結(jié)構(gòu)體
的每個(gè)字節(jié)遞歸地標(biāo)記下去，這顯然會(huì)浪費(fèi)很多時(shí)間。
（能不能清除 變成了概率事件）。

垃圾收集器（CMS收集器為例）
幾個(gè)階段：

初始標(biāo)記
并發(fā)標(biāo)記
最終標(biāo)記
篩選回收

初始標(biāo)記僅僅是標(biāo)記一下GC Roots能直接關(guān)聯(lián)到的對(duì)象，速度很快，并發(fā)標(biāo)記就是進(jìn)行
GC Roots Trancing的過(guò)程，而重新標(biāo)記階段則是為了修正并發(fā)標(biāo)記期間因用戶程序繼
續(xù)運(yùn)行而導(dǎo)致標(biāo)記產(chǎn)生變動(dòng)那一部分對(duì)象的標(biāo)記記錄，這個(gè)階段的停頓時(shí)間比初始標(biāo)記稍
長(zhǎng)一些，但遠(yuǎn)比并發(fā)標(biāo)記時(shí)間短。

stop the world
因?yàn)槔厥盏臅r(shí)候，需要整個(gè)的引用狀態(tài)保持不變，否則判定是垃圾，等我稍后回
收的時(shí)候它又被引用了，這就全亂套了。所以，GC的時(shí)候，其他所有的程序執(zhí)行處于暫停
狀態(tài)，卡住了。
這個(gè)概念提前引入，在這里進(jìn)行對(duì)比，效果會(huì)更好些。與標(biāo)記階段對(duì)比，stop the world發(fā)生在回收階段。

這里我們介紹幾種不同的垃圾回收算法

標(biāo)記清除算法 (Mark-Sweep)

標(biāo)記-清除算法分為兩個(gè)階段：標(biāo)記階段和清除階段。標(biāo)記階段的任務(wù)是標(biāo)記出所有需要被回收的對(duì)象，清除階段就是回收被標(biāo)記的對(duì)象所占用的空間。

優(yōu)點(diǎn)是簡(jiǎn)單，容易實(shí)現(xiàn)。
缺點(diǎn)是容易產(chǎn)生內(nèi)存碎片，碎片太多可能會(huì)導(dǎo)致后續(xù)過(guò)程中需要為大對(duì)象分配空間時(shí)無(wú)法找到足夠的空間而提前觸發(fā)新的一次垃圾收集動(dòng)作。（因?yàn)闆](méi)有對(duì)不同生命周期的對(duì)象采用不同算法，所以碎片多，內(nèi)存容易滿，gc頻率高，耗時(shí)，看了后面的方法就明白了）

分代回收算法

根據(jù)對(duì)象存活的生命周期將內(nèi)存劃分為若干個(gè)不同的區(qū)域。不同區(qū)域采用不同算法（復(fù)制算法，標(biāo)記整理算法），這就是分代回收算法。

一般情況下將堆區(qū)劃分為老年代（Old Generation）和新生代（Young Generation），老年代的特點(diǎn)是每次垃圾收集時(shí)只有少量對(duì)象需要被回收，而新生代的特點(diǎn)是每次垃圾回收時(shí)都有大量的對(duì)象需要被回收，那么就可以根據(jù)不同代的特點(diǎn)采取最適合的收集算法。

1.新生代回收

新生代使用Scavenge算法進(jìn)行回收。在Scavenge算法的實(shí)現(xiàn)中，主要采用了Cheney算法。

Cheney算法是一種采用復(fù)制的方式實(shí)現(xiàn)的垃圾回收算法。
它將內(nèi)存一分為二，每一部分空間稱為semispace。在這兩個(gè)semispace中，一個(gè)處于使用狀態(tài)，另一個(gè)處于閑置狀態(tài)。
簡(jiǎn)而言之，就是通過(guò)將存活對(duì)象在兩個(gè)semispace空間之間進(jìn)行復(fù)制。

復(fù)制過(guò)程采用的是BFS（廣度優(yōu)先遍歷）的思想，從根對(duì)象出發(fā)，廣度優(yōu)先遍歷所有能到達(dá)的對(duì)象

優(yōu)點(diǎn)：時(shí)間效率上表現(xiàn)優(yōu)異（犧牲空間換取時(shí)間）
缺點(diǎn)：只能使用堆內(nèi)存的一半

新生代的空間劃分比例為什么是比例為8：1：1（不是按照上面算法中說(shuō)的1：1）？

新創(chuàng)建的對(duì)象都是放在Eden空間，這是很頻繁的，尤其是大量的局部變量產(chǎn)生的臨時(shí)對(duì)
象，這些對(duì)象絕大部分都應(yīng)該馬上被回收，能存活下來(lái)被轉(zhuǎn)移到survivor空間的往往不
多。所以，設(shè)置較大的Eden空間和較小的Survivor空間是合理的，大大提高了內(nèi)存的使
用率，緩解了Copying算法的缺點(diǎn)。

8：1：1就挺好的，當(dāng)然這個(gè)比例是可以調(diào)整的，包括上面的新生代和老年代的1：2的
比例也是可以調(diào)整的。

Eden空間和兩塊Survivor空間的工作流程是怎樣的？

具體的執(zhí)行過(guò)程是怎樣的？

假設(shè)有類似如下的引用情況：

          +----- A對(duì)象
          |
根對(duì)象----+----- B對(duì)象 ------ E對(duì)象
          |
          +----- C對(duì)象 ----+---- F對(duì)象 
                           |
                           +---- G對(duì)象 ----- H對(duì)象

    D對(duì)象

在執(zhí)行Scavenge之前，F(xiàn)rom區(qū)長(zhǎng)這幅模樣:
```
+---+---+---+---+---+---+---+---+--------+
| A | B | C | D | E | F | G | H |        |
+---+---+---+---+---+---+---+---+--------+
```
那么首先將根對(duì)象能到達(dá)的ABC對(duì)象復(fù)制到To區(qū)，于是乎To區(qū)就變成了這個(gè)樣子：
```
     allocationPtr
             ↓ 
+---+---+---+----------------------------+
| A | B | C |                            |
+---+---+---+----------------------------+
 ↑
scanPtr  

```
接下來(lái)進(jìn)入循環(huán)，掃描scanPtr所指的A對(duì)象，發(fā)現(xiàn)其沒(méi)有指針，于是乎scanPtr移動(dòng)，變成如下這樣

```
          allocationPtr
             ↓ 
+---+---+---+----------------------------+
| A | B | C |                            |
+---+---+---+----------------------------+
     ↑
  scanPtr  
```
接下來(lái)掃描B對(duì)象，發(fā)現(xiàn)其有指向E對(duì)象的指針，且E對(duì)象在From區(qū)，那么我們需要將E對(duì)象復(fù)制到allocationPtr所指的地方并移動(dòng)allocationPtr指針：

```
                allocationPtr
                 ↓ 
+---+---+---+---+------------------------+
| A | B | C | E |                        |
+---+---+---+---+------------------------+
     ↑
  scanPtr  
```
中間過(guò)程省略，具體參考[新生代的垃圾回收具體的執(zhí)行過(guò)程][3]

From區(qū)和To區(qū)在復(fù)制完成后的結(jié)果：
```
//From區(qū)
+---+---+---+---+---+---+---+---+--------+
| A | B | C | D | E | F | G | H |        |
+---+---+---+---+---+---+---+---+--------+
//To區(qū)
+---+---+---+---+---+---+---+------------+
| A | B | C | E | F | G | H |            |
+---+---+---+---+---+---+---+------------+
```

最終當(dāng)scanPtr和allocationPtr重合，說(shuō)明復(fù)制結(jié)束。
注意：如果指向老生代我們就不必考慮它了。（通過(guò)寫屏障）

對(duì)象何時(shí)晉升？

1.當(dāng)一個(gè)對(duì)象經(jīng)過(guò)多次新生代的清理依舊幸存。
2.如果To空間已經(jīng)被使用了超過(guò)25%（后面還要進(jìn)來(lái)許多新對(duì)象，不敢占用太多）
3.大對(duì)象
（其實(shí)這部分，包括次數(shù)，比例等，是視情況設(shè)置的。）

2.老生代回收

Mark-Sweep（標(biāo)記清除）

標(biāo)記清除分為標(biāo)記和清除兩個(gè)階段。
主要是標(biāo)記清除只清除死亡對(duì)象，而死亡對(duì)象在老生代中占用的比例很小，所以效率較高。

Mark-Compact（標(biāo)記整理）

標(biāo)記整理正是為了解決標(biāo)記清除所帶來(lái)的內(nèi)存碎片的問(wèn)題。

大體過(guò)程就是 雙端隊(duì)列標(biāo)記黑（鄰接對(duì)象已經(jīng)全部處理），白（待釋放垃圾），灰（鄰
接對(duì)象尚未全部處理）三種對(duì)象.
 
標(biāo)記算法的核心就是深度優(yōu)先搜索.

補(bǔ)充概念方便理解

1.觸發(fā)GC（何時(shí)發(fā)生垃圾回收？）

一般都是內(nèi)存滿了就回收，下面列舉幾個(gè)常見(jiàn)原因：
GC_FOR_MALLOC: 表示是在堆上分配對(duì)象時(shí)內(nèi)存不足觸發(fā)的GC。
GC_CONCURRENT: 當(dāng)我們應(yīng)用程序的堆內(nèi)存達(dá)到一定量，或者可以理解為快要滿的時(shí)候，系統(tǒng)會(huì)自動(dòng)觸發(fā)GC操作來(lái)釋放內(nèi)存。
GC_EXPLICIT: 表示是應(yīng)用程序調(diào)用System.gc、VMRuntime.gc接口或者收到SIGUSR1信號(hào)時(shí)觸發(fā)的GC。
GC_BEFORE_OOM: 表示是在準(zhǔn)備拋OOM異常之前進(jìn)行的最后努力而觸發(fā)的GC。

2.寫屏障（一個(gè)老年代的對(duì)象需要引用年輕代的對(duì)象，該怎么辦？）

如果新生代中的一個(gè)對(duì)象只有一個(gè)指向它的指針，而這個(gè)指針在老生代中，我們?nèi)绾闻袛?這個(gè)新生代的對(duì)象是否存活？為了解決這個(gè)問(wèn)題，需要建立一個(gè)列表用來(lái)記錄所有老生代
對(duì)象指向新生代對(duì)象的情況。每當(dāng)有老生代對(duì)象指向新生代對(duì)象的時(shí)候，我們就記錄下
來(lái)。
當(dāng)垃圾回收發(fā)生在年輕代時(shí)，只需對(duì)這張表進(jìn)行搜索以確定是否需要進(jìn)行垃圾回收，而不
是檢查老年代中的所有對(duì)象引用。

3.深度、廣度優(yōu)先搜索（為什么新生代用廣度搜索，老生代用深度搜索）

深度優(yōu)先DFS一般采用遞歸方式實(shí)現(xiàn)，處理tracing的時(shí)候，可能會(huì)導(dǎo)致棧空間溢出，所以一般采用廣度優(yōu)先來(lái)實(shí)現(xiàn)tracing（遞歸情況下容易爆棧）。
廣度優(yōu)先的拷貝順序使得GC后對(duì)象的空間局部性（memory locality）變差（相關(guān)變量散開(kāi)了）。
廣度優(yōu)先搜索法一般無(wú)回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索算法法要快些。
深度優(yōu)先搜索法占內(nèi)存少但速度較慢，廣度優(yōu)先搜索算法占內(nèi)存多但速度較快。

結(jié)合深搜和廣搜的實(shí)現(xiàn)，以及新生代移動(dòng)數(shù)量小，老生代數(shù)量大的情況，我們可以得到了解答。