If your hash can be of any real size, I suggest taking an array of keys and iterating over it with for loops rather than cloning the hash.

my @keys = keys %hash;

for my $i ( @keys ) {
    my( $k1, $v1 ) = ( $i, $hash{ $i } );

    for my $j ( @keys ) {
        my( $k2, $v2 ) = ( $j, $hash{ $j } );
        ...
    }
}
[download]

It will only require around 1/3 of the extra memory and run in less than half the time.