From Newsgroup: comp.arch

Well, part of this was prompted by someone recently complaining about
the design of my RP2 format and my claims of it running at "roughly
similar speeds to LZ4".

As can be noted:

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 (Literals, r=(r+1)*8, 8..128)
dddllll0-rrr01111 (l=11..26, d=1..8, r=0..7)
dddddddl-lllllll1-rrr01111 (l=68..323, d=1..128, r=0..7)
rr011111 (r=1..3 bytes, 0=EOB)
rrrrrrrr-r0111111 (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=0..4M, r=0..7)
DD-dddddddd-ddddddll-llllrrr0-11111111 (l=4..67, d=0..4M, r=0..7)
* d: Distance
* l: Match Length
* r: Literal Length


The main implementations I have of RP2 implement the format as
essentially a big if/else tree.

Roughly the top 4 branches are where it spends most of the time,
seemingly roughly (Q=0..3):
Q=0: ~ 75%
Q=1: ~ 19%
Q=2: ~ 3%
Q=3: ~ 2%
Rest: ~ 1%

A lot of the latter cases could be dropped, but having them does still
help with ratio even if rarely used.

The Q=5 case typically only happens right near the end (either to pad
out any remaining literal bytes, or to signal the end).


A more limited variant would be RP2A:
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 (Literals, r=(r+1)*8, 8..128)
xxx01111 -
rr011111 (r=1..3 bytes, 0=EOB)
rrrrrrrr-r0111111 (r=(r+1)*8, 8..4096)
01111111 -
Which is slightly faster with slightly worse compression.

And, in the original variant, Q=4 encodes VLN's for length and distance,
which worked OK for file-like compression, but made some other problems,
and wasn't great for performance (was generally worse than replacing it
with sticking a few more cases onto Q=7 and Q=8).


On my main PC (Xen+), both this and LZ4 tend to run in the area of 1.5
to 2.0 GB/s with my implementations (the WSL/Linux 'lz4' tool tends to
run a little bit faster and gets slightly better compression than my own attempt at LZ4).

If testing with the WAD file from Hexen, "hexen.wad", speeds I was
seeing were roughly:
RP2: 1.7 GB/s
LZ4: 1.9 GB/s (mine), 2.3 GB/s ('lz4' tool)
For reference:
Zstd: ~ 500 MB/s ("-b19"), ~ 700MB/s ("-b1")
gzip: ~ 185 MB/s


Something curious happens if testing on a Laptop with a "Core i7 8th gen":
RP2: 1.3 GB/s (slower)
LZ4: 3.2 GB/s (mine), 3.4 GB/s ('lz4')
Zstd: ~ 300 MB/s ("-b19"), ~ 400MB/s ("-b1")
gzip: ~ 225 MB/s

So, for whatever reason, LZ4 suddenly gets a lot faster on the i7 vs on
the Xen+ (whereas Zstd gets slower).

So, it would appear the other person is right about RP2 and LZ4 not
running at nearly the same speed, if running on Intel hardware...


Both tend to fall short of reaching the "memcpy() limit" on each
machine, though can note that the laptop seems to have a higher
"memcpy()" limit than my Xen, both using apparently the same actual DDR4
RAM speed (1200 MHz).



As can be noted:
On my own CPU / ISA: RP2 is faster.
On A53, they also appears to be nearly tied IIRC (but no recent tests here).


When I originally designed RP2, the working assumption had mostly been
that of relatively cheap branches, but of slow memory loads.

So, as noted, RP2 logic path:
tag=getu64(cs);
if(!(tag&1))
{ first case }
else if(!(tag&2))
{ second case }
else if(!(tag&4))
{ third case }
else ...
Copy-Literals
Copy-Match
Which, seemed to work reasonably well...

LZ4 path is more like:
tag=*cs++;
lr=tag>>4;
ml=(tag&15)+4;
if(lr==15)
{
v=*cs++; lr+=v;
while(v==255)
{ v=*cs++; lr+=v; }
}
Copy-Literals
if(ml==19)
{
v=*cs++; ml+=v;
while(v==255)
{ v=*cs++; ml+=v; }
}
md=*(u16 *)cs;
cs+=2;
Copy-Match

Often, those "while(v==255)" cases in LZ4 take a lot of heat...
Can do, say:
v=*cs++; lr+=v;
if(v==255)
{
v=*cs++; lr+=v;
if(v==255)
{
v=*cs++; lr+=v;
while(v==255)
{ v=*cs++; lr+=v; }
}
}
Which is uglier and doesn't make that big of a difference, merely
spreading some of the heat onto the "if()" branches.

Likewise, the "if(lr==15)" and "if(ml==19)" cases also being pretty hot
cases.

Other than this, is the logic within the match-copy functions, etc.


Did try a few other experiments:

One was to do a format that instead used ALU ops...

Well, behold this arcane junk:
tg=get_u64le(cs);
eo=tg&3;
if(eo==3)
...
cs+=eo+2;
mr=(tg>>2)&7;
ml=tg>>5;
smt=(eo<<3)+11;
sml=(11*smt)>>5;
smd=smt-sml;
md=ml>>sml;
ml=(ml&((1<<sml)-1))+4;
md=(md&((1<<smd)-1))+1;
Copy-Literals
Copy-Match

Result:
Slightly beats RP2 at speed on Xen+, but worse compression (closer to LZ4).

On the i7, this beat out *both* RP2 and LZ4 on decode speed, moving into
the first place (at ~ 3.3 GB/s).

This was not format-compatible with RP2 though.


Also tried another option, with different results:
Replacing the Q=0/1/2 branches with a branch-free version.

Well, basically, this sort of gem:
te_x0=(teo&1); te_x1=(teo>>1)&1;
te_x2=te_x0&te_x1;
eo=te_x0+te_x2; omr=eo+1;
oml=omr+3; smt=(eo<<3)+(12-eo);
mr=(t0>>omr)&7; ml=t0>>oml;
bml=(3+te_x0); sml=((5*smt)>>4)+te_x0;
smd=smt-sml; md=ml>>sml;
mml=((1<<sml)-1); mmd=((1<<smd)-1);
ml=(ml&mml)+bml; md=(md&mmd);

Result:
Minor slight speed-up on the Xen+ (reduced what gap existed between RP2
and LZ4).

But, was notably slower than the original branch based version on the i7.

And, I don't really get why the former went fast but the latter tanks on
the i7, as they are very similar logic...

Had also noted that these branch-free decoders also seem to (in
comparison) perform terribly in debug builds.

I also wouldn't really want to use either version on my own CPU core
though, as I feel fairly confident that both would be slower than the
branch based version.

But, it was an interesting side experiment.



Though, can note that to avoid tanking on some machines (like SiFive
chips), might need something like:
u64 get_u64(byte *ptr)
{
u64 *pv0;
u64 v0, v1, v;
int pr, pr3;
pr=((u64)ptr)&7;
pv0=(u64 *)(ptr-pr);
v0=pv0[0]; v1=pv0[1];
pr3=(pr<<3);
v1&=~((pr-1)>>31); //mask off v1 if pr==0
v=(v0>>pr3)|(v1<<(64-pr3));
return(v);
}
Or, to fall back to working with raw bytes.



Can note also for misaligned load/store, which also had a modest penalty
on Piledriver, and one of the fastest LZ compressors I had for this CPU
(which had outperformed LZ4 at the time, one I had called FeLZ32)
totally lost its advantage after going to a different CPU.

Though, in TestKern, FeLZ32 still remains as one of the options for
pagefile compression, as its design mapped reasonably well to normal RAM
page data patterns (more so than to general purpose data).

It worked in terms of multiples of 32 bits, with a fixed 32-bit tag
size. Where it competes against an even more specialized format (that
operates on 64 bit chunks, rather than multiples of 32 bits).

Well, in this case, the inability for RP2 to as-cheaply encode 8-byte
literals and runs of multiples of 32 bits is a drawback for things like
normal RAM/heap compression (with lots of aligned integer data and
pointers). This was a case which FeLZ32 dealt with well, albeit worse
for compressing free-form data.

Intermediate options are possible, say something that operated primarily
on 32-bit chunks with 16/32 bit tags, which could maybe make sense for
some use-cases (like compressing XG3 and RV64 machine code maybe a
little more efficiently than using LZ4 or RP2).

And, as noted, XG2/XG3/RV64G machine code is a place where LZ4 holds a compression advantage over RP2; likely because it does a little better
with short-but-deep matches and can directly encode groups of 8 or 12
literal bytes.

Say, something like:
dddddddd-llllrrr0 l=2..17, d=1..256 (1K), r=0..7
rrrrrrrr-rrrr0001 r=1..4095 (16K), EOB
dddddddd-dddddddd-llllllll-rrrraa11 l=2..257, d=65536 (256K), r=0..15 Copying 32-bit words, with 'aa' allowing for a misaligned copy.

Would probably still use if/else logic for decoding though.


But, yeah...


Any comments I guess?...

--- Synchronet 3.22a-Linux NewsLink 1.2