[libcxxabi][demangler] Improve representation of substitutions/templates

[erik.pilkington]

Summary

This patch changes the demangler so that it represents substitutions/templates more linearly. Previously, substitions were represented by a vector<vector<Node*>> and template parameter substitutions by a vector<vector<vector<Node*>>>! I wrote a comment in SubTable describing how this is done.
This patch gives a 20%-25% time reduction to demangle the symbols in LLVM, a 25% reduction in code size for the demangler on my machine, and makes the demangler a lot easier to read, IMO.

Thanks for taking a look!
Erik

[dexonsmith]

This looks like a great improvement. I've littered the patch with nit-picks, but my main concern is that there aren't any unit tests for the new data structures. I wonder if there's a hacky way to set that up...

src/cxa_demangle.cpp

1460–1461

This seems like a facility that should/could be unit tested (in C++).

I realize there's no precedent for that for the demangler. Perhaps this file could be #included by a test file:

// unittest/PODSmallVectorTest.h
#include "../src/cxa_demangle.cpp"

namespace {

TEST(PODSmallVectorTest, ...) {
}

} // namespace

Thoughts?

1462

Please add an assertion string, such as "T is required to be a plain-old data type".

1499–1501

This is identical to code in the move constructor. Separate it out into a helper?

1511–1517

Helper?

1527–1535

Should we assert when nullptr is returned from std::malloc or std::realloc?

1540–1542

Assertions on popping/dropping past empty?

1549–1550

Assertions on invalid access?

1562

As I read this patch, I keep reading "sub" as a prefix. Can we just spell this out as "SubstitutionTable"?

Also, this probably deserves unit tests as well.

1577–1580

Can/should this be implemented using pushPack() and pushSubIntoPack()?

1585

Do you need to assert that pushPack has been called at least once (i.e., !PackIndices.empty())?

1595

Perhaps NodeRange would be more clear.

1596–1599

Please be consistent with pointer style in this patch.

• I suspect the rest of the file attaches to the type, i.e., Node** First, which is why I didn't comment earlier on, e.g., Node* Entry.
• LLVM style is to attach to the name, like here.

I have a slight preference for switching toward LLVM style, but if the file consistently uses pointers attached to types, that's fine too. (Just be consistent within the patch.)

1602

This could perhaps use a comment. At least, inside the function to explain the math.

1603

Once you add this assertion to operator[] you can delete it here.

1604

Should there be some assertion on Subs.size() here? Perhaps, if so, this should be &Subs[PackIndices[N]], so that Subs.operator[]() handles it for you. Same below.

1605–1607

Does this deserve its own helper function (e.g., packEnd())? (I haven't read ahead to see if this logic is duplicated anywhere; probably not a separate function if it's not duplicated.)

1621–1631

How much have you thought about these sizes (32, 32, and 4)? Any evidence to back up these specific choices?

[dexonsmith]

Oh, also found a couple of things you should likely split into prep commits to simplify this patch.

src/cxa_demangle.cpp

1575–1577

• Why not rename names as well?
• Please rename these in a separate prep commit to minimize noise on the final patch.

[erik.pilkington]

Address review comments.
Thanks!
Erik

src/cxa_demangle.cpp

1575–1577

Sure, r310415.

1604

We can't use operator[] here because if all we have is an empty parameter pack then &Subs[PackIndices[N]] needs to point the the end() iterator, which is out of bounds. The new patch adds an assert though.

1621–1631

Yep, 32 is enough for the Subs table/names to never overflow when demangling the symbols in LLVM, and 4 seldom overflows TemplateParams. TemplateParams is temporary held on the stack in parse_template_args(), so I wanted it to be smaller.

[dexonsmith]

I have a few more nitpicks; LGTM after you fix those.

src/cxa_demangle.cpp

1621–1631

Sounds great. Please add comments to that effect.

1626–1630

This assertion won't be meaningful in the case that matters: when PackIndices[N + 1] is larger than Substitutions.size(). In that case, End is in the middle of nowhere, and the result of End <= Substitutions.end() is undefined. A smart optimizer would fold that to true.

You should assert PackIndices[N + 1] <= Substitutions.size().

5195–5199

This looks really hairy. This is the only (non-recursive) caller of parse_template_arg... it doesn't seem reasonable for parse_template_arg to modify template params, if we're just going to reset them after without looking.

Please add a FIXME to sort this out (at least to document the logic, if not to refactor it somehow).

5207–5209

Early continue instead of else, if you leave the logic like this.

I'm a little skeptical that this structure is better than before, though, since there's some non-trivial duplicated code. I'll let you decide.

src/cxa_demangle.cpp

 #endif
       char num[FloatData<Float>::max_demangled_size] = {0};
       int n = snprintf(num, sizeof(num), FloatData<Float>::spec, value);
       s += StringView(num, num + n);
     }
   }
 };
 
-template <std::size_t N>
-class arena
-{
-    static const std::size_t alignment = 16;
-    alignas(alignment) char buf_[N];
-    char* ptr_;
-
-    std::size_t 
-    align_up(std::size_t n) noexcept
-        {return (n + (alignment-1)) & ~(alignment-1);}
-
-    bool
-    pointer_in_buffer(char* p) noexcept
-        {return buf_ <= p && p <= buf_ + N;}
-
-public:
-    arena() noexcept : ptr_(buf_) {}
-    ~arena() {ptr_ = nullptr;}
-    arena(const arena&) = delete;
-    arena& operator=(const arena&) = delete;
-
-    char* allocate(std::size_t n);
-    void deallocate(char* p, std::size_t n) noexcept;
-
-    static constexpr std::size_t size() {return N;}
-    std::size_t used() const {return static_cast<std::size_t>(ptr_ - buf_);}
-    void reset() {ptr_ = buf_;}
-};
-
-template <std::size_t N>
-char*
-arena<N>::allocate(std::size_t n)
-{
-    n = align_up(n);
-    if (static_cast<std::size_t>(buf_ + N - ptr_) >= n)
-    {
-        char* r = ptr_;
-        ptr_ += n;
-        return r;
-    }
-    return static_cast<char*>(std::malloc(n));
-}
-
-template <std::size_t N>
-void
-arena<N>::deallocate(char* p, std::size_t n) noexcept
-{
-    if (pointer_in_buffer(p))
-    {
-        n = align_up(n);
-        if (p + n == ptr_)
-            ptr_ = p;
-    }
-    else
-        std::free(p);
-}
-
-template <class T, std::size_t N>
-class short_alloc
-{
-    arena<N>& a_;
-public:
-    typedef T value_type;
-
-public:
-    template <class _Up> struct rebind {typedef short_alloc<_Up, N> other;};
-
-    short_alloc(arena<N>& a) noexcept : a_(a) {}
-    template <class U>
-        short_alloc(const short_alloc<U, N>& a) noexcept
-            : a_(a.a_) {}
-    short_alloc(const short_alloc&) = default;
-    short_alloc& operator=(const short_alloc&) = delete;
-
-    T* allocate(std::size_t n)
-    {
-        return reinterpret_cast<T*>(a_.allocate(n*sizeof(T)));
-    }
-    void deallocate(T* p, std::size_t n) noexcept
-    {
-        a_.deallocate(reinterpret_cast<char*>(p), n*sizeof(T));
-    }
-
-    template <class T1, std::size_t N1, class U, std::size_t M>
-    friend
-    bool
-    operator==(const short_alloc<T1, N1>& x, const short_alloc<U, M>& y) noexcept;
-
-    template <class U, std::size_t M> friend class short_alloc;
-};
-
-template <class T, std::size_t N, class U, std::size_t M>
-inline
-bool
-operator==(const short_alloc<T, N>& x, const short_alloc<U, M>& y) noexcept
-{
-    return N == M && &x.a_ == &y.a_;
-}
-
-template <class T, std::size_t N, class U, std::size_t M>
-inline
-bool
-operator!=(const short_alloc<T, N>& x, const short_alloc<U, M>& y) noexcept
-{
-    return !(x == y);
-}
-
-const size_t bs = 4 * 1024;
-template <class T> using Alloc = short_alloc<T, bs>;
-template <class T> using Vector = std::vector<T, Alloc<T>>;
-
 class BumpPointerAllocator {
   struct BlockMeta {
     BlockMeta* Next;
     size_t Current;
   };
 
   static constexpr size_t AllocSize = 4096;
   static constexpr size_t UsableAllocSize = AllocSize - sizeof(BlockMeta);

       BlockMeta* Tmp = BlockList;
       BlockList = BlockList->Next;
       if (reinterpret_cast<char*>(Tmp) != InitialBuffer)
         delete[] reinterpret_cast<char*>(Tmp);
     }
   }
 };
 
+template <class T, size_t N>
+class PODSmallVector {
+  static_assert(std::is_pod<T>::value, "");
+
+  T *First;
+  T *Last;
+  T *Cap;
+  T Inline[N];
+
+  bool isInline() const { return First == Inline; }
+
+public:
+  PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {}
+
+  PODSmallVector(const PODSmallVector &) = delete;
+  PODSmallVector& operator=(const PODSmallVector&) = delete;
+
+  PODSmallVector(PODSmallVector&& Other) {
+    if (Other.isInline()) {
+      std::copy(Other.begin(), Other.end(), Inline);
+      First = Inline;
+      Last = First + Other.size();
+      Cap = Inline + N;
+      Other.clear();
+      return;
+    }
+
+    First = Other.First;
+    Last = Other.Last;
+    Cap = Other.Cap;
+    Other.First = Other.Inline;
+    Other.Last = Other.Inline;
+    Other.Cap = Other.Inline + N;
+  }
+
+  PODSmallVector& operator=(PODSmallVector&& Other) {
+    if (Other.isInline()) {
+      if (!isInline()) {
+        std::free(First);
+        First = Inline;
+        Last = Inline;
+        Cap = Inline + N;
+      }
+      std::copy(Other.begin(), Other.end(), begin());
+      Last = First + Other.size();
+      return *this;
+    }
+
+    if (!isInline())
+      std::free(First);
+
+    First = Other.First;
+    Last = Other.Last;
+    Cap = Other.Cap;
+
+    Other.First = Other.Inline;
+    Other.Last = Other.Inline;
+    Other.Cap = Other.Inline + N;
+    return *this;
+  }
+
+  void push_back(const T &Elem) {
+    if (Last != Cap) {
+      *Last++ = Elem;
+      return;
+    }
+
+    size_t S = size();
+    if (!isInline()) {
+      First = static_cast<T*>(std::realloc(First, sizeof(T) * S * 2));
+    } else {
+      First = static_cast<T*>(std::malloc(sizeof(T) * S * 2));
+      std::copy(std::begin(Inline), std::end(Inline), First);
+    }
+    Last = First + S;
+    Cap = First + S * 2;
+    *Last++ = Elem;
+    return;
+  }
+
+  void pop_back() { --Last; }
+
+  void dropBack(size_t Index) { Last = First + Index; }
+
+  T *begin() { return First; }
+  T *end() { return Last; }
+
+  bool empty() const { return First == Last; }
+  size_t size() const { return static_cast<size_t>(Last - First); }
+  T& back() { return *(Last - 1); }
+  T& operator[](size_t Index) { return *(begin() + Index); }
+  void clear() { Last = First; }
+
+  ~PODSmallVector() {
+    if (!isInline())
+      std::free(First);
+  }
+};
+
+// Substitution table. This type is used to track the substitutions that are
+// known by the parser.
+template<size_t Size>
+class SubTable {
+  // Subs hold the actual entries in the table, and PackIndices tells us which
+  // entries are members of which pack. For example, if the substitutions we're
+  // tracking are: {int, {float, FooBar}, char}, with {float, FooBar} being a
+  // parameter pack, we represent the substitutions as:
+  // Subs:         int, float, FooBar, char
+  // PackIndices:    0,             1,    3
+  // So, PackIndicies[I] holds the offset of the begin of the Ith pack, and
+  // PackIndices[I + 1] holds the offset of the end.
+  PODSmallVector<Node*, Size> Subs;
+  PODSmallVector<unsigned, Size> PackIndices;
+
+public:
+  // Add a substitution that represents a single name to the table. This is
+  // modeled as a parameter pack with just one element.
+  void pushSub(Node* Entry) {
+    PackIndices.push_back(static_cast<unsigned>(Subs.size()));
+    Subs.push_back(Entry);
+  }
+
+  // Add a new empty pack to the table. Subsequent calls to pushSubIntoPack()
+  // will add to this pack.
+  void pushPack() { PackIndices.push_back(static_cast<unsigned>(Subs.size())); }
+  void pushSubIntoPack(Node* Entry) { Subs.push_back(Entry); }
+
+  // Remove the last pack from the table.
+  void popPack() {
+    unsigned Last = PackIndices.back();
+    PackIndices.pop_back();
+    Subs.dropBack(Last);
+  }
+
+  // For use in a range-for loop.
+  struct NodePair {
+    Node **First;
+    Node **Last;
+    Node **begin() { return First; }
+    Node **end() { return Last; }
+  };
+
+  NodePair nthSub(size_t N) {
+    assert(N < PackIndices.size());
+    Node **Begin = Subs.begin() + PackIndices[N];
+    Node **End = (N + 1 == PackIndices.size())
+                     ? Subs.end()
+                     : Subs.begin() + PackIndices[N + 1];
+    return NodePair{Begin, End};
+  }
+
+  size_t size() const { return PackIndices.size(); }
+  bool empty() const { return PackIndices.empty(); }
+  void clear() {
+    Subs.clear();
+    PackIndices.clear();
+  }
+};
+
 struct Db
 {
-    typedef Vector<Node*> sub_type;
-    typedef Vector<sub_type> template_param_type;
-    sub_type names;
-    template_param_type subs;
-    Vector<template_param_type> template_param;
+    // Name stack, this is used by the parser to hold temporary names that were
+    // parsed. The parser colapses multiple names into new nodes to construct
+    // the AST. Once the parser is finished, names.size() == 1.
+    PODSmallVector<Node*, 32> names;
+
+    // Substitution table. Itanium supports name substitutions as a means of
+    // compression. The string "S42_" refers to the 42nd entry in this table.
+    SubTable<32> Subs;
+
+    // Template parameter table. Like the above, but referenced like "T42_".
+    SubTable<4> TemplateParams;
+
     Qualifiers cv = QualNone;
     FunctionRefQual ref = FrefQualNone;
     unsigned encoding_depth = 0;
     bool parsed_ctor_dtor_cv = false;
     bool tag_templates = true;
     bool fix_forward_references = false;
     bool try_to_parse_template_args = true;
 
     BumpPointerAllocator ASTAllocator;
 
-    template <size_t N>
-    Db(arena<N>& ar) :
-        names(ar),
-        subs(0, names, ar),
-        template_param(0, subs, ar)
-    {}
-
     template <class T, class... Args> T* make(Args&& ...args)
     {
         return new (ASTAllocator.allocate(sizeof(T)))
             T(std::forward<Args>(args)...);
     }
 
     template <class It> NodeArray makeNodeArray(It begin, It end)
     {
         size_t sz = static_cast<size_t>(end - begin);
         void* mem = ASTAllocator.allocate(sizeof(Node*) * sz);
         Node** data = new (mem) Node*[sz];
         std::copy(begin, end, data);
         return NodeArray(data, sz);
     }
 
     NodeArray popTrailingNodeArray(size_t FromPosition)
     {
         assert(FromPosition <= names.size());
         NodeArray res = makeNodeArray(
             names.begin() + (long)FromPosition, names.end());
-        names.erase(names.begin() + (long)FromPosition, names.end());
+        names.dropBack(FromPosition);
         return res;
     }
 };
 
 const char* parse_type(const char* first, const char* last, Db& db);
 const char* parse_encoding(const char* first, const char* last, Db& db);
 const char* parse_name(const char* first, const char* last, Db& db,
                        bool* ends_with_template_args = 0);

                 db.names.push_back(db.make<SpecialSubstitution>(SpecialSubKind::ostream));
                 first += 2;
                 break;
             case 'd':
                 db.names.push_back(db.make<SpecialSubstitution>(SpecialSubKind::iostream));
                 first += 2;
                 break;
             case '_':
-                if (!db.subs.empty())
+                if (!db.Subs.empty())
                 {
-                    for (const auto& n : db.subs.front())
+                    for (Node* n : db.Subs.nthSub(0))
                         db.names.push_back(n);
                     first += 2;
                 }
                 break;
             default:
                 if (std::isdigit(first[1]) || std::isupper(first[1]))
                 {
                     size_t sub = 0;
                     const char* t = first+1;
                     if (std::isdigit(*t))
                         sub = static_cast<size_t>(*t - '0');
                     else
                         sub = static_cast<size_t>(*t - 'A') + 10;
                     for (++t; t != last && (std::isdigit(*t) || std::isupper(*t)); ++t)
                     {
                         sub *= 36;
                         if (std::isdigit(*t))
                             sub += static_cast<size_t>(*t - '0');
                         else
                             sub += static_cast<size_t>(*t - 'A') + 10;
                     }
                     if (t == last || *t != '_')
                         return first;
                     ++sub;
-                    if (sub < db.subs.size())
+                    if (sub < db.Subs.size())
                     {
-                        for (const auto& n : db.subs[sub])
+                        for (Node* n : db.Subs.nthSub(sub))
                             db.names.push_back(n);
                         first = t+1;
                     }
                 }
                 break;
             }
         }
     }

 parse_template_param(const char* first, const char* last, Db& db)
 {
     if (last - first >= 2)
     {
         if (*first == 'T')
         {
             if (first[1] == '_')
             {
-                if (db.template_param.empty())
-                    return first;
-                if (!db.template_param.back().empty())
+                if (!db.TemplateParams.empty())
                 {
-                    for (auto& t : db.template_param.back().front())
+                    for (Node* t : db.TemplateParams.nthSub(0))
                         db.names.push_back(t);
                     first += 2;
                 }
                 else
                 {
                     db.names.push_back(db.make<NameType>("T_"));
                     first += 2;
                     db.fix_forward_references = true;
                 }
             }
             else if (isdigit(first[1]))
             {
                 const char* t = first+1;
                 size_t sub = static_cast<size_t>(*t - '0');
                 for (++t; t != last && isdigit(*t); ++t)
                 {
                     sub *= 10;
                     sub += static_cast<size_t>(*t - '0');
                 }
-                if (t == last || *t != '_' || db.template_param.empty())
+                if (t == last || *t != '_')
                     return first;
                 ++sub;
-                if (sub < db.template_param.back().size())
+                if (sub < db.TemplateParams.size())
                 {
-                    for (auto& temp : db.template_param.back()[sub])
+                    for (Node* temp : db.TemplateParams.nthSub(sub))
                         db.names.push_back(temp);
                     first = t+1;
                 }
                 else
                 {
                     db.names.push_back(
                         db.make<NameType>(StringView(first, t + 1)));
                     first = t+1;

         {
         case 'T':
           {
             size_t k0 = db.names.size();
             t = parse_template_param(first, last, db);
             size_t k1 = db.names.size();
             if (t != first && k1 == k0 + 1)
             {
-                db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                db.Subs.pushSub(db.names.back());
                 first = t;
             }
             else
             {
                 for (; k1 != k0; --k1)
                     db.names.pop_back();
             }
             break;
           }
         case 'D':
             t = parse_decltype(first, last, db);
             if (t != first)
             {
                 if (db.names.empty())
                     return first;
-                db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                db.Subs.pushSub(db.names.back());
                 first = t;
             }
             break;
         case 'S':
             t = parse_substitution(first, last, db);
             if (t != first)
                 first = t;
             else
             {
                 if (last - first > 2 && first[1] == 't')
                 {
                     t = parse_unqualified_name(first+2, last, db);
                     if (t != first+2)
                     {
                         if (db.names.empty())
                             return first;
                         db.names.back() =
                             db.make<StdQualifiedName>(db.names.back());
-                        db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                        db.Subs.pushSub(db.names.back());
                         first = t;
                     }
                 }
             }
             break;
        }
     }
     return first;

                 return first;
             NodeArray expressions = db.makeNodeArray(
                 db.names.begin() + (long)expr_list_begin, db.names.end());
             NodeArray types = db.makeNodeArray(
                 db.names.begin() + (long)type_begin,
                 db.names.begin() + (long)expr_list_begin);
             auto* conv_expr = db.make<ConversionExpr>(
                 types, expressions);
-            db.names.erase(
-                db.names.begin() + (long)type_begin, db.names.end());
+            db.names.dropBack(type_begin);
             db.names.push_back(conv_expr);
             first = t;
         }
     }
     return first;
 }
 
 // pt <expression> <expression>                    # expr->name

                 {
                     bool is_function = *t == 'F';
                     size_t k0 = db.names.size();
                     const char* t1 = parse_type(t, last, db);
                     size_t k1 = db.names.size();
                     if (t1 != t)
                     {
                         if (is_function)
-                            db.subs.pop_back();
-                        db.subs.emplace_back(db.names.get_allocator());
+                            db.Subs.popPack();
+                        db.Subs.pushPack();
                         for (size_t k = k0; k < k1; ++k)
                         {
                             if (cv) {
                                 if (is_function)
                                     db.names[k] = db.make<FunctionQualType>(
                                         db.names[k], cv);
                                 else
                                     db.names[k] =
                                         db.make<QualType>(db.names[k], cv);
                             }
-                            db.subs.back().push_back(db.names[k]);
+                            db.Subs.pushSubIntoPack(db.names[k]);
                         }
                         first = t1;
                     }
                 }
               }
                 break;
             default:
               {
                 const char* t = parse_builtin_type(first, last, db);
                 if (t != first)
                 {
                     first = t;
                 }
                 else
                 {
                     switch (*first)
                     {
                     case 'A':
                         t = parse_array_type(first, last, db);
                         if (t != first)
                         {
                             if (db.names.empty())
                                 return first;
                             first = t;
-                            db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                            db.Subs.pushSub(db.names.back());
                         }
                         break;
                     case 'C':
                         t = parse_type(first+1, last, db);
                         if (t != first+1)
                         {
                             if (db.names.empty())
                                 return first;
                             db.names.back() = db.make<PostfixQualifiedType>(
                                 db.names.back(), " complex");
                             first = t;
-                            db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                            db.Subs.pushSub(db.names.back());
                         }
                         break;
                     case 'F':
                         t = parse_function_type(first, last, db);
                         if (t != first)
                         {
                             if (db.names.empty())
                                 return first;
                             first = t;
-                            db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                            db.Subs.pushSub(db.names.back());
                         }
                         break;
                     case 'G':
                         t = parse_type(first+1, last, db);
                         if (t != first+1)
                         {
                             if (db.names.empty())
                                 return first;
                             db.names.back() = db.make<PostfixQualifiedType>(
                                 db.names.back(), " imaginary");
                             first = t;
-                            db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                            db.Subs.pushSub(db.names.back());
                         }
                         break;
                     case 'M':
                         t = parse_pointer_to_member_type(first, last, db);
                         if (t != first)
                         {
                             if (db.names.empty())
                                 return first;
                             first = t;
-                            db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                            db.Subs.pushSub(db.names.back());
                         }
                         break;
                     case 'O':
                       {
                         size_t k0 = db.names.size();
                         t = parse_type(first+1, last, db);
                         size_t k1 = db.names.size();
                         if (t != first+1)
                         {
-                            db.subs.emplace_back(db.names.get_allocator());
+                            db.Subs.pushPack();
                             for (size_t k = k0; k < k1; ++k)
                             {
                                 db.names[k] =
                                     db.make<RValueReferenceType>(db.names[k]);
-                                db.subs.back().push_back(db.names[k]);
+                                db.Subs.pushSubIntoPack(db.names[k]);
                             }
                             first = t;
                         }
                         break;
                       }
                     case 'P':
                       {
                         size_t k0 = db.names.size();
                         t = parse_type(first+1, last, db);
                         size_t k1 = db.names.size();
                         if (t != first+1)
                         {
-                            db.subs.emplace_back(db.names.get_allocator());
+                            db.Subs.pushPack();
                             for (size_t k = k0; k < k1; ++k)
                             {
                                 db.names[k] = db.make<PointerType>(db.names[k]);
-                                db.subs.back().push_back(db.names[k]);
+                                db.Subs.pushSubIntoPack(db.names[k]);
                             }
                             first = t;
                         }
                         break;
                       }
                     case 'R':
                       {
                         size_t k0 = db.names.size();
                         t = parse_type(first+1, last, db);
                         size_t k1 = db.names.size();
                         if (t != first+1)
                         {
-                            db.subs.emplace_back(db.names.get_allocator());
+                            db.Subs.pushPack();
                             for (size_t k = k0; k < k1; ++k)
                             {
                                 db.names[k] =
                                     db.make<LValueReferenceType>(db.names[k]);
-                                db.subs.back().push_back(db.names[k]);
+                                db.Subs.pushSubIntoPack(db.names[k]);
                             }
                             first = t;
                         }
                         break;
                       }
                     case 'T':
                       {
                         size_t k0 = db.names.size();
                         t = parse_template_param(first, last, db);
                         size_t k1 = db.names.size();
                         if (t != first)
                         {
-                            db.subs.emplace_back(db.names.get_allocator());
+                            db.Subs.pushPack();
                             for (size_t k = k0; k < k1; ++k)
-                                db.subs.back().push_back(db.names[k]);
+                                db.Subs.pushSubIntoPack(db.names[k]);
                             if (db.try_to_parse_template_args && k1 == k0+1)
                             {
                                 const char* t1 = parse_template_args(t, last, db);
                                 if (t1 != t)
                                 {
                                     auto args = db.names.back();
                                     db.names.pop_back();
                                     db.names.back() = db.make<
                                         NameWithTemplateArgs>(
                                         db.names.back(), args);
-                                    db.subs.push_back(Db::sub_type(
-                                        1, db.names.back(),
-                                        db.names.get_allocator()));
+                                    db.Subs.pushSub(db.names.back());
                                     t = t1;
                                 }
                             }
                             first = t;
                         }
                         break;
                       }
                     case 'U':

                                         {
                                             db.names.back() = db.make<ObjCProtoName>(type, db.names.back());
                                         }
                                         else
                                         {
                                             db.names.push_back(db.make<VendorExtQualType>(type, proto));
                                         }
                                     }
-                                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                                    db.Subs.pushSub(db.names.back());
                                     first = t2;
                                 }
                             }
                         }
                         break;
                     case 'S':
                         if (first+1 != last && first[1] == 't')
                         {
                             t = parse_name(first, last, db);
                             if (t != first)
                             {
                                 if (db.names.empty())
                                     return first;
-                                db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                                db.Subs.pushSub(db.names.back());
                                 first = t;
                             }
                         }
                         else
                         {
                             t = parse_substitution(first, last, db);
                             if (t != first)
                             {
                                 first = t;
                                 // Parsed a substitution.  If the substitution is a
                                 //  <template-param> it might be followed by <template-args>.
                                 if (db.try_to_parse_template_args)
                                 {
                                     t = parse_template_args(first, last, db);
                                     if (t != first)
                                     {
                                         if (db.names.size() < 2)
                                             return first;
                                         auto template_args = db.names.back();
                                         db.names.pop_back();
                                         db.names.back() = db.make<
                                           NameWithTemplateArgs>(
                                               db.names.back(), template_args);
                                         // Need to create substitution for <template-template-param> <template-args>
-                                        db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                                        db.Subs.pushSub(db.names.back());
                                         first = t;
                                     }
                                 }
                             }
                         }
                         break;
                     case 'D':
                         if (first+1 != last)
                         {
                             switch (first[1])
                             {
                             case 'p':
                               {
                                 size_t k0 = db.names.size();
                                 t = parse_type(first+2, last, db);
                                 size_t k1 = db.names.size();
                                 if (t != first+2)
                                 {
-                                    db.subs.emplace_back(db.names.get_allocator());
+                                    db.Subs.pushPack();
                                     for (size_t k = k0; k < k1; ++k)
-                                        db.subs.back().push_back(db.names[k]);
+                                        db.Subs.pushSubIntoPack(db.names[k]);
                                     first = t;
                                     return first;
                                 }
                                 break;
                               }
                             case 't':
                             case 'T':
                                 t = parse_decltype(first, last, db);
                                 if (t != first)
                                 {
                                     if (db.names.empty())
                                         return first;
-                                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                                    db.Subs.pushSub(db.names.back());
                                     first = t;
                                     return first;
                                 }
                                 break;
                             case 'v':
                                 t = parse_vector_type(first, last, db);
                                 if (t != first)
                                 {
                                     if (db.names.empty())
                                         return first;
-                                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                                    db.Subs.pushSub(db.names.back());
                                     first = t;
                                     return first;
                                 }
                                 break;
                             }
                         }
                         _LIBCPP_FALLTHROUGH();
                     default:
                         // must check for builtin-types before class-enum-types to avoid
                         // ambiguities with operator-names
                         t = parse_builtin_type(first, last, db);
                         if (t != first)
                         {
                             first = t;
                         }
                         else
                         {
                             t = parse_name(first, last, db);
                             if (t != first)
                             {
                                 if (db.names.empty())
                                     return first;
-                                db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                                db.Subs.pushSub(db.names.back());
                                 first = t;
                             }
                         }
                         break;
                     }
               }
                 break;
             }

 //     extension, the abi says <template-arg>+
 
 const char*
 parse_template_args(const char* first, const char* last, Db& db)
 {
     if (last - first >= 2 && *first == 'I')
     {
         if (db.tag_templates)
-            db.template_param.back().clear();
+            db.TemplateParams.clear();
         const char* t = first+1;
         size_t begin_idx = db.names.size();
         while (*t != 'E')
         {
             if (db.tag_templates)
-                db.template_param.emplace_back(db.names.get_allocator());
-            size_t k0 = db.names.size();
-            const char* t1 = parse_template_arg(t, last, db);
-            size_t k1 = db.names.size();
-            if (db.tag_templates)
-                db.template_param.pop_back();
-            if (t1 == t || t1 == last || k0 > k1)
-                return first;
-            if (db.tag_templates)
             {
-                db.template_param.back().emplace_back(db.names.get_allocator());
+                auto TmpParams = std::move(db.TemplateParams);
+                size_t k0 = db.names.size();
+                const char* t1 = parse_template_arg(t, last, db);
+                size_t k1 = db.names.size();
+                db.TemplateParams = std::move(TmpParams);
+
+                if (t1 == t || t1 == last || k0 > k1)
+                    return first;
+                db.TemplateParams.pushPack();
                 for (size_t k = k0; k < k1; ++k)
-                    db.template_param.back().back().push_back(db.names[k]);
+                    db.TemplateParams.pushSubIntoPack(db.names[k]);
+                t = t1;
+            }
+            else
+            {
+                size_t k0 = db.names.size();
+                const char* t1 = parse_template_arg(t, last, db);
+                size_t k1 = db.names.size();
+                if (t1 == t || t1 == last || k0 > k1)
+                    return first;
+                t = t1;
             }
-            t = t1;
         }
         if (begin_idx > db.names.size())
             return first;
         first = t + 1;
         TemplateParams* tp = db.make<TemplateParams>(
             db.popTrailingNodeArray(begin_idx));
         db.names.push_back(tp);
     }
     return first;
 }
 
 // <nested-name> ::= N [<CV-Qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
 //               ::= N [<CV-Qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
 // 
 // <prefix> ::= <prefix> <unqualified-name>
 //          ::= <template-prefix> <template-args>
 //          ::= <template-param>
 //          ::= <decltype>
 //          ::= # empty
 //          ::= <substitution>
 //          ::= <prefix> <data-member-prefix>
 //  extension ::= L
 // 
 // <template-prefix> ::= <prefix> <template unqualified-name>

                     if (db.names.size() < 2)
                         return first;
                     auto name = db.names.back();
                     db.names.pop_back();
                     if (db.names.back()->K != Node::KEmptyName)
                     {
                         db.names.back() = db.make<QualifiedName>(
                             db.names.back(), name);
-                        db.subs.push_back(
-                            Db::sub_type(1, db.names.back(),
-                                         db.names.get_allocator()));
+                        db.Subs.pushSub(db.names.back());
                     }
                     else
                         db.names.back() = name;
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
                 break;
             case 'T':
                 t1 = parse_template_param(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
                     if (db.names.size() < 2)
                         return first;
                     auto name = db.names.back();
                     db.names.pop_back();
                     if (db.names.back()->K != Node::KEmptyName)
                         db.names.back() =
                             db.make<QualifiedName>(db.names.back(), name);
                     else
                         db.names.back() = name;
-                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                    db.Subs.pushSub(db.names.back());
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
                 break;
             case 'D':
                 if (t0 + 1 != last && t0[1] != 't' && t0[1] != 'T')
                     goto do_parse_unqualified_name;
                 t1 = parse_decltype(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
                     if (db.names.size() < 2)
                         return first;
                     auto name = db.names.back();
                     db.names.pop_back();
                     if (db.names.back()->K != Node::KEmptyName)
                         db.names.back() =
                             db.make<QualifiedName>(db.names.back(), name);
                     else
                         db.names.back() = name;
-                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                    db.Subs.pushSub(db.names.back());
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
                 break;
             case 'I':
                 t1 = parse_template_args(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
                     if (db.names.size() < 2)
                         return first;
                     auto name = db.names.back();
                     db.names.pop_back();
                     db.names.back() = db.make<NameWithTemplateArgs>(
                         db.names.back(), name);
-                    db.subs.push_back(Db::sub_type(
-                        1, db.names.back(), db.names.get_allocator()));
+                    db.Subs.pushSub(db.names.back());
                     t0 = t1;
                     component_ends_with_template_args = true;
                 }
                 else
                     return first;
                 break;
             case 'L':
                 if (++t0 == last)
                     return first;
                 break;
             default:
             do_parse_unqualified_name:
                 t1 = parse_unqualified_name(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
                     if (db.names.size() < 2)
                         return first;
                     auto name = db.names.back();
                     db.names.pop_back();
                     if (db.names.back()->K != Node::KEmptyName)
                         db.names.back() =
                             db.make<QualifiedName>(db.names.back(), name);
                     else
                         db.names.back() = name;
-                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                    db.Subs.pushSub(db.names.back());
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
             }
         }
         first = t0 + 1;
         db.cv = cv;
-        if (pop_subs && !db.subs.empty())
-            db.subs.pop_back();
+        if (pop_subs && !db.Subs.empty())
+            db.Subs.popPack();
         if (ends_with_template_args)
             *ends_with_template_args = component_ends_with_template_args;
     }
     return first;
 }
 
 // <discriminator> := _ <non-negative number>      # when number < 10
 //                 := __ <non-negative number> _   # when number >= 10

           {
             const char* t1 = parse_unscoped_name(t0, last, db);
             if (t1 != t0)
             {
                 if (t1 != last && *t1 == 'I')  // <unscoped-template-name> <template-args>
                 {
                     if (db.names.empty())
                         return first;
-                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                    db.Subs.pushSub(db.names.back());
                     t0 = t1;
                     t1 = parse_template_args(t0, last, db);
                     if (t1 != t0)
                     {
                         if (db.names.size() < 2)
                             return first;
                         auto tmp = db.names.back();
                         db.names.pop_back();

     if (mangled_name == nullptr || (buf != nullptr && n == nullptr))
     {
         if (status)
             *status = invalid_args;
         return nullptr;
     }
 
     size_t internal_size = buf != nullptr ? *n : 0;
-    arena<bs> a;
-    Db db(a);
-    db.template_param.emplace_back(a);
+    Db db;
     int internal_status = success;
     size_t len = std::strlen(mangled_name);
     demangle(mangled_name, mangled_name + len, db,
              internal_status);
 
     if (internal_status == success && db.fix_forward_references &&
-           !db.template_param.empty() && !db.template_param.front().empty())
+        !db.TemplateParams.empty())
     {
         db.fix_forward_references = false;
         db.tag_templates = false;
         db.names.clear();
-        db.subs.clear();
+        db.Subs.clear();
         demangle(mangled_name, mangled_name + len, db, internal_status);
         if (db.fix_forward_references)
             internal_status = invalid_mangled_name;
     }
 
     if (internal_status == success)
     {
         if (!buf)