The following does away with substr alltogether and uses your until loop on the array of characters of the string. This is probably the closest to a C implementation. It is still around a factor 3 slower than your cached version...

sub suffix3 {
    my @input = split //, $_[0];
    my $off = 0;
    my @array = sort { $off=0; until( ($input[$a+$off]//'') cmp ($inpu
+t[$b+$off]//'') ) { $off++ } } 0..@input-1;
    $_++ for @array;
    return @array;
}
[download]