diff options
| author | Cliff Click <cliffc@acm.org> | 2026-11-16 10:18:30 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-11-16 10:18:30 -0800 |
| commit | 51a029304d8105b201bdfb81a7692b8a1b16b028 (patch) | |
| tree | 32f5312796aebf0b857eb9a7042249c9e08a334a /chapter32/src/main/java | |
| parent | c21026c5377429b11e285d251439407074fe3cd1 (diff) | |
| download | Simple-51a029304d8105b201bdfb81a7692b8a1b16b028.tar.gz Simple-51a029304d8105b201bdfb81a7692b8a1b16b028.zip | |
Packing Serialize tighter
Diffstat (limited to 'chapter32/src/main/java')
4 files changed, 49 insertions, 33 deletions
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<Type,Integer>(); @@ -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<count; j++ ) { if( !writeInput(n,j,anodes) ) continue; - Node def = n instanceof MemMergeNode mem ? mem.packedInput(j) : n.in(j); + if( n instanceof MemMergeNode mem && 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<len; i++ ) { + int fileAlias = n instanceof MemMergeNode && 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<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> 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<String,Integer> 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)<<shift; + if( (b & 128)==0 ) return (bits>>>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<s.length(); i++ ) - packed4(s.charAt(i)); + // Strings are bytes, not signed packed integers. Keep ASCII at one + // byte per character and agree on the representation of non-ASCII. + byte[] utf8 = s.getBytes(StandardCharsets.UTF_8); + packed4(utf8.length); + write(utf8); } public String packedS() { int len = packed4(); - String s = new String(_buf,_len,len).intern(); + String s = new String(_buf,_len,len,StandardCharsets.UTF_8).intern(); _len += len; return s; } |
