Got benchmarks to back that up?

#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw 'cmpthese';

our %hash = map {$_, $_} 1 .. 100_000;

cmpthese (-10, { 
    keys    => '$a = 0; for (keys %hash) {$a += $_}',
    while   => '$b = 0; while ($_ = each %hash) {$b += $_}',
});
__END__
        Rate  keys while
keys  5.23/s    --  -26%
while 7.05/s   35%    --
[download]

Now, that's for a simple hash. If the hash is tied to a huge DBM file, the results would be far more dramatic.

Why does perl not implement an automatic iterator when the parser notices a simple sort-free for (keys %foo)? That's such a common idiom I would be amazed it wasn't getting special attention.

Because it isn't common idiom, and changing it to an iterator changes the results. Perl has an iterator, and it's called each. You can't change keys to an iterator:

for my $k1 (keys %hash) {
    for my $k2 (keys %hash) {
    }
}

for my $k (keys %hash) {
    %hash = ();
    ....
}
[download]

Changing either of the "simple sort-free for (keys %foo)" to an iterator will break the code.