LZ4_8088 – Fast LZ4 decompression for the 8088/8086 CPU | Hacker News Reader

LZ4_8088 – Fast LZ4 decompression for the 8088/8086 CPU

oldskool.org

99 pointsnetworked24 comments

For source material that contains long runs of sequences (RLE), decompression is faster than memcpy.

This is not surprising given how RLE decompression works --- memcpy and regular LZ decompression requires copying data, i.e. a memory read followed by a memory write. RLE only requires a read of the value to be repeated, followed by multiple writes.

It is interesting to note that CPUs today are also often limited by memory bandwidth, just like the 8088/8086.

It's not surprising if you think about it. But it may be surprising if you don't.

I wonder how 8-channel memory is going to change that on next gen server chips.

Memory is orders of magnitude slower than the cpu at the moment, so you'd need orders of magnitude more bandwidth to come close. So sure, it's going to be faster, but the cpu is still going to be waiting for memory more than the other way round.

I wonder if the heat-bound nature of especially mobile CPUs these days could contribute to memory "catching up" to CPU performance. That is, the CPU idle while waiting for memory could be seen as necessary for heat dissipation and so you could consider the CPU at capacity.

That's basically what I understand the idea of "race to halt" to be. Mobile CPUs are already designed to finish their current task as quickly as possible so they can idle to cool off (that's how laptop chips can support turbo boost).

I think the time it takes for memory reads is too short to take advantage of though, because of how long it takes chips to come out of sleep & ramp up their clock speed.

Litterally not at all.

L1 cache is 3-5x slower then a CPU register and it has a ~532GiB/s thought put. DDR4 is ~2GiB/a per channel.

Also DDR has extreme latency due to its distance from the die.

Physics is hard. In the cycle of a 2400MHz DDR4 clock, a photon travels 12.5cm. The memory bus distance is on a similar order of magnitude.

Main memory latency will be the big performance bottleneck for the foreseeable future.

They're comparing LZ4-HC with something like zlib. They should compare against Google Zopfli instead of plain zlib (or equivalent). But yes, algorithmic improvements and encoding on a modern CPU mean you can do decode on ancient hardware that seems magical, like 8088 Corruption (from the same people, it seems).

Algorithmic advances are something to marvel at, literal time travel. Isn't there something analogous in that we can bring old algorithms into the present, stuff tuned for a 64k machine has excellent locality. I have this hunch that many things are too tricky by at least half if not a multiple.

Code up an assembly language version of Zopfli and we'll be able to compare the two then! Anything else won't be a fair speed comparison.

If you're just interested in compression ratios, there are already plenty of websites that compare them all.

zopfli is just a compressor for the standard DEFLATE (zlib) format, able to make png, gzip and zip files a bit smaller. It spends a lot more CPU time doing the compression to achieve marginally better compression ratios (i.e. it's like "gzip -99"). It's worth it to crunch minified js and css files (and serve them as pre-compressed "content-encoding: gzip") and png files to make a popular site load a bit faster.

There is no need for special decompression code, in fact that's the whole point: an unmodified DEFLATE decompressor can decompress the file, even though it is smaller than what "gzip -9" can produce.

They are compressing using LZ4-HC which is a slow compressor. They compare it to something like gzip. They should compare it to something that produces gzip-compatible data but spends even more CPU time to get even better compression ratios.

And what I'm saying is that the thing they are comparing it to is something which has optimised 8086 assembly code for the compression. zopfli doesn't, which would make a timing comparison pointless.

They only implemented a decompressor.

Impressive speed. Having that in the 80's would be having much faster load times and much better graphics.

I had an XT clone in the 80s (bought in '87 if I'm not mistaken) & I don't really recall these being a factor on the PC at the time...PC drives were actually relatively fast and CGA/Hercules-era graphics were primitive enough to have put a pretty harsh upper bound on the kind of graphics you could do anyway.

This was very different to the c64 or atari 8 bitters for example (both of which had decent graphics and abysmal floppy performance).

> I had an XT clone in the 80s (bought in '87 if I'm not mistaken) & I don't really recall these being a factor on the PC at the time...PC drives were actually relatively fast and CGA/Hercules-era graphics were primitive enough to have put a pretty harsh upper bound on the kind of graphics you could do anyway.

PCjr CGA+ (adopted also and popularized by Tandy, often known as TGA) graphics were introduced in 1983, EGA graphics were introduced in 1984, VGA in 1987, and there were a number of less-standard higher-resolution and/or higher color modes available and supported in software in addition to those.

Yeah but VGA wasn't popular until at least '90 and EGA probably not much earlier, around '88 maybe (before that you'd probably be more likely to have a c64 than a better-than-CGA PC compatible).

Most people didn't have state of the art computers, a PC AT with EGA & color monitor costed close to $10k in 1984 (1980s dollars!). Going to the mall to play on a color monitor was a thing kids were doing back then.

Can't speak much about Tandy as I think these were mostly only popular in America. In Europe you'd still be playing mostly in CGA well into the 2nd half of the 80s, and the only popular PCs until close to the end of the decade were cheap XT clones with CGA at most, or monochrome Hercules more commonly.

Anyway I'd concede that it would have probably made a big difference to graphics fidelity in the very late 80s or early 90s. But I think a lot of people forget that warp-speed improvement of PC hardware and plummeting prices were more a 90s than an 80s phenomenon - in most of the latter we were still in the flat stage of the S curve!

I remember most people switched directly from CGA to SVGA in the early 90s. I only remember a couple computers with EGA at friend's homes, and offices were mostly CGA and Hercules too (if they had PCs at all, and not 3270).

This was definitely my personal experience, when my brother in law bought a 286 in '91 it already had svga despite only being 4 years newer than our xt.

PC/XT hard disks read at 125KB/s, and floppy disks from 15 to 50KB/s. And it was slower to decompress than to read. 8086 @8MHz RAM bandwidth was about 1200KB/s, so data compression algorithms based on dictionary (LZ77, LZW) were crazy slow. So the LZ4 decompression time achieved is impressive.

Sure, but you wouldn't have played graphically impressive games on an xt either way cause CGA was the bottleneck rather than how much data you could fit on a floppy.

Anecdotally speaking I don't recall loading times were much of an issue on pc games at the time, unlike on some 8 bit platforms.

E.g. MS-DOS 3.20 is slower to boot on a 8086 CPU + floppy disk than e.g. booting Ubuntu or Windows 10 on modern hardware.

Some studios had their own in house compression that was quite impressive at the time. I remember the amount of time our engine coders put into compression routines, it was a significant effort. That being said, I have no idea how it would stack up...

Reply on news.ycombinator.com