We study lazy structure sharing as a tool for optimizing equivalence t
esting on complex data types, We investigate a number of strategies fo
r implementing lazy structure sharing and provide upper and lower boun
ds on their performance (how quickly they effect ideal configurations
of our data structure). In most cases when the strategies are applied
to a restricted case of the problem, the bounds provide nontrivial imp
rovements over the naive linear-time equivalence-testing strategy that
employs no optimization. Only one strategy, however, which employs pa
th compression, seems promising for the most general case of the probl
em.