640K DOS Barrier - Why was RAM compression not used to overcome it?

[JamesWasil]

Although this is not really an issue anymore since the advent of things like HIMEM.sys XMS extenders for the PC XT 286, and DOS4GW and EMM386 for 386SX and beyond to where it was integrated with Windows (and BSD, linux and other versions of Unix always had memory management thereafter)...I still wonder:

Why wasn't data compression used to overcome the 640K limit?
Couldn't we have compressed the contents of RAM by at least 25% on a good day when most of the things loading to them were EXE and COM files and device driver data?

Do you think things would have been done differently or would it have made a big difference to you back then (or now) to have 800k or up to 1MB of memory without an extender board or external RAM? Especially for device drivers and program stack and data?

Would assembly language routines and roms for IBM PCs including hardware compression mnemonics have been a game changer for the industry?

I'm not sure how many will know what I'm saying or appreciate what it would have meant if their first systems were 386 or 486 computers (since they already had bank switching for RAM anywhere from 4MB to 64mb depending on what operating systems they were running years ago), but those of you who used a 286, an MSX, Commodore 64/128, Atari Computer, Tandy Color Computer / TRS80, or similar system from years ago will. Most of those had either 512K, 256K, 128K and some even less than that for conventional memory to where you really had to make sure everything fit under 64k most of the time.

Do you think compression for this back then would have made a difference on what we do now, how we do it, and on computer history today?

[Piotr Tarsa]

RAM compression requires very high speed so the data must be very redundant to be compressible at such very high speeds. With < 1 MB of RAM the applications probably used compact memory representations of objects and that made them less compressible than today's RAM contents {I haven't checked that, that's only my guess}.

Compression also needs to be done in blocks to be effective. From what I saw the memory compressors operate on memory pages, i.e. 4 KiB blocks. Each mutation of such compressed block would require decompressing, mutating and recompressing it. That's a lot of overhead if the mutation is simple. Therefore if there's a lot of simple mutations spread all over the memory then memory compression doesn't help at all. Nowadays with many gigabytes of RAM plenty of it sits idle most of the time, so that's a good candiate for compression, but when RAM capacity was small I think developers loaded to RAM mostly frequently used data.

[Shelwien]

640k limit was more about video memory mapping rather than something real.
PCs simply had video memory at 0xA0000 (=640k) to 0xC0000 and then BIOS from 0xF0000.
0xC0000..0xF0000 could be also used for extended ROMs.
So XMS/EMS were invented which allowed access to more memory, but they were inconvenient (paged access etc).
Anyway, I don't remember memory size being a problem under DOS, actual problem there was address space -
there were some realmode games that required ~600k of continuous free memory and thus only worked under EMM386/QEMM.

Later, in 32-bit "DOS Extender" software, the demand for more memory did appear.
And so memory compression software did appear too: https://en.wikipedia.org/wiki/QEMM#MagnaRAM
But it wasn't very helpful in practice, so didn't become popular.

[WinnieW]

I guess compressing data in RAM does function more efficient by using a flat memory model, but the PC started with a less efficient 16 bit memory adress mode, RAM was adressed in blocks of 64 kByte each. So compressing and decompressing large amounts of data in RAM was not that efficient in terms of memory access.

[JamesB]

It was only the very earliest machines where the 640k limit really mattered in hardware. From 386 on you could directly access the memory and ignore all the 5(?) or so types of memory which were essentially just reversing the DOS limits imposed for reasons of backwards compatibility. Other OSes didn't even care and it was totally invisible to the user, but under DOS the DOS/4GW extender eventually just became ubiquitous to present a flat 32-bit memory model to the application.

Compression was routinely used, but more to shrink data down for floppy disk distribution so it could be decompressed on start up. Textures and the like typically.

[WinnieW]

From 386 on you could directly access the memory and ignore all the 5(?) or so types of memory which were essentially just reversing the DOS limits imposed for reasons of backwards compatibility. Other OSes didn't even care and it was totally invisible to the user, but under DOS the DOS/4GW extender eventually just became ubiquitous to present a flat 32-bit memory model to the application.

Yeah, that's what I had in my mind. The limitations of DOS, because a lot of programs run under DOS. There are quite complicated methods to adress the RAM in 32 bit x86-CPUs.
https://en.wikipedia.org/wiki/X86_memory_segmentation

Compression was routinely used, but more to shrink data down for floppy disk distribution so it could be decompressed on start up. Textures and the like typically.

Data compression for distributions of software was common from mid 1980s. Data compression was uses for software distributions for Commodore 64 computers, as far as I can remember.
Data compression was also used to increase the storage space of hard disc drives.

[introspec]

I think I will give an answer that is pretty different from others. Basically, I believe that it did not happen because
1) They did not have the compression algorithms they needed for this.
2) 25% win just was not worth it with the algorithms they had at the time.
3) Real time decompression on their architecture was not as beneficial to them as it is to a modern programmer.
Let me explain.

1) I am assuming that we are talking about times prior to DOS extenders becoming widely available and used. So, this is something like from early 1980s up to first half of the 1990s. So, what was actually available at the time? Briefly, it looks like this: before 1985 you only have compressors based on static or adaptive Huffman algorithm. In 1985 the first popular adoption of LZW called "compress" becomes available (LZW was invented in 1984, the original LZ78 was not as good). However, LZW was heavily patented, so "compress" ceased to exist within a year or so. Adoption of LZ77 did not happen until the early 1990s; partly, because without improvements offered in LZSS paper, LZ77 is close to useless. The first proper discussions of "modern" LZSS happened in the 1988 in Japan (Okumura's article and code example seem to have been very influential), but these were immediately followed by invention of LZA and LZH which really took the spotlight. The first use of LZ77 in the executable decompressor is in late 1989 (LZEXE by Fabrice Bellard). Fabrice admits basing his compressor on Okumura's source and is also convinced that PKLITE was based on LZEXE: https://bellard.org/lzexe.html
Overall, by the time LZ77/LZSS truly arrived, which is in the first half 1990s, the DOS extenders were already becoming available and the problem simply ceased to be important.

2) Why do I pay so much attention to LZ77? Because most other algorithms do not really qualify for real time decompression. RLE does not compress many types of data well. LZW requires nontrivial amount of memory for dictionary and heavily patented at the time. Huffman-based compressors are slow and are not that impressive. LZA/LZH are also fairly expensive for the hardware at the time.

3) Why LZ4 and similarly-styled compressors became so important nowadays? Because they are basically free - the speed of decompression tends to be faster than the speed of coping uncompressed data. This is happening because modern CPU is massively fast compared to the cost of RAM access. On the hardware of 1980s-1990s this is not really the case, the cost of memory access is not as expensive, so even LZ77-style compression is always about slowing things down. Where would it be different? When the speed of loading compressed data into memory is much slower, i.e. for loading data from floppy discs and HDDs. This is where it really took off straightaway at the time and this is why I used executable compressors as an important example.

My personal experience of old hardware is from using 286 and 386 machines in the early 1990s as well as from having a large coding experience on ZX Spectrum. So, I am not aware of a single compressed game loader during the time of commercial coding. There were some file copiers with real-time RLE, that's about it. The first real compressors become available in 1991-1993, but many of them are quite slow. So, the really common uses of real time storage of data in pages and decompression as needed is a technique that only becomes popular in the second half of 1990s. From this point of view, it is interesting to hear that data compression was more common on C64, but unless someone can expand it with some actual detail, I'd assume that if they were made in the 1980s, they'd used RLE.

[Shelwien]

I don't agree. I think even without LZ compression, just block dedup and RLE (for pattern-filled pages etc) could save some memory,
and were easy to implement in XMS driver or 386+ virtual memory.
I think its more that we didn't lack memory then, memory size in hardware was growing faster than the demand in software.
The only case I remember where I didn't have enough memory was trying to run ACB2 on 386SX... it required 16M.

As I said, memory compression software actually did exist then (QEMM/mangaram) and does exist now (like in win10),
there's just no demand for this - no useful software that would benefit from using more memory than physically available.

[JamesWasil]

I remember having to juggle a device driver for a CD rom drive, a mouse, and a sound card and had to choose to remove one just to be able to run a program because I needed 1K more of free RAM to run it, and the program required both a mouse and the CD rom drive to run from the disc, but not the sound card. I ended up running the game with the PC speaker instead and not sound. (Time period was between 1985 - 1992)

If I had just 1K more available I could have run everything. It was around the time that they expected people to use EMM/XMS memory managers to load device drivers to the upper memory blocks and high memory area, but on that system I didn't have it yet. It was like a jigsaw puzzle trying to get everything to fit, and sometimes you had to make different configuration files to load only what you needed to run different programs. (DOS 3.3 - DOS 6.22 mostly).

The one system I had was a 286 which supported an XMS board for up to 1.5mb of ram, but it had issues locking up frequently so I seldom used it or removed the card. The 386 used EMM386 and didn't have those issues, but I didn't have that system until after 1990 and actually liked trying to make things work with the 286 more lol.

If I'd had a virtual device driver that compressed conventional memory, it would have been possible to fit all of that in 640k without using an extender or memory manager, and run everything with that extra 1K free.

I had found a freeware or shareware program back then on a bulletin board system that did let you free up the extra memory by paging part of the drivers and data loaded to conventional memory to disk (it worked by relocating the data to a pointer file on the hard drive and calls were redirected there even though the computer thought they were still in ram), and it was very useful...but with an RLL or MFM hard drive controller and only 40mb hard drive space, it was really slow at the time.

(It was even slower than it should have been, since I was trying to get 60mb out of that same hard drive by using Stacker, and it took twice as long to page things to disk and compress/decompress that rather than compressing data in ram would have if it were available)

Aside of programming development tools and games that required that extra space in rare cases, I was thinking that programs like Adobe Photoshop or MIDI programs and things like ScreamTracker which came along later (mod music maker) might have benefited from it too.

If it had not have had to page data to disk as much as virtual ram and were able to compress the contents sent to and from actual ram, the computer might have been able to hold more data and samples in ram, adobe scratch disks etc, which might have made a difference in a few situations.

Looking back on it though, this was probably too slow or almost the same speed as sending to or from disk after the algorithm compresses and decompresses things, since there was always that bottleneck back then on the front side bus speed in addition to ram and drive controller.

People today no longer have to worry about this type of thing unless we're using the real hardware from old systems still. All those struggles and challenges to get things to work happen behind the scenes now transparently.

[Shelwien]

> I remember having to juggle a device driver for a CD rom drive, a mouse, and a sound card and had to choose to remove one
> just to be able to run a program because I needed 1K more of free RAM to run it

That's a problem with address space rather than actual amount of RAM.
And TSRs/drivers have to react to interrupts, so I doubt that they'd keep working even if it was possible to somehow swap them within the same address space.
One solution was finding smaller drivers though :)
At least there were many mouse and CD drivers from multiple vendors, so some of them were smaller than others.

[Krishty]

That's a problem with address space rather than actual amount of RAM.

Don’t drivers need a certain amount of non-pageable memory to handle requests during high interrupt priority levels? Because a page fault is also an interrupt? In this case, address space doesn’t buy you anything. Asking carefully here because I didn’t write any drivers back then.

[Shelwien]

DOS drivers mostly used port i/o.
Also address space problem I talk about is related to video memory and ROMs mapped to 640k-1M memory range,
so even on a PC with 1M+ of RAM, most programs could only use 600k or so at most (640k minus command.com and drivers/TSRs and some system areas).

There were two APIs for access to higher memory regions from 16-bit code - XMS and EMS.
XMS only allowed to copy memory blocks, while EMS also allowed to map them to accessible <1M address (which is much faster than copying).
But in practice most programs never used even the available extended memory, so what's the point in compressing it?..

[JamesWasil]

> I remember having to juggle a device driver for a CD rom drive, a mouse, and a sound card and had to choose to remove one
> just to be able to run a program because I needed 1K more of free RAM to run it

That's a problem with address space rather than actual amount of RAM.
And TSRs/drivers have to react to interrupts, so I doubt that they'd keep working even if it was possible to somehow swap them within the same address space.
One solution was finding smaller drivers though
At least there were many mouse and CD drivers from multiple vendors, so some of them were smaller than others.

There was a neat trick to share interrupt requests (there was ironically enough a TSR that did this experimentally), but it was not really stable at all unless you did <2 per location which was advised. (Windows 95 and later started to do this too transparently, remapping IRQs and hardware on the PCI bus rather than letting the user have to worry about it, but in DOS it was still manually done).

If I remember correctly, the program was basically a device driver that responded to an IRQ request and let you share IRQ requests virtually using the hard drive as the middle man for it when you swapped one in and swapped the other out. It would swap data to a file, then loaded it back when it was done to the same address space. It used address ranges that were virtual and did not exist, but the TSR intercepted those and remapped them either to the address currently in use, or to the file (swapping contest from the file back to conventional ram or vice-versa to accomplish it).

It did a little more than stack interrupts though, it was able to use video memory from &HA000 to &HB800 if you had an EGA or VGA card and consolidated that with it to where you had an extra 256k in the virtual driver as usable remappable space from that alone (it used the TSR to manage virtual calls with this, and if you were using text only you could do this, but if you used CGA, EGA, or VGA graphics it wasn't possible because those address spaces were then in use).

It replaced a mini program I wrote to use that area as a ram disk, since not only did it do that but made the address space able to use it as well.

That too was an issue though, and while the TSR did sometimes work for most programs, other times it crashed and gave me "I/O Error. System Halted" in DOS. Usually when it had a program that needed low level access and did not use INT 21H and used bios calls for disk access, it wasn't stable then. For most programs and games it did work, but certain ones (Sierra's King's Quest IV for example) would run but crash.

And you're right, there were a few drivers that were smaller that ended up helping even without this; a replacement for MSCDEX and a smaller MOUSE.COM freed up just enough for a few of them to run without doing any of this.

It's amazing to look back and see the things we had to do before compression and larger drive sizes were mainstream to get things to work smoothly on systems.

P.S: Correct too on the memory. Usually on a system with 640k conventional ram after the system was loaded, there was about 576k or less that was usable by programs.