Interesting, there must be Perl differences too. The spread is not as great with Active State Perl v5.8.7. In particular, Better is not as much better.

               Rate     Greedy        Sep Death_star        Non     Be
+tter
Greedy       9965/s         --       -90%       -94%       -94%       
+-97%
Sep        102700/s       931%         --       -34%       -37%       
+-66%
Death_star 155342/s      1459%        51%         --        -5%       
+-48%
Non        164099/s      1547%        60%         6%         --       
+-46%
Better     301485/s      2925%       194%        94%        84%       
+  --
[download]

The results above used OP's benchmark code (with the addition of Better).