When I talked about PseudoColor displays and window managers, I described things assuming that there was only a single hardware colormap. However, if you read the X11 documentation you'll run across tantalizing things like:

Most workstations have only one hardware look-up table for colors, so only one application colormap can be installed at a given time.

(Emphasis mine.)

'Most' is not all, and indeed this is the case; there were Unix workstations with PseudoColor displays that had multiple hardware colormaps. As it happens I once used such a machine, my SGI R5K Indy. As a sysadmin machine we bought the version with SGI's entry level 8-bit XL graphics, but that was still advanced enough that it had multiple hardware colormaps instead of the single colormap that I was used to from my earlier machines.

When I was using the Indy I didn't really notice the multiple hardware colormaps, which is not too surprising (people rapidly stop noticing things that don't happen, like your display flashing as colormaps have to be swapped around), but in retrospect I think they enabled some things that I didn't think twice about at the time. I believe my Indy was the first time I used pictures as desktop backgrounds, and looking at the 1996 desktop picture in the appendix of this entry, that picture is full colour and not too badly dithered.

(As it happens I still have the source image for this desktop background and it's a JPEG with a reasonably large color range. Some of the dithering is in the original, probably as an artifact of it being scanned from an artbook in the early 1990s.)

In general, I think that having multiple hardware colormaps basically worked the way you'd expect. Any one program (well, window) couldn't have lots of colors, so JPEG images and so on still had to be approximated, but having a bunch of programs on the screen at once was no problem (even with the window manager's colors thrown in). I used that Indy through the era when websites started getting excessively colourful, so its multiple hardware colormaps likely got a good workout from Netscape windows.

(In 1996, Mozilla was well in the future.)

At the time and for years afterward, I didn't really think about how this was implemented in the hardware. Today, it makes me wonder, because X is normally what I'll call a software compositing display system where the X server assembles all pixels from all windows into a single RAM area and has the graphics display that (instead of telling the graphics hardware to composite together multiple separate bits and pieces). This makes perfect sense for a PseudoColor display when there's only one hardware colormap, but when you have multiple hardware colormaps, how does the display hardware know which pixel is associated with which hardware colormap? Perhaps there was a separate additional mapping buffer with two or three bits per pixel that specified the hardware colormap to use.

(Such a mapping buffer would be mostly static, as it only needs to change if a window with its own colormap is moved, added, or removed, and it wouldn't take up too much memory by 1996 standards.)