From b8bcd9c0e826c7cb0b45d1ae5a52a325d22fd048 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 15 Nov 2026 18:45:08 -0800 Subject: Make MemMerge inputs packed --- chapter32/README.md | 48 +++++++++ .../com/seaofnodes/simple/codegen/Serialize.java | 18 ++-- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 12 +-- .../java/com/seaofnodes/simple/node/LoopNode.java | 4 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 110 +++++++++++++++++---- .../java/com/seaofnodes/simple/MemMergeTest.java | 84 ++++++++++++++++ 6 files changed, 239 insertions(+), 37 deletions(-) create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java diff --git a/chapter32/README.md b/chapter32/README.md index 4cb1d79b..d7ca40db 100644 --- a/chapter32/README.md +++ b/chapter32/README.md @@ -221,6 +221,54 @@ After these fixes, all 802 suite executions pass at log 8; 444 chapter tests and 34 focused worklist, scheduling, and memory tests pass at log 1. Existing spill expectations are unchanged. +### Dense MemMerge inputs + +`MemMergeNode` now keeps precise alias slices in a dense input list, with an +`IntHashMap` from alias to input index and a reverse array for iteration. +Alias order is preserved. Missing aliases use input 1, the bulk default. +Deletion compacts the list and rebuilds the small map; graph copies own their +maps. Bulk-Phi splitting and object loading use alias lookup rather than +assuming an alias is an input index. The existing sparse object encoding remains +compatible with the baseline compiler. + +This is deliberately a storage experiment. `_aliasLimit` retains the previous +sparse extent for encoding and fold eligibility. The old `allDefault` test +counts null holes as non-defaults; simply folding whenever the dense list is +empty introduces additional optimizations. That separate trial altered code +quality: graphical Tic-tac-toe's weighted spill score rose from 1085 to 1240 +with its rebuilt library. The retained version preserves the old folding +behavior and matches baseline peephole counts, code sizes, and spill counts on +all measured workloads. + +Against commit `8b80d94c`, the final interleaved comparison measured: + +| Workload | Compile time change | Compiler-thread allocation change | +| --- | ---: | ---: | +| sys library | -5.8% | -3.7% | +| Clock | -2.1% | -10.8% | +| Breakout | -2.9% | -6.4% | +| Graphical tic-tac-toe | -0.5% | -5.3% | +| HelloWorld | -0.6% | -4.5% | + +The timing improvement is modest; sub-percent differences are within noise. +The structural reduction is much larger. After Lower, sys's live MemMerge input +slots fall from 54,388 to 2,462, Clock's from 54,255 to 2,237, and Breakout's from +61,286 to 2,592. These are input-slot counts, not total heap measurements; the +maps and reverse arrays have their own cost. + +Measurements use Java 21, assertions at log10, two active processors, and a +256 MiB initial / 2 GiB maximum heap. The compiler runs through object export, +without gcc, linking, or execution. Isolated compiler class loaders alternate +in one JVM; six measured rounds follow three warmups for each workload. Games +read the same baseline sys objects. Time changes are medians of paired ratios; +allocation uses ThreadMXBean. Earlier separate-process runs drifted enough that +the interleaved comparison is the basis for the table. + +The full suite passes at log8; 444 chapter tests and 18 memory/import tests pass +with every-step verification. Raw measurements, saved compiler classes, and +reproduction commands are in `build/memmerge-dense/`; verification logs are in +`build/test-profile/dense-final-*.log`. + ## Build and test From `chapter32`, using the existing offline dependency caches: diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index b168c4af..e1aee9aa 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -265,9 +265,10 @@ public class Serialize { } // Write out the input indices packed. for( Node n : nodes ) { - for( int j=0; j= GlobalBits.RESERVED ) { - if( def == null ) continue; - local = aliases.map(fileAliases,i); - } - n.setDefX(local,def); + if( n instanceof MemMergeNode mem && i>=2 ) { + if( def==null ) continue; + int alias = i>=GlobalBits.RESERVED ? aliases.map(fileAliases,i) : i; + mem.alias(alias,def); + } else n.setDefX(i,def); // Call's output[0] is always the CallEnd if( n instanceof CallEndNode cend && i==0 ) { var outs = cend.call()._outputs; diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index b49163e7..f4d1e195 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -118,7 +118,7 @@ public class BulkMemPhiNode extends PhiNode { } else if( m instanceof MemMergeNode mmm && mmm.in(1) instanceof BulkMemPhiNode bulk && bulk._aliases.get(alias) && - (alias >= mmm.nIns() || mmm.in(alias)==null) ) + mmm.explicitAlias(alias)==null ) return false; return true; } @@ -187,11 +187,9 @@ public class BulkMemPhiNode extends PhiNode { // First explicit MemMerge slice still covered by this Phi. A user's slice // may point to this Phi after a precise Phi folds; splitting is still valid. private int missingAlias( MemMergeNode mmm ) { - for( int alias=2; alias= 0; alias = bulk._aliases.nextSetBit(alias+1) ) - if( alias >= mmm.nIns() || mmm.in(alias)==null ) + if( mmm.explicitAlias(alias)==null ) return false; return true; } diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java index c4d55335..2ab76429 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -60,12 +60,12 @@ public class LoopNode extends RegionNode { // executing. Keep synthetic nodes local; do not GVN into that graph. Node top = ConstantNode.raw(Type.TOP); top.setDef(0,fun); - Node memout = new MemMergeNode(); + MemMergeNode memout = new MemMergeNode(); memout.addDef(f); // placeholder for control memout.addDef(top); for( Node u : _outputs ) if( u instanceof PhiNode phi && phi._type.isa(TypeMem.BOT) ) - memout.addDef(phi); + memout.alias(memout.nIns(),phi); memout.init(); Node ctrl = ret.ctrl(), mem = ret.mem(), expr = ret.expr(); diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 19420839..d5eaa743 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -8,30 +8,78 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.util.AryInt; +import com.seaofnodes.simple.util.IntHashMap; import java.util.*; /** - * Memory Merge - a merge of many aliases into a "fat memory". All aliases - * are here, but most will be lazy - take the default fat memory. + * Memory merge: default bulk memory plus dense inputs for explicit alias slices. */ public class MemMergeNode extends Node { public MemMergeNode( Node ...nodes) { super(nodes); _type = TypeMem.BOT; } - public MemMergeNode(MemMergeNode mem) { super(mem); } + // Inputs 0/1 are control/default; the remaining inputs are dense precise slices. + // Keep alias order so graph walks retain the old sparse representation's order. + private AryInt _aliases; + private IntHashMap _aliasToInput; + private int _readSize; + // Retain the old sparse extent for encoding and fold eligibility, without its holes. + private int _aliasLimit=2; + + public MemMergeNode(MemMergeNode mem) { super(mem); copyAliases(mem); _aliasLimit=mem._aliasLimit; } + + private void copyAliases(MemMergeNode mem) { + if( mem._aliases==null ) return; + _aliases = new AryInt().addAll(mem._aliases); + _aliasToInput = new IntHashMap(0); + reindex(); + } + + @Override protected Object clone() throws CloneNotSupportedException { + MemMergeNode copy = (MemMergeNode)super.clone(); + copy.copyAliases(this); + return copy; + } + + public int aliasAt(int input) { return _aliases.at(input-2); } + + // Explicit input, or null when the default supplies this alias. + public Node explicitAlias(int alias) { + int input = _aliasToInput==null ? 0 : _aliasToInput.get(alias); + return input==0 ? null : in(input); + } + + // Preserve the existing sparse object encoding; input indices on disk are aliases. + public int packedSize() { return _aliasLimit; } + public int readSize() { return _readSize; } + public Node packedInput(int alias) { return alias<2 ? in(alias) : explicitAlias(alias); } + + private void reindex() { + _aliasToInput.clear(); + for( int i=0; i<_aliases.len(); i++ ) _aliasToInput.put(_aliases.at(i),i+2); + } + + private void removeAlias(int input) { + setDef(input,null); + _inputs.remove(input); + _aliases.remove(input-2); + reindex(); + } @Override public Tag serialTag() { return Tag.MemMerge; } public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { // A memory merge always has inputs. Zero escapes a wide alias table, // preserving every existing nonzero single-byte count. assert nIns()>0; - baos.packed1(nIns()<=255 ? nIns() : 0); - if( nIns()>255 ) baos.packed4(nIns()); + baos.packed1(packedSize()<=255 ? packedSize() : 0); + if( packedSize()>255 ) baos.packed4(packedSize()); } static Node make( BAOS bais ) { int count=bais.packed1(); if( count==0 ) count=bais.packed4(); - Node mem=new MemMergeNode(); - mem.setDefX(count-1,null); + MemMergeNode mem=new MemMergeNode(null,null); + mem._readSize=count; + mem._aliasLimit=count; return mem; } @@ -42,7 +90,7 @@ public class MemMergeNode extends Node { protected ExprPrinter _print1(ExprPrinter p) { p.p("MEM[ "); for( int j=2; j=nIns() || in(i)==null ) - setDefX(i,mem.in(i)); + int alias = mem.aliasAt(i); + if( explicitAlias(alias)==null ) + alias(alias,mem.in(i)); } } CodeGen.CODE.add(mem.in(1)); @@ -140,12 +191,33 @@ public class MemMergeNode extends Node { public Node in( Var v ) { return in(v._idx); } public Node alias( int alias ) { - assert !(in(1) instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) && - (alias >= nIns() || in(alias)==null)); - return alias < nIns() && in(alias)!=null ? in(alias) : in(1); + Node precise = explicitAlias(alias); + assert !(in(1) instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) && precise==null); + return precise==null ? in(1) : precise; } - public Node alias( int alias, Node st ) { return setDefX(alias,st); } + public Node alias( int alias, Node st ) { + if( alias==1 ) return setDef(1,st); + assert alias>1; + _aliasLimit=Math.max(_aliasLimit,alias+1); + int input = _aliasToInput==null ? 0 : _aliasToInput.get(alias); + if( st==null ) { + if( input!=0 ) removeAlias(input); + return st; + } + if( input!=0 ) return setDef(input,st); + if( _aliases==null ) { + _aliases = new AryInt(); + _aliasToInput = new IntHashMap(0); + } + int pos = Arrays.binarySearch(_aliases._es,0,_aliases.len(),alias); + assert pos<0; + pos = -pos-1; + _aliases.insert(pos,alias); + for( int i=pos; i<_aliases.len(); i++ ) _aliasToInput.put(_aliases.at(i),i+2); + insertDef(pos+2,st); + return st; + } // Now one-time do a useless-phi removal void _useless( ) { diff --git a/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java b/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java new file mode 100644 index 00000000..cb17982e --- /dev/null +++ b/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java @@ -0,0 +1,84 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeMem; +import org.junit.Test; +import static org.junit.Assert.*; + +public class MemMergeTest { + @Test public void testDenseAliasesAndDefaults() { + CodeGen code = new CodeGen(""); + Node defaults = code.con(TypeMem.START), value = code.con(TypeMem.BOT).keep(); + MemMergeNode mem = new MemMergeNode(null,defaults); + mem.alias(10000,value); + mem.alias(2,value); + mem.alias(513,value); + assertEquals(5,mem.nIns()); + assertEquals(2,mem.aliasAt(2)); + assertEquals(513,mem.aliasAt(3)); + assertEquals(10000,mem.aliasAt(4)); + assertSame(value,mem.alias(10000)); + assertSame(defaults,mem.alias(512)); + assertEquals(10001,mem.packedSize()); + assertNull(mem.packedInput(9999)); + assertSame(value,mem.packedInput(10000)); + mem.alias(513,null); + assertEquals(4,mem.nIns()); + assertEquals(10000,mem.aliasAt(3)); + assertSame(value,mem.alias(10000)); + mem.alias(2,defaults); + assertSame(mem,mem.idealize()); + assertEquals(3,mem.nIns()); + assertSame(defaults,mem.alias(2)); + // Removing/reinserting colliding keys must not leave tombstones or stale slots. + for( int i=0; i<100; i++ ) { + mem.alias(100+i*8,value); + mem.alias(100+i*8,null); + } + assertEquals(3,mem.nIns()); + mem.alias(10000,defaults); + assertSame(mem,mem.idealize()); + assertEquals(2,mem.nIns()); + // Retain the sparse implementation's fold eligibility for this experiment. + assertNull(mem.idealize()); + assertSame(defaults,new MemMergeNode(null,defaults).idealize()); + value.unkeep(); + } + + @Test public void testIndependentCopyMaps() { + CodeGen code = new CodeGen(""); + Node defaults = code.con(TypeMem.START), value = code.con(TypeMem.BOT); + MemMergeNode mem = new MemMergeNode(null,defaults); + mem.alias(200,value); + MemMergeNode copy = (MemMergeNode)mem.copyEmpty(); + for( Node in : mem._inputs ) copy.addDef(in); + copy.alias(7,value); + assertEquals(3,mem.nIns()); + assertEquals(4,copy.nIns()); + assertSame(defaults,mem.alias(7)); + assertSame(value,mem.alias(200)); + copy.alias(200,null); + assertSame(value,mem.alias(200)); + assertSame(defaults,copy.alias(200)); + code._phase = CodeGen.Phase.Select; + MemMergeNode selected = new MemMergeNode(mem); + assertEquals(200,selected.aliasAt(2)); + assertSame(value,selected.alias(200)); + } + + @Test public void testStackedMergesKeepOverrides() { + CodeGen code = new CodeGen(""); + Node defaults = code.con(TypeMem.START), value = code.con(TypeMem.BOT), override = code.con(TypeMem.TOP); + MemMergeNode inner = new MemMergeNode(null,defaults); + inner.alias(8,value); + inner.alias(10000,value); + MemMergeNode outer = new MemMergeNode(null,inner); + outer.alias(10000,override); + assertSame(outer,outer.idealize()); + assertEquals(4,outer.nIns()); + assertSame(defaults,outer.in(1)); + assertSame(value,outer.alias(8)); + assertSame(override,outer.alias(10000)); + } +} -- cgit v1.2.3