C++ Polymorphic allocator，花式記憶體管理 (一)

本系列文為C++ Weekly PMR Series的整理加上我的一些想法補充之類的

不得不說這真的是一個很有用但也很麻煩的主題，我會盡我所能把細節都描述清楚，盡量啦!

3.5倍的免費性能提升，真的假的?

此系列開門見山的就拋出了3.5x這種極為誇張的效能提升數字，真的是嚇死人了，柬埔寨的薪水都沒有3.5倍那麼多

到底發生了什麼? 我們來看一下code

#include <memory_resource>
#include <list>

void StdList(benchmark::State& state) {
  for (auto _ : state) {
    std::list<int> list{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    benchmark::DoNotOptimize(list);
  }
}
// Register the function as a benchmark
BENCHMARK(StdList);

void PmrList(benchmark::State& state) {
  std::array<std::byte, 1024> buffer;
  for (auto _ : state) {
    std::pmr::monotonic_buffer_resource mem_resource(buffer.data(), buffer.size());
    std::pmr::list<int> list({1, 2, 3, 4 , 5, 6, 7, 8, 9, 10}, &mem_resource);
    benchmark::DoNotOptimize(list);
  }
}
// Register the function as a benchmark
BENCHMARK(PmrList);

在這個benchmark裡頭，我們分別在兩個測項內建構一個有10個int的list物件
- 差別在於一個是pmr::list另一個是一般常見的list
- 結果效能就有了天翻地覆的差異，How?

容器與動態記憶體配置

眾所周知，C++所提供的容器除了std::array以外，那些不用預先告知長度的容器在面對內部物件不斷增多的狀況時，就會透過operator new來向作業系統要一塊位於heap的記憶體資源
- 理所當然的，刪去一個物件時就會使用operator delete來歸還記憶體資源
老師有講過，dynamic allocation是system call對吧?會有overhead的......
- 可想而知上面的regular list耗費在allocation上的時間有多少
那我們可不可以不要做dynamic allocation?
- 還真的可以

我們的詭計，PMR

我們現在知道問題在於我們花了太多時間在heap allocation上，所以我們的目標就是不要那樣做
- 假設我們在stack上建立一塊足夠大的buffer，嗯......我指的是std::array<byte>
- 要是我能夠讓容器裡頭的new跟delete都在這塊buffer上操作那該有多好?
- 這正是PMR的用途了，我們來看一下PmrList()做了啥?
  1
  2
  3
  std::array<std::byte, 1024> buffer;
  std::pmr::monotonic_buffer_resource mem_resource(buffer.data(), buffer.size());
  std::pmr::list<int> list({1, 2, 3, 4 , 5, 6, 7, 8, 9, 10}, &mem_resource);
  在除去了benchmark相關的code後，實際上與pmr相關的部分如上，我們一行一行來看
- 我們建立了一個長度為1024*sizeof(byte)的local buffer
  - 因為她就在我們的stack上，所以叫她local buffer
- 我們將這塊buffer交給monotonic_buffer_resource管理，現在mem_resource就如同遙控器一般，誰拿著他誰就能在這塊buffer上alloc & dealloc記憶體資源
- 我們把這個遙控器交給std::pmr::list<int>，讓他能夠把內部物件配置到local buffer
現在只要物件沒有超過local buffer的大小，基本上我們就可以在沒有動態配置記憶體的狀態下操作容器了
- 我們在quick benchmark上看到的效能差距也正來自於這裡

monotonic_buffer_resource到底幹了啥?

很顯然的，關於monotonic_buffer_resource，我們對他的了解依然不夠透徹，他到底做了啥?

我們用另外一個例子來分析:

void growing_resources() {
  std::array<std::uint8_t, 16> buffer{};
  std::pmr::monotonic_buffer_resource mem_resource(buffer.data(),
                                                   buffer.size());
  std::pmr::vector<std::uint8_t> vec1(&mem_resource);
  vec1.push_back(1);
  print_buffer("1", buffer, vec1);
  vec1.push_back(2);
  print_buffer("2", buffer, vec1);
  vec1.push_back(3);
  print_buffer("3", buffer, vec1);
  vec1.push_back(4);
  print_buffer("4", buffer, vec1);
  vec1.push_back(5);
  print_buffer("5", buffer, vec1);
}

我們仔細觀察一下他的output，會發現一件很有意思的事情
- 我們知道此vector背後的記憶體空間已經不在heap上，而是在我們宣告在stack上的buffer中，但我們每push_back一個元素進去時，buffer內的狀態似乎不太對勁?
  - push_back(1) -> 1, 0, 0, ......
  - push_back(2) -> 1, 1, 2, ...... (?)
  - push_back(3) -> 1, 1, 2, 1, 2, 3, 0 ......
  - push_back(4) -> 1, 1, 2, 1, 2, 3, 4, 0 ...... (!?)
- 我們所預期的內容(1, 2, 3, 4, ...)，並沒有如我們所預期的出現，這牽涉到兩個問題
  - vector的capacity
    - vector這個容器具有提前預留一塊空間備用的功能，跟list來一個要一個不同，這個提前要多少可以透過vector.capacity()得知，我們可以看一下每次呼叫push_back()之前的capacity
      - capacity: 0 -> push_back(1) -> [1], 0, 0, ......
      - capacity: 1 -> push_back(2) -> 1, [1, 2], ......
      - capacity: 2 -> push_back(3) -> 1, 1, 2, [1, 2, 3, 0] ......
      - capacity: 4 -> push_back(4) -> 1, 1, 2, [1, 2, 3, 4], 0 ......
    - 如果當前的元素個數超過的capacity，則vector會向他的allocator(在這裡會是pmr)要一塊更大的記憶體空間，一般來說是2的次方，實際上要看實作
    - 因為我們給了帶有local buffer的monotonic_buffer_resource，所以當超過capacity時，pmr::vector就會往local buffer要一塊更大的空間
      - 關鍵是，沒有動用到dynamic allocation
  - 另外一點是，我們之所以會在buffer內看到push_back()之前的容器狀態殘留在buffer內，是因為monotonic_buffer_resource對於dealloc行為的特性所致，我們來看一下cppreference
    - 直奔重點，monotonic_buffer_resource的do_deallocate是no op，也就是啥也不幹，真正的記憶體釋放只會發生在他的destructor裏頭
      - 真正意義上的帶著進棺材
這種特殊的記憶體分配法有另一個特殊的名字
- Bump Allocator
- 由於Bump allocator容易造成空間浪費(尤其是用於vector的情況下)，若能預先調整capacity的話就可以減輕這個副作用帶來的影響
  - 我指的就是vector.reserve(n)，在開始插入元素之前先行將capacity調整到一個合適的大小
OK，所以我們來做個整理，monotonic_buffer_resource特殊的地方有:
- 他不會在生命週期內釋放任何記憶體資源，唯一釋放資源的時機就是解構時
  - 省去了deallocation的時間
  - 但這也同時意味著他並不適合用於需要頻繁新增、刪除元素的場景
- 他可接受一個外部的buffer作為記憶體資源
  - 省去了dynamic allocation的時間
  - 萬一我們預先準備的buffer爆了，或者我們根本沒給，那還能動嗎?
    - 我們還漏了一個東西沒有講: upstream_resource ## upstream_resource

upstream_resource對於任何memory_resource(好比說monotonic)就如同水流的上游一般，當我這一個層級的memory_resource耗盡時，就會透過upstream_resource再要一塊

大部分預設的行為，upstream_resource會是一個new_delete_resource
- 也就是說回歸普通的heap allocation了

當然，如果你覺得記憶體資源耗盡是一個從設計上來看不應該發生的錯誤，一旦發生就必須拋出異常，那麼你該把upstream_resource設為null_memory_resource，請見此範例

void null_resources() {
  std::array<std::uint8_t, 4> buffer{};
  std::pmr::monotonic_buffer_resource mem_resource(
      buffer.data(),
      buffer.size(), 
      std::pmr::null_memory_resource());
    
  std::pmr::vector<std::uint8_t> vec1(&mem_resource);
  vec1.push_back(1);
  print_buffer("1", buffer, vec1);
  vec1.push_back(2);
  print_buffer("2", buffer, vec1);
  vec1.push_back(3);
  print_buffer("3", buffer, vec1);
  vec1.push_back(4);
  print_buffer("4", buffer, vec1);
  vec1.push_back(5);
  print_buffer("5", buffer, vec1);
}

我們刻意地把local buffer縮到很小，然後再將mem_resource的upstream_resource設為null_memory_resource(constructor #6)
- 其執行結果會在空間耗盡時直接拋出例外:
  1
  terminate called after throwing an instance of 'std::bad_alloc'what(): std::bad_alloc

而倘若我們把null_memory_resource換成new_delete_resource，則在local buffer耗盡之後，所有原本的元素會被複製到經由operator new所分配的記憶體資源上

也就是說，vector要求多少capacity，就new一塊滿足大小要求的memory出來，然後把原本就有的元素丟上去，再放入被push_back的元素

我們來看一下上面的null_resources()，把null換成new_delete之後會發生什麼事

===============    1     ==============
Buffer Address Start: 0x7ffc73c09d6c
vector.data(): 0x7ffc73c09d6c, vector.size(): 1, vector.capacity(): 1
 Item Address: 0x7ffc73c09d6c

===============    2     ==============
Buffer Address Start: 0x7ffc73c09d6c
vector.data(): 0x7ffc73c09d6d, vector.size(): 2, vector.capacity(): 2
 Item Address: 0x7ffc73c09d6d
 Item Address: 0x7ffc73c09d6e

===============    3     ==============
Buffer Address Start: 0x7ffc73c09d6c
vector.data(): 0x205fec0, vector.size(): 3, vector.capacity(): 4
 Item Address: 0x205fec0
 Item Address: 0x205fec1
 Item Address: 0x205fec2

===============    4     ==============
Buffer Address Start: 0x7ffc73c09d6c
vector.data(): 0x205fec0, vector.size(): 4, vector.capacity(): 4
 Item Address: 0x205fec0
 Item Address: 0x205fec1
 Item Address: 0x205fec2
 Item Address: 0x205fec3

===============    5     ==============
Buffer Address Start: 0x7ffc73c09d6c
vector.data(): 0x205fec4, vector.size(): 5, vector.capacity(): 8
 Item Address: 0x205fec4
 Item Address: 0x205fec5
 Item Address: 0x205fec6
 Item Address: 0x205fec7
 Item Address: 0x205fec8

在push_back(3)的時候發生了空間不足，因此mem_resource向他的upstream要了一塊記憶體當作新空間
- 從vector.data()可以看出來空間已經跑去heap了(因為位置很低)
- 看到這裡你就會發現local buffer等同於是廢了
在往後看就可以看出，這個vector已經退化成一個普通的vector了
- 自從我們耗盡了原本的local buffer之後，每次超過capacity，vector都會要一塊基於2的n次方計算出來的空間，然後把原先的元素複製過去
  - 這跟原本的vector有啥不同啊?
因此結論就是，除非你知道你在幹嘛，否則把upstream_resource設為null_memory_resource會是一個比較好的選擇

小結

在本篇文章中，我們簡單的介紹了PMR的基本原理，以及monotonic_buffer_resource的特性
另外我們也提及了當資源耗盡時，兩種可行的upstream_resource
- null_memory_resource
- new_delete_resource
我們在之後的系列文章中會接著介紹更加複雜的PMR操作，以及如何設計一個支援PMR的class