Clone::clone() if I need performance; because it was faster than Storable when I tried it a few years ago. That may have changed; YMMV.

Though often as not when I need to clone something, I'll use a custom clone() for the purpose, that only deals with the cases I need to deal with. For example:

sub clone {
    my $ref = shift;
    ref( $ref ) or return $ref;
    ref( $ref ) eq 'SCALAR' and return \$$ref;
    ref( $ref ) eq 'HASH'   and return { map+( $_, clone( $ref->{$_} )
+), keys %{ $ref } };
    ref( $ref ) eq 'ARRAY'  and return [ map clone( $ref->[$_] ), 0 ..
+ $#{ $ref } ];
}
[download]

That deals with most 'normal' data-structures that don't contain 'exotics' -- bless refs or coderefs and the like.