From 51a029304d8105b201bdfb81a7692b8a1b16b028 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 16 Nov 2026 10:18:30 -0800 Subject: Packing Serialize tighter --- chapter32/README.md | 98 +++++++++++++++++++++- .../com/seaofnodes/simple/codegen/Serialize.java | 23 ++--- .../com/seaofnodes/simple/node/MemMergeNode.java | 21 ++--- .../com/seaofnodes/simple/type/TypeFunPtr.java | 5 +- .../main/java/com/seaofnodes/simple/util/BAOS.java | 33 ++++++-- .../test/java/com/seaofnodes/simple/BAOSTest.java | 58 +++++++++++++ .../java/com/seaofnodes/simple/MemMergeTest.java | 5 +- .../seaofnodes/simple/SeparateCompilationTest.java | 36 ++++++++ .../simple/type/PackedTypeTestSupport.java | 20 +++++ 9 files changed, 260 insertions(+), 39 deletions(-) create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/BAOSTest.java create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java (limited to 'chapter32') diff --git a/chapter32/README.md b/chapter32/README.md index 35387ec2..f06b404f 100644 --- a/chapter32/README.md +++ b/chapter32/README.md @@ -359,15 +359,107 @@ summaries, and 145,482 of node records and input references, plus 88 header bytes. HelloWorld's strings, mappings, and types alone take 14,161 of its 14,635 bytes; its graph records and inputs take only 447 bytes. -That suggests investigating metadata scope before choosing a different integer -encoding. The current writer emits the full compilation's alias, function, and +The broad metadata footprint warrants a separate investigation. The current +writer emits the full compilation's alias, function, and return-PC mappings into each object, along with their names. Restricting them to identities needed by that object's declarations, summaries, and graph may save space, but requires coordinated remapping in the writer and reader. -These measurements make no packing or format changes. Profiling helpers, +Those measurements made no packing or format changes. Profiling helpers, saved baseline classes, per-object sizes, byte breakdowns, and timings are in `build/packing-profile/`. +### Which packed fields have avoidable overhead? + +A deeper byte-count pass on `c21026c5` found three localized candidates: + +| Candidate | Modeled saving across sys | Clock | Breakout | +| --- | ---: | ---: | ---: | +| Unsigned varints for type-child IDs | 40,137 bytes | 2,757 | 3,561 | +| Sparse serialized MemMerge inputs | 34,280 bytes | 7,133 | 12,683 | +| Extend singleton function-ID encoding beyond ID 63 | 23,441 bytes | 1,140 | 1,409 | + +At that baseline, type-child IDs used `packed4`: IDs 128 through 16,383 took five bytes +where an unsigned varint would take two. [MemMerge](src/main/java/com/seaofnodes/simple/node/MemMergeNode.java) +was dense in memory, but its serialized representation retained the old alias +slot space; sys's MemMerge input data contained 36,138 zero bytes for default +slots. The sparse model keeps the first two inputs and encodes a non-default +count plus `(alias, node ID)` pairs, including the extra count/pair cost. +[TypeFunPtr](src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java) had a +compact singleton form for non-null functions with fewer than six arguments, +but only below function ID 64. Larger singleton IDs became mostly-zero bitsets. + +These estimates concern disjoint fields and together amount to about 21% of +sys's `.simple` payload, 25% of Clock's, and 22% of Breakout's. The implementation +and actual measurements follow below. A generic signed-varint substitution is not equivalent: +zigzag encoding would make ordinary ASCII characters 64 through 127 larger. + +The metadata scan also explains HelloWorld's size. One constant pointing to +`class:sys` reaches 672 of its 700 serialized types, including unrelated +namespace members. Consequently, 363 of its 364 alias-map rows are referenced +by the current type representation. Dropping those rows alone is insufficient; +imported-type references or more selective namespace types need investigation. +Return-PC tables are a clearer candidate: only 214 of 7,788 RPC rows written +across sys objects are referenced by the serialized types, nodes, and summaries. + +Adding a general XInt dictionary is less promising: storing unique existing +encodings plus references is already slightly larger across sys, before table +headers. The singleton encoding addresses the common case more directly. +Detailed field counts, size models, and reproduction helpers are in +`build/simple-size/`. The instrumented exports preserve `.text` and `.simple` +bytes in all 27 measured objects; that investigation changed no format. + +## Pack the serialized IR more tightly + +[BAOS.packed4](src/main/java/com/seaofnodes/simple/util/BAOS.java) now uses +signed zigzag varints: -64 through 63 fit in one byte, -8192 through 8191 in +two, and the full signed int range takes at most five bytes. Each byte carries +seven payload bits and a continuation bit. Strings use a packed byte length +followed by raw UTF-8, keeping ordinary ASCII at one byte per character. + +MemMerge writes its control/default inputs and explicit `(alias, node ID)` +pairs, omitting default holes. It retains the old alias extent separately +because that value still affects folding eligibility. The reader remaps each +explicit alias into the importing compilation. Non-null singleton function +types with fewer than six arguments now use the compact form through function +ID 65535, with the matching `packed2` reader. + +Actual `.simple` sizes against `c21026c5`, including all 22 sys objects: + +| Workload | Before, bytes | After, bytes | Reduction | +| --- | ---: | ---: | ---: | +| sys library | 469,881 | 368,694 | 21.5% | +| Clock | 43,854 | 31,906 | 27.2% | +| Breakout | 80,950 | 62,139 | 23.2% | +| Graphical tic-tac-toe | 44,353 | 35,961 | 18.9% | +| HelloWorld | 14,635 | 11,523 | 21.3% | + +Across these 26 objects, the payload falls from 653,673 to 510,223 bytes, +saving 143,450 bytes (21.9%). Sys's type records and child IDs shrink from +180,456 to 116,948 bytes; node inputs shrink from 85,189 to 50,635. Together +those two chunks account for 96.9% of sys's saving. Identity mappings remain +73,564 bytes, leaving the metadata questions above for another pass. + +Compile timings are mixed. Baseline/new median milliseconds were sys +1,056/1,065, Clock 335/352, Breakout 689/674, graphical tic-tac-toe 282/283, +and HelloWorld 69/68. There is no consistent speed win in this run. The +comparison alternates two isolated compiler class loaders, with three warmups +and six measured rounds per workload, Java 21, two active processors, log10 +assertions, and a 256 MiB initial / 2 GiB maximum heap. Each compiler reads +its own freshly generated sys objects. Linking and execution are excluded. + +Every pair has matching peephole/no-progress counts, code sizes, and spill +metrics. All 26 `.text` sections are byte-identical. New tests cover signed +integer boundaries and overflow, Unicode strings, singleton function IDs, +sparse memory imports beyond alias 255, and rejection of the old format. +The Windows suite at log8 and Linux suite at log10 each pass 811 test executions. +Raw measurements, byte breakdowns, helpers, and saved baseline classes are in +`build/format-profile/`. + +The object header changes from `C0DE` to `C0D2`. Existing `.simple` objects +must be rebuilt; an old header produces an explicit rebuild error. For an +existing chapter32 build, `make clean` followed by `make -j 8 release` rebuilds +the generated artifacts. Rebuild any separately maintained Simple libraries too. + ## 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 e1aee9aa..9c43e029 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -103,8 +103,10 @@ public class Serialize { Type startType = TypeTuple.make(Type.CONTROL,stopType.mem(),((StartNode)nodes.at(0)).arg()); BAOS baos = new BAOS(); - // A - Print the C0DE header. The format is not versioned yet. - baos.write('C').write('0').write('D').write('E'); + // A - Print the C0DE header; last byte is the version number. + // Format 2: gradual packed ints, UTF-8 strings, sparse MemMerge edges, + // and wider singleton function IDs. Reject old cached objects clearly. + baos.write('C').write('0').write('D').write('2'); // Count unique Types var types = new HashMap(); @@ -265,10 +267,12 @@ public class Serialize { } // Write out the input indices packed. for( Node n : nodes ) { - int count = n instanceof MemMergeNode mem ? mem.packedSize() : n.nIns(); + int count = n.nIns(); for( int j=0; j=2 ) + baos.packed2(mem.aliasAt(j)); + Node def = n.in(j); Integer idx = def==null ? Integer.valueOf(0) : anodes.get(def); // Imported function constants retain their symbol, not a body. if( idx==null && n instanceof FunPtrNode && j==1 ) idx=0; @@ -331,7 +335,7 @@ public class Serialize { Type.TAGOFFS(); // A - Read a header - if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='E' ) + if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='2' ) throw new IllegalArgumentException("Unsupported serialized IR format; rebuild the object file"); // B - Packed read of #strings, then strings @@ -364,7 +368,7 @@ public class Serialize { String[] strs = elf._strs; if( strs == null ) { // A - Read a header - if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != 'E' ) + if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != '2' ) throw new IllegalArgumentException( "Unsupported serialized IR format; rebuild the object file" ); // B - Packed read of #strings, then strings @@ -503,14 +507,13 @@ public class Serialize { for( Node n : nodes ) { int len = n instanceof MemMergeNode mem ? mem.readSize() : n.nIns(); for( int i = 0; i=2 ? bais.packed2() : 0; int idx = bais.packed2(); Node def = idx==0 ? null : nodes.at(idx-1); - // MemMerge precise aliases are encoded by their input slot. - // Remap populated file-local slots into this compilation's - // local alias numbering; null holes carry no identity. + // Remap only explicit slices; omitted aliases use the default. if( n instanceof MemMergeNode mem && i>=2 ) { if( def==null ) continue; - int alias = i>=GlobalBits.RESERVED ? aliases.map(fileAliases,i) : i; + int alias = aliases.map(fileAliases,fileAlias); mem.alias(alias,def); } else n.setDefX(i,def); // Call's output[0] is always the CallEnd 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 d5eaa743..a077e14b 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -24,7 +24,7 @@ public class MemMergeNode extends Node { private AryInt _aliases; private IntHashMap _aliasToInput; private int _readSize; - // Retain the old sparse extent for encoding and fold eligibility, without its holes. + // Retain the old sparse extent for fold eligibility, without its holes. private int _aliasLimit=2; public MemMergeNode(MemMergeNode mem) { super(mem); copyAliases(mem); _aliasLimit=mem._aliasLimit; } @@ -50,10 +50,8 @@ public class MemMergeNode extends Node { return input==0 ? null : in(input); } - // Preserve the existing sparse object encoding; input indices on disk are aliases. - public int packedSize() { return _aliasLimit; } + // The reader has not wired the dense inputs yet. public int readSize() { return _readSize; } - public Node packedInput(int alias) { return alias<2 ? in(alias) : explicitAlias(alias); } private void reindex() { _aliasToInput.clear(); @@ -68,18 +66,17 @@ public class MemMergeNode extends Node { } @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(packedSize()<=255 ? packedSize() : 0); - if( packedSize()>255 ) baos.packed4(packedSize()); + // Keep the extent even if its last precise slice was removed. Edges + // are dense: control/default followed by explicit (alias,input) pairs. + baos.packed4(_aliasLimit); + baos.packed2(nIns()); } static Node make( BAOS bais ) { - int count=bais.packed1(); - if( count==0 ) count=bais.packed4(); + int limit=bais.packed4(), count=bais.packed2(); + assert 2<=count && count<=limit; MemMergeNode mem=new MemMergeNode(null,null); mem._readSize=count; - mem._aliasLimit=count; + mem._aliasLimit=limit; return mem; } diff --git a/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 19ec5019..c6f53022 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -248,7 +248,7 @@ public class TypeFunPtr extends TypeNil { @Override int TAGOFF() { return 8; } @Override public void packed( BAOS baos, HashMap strs ) { assert _open; // Open: Passing extra args is fine, and extras ignored. - if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx() < 64 ) { + if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx()<=65535 ) { baos.write(TAGOFFS[_type] + nargs()); baos.packed2(fidx()); } else { @@ -259,8 +259,7 @@ public class TypeFunPtr extends TypeNil { } static TypeFunPtr packed( int tag, BAOS bais ) { if( tag < 6 ) { - int fidx = bais.read(); - assert fidx < 64; // Need a larger fidx space + int fidx = bais.packed2(); return malloc((byte)2,true,new Type[tag],null, XInt.make(fidx)); } byte nil = (byte)(tag==6 ? 2 : 3); diff --git a/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java b/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java index a4d1f183..c47d386c 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.util; //import java.util.HashMap; import java.util.Arrays; +import java.nio.charset.StandardCharsets; // "ByteArrayOutputStream", and Input Stream and not synchronized and has // matching pack/unpack strategies. @@ -125,15 +126,29 @@ public class BAOS { return x==0xFF ? read2() : x; } - // Write a packed i32 + // Signed zigzag varint: -64..63 use one byte, -8192..8191 two, + // and the full int range needs at most five. Seven payload bits per byte. public void packed4(int x) { - ((-127 <= x && x <= 127 ) ? write(x) : write(-128).write4(x)).histo(x); + histo(x); + int bits = (x<<1) ^ (x>>31); + while( (bits & ~127)!=0 ) { + write((bits & 127) | 128); + bits >>>= 7; + } + write(bits); } // Read a packed i32 public int packed4() { - int x = _buf[_len++]; // Signed byte read - return x== -128 ? read4() : x; + int bits=0; + for( int shift=0; shift<32; shift+=7 ) { + int b = read(); + if( shift==28 && (b & 0xF0)!=0 ) + throw new IllegalArgumentException("Packed int overflow"); + bits |= (b & 127)<>>1) ^ -(bits & 1); + } + throw new IllegalArgumentException("Unterminated packed int"); } // Write a packed i64 @@ -148,14 +163,16 @@ public class BAOS { } public void packedS(String s) { - packed4(s.length()); - for( int i=0; i f299+=n; return f0+f299;};"); + new CodeGen(null,lib.toString(),null,"Wide",source.toString(),123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + var paths=new Ary<>(new String[]{lib.toString()}); + CodeGen code=new CodeGen(null,null,paths,"WideEval","return Wide.touch((arg<<32)>>32);",123,true,TypeInteger.BOT) + .driver(CodeGen.Phase.TypeCheck); + assertEquals("12",Eval2.eval(code,5)); + TestC.run("return Wide.touch(5)==12 ? 0 : 1;","wide_memory_client",paths, + TestC.CALL_CONVENTION,null,null,"",-1); + } + + @Test public void testOldObjectFormatRequestsRebuild() throws Exception { + Path build=Path.of("build/objs/separate"); + Files.createDirectories(build); + Path lib=Files.createTempDirectory(build,"old-format-"); + new CodeGen(null,lib.toString(),null,"Old","val value=7;",123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + Path file=lib.resolve("Old.o"); + ElfReader elf=ElfReader.load(file.toFile(),null); + byte[] bytes=Files.readAllBytes(file); + bytes[elf._bais.size()+3]='E'; // Previous C0DE header, before format 2. + Files.write(file,bytes); + try { + ElfReader.load(file.toFile(),null).loadPublicTypes(new CodeGen("")); + fail("old format accepted"); + } catch( IllegalArgumentException expected ) { + assertTrue(expected.getMessage().contains("rebuild the object file")); + } + } + @Test public void testImportedReadOnlyPrimitiveArray() throws Exception { Path build=Path.of("build/objs/separate"); Files.createDirectories(build); diff --git a/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java b/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java new file mode 100644 index 00000000..c218e98b --- /dev/null +++ b/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java @@ -0,0 +1,20 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.util.BAOS; +import java.util.HashMap; +import static org.junit.Assert.*; + +public class PackedTypeTestSupport { + public static void singleton(int id) { + Type.TAGOFFS(); + TypeFunPtr fun=TypeFunPtr.make((byte)2,true,new Type[0],TypeInteger.BOT,XInt.make(id)); + BAOS out=new BAOS(); + fun.packed(out,new HashMap<>()); + assertEquals(id<=254 ? 2 : 4,out.size()); + BAOS in=new BAOS(out.toByteArray()); + TypeFunPtr copy=(TypeFunPtr)Type.packed(in,new String[]{""}); + assertEquals(id,copy.fidx()); + assertEquals(0,copy.nargs()); + assertEquals(out.size(),in.size()); + } +} -- cgit v1.2.3