Optimize ItaniumDemangle by using an arena allocator

[scott.smith]

Summary

Use an arena allocator to reduce the number of allocations and frees. Individual allocations become extremely cheap, and individual frees are free. Change from std::string to a custom string implementation that is a reference to immutable data, so that substr and copies are free. Remove the null terminator so that strings can be appended without copying the base.

[davide]

I have some concerns about the approach. Some of the code is non-portable, I guess, but that can be fixed.
You might want to try reducing the amount of memory allocated rather than growing an homemade allocator to amortize malloc()/free() cost. I'm not positive this can be reached with the current design, but there have been several discussions in the past about a full rewrite. (Please note that the demangler has deeper issues, including looking at its own output which has been cause many bugs).

lib/Demangle/ItaniumDemangle.cpp

49–50

I'm not sure this will work with MSVC.

[scott.smith]

lib/Demangle/ItaniumDemangle.cpp

49–50

The admittedly non-portable extension works on MSVC, gcc, and clang. So it's mostly portable ;-) But it's a hack, I admit.

Though I would prefer to remove plus the arena through to all the callsites. It would make the diff less readable, so I thought I'd start with this version. Sorry I should have made that clear from the beginning.

[scott.smith]

With added parallelism to lldb, this change no longer has an impact, and I sense an uphill battle trying to get this into libcxx, and then llvm.

lib/Demangle/ItaniumDemangle.cpp

   CV_restrict = (1 << 2),
 };
 
+namespace {
+
+class arena;
+
+static __thread arena * thread_arena = nullptr;
+
+class arena {
+public:
+  arena()
+  {
+    thread_arena = this;
+  }
+
+  ~arena();
+
+  char * alloc(size_t len)
+  {
+    if (m_current_end < m_current_next + len)
+      grow(len);
+    char * ret = m_current_next;
+    m_current_last = ret;
+    m_current_next = ret + len;
+    return ret;
+  }
+
+  char * realloc(const char * &old_begin, const char * &old_end, size_t extra)
+  {
+    if (old_begin == m_current_last &&
+        old_end == m_current_next &&
+        old_end + extra <= m_current_end) {
+      char * ret = m_current_next;
+      old_end = m_current_next = ret + extra;
+      return ret;
+    } else {
+      return slow_realloc(old_begin, old_end, extra);
+    }
+  }
+
+private:
+  struct arena_page {
+    arena_page * next;
+  };
+
+  void grow(size_t len);
+  char * slow_realloc(const char * &old_begin, const char * &old_end, size_t extra);
+
+  arena_page * m_current = nullptr;
+  char * m_current_last = nullptr;
+  char * m_current_next = nullptr;
+  char * m_current_end = nullptr;
+};
+
+arena::~arena()
+{
+  while (arena_page * cur = m_current) {
+    m_current = cur->next;
+    free(cur);
+  }
+  thread_arena = nullptr;
+}
+
+void arena::grow(size_t len)
+{
+  len = std::max(len * 2,                    // Make sure appends are O(n)
+                 2048 - sizeof(arena_page)); // Reasonable default
+  arena_page * elem = static_cast<arena_page *>(malloc(sizeof(arena_page) + len));
+  elem->next = m_current;
+  m_current = elem;
+  m_current_next = reinterpret_cast<char *>(elem + 1);
+  m_current_end = m_current_next + len;
+}
+
+char * arena::slow_realloc(const char * &old_begin, const char * &old_end, size_t extra)
+{
+  size_t old_len = old_end - old_begin;
+  char * ret = alloc(old_len + extra);
+  memcpy(ret, old_begin, old_len);
+  old_begin = ret;
+  old_end = ret + old_len + extra;
+  return ret + old_len;
+}
+
+template<typename T>
+class arena_allocator {
+public:
+  typedef T value_type;
+  typedef T * pointer;
+  typedef std::size_t size_type;
+
+  pointer allocate( size_type n, std::allocator<void>::const_pointer hint = 0 )
+  {
+    return reinterpret_cast<pointer>(thread_arena->alloc(n * sizeof(T)));
+  }
+
+  void deallocate( T* p, std::size_t n )
+  {
+    // Nothing to do!  So cheap!
+  }
+};
+
+class demangle_string {
+public:
+  demangle_string()
+    : m_first(nullptr)
+    , m_last(nullptr)
+  {
+  }
+
+  demangle_string(demangle_string const & rhs)
+    : m_first(rhs.m_first)
+    , m_last(rhs.m_last)
+  {
+  }
+
+  demangle_string(const char * f, const char * l)
+    : m_first(f)
+    , m_last(l)
+  {
+  }
+
+  demangle_string(const char * str, size_t len)
+    : m_first(str)
+    , m_last(str + len)
+  {
+  }
+
+  demangle_string(const char * str)
+    : m_first(str)
+    , m_last(str + strlen(str))
+  {
+  }
+
+  void clear()
+  {
+    m_last = m_first;
+  }
+
+  const char & front() const
+  {
+    return m_first[0];
+  }
+
+  const char & back() const
+  {
+    return *(m_last - 1);
+  }
+
+  const char & operator[](size_t idx) const
+  {
+    return m_first[idx];
+  }
+
+  void append(demangle_string const & b)
+  {
+    if (empty()) {
+      *this = b;
+    } else if (!b.empty()) {
+      size_t blen = b.size();
+      memcpy(thread_arena->realloc(m_first, m_last, blen), b.m_first, blen);
+    }
+  }
+
+  void append(const char * rhs)
+  {
+    append(demangle_string(rhs));
+  }
+
+  void append(const char * a, const char * b)
+  {
+    append(demangle_string(a, b));
+  }
+
+  void push_back(char c)
+  {
+    append(demangle_string(&c, 1));
+  }
+
+  void replace(const char * cut_first, const char * cut_last, demangle_string const & b)
+  {
+    cut_first = std::min(cut_first, m_last);
+    cut_last = std::min(cut_last, m_last);
+    const char * last = m_last;
+    m_last = cut_first;
+    append(b.m_first, b.m_last);
+    append(cut_last, last);
+  }
+
+  void replace(size_t pos, size_t count, demangle_string const & b)
+  {
+    replace(m_first + pos, m_first + pos + count, b);
+  }
+
+  void replace(const char * f, const char * l, const char * b)
+  {
+    replace(f, l, demangle_string(b));
+  }
+
+  void replace(size_t pos, size_t count, const char * b)
+  {
+    replace(m_first + pos, m_first + pos + count, b);
+  }
+
+  void insert(size_t pos, demangle_string const & b)
+  {
+    replace(m_first + pos, m_first + pos, b);
+  }
+
+  void insert(size_t pos, const char * b)
+  {
+    insert(pos, demangle_string(b));
+  }
+
+  void insert(size_t pos, const char * a, const char * b)
+  {
+    insert(pos, demangle_string(a, b));
+  }
+
+  void erase(size_t pos, size_t count)
+  {
+    replace(pos, count, demangle_string());
+  }
+
+  // NOTE: Not null terminated!
+  const char * data() const {
+    return m_first;
+  }
+
+  size_t size() const {
+    return m_last - m_first;
+  }
+
+  bool empty() const {
+    return m_first == m_last;
+  }
+
+  bool operator==(demangle_string const & rhs) const
+  {
+    size_t alen = m_last - m_first;
+    size_t blen = rhs.m_last - rhs.m_first;
+    return alen == blen && !memcmp(m_first, rhs.m_first, alen);
+  }
+
+  bool operator!=(demangle_string const & rhs) const
+  {
+    return !operator==(rhs);
+  }
+
+  bool operator==(const char * rhs) const
+  {
+    return *this == demangle_string(rhs);
+  }
+
+  bool operator!=(const char * rhs) const
+  {
+    return *this != demangle_string(rhs);
+  }
+
+  demangle_string substr(size_t pos, size_t count) const
+  {
+    const char * f = std::min(m_first + pos, m_last);
+    const char * l = std::min(m_first + pos + count, m_last);
+    return demangle_string(f, l);
+  }
+
+  demangle_string & operator=(demangle_string const & src)
+  {
+    m_first = src.m_first;
+    m_last = src.m_last;
+    return *this;
+  }
+
+  // This is purposefully deleted to remind developers NOT to do "a += b + c" but instead "a = a +
+  // b + c", which reduces the number of copies.  If you really need to append a single
+  // demangle_string, call append.
+  demangle_string & operator+=(demangle_string const & rhs) = delete;
+
+  demangle_string operator+(demangle_string const & rhs) const
+  {
+    demangle_string copy(*this);
+    copy.append(rhs);
+    return copy;
+  }
+
+  demangle_string operator+(const char * rhs) const
+  {
+    return *this + demangle_string(rhs);
+  }
+
+  demangle_string operator+(const char rhs) const
+  {
+    return *this + demangle_string(&rhs, 1);
+  }
+
+private:
+  const char * m_first = nullptr; // inclusive
+  const char * m_last = nullptr; // exclusive
+};
+
+demangle_string operator+(const char * lhs, demangle_string const & rhs)
+{
+  return demangle_string(lhs) + rhs;
+}
+
+demangle_string & operator+=(demangle_string & lhs, const char * rhs)
+{
+  lhs.append(rhs);
+  return lhs;
+}
+
+demangle_string & operator+=(demangle_string & lhs, const char ch)
+{
+  lhs.push_back(ch);
+  return lhs;
+}
+
+template <class StrT> struct string_pair {
+  StrT first;
+  StrT second;
+
+  string_pair() = default;
+  string_pair(StrT f) : first(std::move(f)) {}
+  string_pair(StrT f, StrT s) : first(std::move(f)), second(std::move(s)) {}
+  template <size_t N> string_pair(const char (&s)[N]) : first(demangle_string(s, N - 1)) {}
+
+  size_t size() const { return first.size() + second.size(); }
+  StrT full() const { return first + second; }
+  string_pair move_full() { return *this; }
+  bool empty() const { return first.empty() && second.empty(); }
+};
+
+demangle_string & operator+=(demangle_string & lhs, string_pair<demangle_string> const & rhs)
+{
+  lhs.append(rhs.first);
+  lhs.append(rhs.second);
+  return lhs;
+}
+
+demangle_string operator+(demangle_string lhs, string_pair<demangle_string> const & rhs)
+{
+  return lhs += rhs;
+}
+
+demangle_string operator+(const char * lhs, string_pair<demangle_string> const & rhs)
+{
+  return demangle_string(lhs) + rhs;
+}
+
+demangle_string operator+(string_pair<demangle_string> const & lhs, const char * rhs)
+{
+  demangle_string ret = lhs.first;
+  ret.append(lhs.second);
+  ret.append(rhs);
+  return ret;
+}
+
+}  // namespace
+
 template <class C>
 static const char *parse_type(const char *first, const char *last, C &db);
 template <class C>

 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
       std::reverse(buf, e);
 #endif
-      char num[float_data<Float>::max_demangled_size] = {0};
-      int n = snprintf(num, sizeof(num), float_data<Float>::spec, value);
-      if (static_cast<std::size_t>(n) >= sizeof(num))
+      size_t const numlen = float_data<Float>::max_demangled_size;
+      char * num = thread_arena->alloc(numlen);
+      int n = snprintf(num, numlen, float_data<Float>::spec, value);
+      if (static_cast<std::size_t>(n) >= numlen)
         return first;
-      db.names.push_back(std::string(num, static_cast<std::size_t>(n)));
+      db.names.push_back(demangle_string(num, static_cast<std::size_t>(n)));
       first = t + 1;
     }
   }

           return first;
       }
       if (static_cast<size_t>(last - t) >= n) {
-        std::string r(t, n);
+        demangle_string r(t, n);
         if (r.substr(0, 10) == "_GLOBAL__N")
           db.names.push_back("(anonymous namespace)");
         else

             db.names.push_back(temp);
           first = t + 1;
         } else {
-          db.names.push_back(std::string(first, t + 1));
+          db.names.push_back(demangle_string(first, t + 1));
           first = t + 1;
           db.fix_forward_references = true;
         }

     const char *t = parse_template_param(first + 2, last, db);
     size_t k1 = db.names.size();
     if (t != first + 2) {
-      std::string tmp("sizeof...(");
+      demangle_string tmp("sizeof...(");
       size_t k = k0;
       if (k != k1) {
         tmp += db.names[k].move_full();
         for (++k; k != k1; ++k)
-          tmp += ", " + db.names[k].move_full();
+          tmp = tmp + ", " + db.names[k].move_full();
       }
       tmp += ")";
       for (; k1 != k0; --k1)

       const char *t = parse_cv_qualifiers(first + 2, last, cv);
       const char *t1 = parse_number(t, last);
       if (t1 != last && *t1 == '_') {
-        db.names.push_back("fp" + std::string(t, t1));
+        db.names.push_back("fp" + demangle_string(t, t1));
         first = t1 + 1;
       }
     } else if (first[1] == 'L') {

         const char *t = parse_cv_qualifiers(t0, last, cv);
         const char *t1 = parse_number(t, last);
         if (t1 != last && *t1 == '_') {
-          db.names.push_back("fp" + std::string(t, t1));
+          db.names.push_back("fp" + demangle_string(t, t1));
           first = t1 + 1;
         }
       }

           return first;
         auto expr = db.names.back().move_full();
         db.names.pop_back();
-        db.names.back().first += ".*" + expr;
+        db.names.back().first = db.names.back().first + ".*" + expr;
         first = t1;
       }
     }

             return first;
           auto s = db.names.back().move_full();
           db.names.pop_back();
-          db.names.back().first += "::" + std::move(s);
+          db.names.back().first = db.names.back().first + "::" + std::move(s);
           t = t1;
         }
         ++t;

           return first;
         auto s = db.names.back().move_full();
         db.names.pop_back();
-        db.names.back().first += "::" + std::move(s);
+        db.names.back().first = db.names.back().first + "::" + std::move(s);
         first = t1;
       } else {
         t += 2;

             return first;
           auto s = db.names.back().move_full();
           db.names.pop_back();
-          db.names.back().first += "::" + std::move(s);
+          db.names.back().first = db.names.back().first + "::" + std::move(s);
           first = t1;
         } else {
           t1 = parse_unresolved_qualifier_level(t, last, db);

               return first;
             auto s = db.names.back().move_full();
             db.names.pop_back();
-            db.names.back().first += "::" + std::move(s);
+            db.names.back().first = db.names.back().first + "::" + std::move(s);
             t = t1;
           }
           ++t;

             return first;
           auto s = db.names.back().move_full();
           db.names.pop_back();
-          db.names.back().first += "::" + std::move(s);
+          db.names.back().first = db.names.back().first + "::" + std::move(s);
           first = t1;
         }
       }

         db.names.pop_back();
         if (db.names.empty())
           return first;
-        db.names.back().first += "." + name;
+        db.names.back().first = db.names.back().first + "." + name;
         first = t1;
       }
     }

         return first;
       if (db.names.empty())
         return first;
-      db.names.back().first += db.names.back().second;
-      db.names.back().second = std::string();
+      db.names.back().first.append(db.names.back().second);
+      db.names.back().second = demangle_string();
       db.names.back().first.append("(");
       bool first_expr = true;
       while (*t != 'E') {

             db.names.back().first.append(", ");
             first_expr = false;
           }
-          db.names.back().first.append(tmp);
+          db.names.back().first += tmp;
         }
         t = t1;
       }

             if (db.names.empty())
               return first;
             db.names.back().first.append(", ");
-            db.names.back().first.append(tmp);
+            db.names.back().first += tmp;
             first_expr = false;
           }
         }

               if (db.names.empty())
                 return first;
               db.names.back().first.append(", ");
-              db.names.back().first.append(tmp);
+              db.names.back().first += tmp;
               first_expr = false;
             }
           }

       }
       if (*t != 'E')
         return first;
-      std::string init_list;
+      string_pair<demangle_string> init_list;
       if (has_init) {
         if (db.names.empty())
           return first;

         return first;
       auto type = db.names.back().move_full();
       db.names.pop_back();
-      std::string expr_list;
+      string_pair<demangle_string> expr_list;
       if (has_expr_list) {
         if (db.names.empty())
           return first;
         expr_list = db.names.back().move_full();
         db.names.pop_back();
       }
-      std::string r;
+      demangle_string r;
       if (parsed_gs)
         r = "::";
       if (is_array)

       else
         r += " ";
       if (has_expr_list)
-        r += "(" + expr_list + ") ";
+        r = r + "(" + expr_list + ") ";
       r += type;
       if (has_init)
-        r += " (" + init_list + ")";
+        r = r + " (" + init_list + ")";
       db.names.push_back(std::move(r));
       first = t + 1;
     }

                 if (db.names.empty())
                   return first;
                 db.names.back().first.append(", ");
-                db.names.back().first.append(tmp);
+                db.names.back().first += tmp;
                 first_expr = false;
               }
             }

       const char *t1 = parse_type(t, last, db);
       if (t1 != t) {
         t = t1;
-        std::string sig("(");
+        demangle_string sig("(");
         int ref_qual = 0;
         while (true) {
           if (t == last) {

           if (db.names.back().second.substr(0, 2) == " [")
             db.names.back().second.erase(0, 1);
           db.names.back().second.insert(0,
-                                        " [" + std::string(first + 1, t) + "]");
+                                        " [" + demangle_string(first + 1, t) + "]");
           first = t2;
         }
       }

           if (t1 != t) {
             if (db.names.empty())
               return first;
-            db.names.back().first += " vector[" + std::string(num, sz) + "]";
+            db.names.back().first = db.names.back().first + " vector[" +
+              demangle_string(num, sz) + "]";
             first = t1;
           }
         } else {
           ++t;
-          db.names.push_back("pixel vector[" + std::string(num, sz) + "]");
+          db.names.push_back("pixel vector[" + demangle_string(num, sz) + "]");
           first = t;
         }
       }
     } else {
-      std::string num;
+      string_pair<demangle_string> num;
       const char *t1 = first + 2;
       if (*t1 != '_') {
         const char *t = parse_expression(t1, last, db);

         if (t != t1) {
           if (db.names.empty())
             return first;
-          db.names.back().first += " vector[" + num + "]";
+          db.names.back().first = db.names.back().first + " vector[" + num + "]";
           first = t;
         }
       }

                 if (db.names.back().first.substr(0, 9) != "objcproto") {
                   db.names.back() = type + " " + db.names.back().move_full();
                 } else {
-                  auto proto = db.names.back().move_full();
+                  auto proto = db.names.back().full();
                   db.names.pop_back();
                   t = parse_source_name(proto.data() + 9,
                                         proto.data() + proto.size(), db);

 
 template <class C>
 static const char *parse_integer_literal(const char *first, const char *last,
-                                         const std::string &lit, C &db) {
+                                         const char * lit, C &db) {
   const char *t = parse_number(first, last);
   if (t != first && t != last && *t == 'E') {
-    if (lit.size() > 3)
-      db.names.push_back("(" + lit + ")");
+    bool is_short_lit = strlen(lit) <= 3;
+    if (!is_short_lit)
+      db.names.push_back(demangle_string("(") + lit + ")");
     else
       db.names.emplace_back();
     if (*first == 'n') {

       ++first;
     }
     db.names.back().first.append(first, t);
-    if (lit.size() <= 3)
+    if (is_short_lit)
       db.names.back().first += lit;
     first = t + 1;
   }

             if (db.names.empty())
               return first;
             db.names.back() =
-                "(" + db.names.back().move_full() + ")" + std::string(t, n);
+                "(" + db.names.back().move_full() + ")" + demangle_string(t, n);
             first = n + 1;
             break;
           }

   return first;
 }
 
-static std::string base_name(std::string &s) {
+static demangle_string base_name(demangle_string &s) {
   if (s.empty())
     return s;
   if (s == "std::string") {

     unsigned c = 1;
     while (true) {
       if (--pe == pf)
-        return std::string();
+        return demangle_string();
       if (pe[-1] == '<') {
         if (--c == 0) {
           --pe;

     }
   }
   if (pe - pf <= 1)
-    return std::string();
+    return demangle_string();
   const char *p0 = pe - 1;
   for (; p0 != pf; --p0) {
     if (*p0 == ':') {

       break;
     }
   }
-  return std::string(p0, pe);
+  return demangle_string(p0, pe);
 }
 
 // <ctor-dtor-name> ::= C1    # complete object constructor

     char type = first[1];
     switch (type) {
     case 't': {
-      db.names.push_back(std::string("'unnamed"));
+      db.names.push_back("'unnamed");
       const char *t0 = first + 2;
       if (t0 == last) {
         db.names.pop_back();

       first = t0 + 1;
     } break;
     case 'l': {
-      db.names.push_back(std::string("'lambda'("));
+      db.names.push_back("'lambda'(");
       const char *t0 = first + 2;
       if (first[2] == 'v') {
         db.names.back().first += ')';

           return first;
         auto tmp = db.names.back().move_full();
         db.names.pop_back();
-        db.names.back().first.append(tmp);
+        db.names.back().first += tmp;
         t0 = t1;
         while (true) {
           t1 = parse_type(t0, last, db);

           db.names.pop_back();
           if (!tmp.empty()) {
             db.names.back().first.append(", ");
-            db.names.back().first.append(tmp);
+            db.names.back().first += tmp;
           }
           t0 = t1;
         }

         const char *t1 = t0 + 1;
         while (t1 != last && std::isdigit(*t1))
           ++t1;
-        db.names.back().first.insert(db.names.back().first.begin() + 7, t0, t1);
+        db.names.back().first.insert(7, t0, t1);
         t0 = t1;
       }
       if (t0 == last || *t0 != '_') {

 
 template <class C>
 static const char *parse_prefix_expression(const char *first, const char *last,
-                                           const std::string &op,
+                                           const char * op,
                                            C &db) {
   const char *t1 = parse_expression(first, last, db);
   if (t1 != first) {
     if (db.names.empty())
       return first;
-    db.names.back().first = op + "(" + db.names.back().move_full() + ")";
+    db.names.back().first = demangle_string(op) + "(" + db.names.back().move_full() + ")";
     first = t1;
   }
   return first;

 
 template <class C>
 static const char *parse_binary_expression(const char *first, const char *last,
-                                           const std::string &op,
+                                           const char * op,
                                            C &db) {
   const char *t1 = parse_expression(first, last, db);
   if (t1 != first) {

       auto op1 = db.names.back().move_full();
       auto &nm = db.names.back().first;
       nm.clear();
-      if (op == ">")
+      bool is_greater_than = (op[0] == '>' && op[1] == 0);
+      if (is_greater_than)
         nm += '(';
-      nm += "(" + op1 + ") " + op + " (" + op2 + ")";
-      if (op == ">")
+      nm = nm + "(" + op1 + ") " + op + " (" + op2 + ")";
+      if (is_greater_than)
         nm += ')';
       first = t2;
     } else if (!db.names.empty())

           if (db.names.empty())
             return first;
           db.names.back().first =
-              (parsed_gs ? std::string("::") : std::string()) + "delete[] " +
+              (parsed_gs ? demangle_string("::delete[] ") : demangle_string("delete[] ")) +
               db.names.back().move_full();
           first = t1;
         }

           if (db.names.empty())
             return first;
           db.names.back().first =
-              (parsed_gs ? std::string("::") : std::string()) + "delete " +
+              (parsed_gs ? demangle_string("::delete ") : demangle_string("delete ")) +
               db.names.back().move_full();
           first = t1;
         }

     if (db.tag_templates)
       db.template_param.back().clear();
     const char *t = first + 1;
-    std::string args("<");
+    demangle_string args("<");
     while (*t != 'E') {
       if (db.tag_templates)
         db.template_param.emplace_back();

           if (db.names.empty())
             return first;
           if (!db.names.back().first.empty()) {
-            db.names.back().first += "::" + name;
+            db.names.back().first = db.names.back().first + "::" + name;
             db.subs.push_back(typename C::sub_type(1, db.names.back()));
           } else
-            db.names.back().first = name;
+            db.names.back().first = name.full();
           pop_subs = true;
           t0 = t1;
         } else

           if (db.names.empty())
             return first;
           if (!db.names.back().first.empty())
-            db.names.back().first += "::" + name;
+            db.names.back().first = db.names.back().first + "::" + name;
           else
-            db.names.back().first = name;
+            db.names.back().first = name.full();
           db.subs.push_back(typename C::sub_type(1, db.names.back()));
           pop_subs = true;
           t0 = t1;

           if (db.names.empty())
             return first;
           if (!db.names.back().first.empty())
-            db.names.back().first += "::" + name;
+            db.names.back().first = db.names.back().first + "::" + name;
           else
-            db.names.back().first = name;
+            db.names.back().first = name.full();
           db.subs.push_back(typename C::sub_type(1, db.names.back()));
           pop_subs = true;
           t0 = t1;

           if (db.names.empty())
             return first;
           if (!db.names.back().first.empty())
-            db.names.back().first += "::" + name;
+            db.names.back().first = db.names.back().first + "::" + name;
           else
-            db.names.back().first = name;
+            db.names.back().first = name.full();
           db.subs.push_back(typename C::sub_type(1, db.names.back()));
           pop_subs = true;
           t0 = t1;

               if (db.names.empty())
                 return first;
               db.names.back().first.append("::");
-              db.names.back().first.append(name);
+              db.names.back().first += name;
               first = t1;
             } else if (!db.names.empty())
               db.names.pop_back();

           if (db.names.empty())
             return first;
           db.names.back().first.append("::");
-          db.names.back().first.append(name);
+          db.names.back().first += name;
         } else if (!db.names.empty())
           db.names.pop_back();
       } break;

           save_value<bool> sb2(db.tag_templates);
           db.tag_templates = false;
           const char *t2;
-          std::string ret2;
+          demangle_string ret2;
           if (db.names.empty())
             return first;
-          const std::string &nm = db.names.back().first;
-          if (nm.empty())
+          if (db.names.back().first.empty())
             return first;
           if (!db.parsed_ctor_dtor_cv && ends_with_template_args) {
             t2 = parse_type(t, last, db);

               if (t2 == t)
                 break;
               if (k1 > k0) {
-                std::string tmp;
+                demangle_string tmp;
                 for (size_t k = k0; k < k1; ++k) {
                   if (!tmp.empty())
                     tmp += ", ";

                     db.names.back().first += ", ";
                   else
                     first_arg = false;
-                  db.names.back().first += tmp;
+                  db.names.back().first.append(tmp);
                 }
               }
               t = t2;

             db.names.back().first.append(" &");
           else if (ref == 2)
             db.names.back().first.append(" &&");
-          db.names.back().first += ret2;
+          db.names.back().first.append(ret2);
           first = t;
         } else
           first = t;

   if (first != last && *first == '.') {
     if (db.names.empty())
       return first;
-    db.names.back().first += " (" + std::string(first, last) + ")";
+    db.names.back().first = db.names.back().first + " (" + demangle_string(first, last) + ")";
     first = last;
   }
   return first;

 }
 
 namespace {
-template <class StrT> struct string_pair {
-  StrT first;
-  StrT second;
-
-  string_pair() = default;
-  string_pair(StrT f) : first(std::move(f)) {}
-  string_pair(StrT f, StrT s) : first(std::move(f)), second(std::move(s)) {}
-  template <size_t N> string_pair(const char (&s)[N]) : first(s, N - 1) {}
-
-  size_t size() const { return first.size() + second.size(); }
-  StrT full() const { return first + second; }
-  StrT move_full() { return std::move(first) + std::move(second); }
-};
-
 struct Db {
-  typedef std::vector<string_pair<std::string>> sub_type;
-  typedef std::vector<sub_type> template_param_type;
+  arena arena; // Declare before vectors that may use it.
+  typedef std::vector<string_pair<demangle_string>,
+                      arena_allocator<string_pair<demangle_string>>> sub_type;
+  typedef std::vector<sub_type, arena_allocator<sub_type>> template_param_type;
   sub_type names;
   template_param_type subs;
-  std::vector<template_param_type> template_param;
+  std::vector<template_param_type, arena_allocator<template_param_type>> template_param;
   unsigned cv = 0;
   unsigned ref = 0;
   unsigned encoding_depth = 0;

       }
     }
     if (buf != nullptr) {
-      db.names.back().first += db.names.back().second;
+      db.names.back().first.append(db.names.back().second);
       std::memcpy(buf, db.names.back().first.data(), sz - 1);
       buf[sz - 1] = char(0);
     }