[C++] pinned_vector - Pointer Invalidation Issue on std::vector

pointer invalidation 在 C++ container 是個滿重要 (但很容易被忽略) 的議題，主要原因在於 C++ container 會自己在 runtime 依據使用情況去調整記憶體使用量。也因此，如果用 pointer 去存取 container 中的東西時有時會遇上 container 因為你的操作 (比方說新增/刪除) 導致既有的 pointer 不再合法 (也就是原本指到的地方已經不再是你原本指向的東西，可能已經變成其他的東西或是不能被存取了)，這就是所謂的 pointer invalidation，在 C++ reference 上各個 container 的 member function 其實可以看到會有一段在描述 iterator validity，那個就是在講這個議題。

當然，不同方式的 container 在 pointer validity 會有不同的情況 (比方說 std::list 沒有這問題，但是他的 element 就不會是在連續的記憶體上)，選用 std container 的時候其實有一部份是要謹慎考量這問題的，因為這攸關使用情境以及效能。這次在 Meeting C++ 2018 看到的 pinned_vector 簡單來說就是提出一個可以滿足最低限度的 pointer validity 的改良版 std::vector

所謂最低限度其實要看怎麼定義，而這邊提出的最低限度指的是下面的條件：

If insertion or erasure occurs only at the end of the container, then pointers to all other elements shall remain valid.

這個條件的概念主要在於

1. vector 中的 element 應該要是處在一段連續的記憶體 (其他做法無法滿足這要求)
2. 在記憶體無限大的情況下，第一點一定成立

聽來很單純，不過第二點不可能辦到，所以不會有這種東西。但是要求比實際擁有的記憶體還要大的記憶體使用量仍然是可能的，為什麼呢？因為現在的 OS 跟 CPU 有 Virtual Memory, Memory Management Unit (MMU), Translation Lookaside Buffer (TLB) 以及 Page 這些東西，詳細介紹這邊不多講，可以去看計算機組織/架構相關文章或是從 reference 的影片 (10:11 秒開始)。這些東西簡單來說就是讓 OS 只把你現在實際會用到的東西才放進實體記憶體，你目前沒用到的他就找個暫存區 (像是你的硬碟) 丟在那，所以你其實可以要求比你擁有的記憶體還要大記憶體使用量。

所以這個影片的 pinned_vector 其實就是在做上面那段講的事情：他先跟 OS 說幫忙保留一段非常大 (比你所需的記憶體使用量還大就好，那就相當於無限的記憶體了)，不過只是保留，實際上因為 virtual memory 的存在，你沒用到的記憶體他實際上就不會真的配置一塊實體記憶體給你用。如此一來，程式運行中因為 pinned_vector 會認為記憶體夠用所以不會 reallocate 而維持 pointer validity，但又不會真的佔用一大堆沒用到的記憶體。

就結論來說：element 數量不多 (也就是記憶體用量不大時，數據請看影片)，std::vector 佔優，反之則是 pinned_vector 較佳。原因在於 pinned_vector 需要在向 OS 要求保留記憶體時有一定的負擔在，只要求少量的記憶體時 std::vector 可以較快完成；反之，element 數量多時每次數量一增長就會有 reallocate + copy 等等的需求，反而很費時。

就我個人來說，想法很有趣，因為是從不同的角度思考這個問題，雖然有其價值，不過要能看到這個價值其門檻其實不低，從影片中大致上可以發現大概要 1MB 以上才會開始有改善。而且因為沒有甚麼根本性上的改善 (以這議題來說也不太可能)，所以瞭解其概念後就覺得沒興趣了。

Reference:
https://www.youtube.com/watch?v=Ke1mJiGO-pU