avoid allocations in SymbolTable::create

speeds up parsing by ~3%, system builds by a bit more than 1%

 # before

Benchmark 1: nix search --offline nixpkgs hello
  Time (mean ± σ):     574.7 ms ±   2.8 ms    [User: 566.3 ms, System: 8.0 ms]
  Range (min … max):   569.2 ms … 580.7 ms    50 runs

Benchmark 2: nix eval -f ../nixpkgs/pkgs/development/haskell-modules/hackage-packages.nix
  Time (mean ± σ):     394.4 ms ±   0.8 ms    [User: 361.8 ms, System: 32.3 ms]
  Range (min … max):   392.7 ms … 395.7 ms    50 runs

Benchmark 3: nix eval --raw --impure --expr 'with import <nixpkgs/nixos> {}; system'
  Time (mean ± σ):      2.976 s ±  0.005 s    [User: 2.757 s, System: 0.218 s]
  Range (min … max):    2.966 s …  2.990 s    50 runs

 # after

Benchmark 1: nix search --offline nixpkgs hello
  Time (mean ± σ):     572.4 ms ±   2.3 ms    [User: 563.4 ms, System: 8.6 ms]
  Range (min … max):   566.9 ms … 579.1 ms    50 runs

Benchmark 2: nix eval -f ../nixpkgs/pkgs/development/haskell-modules/hackage-packages.nix
  Time (mean ± σ):     381.7 ms ±   1.0 ms    [User: 348.3 ms, System: 33.1 ms]
  Range (min … max):   380.2 ms … 387.7 ms    50 runs

Benchmark 3: nix eval --raw --impure --expr 'with import <nixpkgs/nixos> {}; system'
  Time (mean ± σ):      2.936 s ±  0.005 s    [User: 2.715 s, System: 0.221 s]
  Range (min … max):    2.923 s …  2.946 s    50 runs

2 files changed, 15 insertions, 8 deletions

diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index a75357871..640c44c01 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -473,7 +473,7 @@ string ExprLambda::showNamePos() const
 size_t SymbolTable::totalSize() const
 {
     size_t n = 0;
-    for (auto & i : symbols)
+    for (auto & i : store)
         n += i.size();
     return n;
 }
diff --git a/src/libexpr/symbol-table.hh b/src/libexpr/symbol-table.hh
index 4eb6dac81..a090ebae5 100644
--- a/src/libexpr/symbol-table.hh
+++ b/src/libexpr/symbol-table.hh
@@ -1,7 +1,8 @@
 #pragma once
 
+#include <list>
 #include <map>
-#include <unordered_set>
+#include <unordered_map>
 
 #include "types.hh"
 
@@ -70,15 +71,21 @@ public:
 class SymbolTable
 {
 private:
-    typedef std::unordered_set<string> Symbols;
-    Symbols symbols;
+    std::unordered_map<std::string_view, Symbol> symbols;
+    std::list<string> store;
 
 public:
     Symbol create(std::string_view s)
     {
-        // FIXME: avoid allocation if 's' already exists in the symbol table.
-        std::pair<Symbols::iterator, bool> res = symbols.emplace(std::string(s));
-        return Symbol(&*res.first);
+        // Most symbols are looked up more than once, so we trade off insertion performance
+        // for lookup performance.
+        // TODO: could probably be done more efficiently with transparent Hash and Equals
+        // on the original implementation using unordered_set
+        auto it = symbols.find(s);
+        if (it != symbols.end()) return it->second;
+
+        const string & rawSym = store.emplace_back(s);
+        return symbols.emplace(rawSym, Symbol(&rawSym)).first->second;
     }
 
     size_t size() const
@@ -91,7 +98,7 @@ public:
     template<typename T>
     void dump(T callback)
     {
-        for (auto & s : symbols)
+        for (auto & s : store)
             callback(s);
     }
 };