Do not intern values during parsing

[Vexu]

I suspect that the performance hit caused by the interner is greater than any memory savings from it. One way to test this would be to disable the hashing in Interner and benchmark that against master on something like the sqlite amalgamation with -fsyntax-only (also maybe against clang and gcc) but I haven't done so yet.

[Vexu]

Some stats:

$ poop "intern/bin/arocc sqlite-amalgamation-3510100/sqlite3.c -Wno-unreachable-code -Wno-cast-qualifiers -fsyntax-only"  "no-intern/bin/arocc sqlite-amalgamation-3510100/sqlite3.c -Wno-unreachable-code -Wno-cast-qualifiers -fsyntax-only"
Benchmark 1 (25 runs): intern/bin/arocc sqlite-amalgamation-3510100/sqlite3.c -Wno-unreachable-code -Wno-cast-qualifiers -fsyntax-only
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           201ms ± 5.50ms     198ms …  227ms          1 ( 4%)        0%
  peak_rss           76.5MB ±  232KB    76.0MB … 76.8MB          0 ( 0%)        0%
  cpu_cycles         1.05G  ± 3.56M     1.04G  … 1.06G           0 ( 0%)        0%
  instructions       3.07G  ± 12.2      3.07G  … 3.07G           1 ( 4%)        0%
  cache_references   75.5M  ±  144K     75.3M  … 75.8M           0 ( 0%)        0%
  cache_misses       1.10M  ± 12.3K     1.06M  … 1.12M           2 ( 8%)        0%
  branch_misses      8.59M  ± 41.9K     8.53M  … 8.69M           0 ( 0%)        0%
Benchmark 2 (26 runs): no-intern/bin/arocc sqlite-amalgamation-3510100/sqlite3.c -Wno-unreachable-code -Wno-cast-qualifiers -fsyntax-only
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           196ms ±  978us     195ms …  199ms          0 ( 0%)        ⚡-  2.3% ±  1.1%
  peak_rss           78.8MB ±  189KB    78.4MB … 79.3MB          1 ( 4%)        💩+  3.1% ±  0.2%
  cpu_cycles         1.03G  ± 4.14M     1.02G  … 1.03G           0 ( 0%)        ⚡-  2.2% ±  0.2%
  instructions       3.03G  ± 15.0      3.03G  … 3.03G           0 ( 0%)        ⚡-  1.5% ±  0.0%
  cache_references   71.7M  ±  224K     71.3M  … 72.2M           0 ( 0%)        ⚡-  5.1% ±  0.1%
  cache_misses       1.11M  ± 15.4K     1.08M  … 1.15M           1 ( 4%)          +  1.2% ±  0.7%
  branch_misses      8.73M  ± 59.7K     8.64M  … 8.86M           0 ( 0%)        💩+  1.6% ±  0.3%

no-intern

diff --git a/src/aro/Value.zig b/src/aro/Value.zig
index 353b8ef8..d0b64731 100644
--- a/src/aro/Value.zig
+++ b/src/aro/Value.zig
@@ -987,11 +987,14 @@ pub fn complexConj(val: Value, qt: QualType, comp: *Compilation) !Value {
 }
 
 fn shallowCompare(lhs: Value, op: std.math.CompareOperator, rhs: Value) ?bool {
-    if (op == .eq) {
-        return lhs.opt_ref == rhs.opt_ref;
-    } else if (lhs.opt_ref == rhs.opt_ref) {
-        return std.math.Order.eq.compare(op);
-    }
+    _ = lhs; // autofix
+    _ = op; // autofix
+    _ = rhs; // autofix
+    // if (op == .eq) {
+    //     return lhs.opt_ref == rhs.opt_ref;
+    // } else if (lhs.opt_ref == rhs.opt_ref) {
+    //     return std.math.Order.eq.compare(op);
+    // }
     return null;
 }
 
diff --git a/src/backend/Interner.zig b/src/backend/Interner.zig
index 683b18d7..8dcb9024 100644
--- a/src/backend/Interner.zig
+++ b/src/backend/Interner.zig
@@ -8,7 +8,8 @@ const Limb = std.math.big.Limb;
 
 const Interner = @This();
 
-map: std.AutoArrayHashMapUnmanaged(void, void) = .empty,
+// map: std.AutoArrayHashMapUnmanaged(void, void) = .empty,
+count: usize = 0,
 items: std.MultiArrayList(struct {
     tag: Tag,
     data: u32,
@@ -571,7 +572,7 @@ pub const PackedU64 = packed struct(u64) {
 };
 
 pub fn deinit(i: *Interner, gpa: Allocator) void {
-    i.map.deinit(gpa);
+    // i.map.deinit(gpa);
     i.items.deinit(gpa);
     i.extra.deinit(gpa);
     i.limbs.deinit(gpa);
@@ -580,9 +581,9 @@ pub fn deinit(i: *Interner, gpa: Allocator) void {
 
 pub fn put(i: *Interner, gpa: Allocator, key: Key) !Ref {
     if (key.toRef()) |some| return some;
-    const adapter: KeyAdapter = .{ .interner = i };
-    const gop = try i.map.getOrPutAdapted(gpa, key, adapter);
-    if (gop.found_existing) return @enumFromInt(gop.index);
+    // const adapter: KeyAdapter = .{ .interner = i };
+    // const gop = try i.map.getOrPutAdapted(gpa, key, adapter);
+    // if (gop.found_existing) return @enumFromInt(gop.index);
     try i.items.ensureUnusedCapacity(gpa, 1);
 
     switch (key) {
@@ -751,7 +752,8 @@ pub fn put(i: *Interner, gpa: Allocator, key: Key) !Ref {
         => unreachable,
     }
 
-    return @enumFromInt(gop.index);
+    defer i.count += 1;
+    return @enumFromInt(i.count);
 }
 
 fn addExtra(i: *Interner, gpa: Allocator, extra: anytype) Allocator.Error!u32 {

There is more interning going on than I expected:

total interned 8277
    1 items interned 3835 times
    2 items interned 1390 times
    3 items interned 1102 times
    6 items interned 330 times
    4 items interned 319 times
    5 items interned 169 times
    9 items interned 121 times
    7 items interned 95 times
    8 items interned 81 times
   12 items interned 67 times
   10 items interned 47 times
   18 items interned 32 times
   14 items interned 30 times
   11 items interned 29 times
   15 items interned 28 times
   21 items interned 23 times
   24 items interned 23 times
   16 items interned 19 times
   13 items interned 19 times
   20 items interned 18 times
   30 items interned 18 times
   17 items interned 15 times
   25 items interned 14 times
   27 items interned 13 times
   22 items interned 12 times
   33 items interned 12 times
   40 items interned 11 times
   26 items interned 11 times
   28 items interned 10 times
   19 items interned 10 times
.{ .int = .{ .u64 = 2147483647 } } interned 54238 times
.{ .int = .{ .big_int = .{ .limbs = { ... }, .positive = true } } } interned 47923 times
.{ .int = .{ .u64 = 2 } } interned 5240 times
.{ .int = .{ .u64 = 8 } } interned 3205 times
.{ .int = .{ .u64 = 4 } } interned 2909 times
.{ .int = .{ .u64 = 3 } } interned 2101 times
.{ .int = .{ .u64 = 7 } } interned 1871 times
.{ .int = .{ .u64 = 16 } } interned 1623 times
.{ .int = .{ .u64 = 32 } } interned 1492 times
.{ .int = .{ .u64 = 64 } } interned 1358 times
.{ .int = .{ .u64 = 5 } } interned 1335 times
.{ .int = .{ .u64 = 128 } } interned 1087 times
.{ .int = .{ .i64 = -1 } } interned 1079 times
.{ .int = .{ .u64 = 1254 } } interned 1005 times
.{ .int = .{ .u64 = 10 } } interned 864 times
.{ .int = .{ .u64 = 6 } } interned 804 times
.{ .int = .{ .u64 = 12 } } interned 639 times
.{ .int = .{ .u64 = 24 } } interned 614 times
.{ .int = .{ .u64 = 323 } } interned 543 times

intern stats

diff --git a/src/aro/Compilation.zig b/src/aro/Compilation.zig
index ff68b339..06fb62d7 100644
--- a/src/aro/Compilation.zig
+++ b/src/aro/Compilation.zig
@@ -225,6 +225,50 @@ pub fn deinit(comp: *Compilation) void {
     comp.generated_buf.deinit(gpa);
     comp.builtins.deinit(gpa);
     comp.string_interner.deinit(gpa);
+    {
+        const T = struct { key: Interner.Key, count: u32 };
+        var list: std.ArrayList(T) = .empty;
+        defer list.deinit(gpa);
+
+        var by_count: std.AutoArrayHashMapUnmanaged(u32, u32) = .empty;
+        defer by_count.deinit(gpa);
+
+        for (comp.interner.map.values(), 0..) |count, index| {
+            const gop = by_count.getOrPut(gpa, count) catch @panic("OOM");
+            if (gop.found_existing) {
+                gop.value_ptr.* += 1;
+            } else {
+                gop.value_ptr.* = 1;
+            }
+            if (count > 500) {
+                list.append(gpa, .{
+                    .count = count,
+                    .key = comp.interner.get(@enumFromInt(index)),
+                }) catch @panic("OOM");
+            }
+        }
+
+        std.mem.sort(T, list.items, {}, struct {
+            fn lessThan(_: void, lhs: T, rhs: T) bool {
+                return lhs.count > rhs.count;
+            }
+        }.lessThan);
+        by_count.sort(struct {
+            values: []u32,
+            pub fn lessThan(ctx: @This(), a_index: usize, b_index: usize) bool {
+                return ctx.values[a_index] > ctx.values[b_index];
+            }
+        }{ .values = by_count.values() });
+
+        std.debug.print("total interned {d}\n", .{comp.interner.map.count()});
+        for (by_count.keys(), by_count.values()) |count, times| {
+            if (times < 10) continue;
+            std.debug.print("{d: >5} items interned {d} times\n", .{ count, times });
+        }
+        for (list.items) |entry| {
+            std.debug.print("{any} interned {d} times\n", .{ entry.key, entry.count });
+        }
+    }
     comp.interner.deinit(gpa);
     comp.environment.deinit(gpa);
     comp.type_store.deinit(gpa);
diff --git a/src/backend/Interner.zig b/src/backend/Interner.zig
index 683b18d7..fd452439 100644
--- a/src/backend/Interner.zig
+++ b/src/backend/Interner.zig
@@ -8,7 +8,7 @@ const Limb = std.math.big.Limb;
 
 const Interner = @This();
 
-map: std.AutoArrayHashMapUnmanaged(void, void) = .empty,
+map: std.AutoArrayHashMapUnmanaged(void, u32) = .empty,
 items: std.MultiArrayList(struct {
     tag: Tag,
     data: u32,
@@ -582,7 +582,11 @@ pub fn put(i: *Interner, gpa: Allocator, key: Key) !Ref {
     if (key.toRef()) |some| return some;
     const adapter: KeyAdapter = .{ .interner = i };
     const gop = try i.map.getOrPutAdapted(gpa, key, adapter);
-    if (gop.found_existing) return @enumFromInt(gop.index);
+    if (gop.found_existing) {
+        gop.value_ptr.* += 1;
+        return @enumFromInt(gop.index);
+    }
+    gop.value_ptr.* = 1;
     try i.items.ensureUnusedCapacity(gpa, 1);
 
     switch (key) {

[Vexu]

For reference:

Benchmark 1 (25 runs): intern/bin/arocc sqlite-amalgamation-3510100/sqlite3.c -Wno-cast-qualifiers -fsyntax-only
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           201ms ± 5.19ms     198ms …  225ms          1 ( 4%)        0%
  peak_rss           76.6MB ±  272KB    76.2MB … 77.2MB          0 ( 0%)        0%
  cpu_cycles         1.05G  ± 3.55M     1.04G  … 1.06G           0 ( 0%)        0%
  instructions       3.07G  ± 14.9      3.07G  … 3.07G           0 ( 0%)        0%
  cache_references   75.8M  ±  383K     75.3M  … 76.6M           0 ( 0%)        0%
  cache_misses       1.11M  ± 16.5K     1.07M  … 1.14M           0 ( 0%)        0%
  branch_misses      8.59M  ± 30.0K     8.54M  … 8.66M           0 ( 0%)        0%
Benchmark 2 (26 runs): no-intern/bin/arocc sqlite-amalgamation-3510100/sqlite3.c -Wno-cast-qualifiers -fsyntax-only
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           196ms ±  988us     194ms …  199ms          4 (15%)        ⚡-  2.3% ±  1.0%
  peak_rss           79.0MB ±  210KB    78.4MB … 79.3MB          1 ( 4%)        💩+  3.1% ±  0.2%
  cpu_cycles         1.03G  ± 3.27M     1.02G  … 1.03G           1 ( 4%)        ⚡-  2.2% ±  0.2%
  instructions       3.03G  ± 12.4      3.03G  … 3.03G           0 ( 0%)        ⚡-  1.4% ±  0.0%
  cache_references   71.7M  ±  217K     71.4M  … 72.2M           0 ( 0%)        ⚡-  5.4% ±  0.2%
  cache_misses       1.11M  ± 10.0K     1.10M  … 1.14M           1 ( 4%)          +  0.3% ±  0.7%
  branch_misses      8.71M  ± 42.5K     8.64M  … 8.80M           0 ( 0%)        💩+  1.4% ±  0.2%
Benchmark 3 (20 runs): clang sqlite-amalgamation-3510100/sqlite3.c -fsyntax-only
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           253ms ± 3.91ms     250ms …  268ms          2 (10%)        💩+ 25.8% ±  1.4%
  peak_rss            123MB ±  333KB     122MB …  124MB          1 ( 5%)        💩+ 60.4% ±  0.2%
  cpu_cycles         1.34G  ± 16.9M     1.33G  … 1.41G           1 ( 5%)        💩+ 27.9% ±  0.7%
  instructions       3.13G  ±  797K     3.13G  … 3.13G           0 ( 0%)        💩+  1.9% ±  0.0%
  cache_references    277M  ± 1.18M      276M  …  281M           1 ( 5%)        💩+266.2% ±  0.7%
  cache_misses       15.5M  ±  406K     14.8M  … 16.6M           1 ( 5%)        💩+1293.8% ± 14.7%
  branch_misses      7.76M  ± 75.7K     7.67M  … 7.99M           1 ( 5%)        ⚡-  9.7% ±  0.4%
Benchmark 4 (26 runs): gcc sqlite-amalgamation-3510100/sqlite3.c -fsyntax-only
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           199ms ± 1.44ms     197ms …  203ms          0 ( 0%)          -  0.7% ±  1.1%
  peak_rss           94.4MB ±  339KB    93.6MB … 95.1MB          1 ( 4%)        💩+ 23.2% ±  0.2%
  cpu_cycles         1.03G  ± 5.55M     1.02G  … 1.04G           2 ( 8%)        ⚡-  2.0% ±  0.3%
  instructions       2.73G  ±  370K     2.73G  … 2.73G           0 ( 0%)        ⚡- 11.1% ±  0.0%
  cache_references    132M  ±  343K      131M  …  132M           0 ( 0%)        💩+ 73.7% ±  0.3%
  cache_misses       6.42M  ± 54.0K     6.33M  … 6.52M           0 ( 0%)        💩+477.3% ±  2.1%
  branch_misses      7.05M  ± 22.6K     7.00M  … 7.11M           0 ( 0%)        ⚡- 17.9% ±  0.2%
Benchmark 5 (114 runs): tcc sqlite-amalgamation-3510100/sqlite3.c -c
  measurement          mean ± σ            min … max           outliers         delta
  wall_time          44.0ms ±  892us    41.5ms … 46.1ms          2 ( 2%)        ⚡- 78.1% ±  0.5%
  peak_rss           15.2MB ±  214KB    14.5MB … 15.7MB          2 ( 2%)        ⚡- 80.2% ±  0.1%
  cpu_cycles          222M  ± 2.58M      216M  …  227M           5 ( 4%)        ⚡- 78.8% ±  0.1%
  instructions        617M  ± 1.43K      617M  …  617M           6 ( 5%)        ⚡- 79.9% ±  0.0%
  cache_references   10.2M  ±  131K     9.91M  … 10.6M           2 ( 2%)        ⚡- 86.5% ±  0.1%
  cache_misses        244K  ± 13.1K      213K  …  282K           1 ( 1%)        ⚡- 78.0% ±  0.5%
  branch_misses      2.10M  ± 20.3K     2.04M  … 2.15M           2 ( 2%)        ⚡- 75.6% ±  0.1%