Software implementations of MPEG decompression provide flexibility at low cost but suffer performance problems, including poor cache behavior. For MPEG video, decompressing the video in the implied order does not take advantage of coherence generated by dependent macroblocks and, therefore, undermines the effectiveness of processor caching. In this paper, we investigate the caching performance gain which is available to algorithms that use different traversal algorithms to decompress these MPEG streams. We have found that the total cache miss rate can be reduced considerably at the expense of a small increase in instructions. To show the potential gains available, we have implemented the different traversal algorithms using the standard Berkeley MPEG player. Without optimizing the MPEG decompression code itself, we are able to obtain better cache performance for the traversal orders examined. In one case, faster decompression rates are achieved by making better use of processor caching, even though additional overhead is introduced to implement the different traversal algorithm. With better instruction-level support in future architectures, low cache miss rates will be crucial for the overall performance of software MPEG video decompression.