"Fast solutions will terminate comparing as soon as a difference has been found." - good point. Hard to say what the common case will be.

I'd think it's totally irrelevant in your case. Or at least, it would totally irrelevant if I were to make something similar that what you describe you are making. I wouldn't go and compare every outstanding object to see whether it may match - if speed is important, I certainly don't want to do a linear search!

If you were going to use Data::Dumper or YAML, why wouldn't you use Storable - isn't that generally the fastest serializer?

Because I know Data::Dumper and YAML, and I don't know Storable very well. And I like YAML. As for what is the fastest, I would only consider that if I was convinced the constructor was that much of a bottleneck that it would matter.