Immutable vs mutable performance

I've stated before that I believe immutability should be used by default, and mutability is actually an optimisation technique. Opponents of immutable data structures usually states »

Immutability comes with design patterns

Recently I have tried to implement some design patterns using only immutable data structures/classes. Immutable data structures - what does it mean? * no setters - »