1. A method in a data processing system for compressing trace data, the method comprising: identifying an instruction stream; and responsive to identifying the instruction stream, replacing instruction addresses in the instruction stream with a stream identifier for a compressed trace data, wherein compression occurs using fixed-size storage structures.