You are right, I didn't do the math on paper originally, and due to false laziness, lack of an existing encode() or motivation to write one made me not verify my code with different data, even though I knew that might come back and bite me in the tender parts.

I fixed the code; this time, no comments, since I don't know how to explain it briefly. I guess it warrants a longer comment in front of the subroutine containing the math.

sub decode3 {
    my ($diff, $delta, $next);
    $diff = $_[0];
    $delta = -$_[0];
    $diff -= $delta += $_ for @_;
    $_[0] = $diff/@_;
    return map { $next += $_ } @_;
}
[download]

Your tests verify this one, and the benchmark on my 5.6.1 says it is consistently about 42% faster than the for version and 35% faster than the map one. The main win was removing the intermediary @results. If I put that step back in, it only beats the vanilla versions by 12% and 8%, respectively, which means you can speed up your own versions by 25% if you omit the temporary array.

Makeshifts last the longest.

I think it's avoiding those "off by one" corrections that helps. Because of the interpretive nature, ($x+1) has a certain amount of overhead, compared to the machine INCrement instruction of a register. But "big" instructions like map and foreach have spread the overhead over a lot of work, so it is not noticable.

I conjecture that map is good because it knows that the output list will be the same size as the input list, and can set things up properly ahead of time, as opposed to push'ing each element as a separate instruction

Very clever how you initialize $delta to avoid the shift and "+1" corrections. Many thanks for illustrating your techniques.

—John

Actually, map doesn't know that. You can write something like @x = map { () } @y; and then the resulting list is empty. You can also do something like @x = map { ($_, func($_)) } @y; in which case it's twice as large as the input list. Or something like @x = map { split } @y; in which case it's entirely up in the air how many elements the result list will have. If you do @x = map /re(g)(ex)/, @y;, input strings that don't match the regex will leave no trace in the output list, while those that do produce two entries each. And if you add a /g to the regex, even the latter constant becomes random.

I have no idea of the perl guts, but my guess is that it's because in a for loop, the array modification is an explicit operation. It's an independent op which needs to deduce the address to a scalar inside the array, and so it does so for each iteration, over and over. The map on the other hand creates a list implicitly and knows to keep track of where to dump the next value(s).

Anyway, that's just an educated guess. If anyone who knows better can offer some enlightenment, I'll be glad to learn more.

Makeshifts last the longest.