The copyright section of sed(1) suggests that the Debian package sed (I'm running wheezy) is Gnu sed 4.2.1[1]. Plan9 sed is also available in the 9base package. I'm running perl 5.12.4 (also from Debian testing). I don't see any significant difference in speed with vanilla 5.14.1 and the commands I mentioned earlier.

[1] http://www.gnu.org/software/sed/