The whole concept of generic algorithms working on strings efficientlydoesn't work.Apparently std.algorithm does.
According to my research[1], std.array.replace (which uses std.algorithm under the hood) can be at least 40% faster when there is a match and 70% faster when there isn't one.
I don't think this is actually related to UTF, though.[1]: http://dump.thecybershadow.net/5cfb6713ce6628686c6aa8a23b15c99e/test.d
