From Newsgroup: comp.arch
On 9/27/2026 8:12 PM, Paul Clayton wrote:
On 9/25/26 11:46 AM, Stefan Monnier wrote:
So, the idea of using actual compression seems interesting.
This has been tried in the past, but it didn't catch on.
There are different levels at (and ways in) which compression can be
applied, with very different tradeoffs.
E.g. I remember an article years ago (maybe from ETHZ?) doing
compression on bytecode where common sequences of bytecode were turned
into something akin to "functions", IOW a kind of "common sub-expression
elimination" that's also reminiscent of LempelZiv. The result was
compressed bytecode executable "without decompression".
Christopher W. Fraser ("An Instruction for Direct Interpretation
of LZ77-compressed Programs", 2002) proposed an echo
(specialized call) instruction that included a length field so
that an explicit return instruction was not required. The
"function" was also embedded into ordinary code ("inlined" into
one of the uses of the code sequence); this reduces program size
by the number of echo functions times the size of the echo
instruction but it also impacts the effectiveness of small
offsets. (Having variously aligned instruction-address relative
storage — an idea toward which I am overly fond — might
facilitate shorter offsets with wide sharing. Such seems to
introduce more TLB pressure. With extracted functions, it might
also be useful to use a larger index granularity and have
functions converge inward; e.g., a 12-instruction-parcel block
might have one forward-read 8 parcel function and one backward-
read 4 parcel function. I suspect even with converge-inward
this would have too much internal fragmentation for the modest
savings in target bits.)
Obviously, the use of a stack ISA (or even a random-read-queue
ISA) would tend to increase the repeated code sequences, though
a compiler might be able to adjust register allocation to
provide replicated code sequences for a traditional register
ISA.
This is one traditional limitation, though would be difficult to make
register allocation more repeatable in a way that doesn't adversely
effect the effectiveness of the register allocation.
But, yeah, it is a property that code tends to be dominated more by
larger numbers of widely spread short repeats rather than smaller number
of longer repeats. Most of the repeats being only a few instructions.
Well, to beat more on my own format, as it exists ATM:
* dddddddd-dlllrrr0 (l=3..10, d=0..511, r=0..7)
* dddddddd-dddddlll-lllrrr01 (l=4..67, d=0..8191)
* dddddddd-dddddddd-dlllllll-llrrr011 (l=4..515, d=0..131071)
* rrrr0111 (Raw, r=(r+1)*8, 8..128)
* * rrr01111 (Original Long Match)
* dddllll0-rrr01111 (l=11..26, d=1..8, r=0..7)
* dddddddl-lllllll1-rrr01111 (l=68..323, d=128, r=0..7)
* rr011111 (r=1..3 bytes, 0=EOB)
* rrrrrrrr-r0111111 (Raw, r=(r+1)*8, 8..4096)
* lllllll0-01111111 (l=4..131, d=1, r=0)
* 2x D-ddddddll-llllllll-llllrrr1-01111111 (l=4..16K, d=4M, r=0..7)
* DD-dddddddd-ddddddll-llllrrr0-11111111 (l=4..67, d=4M, r=0..7)
** d: Distance
** l: Match Length
** r: Literal Length
Which beats LZ4 for general data compression, but often loses for
executable code in the ISA's I am using.
Why?
Because ability to more easily encode 8/12 raw bytes, or 3-byte matches
in the 8K to 64K range, gives an advantage to LZ4 in this case.
Where, say, LZ4 is (IIRC):
Tag byte:
(7:4): raw/literal length: 0..14, 15=Escape
(3:0): match length, 4..17, Escape
If literal escape:
Mod-255-VLN for literal length;
Literal Bytes;
If match escape:
Mod-255-VLN for match length;
16-bit match distance.
So:
L= 4..11, D=1.. 511 : RP2=2B, LZ4=3B, RP2 wins
L=12..14, D=1.. 511 : RP2=3B, LZ4=3B, Tie (RP2 can win if D<=8)
L= 4..14, D=1..8191 : RP2=3B, LZ4=3B, Tie
L=15..67, D=1..8191 : RP2=3B, LZ4=4B, RP2 Wins
L= 4..14, D=8K..64K : RP2=4B, LZ4=3B, LZ4 Wins (*1)
L=15..269, D=8K..64K: RP2=4B, LZ4=4B, Tie
L=270..515, D=1..64K: RP2=4B, LZ4=5B, RP2 Wins
L>524 || D > 64K : RP2 wins by default (*2).
*1: But, very common for ".text".
*2: Distance: LZ4 limited to a 64K window
Length: All LZ4 cases need 6+ bytes to encode.
Ironically though, is sliding window is reduced to 8K or 16K, LZ4's
advantage for machine code evaporates.
And, LZ4's continued effectiveness strongly hints at most of the repeats
being between 1 and 3 instructions.
Well, LZ4 can also win potentially for raw bytes runs in the 8..14 byte
range; but this seems to be less decisive (even if being able to encode
a miss of 8 bytes would be a merit with 32-bit instructions).
Likewise note the final case of the 5-byte l=4..67, d=0..4M case, this
was a last-minute addition to deal with a case (general file
compression) where my newer variants were doing worse than my original
variant (which had a fallback case that used VLNs).
This being because it turned out there were a lot of short matches in
the 128K..4MB range.
Can note though that it is hit/miss, as while there are a lot of short
misses out there, actually taking these matches negatively impacts
speed. There is a case that can me made for limiting all matches past
128K to a minimum of 16 bytes, which seemingly made the difference (for decompression speed) between 1500MB/s and 1800MB/s.
Well, and recently posted code for a Huffman post compressor:
https://github.com/cr88192/bgbtech_misc/blob/master/misc_btrp2lz/rp2post_h12d.c
Just sort of awkwardly dropping them in near the TgvLz code.
TgvLz doesn't actually use them, but the way of using post-compressors
is a little awkward.
This one was sort of in limbo for a bit:
It only really works effectively on buffers larger than 32K, which are a
minor case;
For 2K .. 32K, the STF+AdRice compressor tends to hold a lead.
Below 2K, STF+AdRice becomes ineffective.
Between 768 bytes and 2K, the Range-Coder post compressor can be
effective, but is the slowest option (and there isn't any payload size
range where it becomes "fast").
In the 2K..32K, the relative inefficiency of the per-symbol logic cost
of the STF+AdRice encoder is offset by the lower constant-time costs
(within this area, the space needed for the Huffman tables, and CPU time needed to initialize the Huffman tables, being major factors).
Likewise, within the Huffman post-compressor (for the "XBlob"):
The break even point between linearly encoded symbols, and 4-wide
interleaved symbols, being 192 bytes.
Below 192: Faster to encode symbols linearly.
Above 192: Faster to use the more complex interleaved decoding.
Also the 4-wide case effectively needs to pad up to the next multiple of
4 symbols (this was the most speed-efficient option, even if not the
most space efficient). The encoder pads the blob with the shortest
symbol to minimize space overhead.
Generally, the encoder splits things up so that none of these buffers
will exceed 4K (and reuses the Huffman tables between chunks), but this
is mostly a thing of trying to keep everything inside of a 32K L1 cache footprint.
But, yeah, the great pains of trying to make Huffman decoding "not slow".
I have not really run extensive benchmarks on this specific decoder, but
I will guess probably around 600 - 700MB/s (on my Zen+), as this is
about what I got the last time I tried a Huffman coded LZ compressor
with a similar design.
Was "kinda meh", very difficult to try to reach GB/s territory with the anchor-weight that is entropy coding.
Though, in this case, it is possible that first decoding to RP2 and then decoding the RP2 would add some overhead. Could maybe make sense as a possibility to allow a post-compressor's decoder frontend that also decompresses RP2 directly.
TODO: Set up some proper benchmarks for this.
Nevermind if this sort of ad-hoc modular approach seems kinda jank.
For thinks like building file formats, this sort of "lego blocks"
approach tends to work better IME.
Can also note that I am using neither RP2 nor LZ4 for pagefile
compression, but rather a different LZ compressor tuned more
specifically around 32/64 bit elements, which was a little faster in
this case and a better fit around the patterns typically seen in RAM
pages (typically a lot of 32/64 bit words and not so much free-form byte-oriented data).
Well, options used for pagefile:
FeLZ32: 32-bit command-tags, data stream is aligned 32-bit elements;
FeLZ64:
16-bit (or 16/32) command-tags,
data stream is 64-bit elements.
Specifically tuned to the pagefile use-case.
Potentially a FeLZ32 like design with 16/32 bit tags, could also be
worth exploring for code compression; or potentially maybe even a
version of PEL that can switch compressors dynamically.
Though, this might make sense to go along with support for being able to support random page-loading (which would need to reset the sliding
window between blocks). TBD how to best support such things in a way
that "doesn't suck" though (loading the image as a series of variable
amounts of data packed into 1K blocks would not mix efficiently with
trying to also break the compressed PE image into separately-coded
page-sized chunks).
One possibility I guess could be, say:
Each 16K page is encoded as a variable-length series of 256 byte blocks,
with the compressor chosen per-page. This would give a statistical
noise-floor of around 5% for size overhead, which is likely acceptable
(but, then if already less than 512, or sector-sized, why not just 64
bytes to reduce chunking overhead to around 1% ?...).
Either way, it would mean a stream loader would need to keep track of a roughly 17K sliding window:
Decode a page, starting near start of window;
Slide whole window back (memmove);
Read in sectors to fill rest of window.
Maybe could be delayed if next-page falls within loaded region.
Possible, but is more complicated than the current approach, and is
maybe a big ask for the Boot ROM (code space limited).
Well, or this PEL variant is only allowed for user-land binaries, and
not for the kernel. In this case, one can also more safely assume that
the OS has a fully functional filesystem driver.
To be useful though, does imply the assumption that the pages don't have
any base relocs. May make sense to try to figure out some way to
consolidate most of the PBO relocs and similar into a smaller number of
pages.
Could maybe be addressed by making the function-locality sorting also
take this into account:
High priority functions, along with those needing base relocs, are
clustered together. This way, the loader can (hopefully) consolidate
them into a smaller area while leaving most of the rest of the functions alone.
Most naive way to do this being to add a large priority boost to any
function marked as a DLL export or similar...
...
You can gain some savings by playing at the bit-level to take advantage
of Hufmann-style compression, but another way to attack the problem is
to design an ISA where you can easily share common sequences of
instructions (I guess you could call it "outlining"), for example by
providing a very concise way to call and write short functions.
And maybe the micro-architecture could be taught to inline those calls
(I guess it would naturally happen if you use a trace cache).
Something like a branch target instruction cache might facilitate high
fetch bandwidth. Inlining a known-size function seems likely to be practical. However, the problem of prefetch
would still exist. With an instruction stream, simple sequential
prefetch works very well. For a microcontroller in which at
least the tiny functions could be placed in scratchpad memory,
this might not be an issue. Even for a microcontroller, code in
flash memory does not perform well with many control flow changes.
Yeah.
Had noted in the past that naive prefetch (always assume flow will go forwards) and 2-way set associativity (vs direct mapped) both work well
with L1 I$.
Main reason L1 is not set associative is mostly that the resource cost
of set-associative L1 is higher than that of 32K L1 on the FPGA, and 32K
L1 provides a larger relative benefit (though both modest over 16K DM).
But, yeah, if one sees that a following cache-line in an I$ fetch will
miss, if one can prefetch it without a stall, this is usually a win.
Though, if there is much ILP, it will typically crash into the missing
line before the response gets back, so it maybe saves 1 or 2 cycles off
the cost of L1 miss handling.
Though as a merit for typical cases, looping means that code is likely
to loop back to places it has already recently been, so more likely to
hit (this seems to be the merit of set-associativity in this case, as it
deals better with conflict misses within loop bodies if calling
functions from within the loop).
OTOH: The external victim cache also helps some with conflict misses, if
it remembers cache lines that recently passed its way.
But, also yeah, branching all over would suck for performance (not free
even with a good branch predictor).
(The integrated storage of a microcontroller also presents the
opportunity to limit the octet granularity to external code.
Even a limited amount of external code might be "extended" with
bits from integrated storage. This is another of my fond little
conceptions.)
...
--- Synchronet 3.22a-Linux NewsLink 1.2