GC: （Garbage Collector懒闷， 垃圾回收器）
在 CPython 中
垃圾回收采用了引用計數(shù)+ 標(biāo)記-清除 + 分代回收 的組合回收方法。
即給每個對象設(shè)置引用計數(shù)宗弯，當(dāng)引用計數(shù)為0就立即回收內(nèi)存；
但是由于對象之間存在互相引用的問題搂妻，單單使用引用計數(shù)是不夠的蒙保，于是引入了標(biāo)記-清除算法來回收來遍歷引用到了的對象，將沒有引用到的對象銷毀
標(biāo)記-清除方法需要消耗很多時間欲主，為了提升效率邓厕，又引入了分代回收，將多次檢測都有效的對象升級為下一代扁瓢，代數(shù)越高則檢查的次數(shù)就越少（共3代详恼，每代實際上就是一個鏈表），以此來增加效率
Micropython GC
與 CPython不同引几，Micropython 只使用了 標(biāo)記-清除算法昧互，可以說是教科書般的標(biāo)記-清除算法實現(xiàn)了（官方的說法2333）
這里 GC 不單單包括了垃圾回收，實際上內(nèi)存分配方法也包含在了里面伟桅，大致上包含了以下幾個點：
- 系統(tǒng)預(yù)分配一塊內(nèi)存給
GC使用敞掘，之后所有的操作都在這塊內(nèi)存上進行 - 然后分配和釋放時根據(jù)分配算法進行分配和釋放（后面再詳細說明）
- 在以下幾個情況執(zhí)行回收（使用
標(biāo)記-清除算法(mark-sweep)：- 無法分配內(nèi)存
- 設(shè)置了回收閾值(
threshold)，當(dāng)距離上幾次回收后分配的空間（塊）數(shù)量打到了設(shè)置的閾值楣铁，則自動進行回收渐逃。當(dāng)然為了減少回收次數(shù)（某種意義上的）可以禁用這個功能 - 手動調(diào)用函數(shù)進行回收
Micropython 中的 GC 詳細分析
數(shù)據(jù)儲存結(jié)構(gòu)
為了簡化程序，uPy將初始化時獲得的一段連續(xù)內(nèi)存區(qū)域分成3部分:
- 儲存數(shù)據(jù)塊分配信息民褂，標(biāo)記內(nèi)存分配情況茄菊，稱為
ATB(alloc table) - 儲存銷毀對象時是否需要調(diào)用析構(gòu)函數(shù)（finaliser）（
__del__)，稱為FTB(finaliser table) - 實際儲存數(shù)據(jù)的區(qū)域赊堪，稱為內(nèi)存池（pool）面殖，由多個塊（block）組成
uPy 分配內(nèi)存的最小單位是塊(block)(比如設(shè)置為16或者32字節(jié))，所以ATB FTB中記錄也是以塊為單位記錄的哭廉。
其中 ATB 標(biāo)記每個塊的狀態(tài)脊僚，包括 free， head（多個連續(xù)分配的塊的開始（頭））遵绰， tail（多個連續(xù)分配的塊的除了頭部塊以外的塊）辽幌， mark（標(biāo)記了的頭部，在回收時（collect）中才會標(biāo)記） 幾種狀態(tài)椿访，每兩位表示一個block狀態(tài)乌企，即每個字節(jié)可以表示4個block的狀態(tài)
FTB 則標(biāo)記是否使用 finaliser，每位表示一個block是否使用finaliser成玫，即每個字節(jié)表示8個block是否使用finaliser
名詞
- block： 塊加酵，分配的最小單位拳喻，比如設(shè)置為16或者32字節(jié)。
- finaliser：這里可理解成析構(gòu)猪腕，調(diào)用 類的
__del__方法冗澈，（mpy目前(2019.5)還沒有實現(xiàn)調(diào)用用戶類的__del__方法） - ATB: alloc table，標(biāo)記每個block的狀態(tài)陋葡，包括
free亚亲，head（多個連續(xù)分配的塊的開始（頭）），tail（多個連續(xù)分配的塊的除了頭部塊以外的塊）腐缤，mark（標(biāo)記了的頭部） 幾種狀態(tài)朵栖，每兩位表示一個block狀態(tài)，即每個字節(jié)可以表示4個block的狀態(tài) - FTB: finaliser table標(biāo)記是否使用 finaliser柴梆，每位表示一個block是否使用finaliser，即每個字節(jié)表示8個block是否使用finaliser
- pool: 實際分配給用戶使用的空間（alloc 返回的地址）终惑，也就是數(shù)據(jù)實際儲存的位置绍在，最小單位是塊
- (block) chain: （塊）鏈，分配內(nèi)存的最小單位是塊雹有，比如一個塊32字節(jié)偿渡，如果用戶程序需要分配36個字節(jié)，則直接分配2個塊即64字節(jié)霸奕，這兩個塊稱為一個塊鏈（chain）溜宽，我們標(biāo)記第一個塊為頭，后面的所有塊為尾(注意不是最后一個质帅，是除了頭的所有塊）
- reachable object： 可達的對象适揉，即可以通過變量引用引用得到的對象
- root object： 根節(jié)點對象，主要是指
uPy的一些特殊變量煤惩，比如局部字典嫉嘀、全局字典等，Micropython中代碼如下：
////////////////////////////////////////////////////////////
// START ROOT POINTER SECTION
// Everything that needs GC scanning must start here, and
// is followed by state in the mp_state_vm_t structure.
//
mp_obj_dict_t *dict_locals;
mp_obj_dict_t *dict_globals;
nlr_buf_t *nlr_top;
.
.
.
//
// END ROOT POINTER SECTION
////////////////////////////////////////////////////////////
初始化
指定一塊內(nèi)存區(qū)域用來內(nèi)存分配使用：
void gc_init(void *start, void *end)
#define BYTES_PER_WORD (sizeof(mp_uint_t))
#define MICROPY_BYTES_PER_GC_BLOCK (4 * BYTES_PER_WORD)
#define BYTES_PER_BLOCK (MICROPY_BYTES_PER_GC_BLOCK)
end = (void*)((uintptr_t)end & (~(BYTES_PER_BLOCK - 1))); // 內(nèi)存對齊
從GC分配空間
uPy分配內(nèi)存時以一個塊為最小單位進行分配魄揉，并且對這些塊進行了標(biāo)記剪侮，初始化時所有塊的標(biāo)記都是free
每次分配，都至少分配1個塊洛退，稱這次分配的空間為一個鏈（chain瓣俯，即分配的連續(xù)內(nèi)存大于一個塊的大小時，比如一個塊32字節(jié)兵怯，需要分配124字節(jié)實際分配了128字節(jié)即128/32=4塊彩匕，稱這4塊為一個鏈（chain）），開頭第一個塊標(biāo)記為head媒区，后面的塊都標(biāo)記為tail推掸。 在代碼中桶蝎，使用m_new(type, size)函數(shù)即可分配
另外，Micropython 有一個 finaliser的功能谅畅，可以簡單地理解為登渣，如果在釋放對象時會嘗試去調(diào)用它的__del__方法（如果存在的話），在創(chuàng)建對象的時候會在對應(yīng)的 FTB 中設(shè)置標(biāo)記毡泻，表示這個block在釋放時需要調(diào)用__del__方法胜茧，只需要設(shè)置這一個block,比如一個對象占用了從第50到100共50個block， 申請時會在ATB的第50個block設(shè)置head標(biāo)記仇味，剩下的全部設(shè)置tail呻顽，會在FTB的第50個位設(shè)置標(biāo)記（置1），其它位置不置1丹墨。
注意廊遍，使用finaliser的時候不再使用m_new，而是使用m_new_obj_with_finaliser（）來進行分配贩挣，這個函數(shù)里面會自動標(biāo)記喉前。 另外如果使用這個函數(shù)創(chuàng)建的對象必須是一個有效的Micropython對象定義，比如
typedef struct{
int a;
int b;
} data_t;
data_t* p = m_new(data_t, 1);
這只是一個普通的結(jié)構(gòu)體王财；
在每個定義的第一個成員必須是mp_obj_base_t base卵迂；，在實例化對象的時候必須指定base.type（type是mp_obj_type_t類型）绒净， 比如
typedef struct{
mp_obj_base_t base;
int a;
int b;
}
data_t* p = m_new(data_t, 1);
p->base.type = NULL;
如果使用了m_new_obj_with_finaliser來創(chuàng)建對象见咒，但是結(jié)構(gòu)體里面第一個成員又不是base，則最后在調(diào)用finaliser時就會出現(xiàn)致命的問題挂疆，可能會導(dǎo)致程序崩潰
比如 I2C 模塊中：
typedef struct _machine_hard_i2c_obj_t {
mp_obj_base_t base;
i2c_device_number_t i2c;
machine_i2c_mode_t mode;
uint32_t freq; // Hz
uint32_t timeout; // reserved
uint16_t addr;
uint8_t addr_size;
mp_obj_t on_receive;
mp_obj_t on_transmit;
mp_obj_t on_event;
int pin_scl;
int pin_sda;
} machine_hard_i2c_obj_t;
STATIC const mp_rom_map_elem_t machine_i2c_locals_dict_table[] = {
{ MP_ROM_QSTR(MP_QSTR_init), MP_ROM_PTR(&machine_i2c_init_obj) },
{ MP_ROM_QSTR(MP_QSTR___del__), MP_ROM_PTR(&machine_i2c_deinit_obj) },
改览。
。
缤言。
};
MP_DEFINE_CONST_DICT(mp_machine_soft_i2c_locals_dict, machine_i2c_locals_dict_table);
const mp_obj_type_t machine_hard_i2c_type = {
{ &mp_type_type },
.name = MP_QSTR_I2C,
.print = machine_hard_i2c_print,
.make_new = machine_hard_i2c_make_new,
.protocol = &machine_hard_i2c_p,
.locals_dict = (mp_obj_dict_t*)&mp_machine_soft_i2c_locals_dict,
};
在machine_hard_i2c_make_new函數(shù)中恃疯，即用戶通過i2c = machine.I2C()來創(chuàng)建對象的時候調(diào)用的函數(shù)中，會創(chuàng)建一個machine_hard_i2c_obj_t的對象墨闲，如果不使用finaliser：
machine_hard_i2c_obj_t *self = m_new_obj(machine_hard_i2c_obj_t);
self->base.type = &machine_hard_i2c_type;
.
.
.
return MP_OBJ_FROM_PTR(self);
這樣在對象銷毀時不會調(diào)用__del__方法今妄，如果需要自動調(diào)用：
machine_hard_i2c_obj_t *self = m_new_obj_with_finaliser(machine_hard_i2c_obj_t);
self->base.type = &machine_hard_i2c_type;
內(nèi)存分配策略
一塊連續(xù)內(nèi)存，多個塊鸳碧，從左到右依次查找盾鳞，直到找到符合大小的一塊連續(xù)區(qū)域。
會有一個指針指向最左邊的空閑的塊瞻离，每次從這個指針查找的地方往右開始找腾仅，一旦最左邊的空閑塊位置發(fā)生了變動（更左邊的已經(jīng)分配的塊得到了釋放或者最左邊的空閑塊被分配），這個指針的值也要及時更新套利。
當(dāng)然推励，這種分配算法簡單有效鹤耍，但是也沒法避免內(nèi)存碎片的問題
內(nèi)存釋放
調(diào)用釋放函數(shù)時直接設(shè)置對應(yīng)塊的標(biāo)識為free即可，
記得更新指向最左邊空閑塊的指針
回收過程（標(biāo)記-清除(mark-sweep)算法）
執(zhí)行回收的時機在文章開頭已經(jīng)介紹验辞，這里闡述回收過程
uPy中實現(xiàn)自動垃圾回收使用了 mark-sweep 算法稿黄， 在gc_collect()函數(shù)中實現(xiàn)：
遍歷
root objects找到所有能夠找到的有效塊（通過查找mp_state_ctx變量中保存的一系列變量，比如局部字典跌造、全局字典杆怕、）對這些找到的塊進行標(biāo)記，所有標(biāo)記為
head標(biāo)識的標(biāo)記為mark壳贪， 那些已經(jīng)無法找到的塊則仍然為head標(biāo)識遍歷所有塊陵珍，對所有的標(biāo)記為
mark的塊重新標(biāo)記為head，對標(biāo)記為head的塊則進行銷毀（標(biāo)記為free）违施，這些標(biāo)記為head的塊是在上一步?jīng)]有找到的互纯，也就是說內(nèi)存已經(jīng)是垃圾內(nèi)存了，所以直接銷毀銷毀對象時檢查是否需要調(diào)用
finaliser（檢查FTB標(biāo)記）磕蒲，即嘗試調(diào)用對象的__del__方法（如果存在的話）留潦，并且清除FTB標(biāo)記
注意到這里使用了遍歷這個詞，雖然實現(xiàn)起來簡單有效亿卤，但是注定效率不算高，所以寫對時間要求高的micropython程序需要注意回收的時機鹿霸，能手動定期回收也不錯排吴。(實際測試在 MaixPy 運行在400MHz的k210上collect()一次需要花費600us+
使用 GC 注意的地方
C層面使用 GC 注意
底層使用的變量被自動回收了（變量沒有鏈接到root objects，gc無法知道變量仍然有用）懦鼠，再使用時出錯
使用gc創(chuàng)建變量不能像平時使用malloc函數(shù)一樣使用钻哩， malloc只要創(chuàng)建了不free就會一直存在，但是gc通過alloc創(chuàng)建的變量如果沒有加入到gc遍歷時能遍歷到的變量中肛冶，gc就會認為是垃圾街氢，會回收，如果我們的c程序邏輯既沒有把它加入到gc睦袖，可以遍歷到的變量中珊肃，還把它當(dāng)成和普通一樣的malloc的變量使用，就會出現(xiàn)bug
因為 內(nèi)存不夠時會自動回收馅笙，那些沒有被引用的資源自然就會被釋放掉了伦乔，如果是修改 micropython的源碼時需要注意，比如在c層面創(chuàng)建了一個str（vstr_init）董习，然后添加字符（vstr_add_strn）烈和，可能底層某個地方在使用這個變量，并且在某個時候會手動調(diào)用vstr_clear函數(shù)進行清除皿淋，但是由于這個變量沒有被python引用招刹，在系統(tǒng)回收垃圾時有可能會將其回收掉恬试，然后在后來的某個時間c在某個地方調(diào)用了vstr_clear去手動刪除字符串，這時會出錯疯暑，因為已經(jīng)被free過了
解決方法就是將這個變量被系統(tǒng)的變量引用一下
（比如創(chuàng)建一個變量鏈接到global變量中,或者當(dāng)成python層面的某個返回值训柴，讓python層面有確定的使用范圍（比如img = image.Image()， 在這個方法中缰儿，c層面使用了gc分配內(nèi)存畦粮，python層面img變量引用了，只要img變量有效它就不會被自動回收）乖阵，
或者干脆不要使用gc來創(chuàng)建宣赔，可以使用靜態(tài)數(shù)組或者其它不屬于gc管理的內(nèi)存。
可以看MaixPy的a21188b23fa1853b211c0ad65b2bfc4bef8343b2（fix str bug(for ide)) 提交
finaliser 使用時需要注意結(jié)構(gòu)體是否是一個合法的對象形式
創(chuàng)建對象如果需要使用finaliser（使用m_new_obj_with_finaliser函數(shù)創(chuàng)建對象）瞪浸，結(jié)構(gòu)體最開始一定要有mp_obj_base_t定義的變量（base）儒将，base變量下的type來指定變量的類型，否則會出現(xiàn)嚴重問題６云选９澄谩！
注意觸發(fā)回收的時機
前面說了三種時機會觸發(fā)垃圾回收（collect)蹈矮，所以寫python程序時需要注意自動回收會不會影響到程序的性能和穩(wěn)定性砰逻，以及需不需要自己手動調(diào)用collect來主動執(zhí)行回收程序
