This was back in the summer of 2004; I don't remember historical cache sizes, but I do remember Wheeler saying something about cache misses (because the BWT sor

This was back in the summer of 2004; I don't remember historical cache sizes, but I do remember Wheeler saying something about cache misses (because the BWT sorts things by blockwise context -- all the "_he quick brown fox" strings get arranged by position -- it tends to jump around a bit more), but he never addressed multicore capacity, in which bzip2 shines, because each block can go onto a different core, and you're just limited by memory bandwidth. Most chips only had 1 core in those days. IIRC, the blocksorting algorithm requires more than 1MB; the figure 12n for the suffix sort sticks in my head, but I don't recall the specifics.