Můžete to trochu rozvést? Jaký existuje rychlý algoritmus pro substr z UTF-16, ve kterém může být jeden znak uložen ve 2 nebo 4 bajtech? Napadá mě jedině ukládat si kromě samotného řetězce také tabulku pozic znaků zabírajících 4 bajty (což v PHP pravděpodobně bude), ale totéž by přeci šlo udělat i s UTF-8. str_replace nedělá problém ani v jednom kódování, v UTF-8 naopak bude většinou kvůli menší paměťové náročnosti rychlejší.