Update: I misread your post. Sorry.

This might be a little quicker as it avoids the sorting

#! perl -slw
use strict;

sub cmpAoAs{
    my( $a, $b ) = @_;
    my %h;
    $h{ $_ }++ for map{ @$_ } @$a;
    $h{ $_ }-- for map{ @$_ } @$b;
    return 0 == grep{ $_ } values %h;
}

my $ha = [ [1,2], [5,5,5], [1,2], [3,4] ];
my $hb = [ [4,3], [1,2], [2,1], [5,5,5] ];

print 'Same' if cmpAoAs $ha, $hb;
__END__
P:\test>342841
Same
[download]

However, on the surface of what you've told us, it loooks a little like your using the wrong structure if only the presence and count of a value (rather than it's position) determine equivalence. But I realise that I am not party to the full sp on your application:)