From Newsgroup: comp.arch

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute. Pure RISCS have very
little compression, RISC-V has some, CISC has some more. AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

So, the idea of using actual compression seems interesting.
This has been tried in the past, but it didn't catch on.

There are a few basic problems to be solved. One that comes to
mind immediately is branch addresses. If the instruction stream
is compressed, any bit of the compressed stream can start an
instruction, and calculating the target of a branch instruction
is not straightforward. To avoid having to decode the whole
program, it would be necessary to create blocks of some sort,
which could be decoded on loading into a suitable cache level.

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

Branch targets could then be in the form block,instruction in
block. There would have to be an upper limit on the number
of instructions per block, leading to some waste for easily
compressible instructions. Also, instructions which no
longer fit in a block would reduce the efficieny.

One would also have to look at PC-relative branches; these
would probably become block-relative + instruction in block.

Writing binutils for this kind of architecture would be fun,
in the sense of absoutely no fun at all. Object code would
probably be uncompressed, with the poor guy implementing the
linker having to do all the dirty work.

The ISA to be compressed would not be limited by having to
fit into a container determined by byte or word sizes.
If one so desired, one could chose an ISA based on any
bit size, although having instructions based on an n-bit
package size (with multiples) would still make sense for
further decoding of the micro-ops.

Other thoughts?
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch


Thomas Koenig <tkoenig@netcologne.de> posted:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute. Pure RISCS have very
little compression, RISC-V has some, CISC has some more. AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

So, the idea of using actual compression seems interesting.
This has been tried in the past, but it didn't catch on.

Pitfalls...

There are a few basic problems to be solved. One that comes to
mind immediately is branch addresses. If the instruction stream
is compressed, any bit of the compressed stream can start an
instruction, and calculating the target of a branch instruction
is not straightforward. To avoid having to decode the whole
program, it would be necessary to create blocks of some sort,
which could be decoded on loading into a suitable cache level.

Realistically, adding 3-or-4-bits to IP (or equally restricting
IP to 60-DoubleWord address-bits would allow bit indexing at
FETCH.

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

What happens when somebody (ld.so) writes into code space ??
What happens when SSD writes into code space ??

Branch targets could then be in the form block,instruction in
block.

Or bit addresses (see above) and leave out blocks altogether.

There would have to be an upper limit on the number
of instructions per block, leading to some waste for easily
compressible instructions. Also, instructions which no
longer fit in a block would reduce the efficieny.

Packet and trace caches have this problem. After building a
packet-cache (1991) and seeing the instruction density (60%
filled and less than 1/2 as dense as normal instruction
cache--I decided to go a different direction for my current
6-wide machine.

One would also have to look at PC-relative branches; these
would probably become block-relative + instruction in block.

Bit addressing solves this, too !!

Writing binutils for this kind of architecture would be fun,

For a perverse definition of "fun".

in the sense of absoutely no fun at all. Object code would
probably be uncompressed, with the poor guy implementing the
linker having to do all the dirty work.

Imaging the poor guy trying to debug::

ADD IP,R7,#1234567

The ISA to be compressed would not be limited by having to
fit into a container determined by byte or word sizes.

Not at all--see Mill.

If one so desired, one could chose an ISA based on any
bit size, although having instructions based on an n-bit
package size (with multiples) would still make sense for
further decoding of the micro-ops.

Other thoughts?

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC), Thomas Koenig
<tkoenig@netcologne.de> wrote:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute.

That's certainly true of the schemes I've been coming up with.

But since it takes so much time to fetch stuff from DRAM, some
machines offer a mode where instructions are actually decrypted using
a block cipher after being fetched!
Given that, presumably the time cost of doing "real" compression on
program code is not excessive.
So, why doesn't anyone do this? I can think of many reasons why such a
scheme could cause agony... but I also see a simple, plain
alternative.
Why not just have a compressed disk format for executable files in an
operating system? Unpack them into conventional format when loading
them into memory. That saves space where it is more doable, where the
programs are lying idle, so they can be compressed with context
obtained from their whole length.

It doesn't achieve as much, but it avoids all the branching headaches.

John Savard
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 9/24/2026 5:17 PM, MitchAlsup wrote:

Thomas Koenig <tkoenig@netcologne.de> posted:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute. Pure RISCS have very
little compression, RISC-V has some, CISC has some more. AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

So, the idea of using actual compression seems interesting.
This has been tried in the past, but it didn't catch on.

Pitfalls...

Yes.

Fixed length: Cheapest;
16/32: Affordable;
Variable Bytes: Expensive;
Variable Bits: Impractical.

Often, one can get part of the way to the results of a more expensive
solution by being more clever with the cheaper solution.


The stronger tools may seem like magic, but they don't come free.

There are a few basic problems to be solved. One that comes to
mind immediately is branch addresses. If the instruction stream
is compressed, any bit of the compressed stream can start an
instruction, and calculating the target of a branch instruction
is not straightforward. To avoid having to decode the whole
program, it would be necessary to create blocks of some sort,
which could be decoded on loading into a suitable cache level.

Realistically, adding 3-or-4-bits to IP (or equally restricting
IP to 60-DoubleWord address-bits would allow bit indexing at
FETCH.

If the bit lengths are variable, branch displacements and relocs are
going to be straight up evil.

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

What happens when somebody (ld.so) writes into code space ??
What happens when SSD writes into code space ??

Branch targets could then be in the form block,instruction in
block.

Or bit addresses (see above) and leave out blocks altogether.

There would have to be an upper limit on the number
of instructions per block, leading to some waste for easily
compressible instructions. Also, instructions which no
longer fit in a block would reduce the efficieny.

Packet and trace caches have this problem. After building a
packet-cache (1991) and seeing the instruction density (60%
filled and less than 1/2 as dense as normal instruction
cache--I decided to go a different direction for my current
6-wide machine.

One would also have to look at PC-relative branches; these
would probably become block-relative + instruction in block.

Bit addressing solves this, too !!

Writing binutils for this kind of architecture would be fun,

For a perverse definition of "fun".

in the sense of absoutely no fun at all. Object code would
probably be uncompressed, with the poor guy implementing the
linker having to do all the dirty work.

Imaging the poor guy trying to debug::

ADD IP,R7,#1234567

Looks at hex dump of memory: White noise.

Branch goes wrong: White noise.
Or, if you compression is good enough, the instruction stream looks like something plausible, but completely wrong. Like if an LLM hallucinated
ones' disassembler output.

The ISA to be compressed would not be limited by having to
fit into a container determined by byte or word sizes.

Not at all--see Mill.

If one so desired, one could chose an ISA based on any
bit size, although having instructions based on an n-bit
package size (with multiples) would still make sense for
further decoding of the micro-ops.

Other thoughts?

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch


quadibloc@invalid.com (John Savard) posted:

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC), Thomas Koenig <tkoenig@netcologne.de> wrote:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute.

That's certainly true of the schemes I've been coming up with.

But since it takes so much time to fetch stuff from DRAM, some
machines offer a mode where instructions are actually decrypted using
a block cipher after being fetched!

I remember (I think) IBM compressing pages, but not cache lines.

Given that, presumably the time cost of doing "real" compression on
program code is not excessive.

Once you have the HW budget, LemplZiv is quite efficient.

So, why doesn't anyone do this?

Big memory became cheap enough; disks (and SSDs) became big enough.
Also I/O busses became fast enough that saving 40% memory cycles no
longer paid off, once SW had to read the stuff in and convert it.

I can think of many reasons why such a
scheme could cause agony... but I also see a simple, plain
alternative.

Why not just have a compressed disk format for executable files in an operating system? Unpack them into conventional format when loading
them into memory.

How do you page the code directly from the disk into executable memory ?

That saves space where it is more doable, where the programs are lying idle, so they can be compressed with context
obtained from their whole length.

Programs lying idle can rest on the disk in memory format.

It doesn't achieve as much, but it avoids all the branching headaches.

John Savard

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2026-09-24 4:04 p.m., Thomas Koenig wrote:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute. Pure RISCS have very
little compression, RISC-V has some, CISC has some more. AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

So, the idea of using actual compression seems interesting.
This has been tried in the past, but it didn't catch on.

There are a few basic problems to be solved. One that comes to
mind immediately is branch addresses. If the instruction stream
is compressed, any bit of the compressed stream can start an
instruction, and calculating the target of a branch instruction
is not straightforward. To avoid having to decode the whole
program, it would be necessary to create blocks of some sort,
which could be decoded on loading into a suitable cache level.

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

Branch targets could then be in the form block,instruction in
block. There would have to be an upper limit on the number
of instructions per block, leading to some waste for easily
compressible instructions. Also, instructions which no
longer fit in a block would reduce the efficieny.

One would also have to look at PC-relative branches; these
would probably become block-relative + instruction in block.

Writing binutils for this kind of architecture would be fun,
in the sense of absoutely no fun at all. Object code would
probably be uncompressed, with the poor guy implementing the
linker having to do all the dirty work.

The ISA to be compressed would not be limited by having to
fit into a container determined by byte or word sizes.
If one so desired, one could chose an ISA based on any
bit size, although having instructions based on an n-bit
package size (with multiples) would still make sense for
further decoding of the micro-ops.

Other thoughts?

Micro-ops are the opposite of compressed instructions. They are
typically wider than the instructions encoded.

Writing software for dumps of code and other such things is much more expensive (takes more time) when things are not byte aligned.

Even with compressed instructions the savings in memory space is
typically < 40%. The savings in execution time is far less.

Instruction size is an engineering issue. With most instructions,
including constants, fitting into 36 bits or less, a 32-bit instruction
parcel covers a high percentage of instruction use.

Variable bit length instructions could be asking for a nasty instruction decoder.

No system is going to be perfect.

Compressing the instruction stream may be useful for transferring the
code over wire and for storage. Once in the CPUrCOs memory I think it is
less important for compression. For instance, micro-ops use much more
memory than the instructions from the program code, but they are used in
some designs.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC)
Thomas Koenig <tkoenig@netcologne.de> wrote:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute. Pure RISCS have very
little compression, RISC-V has some, CISC has some more. AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

Can I ask what you find special in AMD's micro-op cache relatively to
Intel's?
To me it looks like Zen1 mostly copied 6 years earlier Sandy Bridge
tech. Following generations of Zen, while doing new things in other
parts of the core, left principles of micro-op cache mostly intact.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

Thomas Koenig <tkoenig@netcologne.de> posted:

<snip>

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

What happens when somebody (ld.so) writes into code space ??

Generally it doesn't. The code space is mapped into
read-only pages. The RTLD updates the PLT and GOT, not
the code.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC)
Thomas Koenig <tkoenig@netcologne.de> wrote:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute. Pure RISCS have very
little compression, RISC-V has some, CISC has some more. AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

So, the idea of using actual compression seems interesting.
This has been tried in the past, but it didn't catch on.

There are a few basic problems to be solved. One that comes to
mind immediately is branch addresses. If the instruction stream
is compressed, any bit of the compressed stream can start an
instruction, and calculating the target of a branch instruction
is not straightforward. To avoid having to decode the whole
program, it would be necessary to create blocks of some sort,
which could be decoded on loading into a suitable cache level.

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

Branch targets could then be in the form block,instruction in
block. There would have to be an upper limit on the number
of instructions per block, leading to some waste for easily
compressible instructions. Also, instructions which no
longer fit in a block would reduce the efficieny.

One would also have to look at PC-relative branches; these
would probably become block-relative + instruction in block.

Writing binutils for this kind of architecture would be fun,
in the sense of absoutely no fun at all. Object code would
probably be uncompressed, with the poor guy implementing the
linker having to do all the dirty work.

The ISA to be compressed would not be limited by having to
fit into a container determined by byte or word sizes.
If one so desired, one could chose an ISA based on any
bit size, although having instructions based on an n-bit
package size (with multiples) would still make sense for
further decoding of the micro-ops.

Other thoughts?

Last time I gave it a serious thought was more than 5 but less
than 10 years ago. Then I came to conclusion that the only practical
way for bit-compressed instruction set is "reversed VL-VLIW".
I.e. instruction stream consists of aligned fixed-width chunks, most
likely 256 bit, but 512 bit is also possible if it turns out that 256b
is not enough for good compression. Each chunk carries variable number
of individual instructions. Details of encoding may vary, but probably
based on format header that is placed in fixed position in the chunk
that governs the rest of parsing.

Jumps into the middle of chunk are allowed, jump target is expressed as
a tuple - address-of-chunk:index-of-instruction-in-chunk. For
conditional branches address part is relative and covers limited
distance, may be -256 to + 255 chuncks, similarly to conventional
designs.

I didn't rethink it since then, but I know that I didn't become any
smarter.













--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

quadibloc@invalid.com (John Savard) posted:

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC), Thomas Koenig
<tkoenig@netcologne.de> wrote:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute.

That's certainly true of the schemes I've been coming up with.

But since it takes so much time to fetch stuff from DRAM, some
machines offer a mode where instructions are actually decrypted using
a block cipher after being fetched!

I remember (I think) IBM compressing pages, but not cache lines.

https://www.marvell.com/blogs/structera-xa-cxl-compression-every-gigabyte-counts.html

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Michael S <already5chosen@yahoo.com> schrieb:

On Thu, 24 Sep 2026 20:04:24 -0000 (UTC)
Thomas Koenig <tkoenig@netcologne.de> wrote:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute. Pure RISCS have very
little compression, RISC-V has some, CISC has some more. AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

Can I ask what you find special in AMD's micro-op cache relatively to Intel's?

Nothing in particular, it was just something I mentioned as an
example. Plus, I looked the format of AMD microops some time ago.
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

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".

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).


=== Stefan
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Robert Finch <robfi680@gmail.com> schrieb:

On 2026-09-24 4:04 p.m., Thomas Koenig wrote:

It seems that the different CISC and compressed instruction sets
are ad-hoc (and not very good) attempts at compression of the
actual instructions that machines execute. Pure RISCS have very
little compression, RISC-V has some, CISC has some more. AMD's
micro-op cache goes some way towards this when it splits
x86_64 instructions into micro-ops.

So, the idea of using actual compression seems interesting.
This has been tried in the past, but it didn't catch on.

There are a few basic problems to be solved. One that comes to
mind immediately is branch addresses. If the instruction stream
is compressed, any bit of the compressed stream can start an
instruction, and calculating the target of a branch instruction
is not straightforward. To avoid having to decode the whole
program, it would be necessary to create blocks of some sort,
which could be decoded on loading into a suitable cache level.

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

Branch targets could then be in the form block,instruction in
block. There would have to be an upper limit on the number
of instructions per block, leading to some waste for easily
compressible instructions. Also, instructions which no
longer fit in a block would reduce the efficieny.

One would also have to look at PC-relative branches; these
would probably become block-relative + instruction in block.

Writing binutils for this kind of architecture would be fun,
in the sense of absoutely no fun at all. Object code would
probably be uncompressed, with the poor guy implementing the
linker having to do all the dirty work.

The ISA to be compressed would not be limited by having to
fit into a container determined by byte or word sizes.
If one so desired, one could chose an ISA based on any
bit size, although having instructions based on an n-bit
package size (with multiples) would still make sense for
further decoding of the micro-ops.

Other thoughts?

Micro-ops are the opposite of compressed instructions. They are
typically wider than the instructions encoded.

Writing software for dumps of code and other such things is much more expensive (takes more time) when things are not byte aligned.

Even with compressed instructions the savings in memory space is
typically < 40%. The savings in execution time is far less.

The work I have seen is motivated by saving energy
for embedded systems. They didn't use Micro-Ops, but
standard ISAs. Here is a relatively recent example: https://link.springer.com/article/10.1007/s10617-024-09290-2

It doesn't look too bad, but I am not holding my breath that
this will be used widely.
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <NIvtS.6$MR2.5@fx39.iad>, Scott Lurndal <slp53@pacbell.net> wrote: >MitchAlsup <user5857@newsgrouper.org.invalid> writes:

Thomas Koenig <tkoenig@netcologne.de> posted:

<snip>

For example, one could make the Icache into a micro-op-store
and decode on fetching from L2.

What happens when somebody (ld.so) writes into code space ??

Generally it doesn't. The code space is mapped into
read-only pages. The RTLD updates the PLT and GOT, not
the code.

Right. The GOT is mapped into private R/W data space
specifically to avoid having to mutate R/O text.

I think 32-bit SPARC was an exception.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 9/25/2026 10: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".

BGBCC often does something similar with prologs and epilogs:
If more than a certain number of registers are saved/restored, the
sequences are folded off and then a call/branch is used to do the actual
bulk save/restore.

Luckily, works regardless of ISA.
Don't want to go too small though for the limit, or else it may reduce performance and/or make code density worse (if very small).

So, a usual cutoff is around 6 or 8 loads/stores (or 12 or 16 registers
if one has Load/Store Pair).


This isn't really done inside functions though, and something like semi-efficient basic-block folding/reuse would be a much harder problem
(even if functions have similar basic blocks, they will not necessarily
have similar stack frames or register allocation).


LZ77 can work, but no good way to do it live.

For RAM saving though, one could do something like page-level LZ with
dynamic decompression. So, the program is initially read into RAM in a compressed form, but not actually fully mapped in. When one of these
pages is hit, the corresponding page for the image is decompressed.

I guess, in theory, I could map something like this onto my existing
PEL4 format, by building a block-offset table. Random access decoding
would require explicit window breaks at regular intervals though (say,
for example, once every 8K or so).

However, an 8K window break would likely shift the "optimality" balance
from LZ4 to RP2 (the main merit LZ4 seemingly has here is that it works
better for distant but short matches, *; but reducing the effective
window size would lessen this advantage).


*: RP2's design essentially assumes a positive correlation between match length and distance. This is true for general data, but less true for executable code (where all matches tend to be shorter, but have a wider distribution). LZ4 does better for "hey, here is 12 bytes from 60K ago"
(which it can encode in 3 bytes, vs needing 4 in RP2; however an 8K
sliding window means RP2 matches could operate within the 3-byte regime; l=4..67, d=8K).

Ironically, I also found that RP2 was less ideal for matches entirely
within fixed-size 256 byte blocks (with a window limited to a single
block), as again, the length and distance became negatively correlated
(such a negative correlation was also noted in raster image compression, typically in the form of long matches with short distances).

The most common RLE case was partly addressed in the more recent RP2B
variant by adding a 2-byte Len=4..131, Dist=1 case.


Debatable:
Maybe could reuse the retired "Long Match" case for a new 2-byte cases, say:
dddlllll-rrr01111 (len=4..35, dist=1..8, raw=0..7)
Which could hit on some cases that miss with the added RP2B case:
lllllll0-01111111 (RP2B, len=4..131, dist=1, raw=0)

And, complements the existing 2-byte match:
dddddddd-dlllrrr0 (len=3..10, dist=0..511, raw=0..7)

Though, maybe a case could be made for 3-byte, say:
dddddddd-llllllll-rrr01111 (l=4..259, d=1..256)

Or, errm, both:
ddlllll0-rrr01111 (len=4..35, dist=1..4, raw=0..7)
dddddddl-lllllll1-rrr01111 (len=4..259, d=1..128, raw=0..7)

May need to do some testing to figure out which possibility would work
better here.


Also kind of annoying that even RP2 has fragmented:
RP2 (Original)
RP2A (Limits sliding window to 128K, drops Long Match)
RP2B (Re-adds support for a 4MB sliding window via new matches)
RP2C(?) Maybe reuse "Long Match" case as above

The original VLN based Long-Match case was dropped mostly because using
it was detrimental to speed as well as needless pain for both ASM implementations and post compressors.

For RP2B, made more sense to replace it with a fixed-length 6-byte
format (with 16K matches and a 4MB window, but no VLNs).

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).

In an ISA, one could leverage the support in RISC-V for multiple Link Registers for the latter.


Say:
X1 is the main link register for function calls;
X5 is a second link register for outlined blobs and threaded-code helpers.

At a minimum, one would need a JAL+JALR of overhead, so would mean the "minimum break even" point (space-wise) would be around 4 instructions. Break-even point could be reduced to 2 instructions if one had a "Branch
here, run N instructions, then auto-return" instruction.

Would need a higher limit though if performance is a concern.


One other wacky idea could be to do something like RV-C, but instead of
a fixed compressed ISA, have an ISA that is essentially built at compile
time as a sort of table of patterns. The CPU then looks into this table
and dynamically unpacks into a virtual 32-bit instruction.

Couldn't really make sense to have RVC as a preset in such as scheme, as ideally one wants an encoding scheme that that is more regular / less
dog chewed.

This sort of approach would make an evil mess for things like dynamic
linking though.

Also, would unlikely gain much as RV-C is already mostly aligned with
the (statistically speaking) most common instructions. Well, at least if
one assumes that the code is being generated by GCC; it is a worse fit
for BGBCC as BGBCC tends to mostly use callee save registers for local variables, which greatly reduces the effectiveness of the Reg3
instructions (and, X8/X9/X10/X11, X24/X25/X26/X27, would be a harder
sell). Does at least work OK for leaf functions, if one assumes that
most code is leaf functions.


There are very few instructions common enough to justify a single byte encoding.

The biggest gain I saw in terms of maximizing code density was with a
16/24/32 encoding scheme.

But, even then, the 24 bit instructions weren't worth the added hassle,
and then one either needs there to exist a 1-byte NOP or other messes
may result.

...



Meanwhile, a Huffman-compressed instruction stream is more in "I
wouldn't want to poke this thing with a pole".

Rice coding the instructions would be bad enough, but at least Rice
coding would allow for a more affordable hardware decoder. Still not ideal.

=== Stefan

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch


BGB <cr88192@gmail.com> posted:

On 9/25/2026 10: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".

BGBCC often does something similar with prologs and epilogs:
If more than a certain number of registers are saved/restored, the
sequences are folded off and then a call/branch is used to do the actual bulk save/restore.

Luckily, works regardless of ISA.
Don't want to go too small though for the limit, or else it may reduce performance and/or make code density worse (if very small).

So, a usual cutoff is around 6 or 8 loads/stores (or 12 or 16 registers
if one has Load/Store Pair).

How does the hardware recognize that this sequence of STs (prologue)
or LDs (epilogue) are using a dense set of addresses so that one only
needs to access the tag once (or twice) instead of (12-16) times?

How does the hardware recognize that this sequence stays all within
one page and thus one TLB hit suffices for 12-16 memory references ??

And if performed with Call/Return semantics, how do non-memory instructions
get through the Decoder and into Reservation Stations--while those strings
of memory references get performed ??

Instead, if one uses ENTER/EXIT, one address calculation satisfies many accesses, one TLB lookup satisfies all those accesses, and the cache tag
is only accesses once (or twice).

You also get the ability to scoreboard all the registers being written, scoreboard all the registers being read, read the return address before
reading the preserved registers, and begin fetch before all the loads
have been performed.

And, ENTER is only 1 32-bit instruction without any flow control while
EXIT is 1 32-bit instruction with flow control faster than data access.


--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 9/25/2026 5:59 PM, MitchAlsup wrote:

BGB <cr88192@gmail.com> posted:

On 9/25/2026 10: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".

BGBCC often does something similar with prologs and epilogs:
If more than a certain number of registers are saved/restored, the
sequences are folded off and then a call/branch is used to do the actual
bulk save/restore.

Luckily, works regardless of ISA.
Don't want to go too small though for the limit, or else it may reduce
performance and/or make code density worse (if very small).

So, a usual cutoff is around 6 or 8 loads/stores (or 12 or 16 registers
if one has Load/Store Pair).

How does the hardware recognize that this sequence of STs (prologue)
or LDs (epilogue) are using a dense set of addresses so that one only
needs to access the tag once (or twice) instead of (12-16) times?

Load/Store Pair gets it down to 6/8 ...

I guess in theory a CPU could recognize that pairs of LDP/SDP
instructions are, say, actually LDQ/SDQ operations. Though, this would
mean a 256 bit memory port, and needing to move 4 registers at a time.
This wouldn't really work with a 4R2W or 6R3W register file with 64-bit
ports though.

Well, or add special instructions, assuming the CPU has the register
ports to make it happen.


Could in theory work if one did a register file as 4R2W 128-bit (then
with some trickery to support 64-bit operations). I once looked into
this, but noted that a 4R2W regfile operating 2-wide with 128-bit ports
(but faking 64-bit operations at the register-port level) would give
worse performance on-average than a 6R3W regfile with 64-bit ports for
64-bit operations (would mostly make sense if the goal was more
specifically to try to build a SIMD monster with a 256 bits/cycle
throughput or similar).

Ironically, wouldn't really need to change the ISA for this, though it
would have effects on the compiler's instruction shuffling/scheduling heuristics.

How does the hardware recognize that this sequence stays all within
one page and thus one TLB hit suffices for 12-16 memory references ??

Dunno. Likely the absence of TLB misses would imply a hits by extension.

And if performed with Call/Return semantics, how do non-memory instructions get through the Decoder and into Reservation Stations--while those strings
of memory references get performed ??

FWIW, with an in-order pipeline, I explicitly don't allow anything to co-execute with branch style instructions. With OoO, dunno. Probably
need some way to create a barrier to separate between the pre-branch and post-branch parts of the pipeline so that if a branch mispredict happens
one isn't "up a creek".

Instead, if one uses ENTER/EXIT, one address calculation satisfies many accesses, one TLB lookup satisfies all those accesses, and the cache tag
is only accesses once (or twice).

You do however, need a mechanism to orchestrate these sub-tasks, vs just
using a naive instruction sequence.

Can also note that ARM32 had LDM/STM, but ARM64 explicitly dropped to Load/Store Pair.

Went and checked before, seemingly Load/Store Pair is safe, as the way
it works in XG2 and XG3 is effectively covered by prior art established
by SPARC.


Then again, can also note that seemingly most of the ARM64 cores are 2
or 3 wide, so would likely face the same issue as above.

Seemingly, going 4-wide (or wider) mostly being a thing in PC/server
class processors.

You also get the ability to scoreboard all the registers being written, scoreboard all the registers being read, read the return address before reading the preserved registers, and begin fetch before all the loads
have been performed.

And, ENTER is only 1 32-bit instruction without any flow control while
EXIT is 1 32-bit instruction with flow control faster than data access.

Using a call or branch for a reused Load/Store blob, while not free,
does at leas not ask anything special from the CPU...

Like, the compiler then is the only one that needs to care (and the CPU
can remain dumb).

...


Then again, thinking about it more, would maybe be interesting if there
were some way to (somehow) cram an instruction-level LZ decompressor
into the I$.

Hard thing would be trying to figure out some way to make it play well
with interrupts (and would need to somehow deal with potentially
multiple independent locations per-cycle).

...

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 9/25/2026 4:09 PM, BGB wrote:

...

*: RP2's design essentially assumes a positive correlation between match length and distance. This is true for general data, but less true for executable code (where all matches tend to be shorter, but have a wider distribution). LZ4 does better for "hey, here is 12 bytes from 60K
ago" (which it can encode in 3 bytes, vs needing 4 in RP2; however an 8K sliding window means RP2 matches could operate within the 3-byte regime; l=4..67, d=8K).

Ironically, I also found that RP2 was less ideal for matches entirely
within fixed-size 256 byte blocks (with a window limited to a single
block), as again, the length and distance became negatively correlated
(such a negative correlation was also noted in raster image compression, typically in the form of long matches with short distances).

The most common RLE case was partly addressed in the more recent RP2B variant by adding a 2-byte Len=4..131, Dist=1 case.

Debatable:
Maybe could reuse the retired "Long Match" case for a new 2-byte cases,
say:
-a dddlllll-rrr01111-a (len=4..35, dist=1..8, raw=0..7)
Which could hit on some cases that miss with the added RP2B case:
-a lllllll0-01111111-a (RP2B, len=4..131, dist=1, raw=0)

And, complements the existing 2-byte match:
-a dddddddd-dlllrrr0-a (len=3..10, dist=0..511, raw=0..7)

Though, maybe a case could be made for 3-byte, say:
-a dddddddd-llllllll-rrr01111-a (l=4..259, d=1..256)

Or, errm, both:
-a-a-a-a-a-a-a-a-a-a ddlllll0-rrr01111-a (len=4..35, dist=1..4, raw=0..7)
-a dddddddl-lllllll1-rrr01111-a (len=4..259, d=1..128, raw=0..7)

May need to do some testing to figure out which possibility would work better here.

Then went and did a grind against a handful of various types of files to
see what combination did best, and eventually mostly settled onto:
dddllll0-rrr01111 (RP2C, l=11..26, d=1..8, r=0..7)
dddddddl-lllllll1-rrr01111 (RP2C, l=68..323, d=1..128, r=0..7)

These combine with the original patterns:
dddddddd-dlllrrr0 (l=3..10, d=0..511, r=0..7)
dddllll0-rrr01111 (RP2C, l=11..26, d=1..8, r=0..7)
dddddddd-dddddlll-lllrrr01 (l=4..67, d=0..8191)
dddddddl-lllllll1-rrr01111 (RP2C, l=68..323, d=1..128, r=0..7)

All then fall back to (to the original pattern):
dddddddd-dddddddd-dlllllll-llrrr011 (l=4..515, d=0..131071)


Granted, space-savings from these RP2C cases are typically small, so it
is more debatable (and a lot of the races were pretty close here).

No good way to add a very short but deep case.

...



--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

BGB <cr88192@gmail.com> writes:

On 9/25/2026 5:59 PM, MitchAlsup wrote:

BGB <cr88192@gmail.com> posted:

How does the hardware recognize that this sequence of STs (prologue)
or LDs (epilogue) are using a dense set of addresses so that one only
needs to access the tag once (or twice) instead of (12-16) times?

Load/Store Pair gets it down to 6/8 ...

I guess in theory a CPU could recognize that pairs of LDP/SDP
instructions are, say, actually LDQ/SDQ operations.

It's not theory. Many of the ARM server-grade CPUs in the last decade have supported converting LDP/SDP into a single twice as wide potentially
*atomic* memory operation.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 9/28/2026 10:26 AM, Scott Lurndal wrote:

BGB <cr88192@gmail.com> writes:

On 9/25/2026 5:59 PM, MitchAlsup wrote:

BGB <cr88192@gmail.com> posted:

How does the hardware recognize that this sequence of STs (prologue)
or LDs (epilogue) are using a dense set of addresses so that one only
needs to access the tag once (or twice) instead of (12-16) times?

Load/Store Pair gets it down to 6/8 ...

I guess in theory a CPU could recognize that pairs of LDP/SDP
instructions are, say, actually LDQ/SDQ operations.

It's not theory. Many of the ARM server-grade CPUs in the last decade have supported converting LDP/SDP into a single twice as wide potentially
*atomic* memory operation.

It makes sense to do so if the CPU has the resources to pull it off...

I wouldn't expect to see this all that much in smartphone class SOCs or similar though at present (at least excluding high-end / flagship models).


--- Synchronet 3.22a-Linux NewsLink 1.2