replace most Pos objects/ptrs with indexes into a position table

Pos objects are somewhat wasteful as they duplicate the origin file name and
input type for each object. on files that produce more than one Pos when parsed
this a sizeable waste of memory (one pointer per Pos). the same goes for
ptr<Pos> on 64 bit machines: parsing enough source to require 8 bytes to locate
a position would need at least 8GB of input and 64GB of expression memory. it's
not likely that we'll hit that any time soon, so we can use a uint32_t index to
locate positions instead.

1 files changed, 52 insertions, 0 deletions

diff --git a/src/libutil/types.hh b/src/libutil/types.hh
index 00ba567c6..22bc2b8dd 100644
--- a/src/libutil/types.hh
+++ b/src/libutil/types.hh
@@ -5,6 +5,7 @@
 #include <list>
 #include <set>
 #include <string>
+#include <limits>
 #include <map>
 #include <variant>
 #include <vector>
@@ -102,4 +103,55 @@ public:
     Ptr operator->() const { return Ptr(**this); }
 };
 
+/* Provides an indexable container like vector<> with memory overhead
+   guarantees like list<> by allocating storage in chunks of ChunkSize
+   elements instead of using a contiguous memory allocation like vector<>
+   does. Not using a single vector that is resized reduces memory overhead
+   on large data sets by on average (growth factor)/2, mostly
+   eliminates copies within the vector during resizing, and provides stable
+   references to its elements. */
+template<typename T, size_t ChunkSize>
+class ChunkedVector {
+private:
+    uint32_t size_ = 0;
+    std::vector<std::vector<T>> chunks;
+
+    /* keep this out of the ::add hot path */
+    [[gnu::noinline]]
+    auto & addChunk()
+    {
+        if (size_ >= std::numeric_limits<uint32_t>::max() - ChunkSize)
+            abort();
+        chunks.emplace_back();
+        chunks.back().reserve(ChunkSize);
+        return chunks.back();
+    }
+
+public:
+    ChunkedVector(uint32_t reserve)
+    {
+        chunks.reserve(reserve);
+        addChunk();
+    }
+
+    uint32_t size() const { return size_; }
+
+    std::pair<T &, uint32_t> add(T value)
+    {
+        const auto idx = size_++;
+        auto & chunk = [&] () -> auto & {
+            if (auto & back = chunks.back(); back.size() < ChunkSize)
+                return back;
+            return addChunk();
+        }();
+        auto & result = chunk.emplace_back(std::move(value));
+        return {result, idx};
+    }
+
+    const T & operator[](uint32_t idx) const
+    {
+        return chunks[idx / ChunkSize][idx % ChunkSize];
+    }
+};
+
 }