The scenario implies that the HoHoA is already loaded at the point that you go into this three-level loop over the data structure, and you obviously have not run out of memory at that point. So there must be something about how you are trying to access the data structure that is causing perl to consume a lot more memory than was needed to store the original data structure.

You say the structure is "not sparse", but if loading the structure happens to take up, say, 80% of available memory, then you might end up going over the limit if you auto-vivify a relatively small percentage of previously non-existent cells in the overall structure.

I wonder if it would help to try the loop like this:

for (my $i = 0; $i < scalar(@array); $i++) {
    my $subhash = $hash{$array[$i]};  # does not autovivify new $hash 
+element
    next unless $subhash;         # equivalent to "exists($hash{$array
+[$i]})"

    for (my $j = $i; $j < scalar(@array); $j++) {
        my $subarray = $$subhash{$array[$j]};        # same comments a
+s above
        next unless $subarray;

        foreach my $value ( @$subarray ) {
            # do great deeds
        }
    }
}
[download]

If the OP code actually works on a given (smaller) data set, it might turn out that this different form of the nested looping could produce the same output in less time (but I haven't tested that).

The point of this approach is that you can easily check whether a given hash element exists before trying to use its contents as an array ref, and skip it if it does not exist; this involves extra steps within the loops, but these could end up saving a lot of execution time overall. And if they save enough unnecessary memory consumption as well (making the difference between crashing and finishing), speed may be a lesser concern.

update: I think the code as suggested above would be "good enough", if you're confident about how the data structure was being created, but I would be tempted to be more careful:

    next unless ( ref( $subhash ) eq 'HASH' );
    ...

        next unless ( ref( $subarray ) eq 'ARRAY' );
        ...
[download]