最速のreplaceAll()を求めて

Javascriptでは文字を全置換するビルトイン関数が存在しないので、よりよいreplaceAll()はどれか調べました。
replaceAll()の引数には文字列をとるものとします。
正規表現オブジェクトやエスケープされた文字列を渡すのは無しです。

この記事ではFoo.protoype.barはFoo::barと表記します (例: Array.prototype.join -> Array::join)

前置き

JavaScript で全置換(正規表現も使った)の速度比較 - Qiita という記事をこの前改めて見て、昔もった違和感の原因を思いついたので検証してみようと思いまして。
というのもString::split() -> Array::join()のほうがString::replace(Reg(String::replace(before)), after)よりも速いのは計算量的にしっくりこなかったのです。
この原因は追って説明していきます。

replaceAll()をつくっていく

文字を全置換するには二つのアプローチが考えられます。
一つ目は、正規表現を利用する方法。
二つ目は、単純に文字列処理(String::indexOfなど)を利用していく方法。
ここから一つ目はreplaceAllS、二つ目はreplaceAllRと名付けていきます。
比較のために現在よく使われる(?)、検索で出てくるものもreplaceAllDと名付けていこうと思います。

replaceAllD

replaceAllD1

var replaceAllD1 = (str, beforeReg, after) => {
  return str.replace(beforeReg, after);
};

おそらく一番使われているのはないかなと思います。
これは引数に正規表現オブジェクトを渡すので、
replaceAll()には当てはまりませんが比較のために使います。

replaceAllD2

var replaceAllD2 = (str, before, after) => {
  return str.split(before).join(after);
};

これは簡単にかけてとても楽ですね。
ただ見る感じ結構無駄な処理をしてそうではあります。

replaceAllR

replaceAllR1

var replaceAllR1 = (str, before, after) => {
  return str.replace(new RegExp(
      before.replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
    , 'g'), after);
};

前書きで書いたJavaScript で全置換(正規表現も使った)の速度比較 - Qiitaのコメント欄にあるものです。
beforeを正規表現オブジェクトに変換するために正規表現でエスケープして、String::replaceを使うというものです。
ここからはこれをいじっていこうと思います。

replaceAllR2

var Replacer = function (before, after) {
  this.before = new RegExp(before
    .replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
  , 'g')
  this.after = after;
};
Replacer.prototype.replace = function (str) {
  return str.replace(this.before, this.after);
};
  
var r = new Replacer("abc", "123");
var replaceAllR21 = (str) => {
  return r.replace(str);
};
  
var Replacer2 = class {
  constructor(before, after) {
    this.before = new RegExp(before
      .replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
    , 'g');
    this.after = after;
  }
  replace(str) {
    return str.replace(this.before, this.after);
  }
};
  
var r2 = new Replacer2("abc", "123");
var replaceAllR22 = (str) => {
  return r2.replace(str);
};

D1は正規表現リテラルを使っているので予め正規表現がコンパイルされているのですが¹、R1では置き換えを実行するたびに正規表現オブジェクトを生成しているのでR2ではそこを改善しました。
str.replaceAll(before, after)でstrの値は変わってもbeforeとafterが変わることは多くはないのではないかということで固定しました。(そもそも一回しか実行しないならどの関数だろうが誤差レベルでしょうし、beforeを変えるなら正規表現で一つにまとめたほうが速そうですし…)
prototypeを使ったものとclassを使ったものの二つ書いてありますが、仕組みは変わりません。
ただ、もしかしたらclassのほうはJavascriptエンジン側の最適化ができてないかもしれないって程度で書きました。

replaceAllR3

var regs = Object.create(null);
var replaceAllR31 = function (str, before, after) {
  var beforeReg;
  if (before in regs) {
    beforeReg = regs[before];
  } else {
    beforeReg = new RegExp(before
      .replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
    , 'g');
    regs[before] = beforeReg;
  }
  return str.replace(beforeReg, after)
};
  
var regsM = new Map();
var replaceAllR32 = function (str, before, after) {
  var beforeReg;
  if (regsM.has(before)) {
    beforeReg = regsM.get(before);
  } else {
    beforeReg = new RegExp(before
      .replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
    , 'g');
    regsM.set(before, beforeReg);
  }
  return str.replace(beforeReg, after)
};

一々newしてというのはめんどくさいだろうなと思ってnewしなくてもいいようにしました。
ただ、先ほどのR2と違ってメモリ開放の手段がないので(R2はReplaceR = nullで解放できる)、一度しか使わないといった場合でメモリを食うかもしれません。(解放用の関数を作ってregs[before] = nullなどすればできなくはない)
ObjectとMapの二種類用意してありますが、前のprototypeとclassと同じ理由です。

replaceAllS

replaceAllS1

var replaceAllS1 = (str, before, after) => {
  var result = str;
  do {
    str = result;
    result = str.replace(before, after);
  } while (str !== result);
  return result;
};

先ほど取り上げた記事の前の記事のJavaScript全置換(正規表現使わない)の速度比較 - Qiitaの冒頭にのっている関数です。
String::replaceを繰り返すというものですね。

replaceAllS2

var replaceAllS2 = (str, before, after) => {
  var b = str.indexOf(before);
  if (b === -1) return str;
  return str.slice(0, b) + after + replaceAllS2(str.slice(b+before.length), before, after);
};

String::replaceを繰り返すと既に走査済みのところも走査してしまうのでString::indexOfとString::sliceを利用するようにしました。
分割して見つかった場所より後ろの部分を分割して…と繰り返します。

replaceAllS3

var replaceAllS3 = (str, before, after) => {
  var i = 0;
  var result = "";
  while(true) {
    i = str.indexOf(before);
    if (i === -1) {
      result += str;
      break;
    }
    result += str.slice(0, i) + after;
    str = str.slice(i+before.length);
  }
  return result;
};

ただS2の再帰呼び出しをwhileで書き直しました。
S2は末尾再帰最適化²が効かない形³なので、置き換え箇所が多数あるとUncaught RangeError: Maximum call stack size exceededが発生します。
また、関数呼び出しは遅いというのもあります。

replaceAllS4

var replaceAllS4 = (str, before, after) => {
  var i = str.indexOf(before);
  if (i === -1) return str;
  var result = str.slice(0, i) + after;
  var j = str.indexOf(before, i+before.length);
  while (j !== -1) {
    result += str.slice(i+before.length, j) + after;
    i = j;
    j = str.indexOf(before, i+before.length);
  }
  return result + str.slice(i+before.length);
};

S3ではstrを書き換えていたのでstrを書き換えないようにしました。
文字列を書き換えるのと数値を書き換えるのだと数値を書き換えるほうが速いです。(割と違いました)

replaceAllS5

var replaceAllS5 = (str, before, after) => {
  var i = str.indexOf(before);
  if (i === -1) return str;
  var bLen = before.length;
  var result = str.slice(0, i) + after;
  i += bLen;
  var j;
  while ((j = str.indexOf(before, i)) !== -1) {
    result += str.slice(i, j) + after;
    i = j+bLen;
  }
  return result + str.slice(i);
};

いわゆる人類には(早|速)すぎる高速化ってやつです。
たぶん無駄にごちゃごちゃして意味不明になっただけです。
ほぼ変わらないと思います。

結果

ここまでたくさんのreplaceAll()を書きましたがその計測結果を書きます。
jsPerfは偉大…

replaceAll()	Chrome66(Win)	Canary70(Win)	Chrome68(Android)
D1	571,467	551,045	211,071
D2	358,059	333,419	176,312
R1	414,472	422,145	164,451
R2-1	513,877	493,442	171,090
R2-2	496,295	499,116	172,678
R3-1	496,193	495,639	178,892
R3-2	501,193	495,095	162,004
S1	102,670	127,185	49,012
S2	457,978	450,517	201,365
S3	497,030	505,375	219,658
S4	654,655	716,908	269,525
S5	656,770	729,293	270,619
単位は(Ops/sec)
replaceAlls - jsPerf

S1 << D2 < S2 < R2,R3 < S3 < D1 < S4 <= S5
こんな感じですかね。
計測結果から正規表現レテラルでもよいならD1、使いたくないならR3もしくはS4あたりがよさそうですかね。
ぱぱっと使うだけならD2で十分だとは思います。

もっと速くなる！！！って方法がありましたら是非コメントを！！

1. 正規表現リテラルは早いのか？ - Qiita ↩

2. 末尾再帰による最適化 - Qiita ↩

3. 効く形でも現地点(2018/08/09)ではSafariしか対応していない ↩