"std::allocator…"

Andrei Alexandrescu at CppCon 2015

• malloc 需要指定 size, free 卻不用？
  所以 allocator 需要管理 size
• Allocator = Compositions of strategies
  根據不同的需求/狀況決定應該要採取哪種 allocate 策略

Types of common allocator

• Fallback allocator
  分兩個 allocator，如果 primary 失敗的話，就試試看 fallback allocator
• Stack allocator
  • alloc/free 快速，只要操控 tos pointer 就好
  • 缺點是比較沒有彈性，沒辦法 alloc A -> alloc B -> free A -> free B
• Freelist
  利用 linked list 來管理記憶體，減少頻繁使用 alloc/free 帶來的成本
• Affix allocator
  替一段分配過的記憶體區間加上 prefix 和 suffix 作為 guard，檢測 memory 是否損毀。
• Bitmapped Block
  • 利用一些 bitmapped block 記錄區塊是否有被佔用
  • Bitwise operation 很快
  • Fragmentation issue
  • Multithreading issue，使用大於 1 個 block 時需要 lock
• Cascading allocator
  • Bitmapped block 的延伸，大小不夠就合併多個 bitmapped block，再 maintain 這個 block。
• Segregator
  • 有 threshold 來區分要使用哪個 allocator
  • self-composable -> 形成 binary tree 的型式
  • 需要很多種 size 時可以使用
• Bucketizer
  • 類似 segregator，把一個區間分成不同 steps 的大小，使用不同的 allocator
• MDFINAE: Method Definition Failure Is Not An Error