4 ms·
The creator of bzip lamented this very fact, at a conference about the "b" transform that powers it, the Burrows-Wheeler Blocksort. With gzip, the output comes
by lsb 18y ago
The creator of bzip lamented this very fact, at a conference about the "b" transform that powers it, the Burrows-Wheeler Blocksort. With gzip, the output comes from looking up strings in a hash table, and just streaming it out, but bzip sorts (and unsorts) blockwise, quasi-randomly accessing locations for 1MB of memory, and as we get more and more layers of caching, it'll just get slower and slower.
- Retric 18y agoCould you explain that a little more? If it only needs 1MB of memory I would assume it fit's on most modern CPU's L2 cache. At which point I don't see why it would get slower if you added L3 cache etc.
- lsb 18y agoThis 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.
- cperciva 18y agoThere are much better suffix sorting algorithms available now than when bzip2 was first written. I'm sure bzip2 could be sped up considerably by using one of them if anyone wanted to bother.
- kragen 18y agoAdding L3 cache to a machine won't make it (noticeably) slower, but if the memory behavior is random and bigger than the L3 (which it isn't in bzip2's case but anyway) it won't make it faster either. But the point at which you want to add L3 is when main memory is very slow relative to L2, and that's the case when random memory access loses. But hey, you can merge-sort a million records in only 20 sequential passes! Not sure how to apply that to BWT though.
- Retric 18y agoAssuming the issue is memory latency not bandwidth adding cache to a system with random memory access can sill increase performance. Granted if your accessing 10 times as much memory as will fit into you're cache you would be limited to a 10% increase in speed which might be eaten up by overhead.